Diff
Modified: trunk/Source/_javascript_Core/CMakeLists.txt (214409 => 214410)
--- trunk/Source/_javascript_Core/CMakeLists.txt 2017-03-26 22:11:13 UTC (rev 214409)
+++ trunk/Source/_javascript_Core/CMakeLists.txt 2017-03-27 04:17:52 UTC (rev 214410)
@@ -180,6 +180,7 @@
b3/B3ValueKey.cpp
b3/B3ValueRep.cpp
b3/B3Variable.cpp
+ b3/B3VariableLiveness.cpp
b3/B3VariableValue.cpp
b3/B3WasmAddressValue.cpp
b3/B3WasmBoundsCheckValue.cpp
Modified: trunk/Source/_javascript_Core/ChangeLog (214409 => 214410)
--- trunk/Source/_javascript_Core/ChangeLog 2017-03-26 22:11:13 UTC (rev 214409)
+++ trunk/Source/_javascript_Core/ChangeLog 2017-03-27 04:17:52 UTC (rev 214410)
@@ -1,3 +1,90 @@
+2017-03-26 Filip Pizlo <[email protected]>
+
+ B3::fixSSA should do liveness pruning
+ https://bugs.webkit.org/show_bug.cgi?id=170111
+
+ Reviewed by Saam Barati.
+
+ This moves all of the logic of Air::Liveness<> to WTF::Liveness<> and then uses that to
+ create B3::VariableLiveness. Then this uses VariableLiveness::LiveAtHead to prune Phi
+ construction.
+
+ This makes B3::fixSSA run twice as fast. This is a 13% progression on WasmBench compile
+ times.
+
+ * CMakeLists.txt:
+ * _javascript_Core.xcodeproj/project.pbxproj:
+ * b3/B3BasicBlock.h:
+ (JSC::B3::BasicBlock::get):
+ * b3/B3FixSSA.cpp:
+ (JSC::B3::fixSSA):
+ * b3/B3VariableLiveness.cpp: Added.
+ (JSC::B3::VariableLiveness::VariableLiveness):
+ (JSC::B3::VariableLiveness::~VariableLiveness):
+ * b3/B3VariableLiveness.h: Added.
+ (JSC::B3::VariableLivenessAdapter::VariableLivenessAdapter):
+ (JSC::B3::VariableLivenessAdapter::numIndices):
+ (JSC::B3::VariableLivenessAdapter::valueToIndex):
+ (JSC::B3::VariableLivenessAdapter::indexToValue):
+ (JSC::B3::VariableLivenessAdapter::blockSize):
+ (JSC::B3::VariableLivenessAdapter::forEachEarlyUse):
+ (JSC::B3::VariableLivenessAdapter::forEachLateUse):
+ (JSC::B3::VariableLivenessAdapter::forEachEarlyDef):
+ (JSC::B3::VariableLivenessAdapter::forEachLateDef):
+ * b3/air/AirCFG.h: Added.
+ (JSC::B3::Air::CFG::CFG):
+ (JSC::B3::Air::CFG::root):
+ (JSC::B3::Air::CFG::newMap):
+ (JSC::B3::Air::CFG::successors):
+ (JSC::B3::Air::CFG::predecessors):
+ (JSC::B3::Air::CFG::index):
+ (JSC::B3::Air::CFG::node):
+ (JSC::B3::Air::CFG::numNodes):
+ (JSC::B3::Air::CFG::dump):
+ * b3/air/AirCode.cpp:
+ (JSC::B3::Air::Code::Code):
+ * b3/air/AirCode.h:
+ (JSC::B3::Air::Code::cfg):
+ * b3/air/AirLiveness.h:
+ (JSC::B3::Air::LivenessAdapter::LivenessAdapter):
+ (JSC::B3::Air::LivenessAdapter::blockSize):
+ (JSC::B3::Air::LivenessAdapter::forEachEarlyUse):
+ (JSC::B3::Air::LivenessAdapter::forEachLateUse):
+ (JSC::B3::Air::LivenessAdapter::forEachEarlyDef):
+ (JSC::B3::Air::LivenessAdapter::forEachLateDef):
+ (JSC::B3::Air::TmpLivenessAdapter::TmpLivenessAdapter):
+ (JSC::B3::Air::TmpLivenessAdapter::numIndices):
+ (JSC::B3::Air::StackSlotLivenessAdapter::StackSlotLivenessAdapter):
+ (JSC::B3::Air::StackSlotLivenessAdapter::numIndices):
+ (JSC::B3::Air::StackSlotLivenessAdapter::indexToValue):
+ (JSC::B3::Air::Liveness::Liveness):
+ (JSC::B3::Air::Liveness::LocalCalc::LocalCalc): Deleted.
+ (JSC::B3::Air::Liveness::LocalCalc::Iterable::Iterable): Deleted.
+ (JSC::B3::Air::Liveness::LocalCalc::Iterable::iterator::iterator): Deleted.
+ (JSC::B3::Air::Liveness::LocalCalc::Iterable::iterator::operator++): Deleted.
+ (JSC::B3::Air::Liveness::LocalCalc::Iterable::iterator::operator*): Deleted.
+ (JSC::B3::Air::Liveness::LocalCalc::Iterable::iterator::operator==): Deleted.
+ (JSC::B3::Air::Liveness::LocalCalc::Iterable::iterator::operator!=): Deleted.
+ (JSC::B3::Air::Liveness::LocalCalc::Iterable::begin): Deleted.
+ (JSC::B3::Air::Liveness::LocalCalc::Iterable::end): Deleted.
+ (JSC::B3::Air::Liveness::LocalCalc::Iterable::contains): Deleted.
+ (JSC::B3::Air::Liveness::LocalCalc::live): Deleted.
+ (JSC::B3::Air::Liveness::LocalCalc::isLive): Deleted.
+ (JSC::B3::Air::Liveness::LocalCalc::execute): Deleted.
+ (JSC::B3::Air::Liveness::rawLiveAtHead): Deleted.
+ (JSC::B3::Air::Liveness::Iterable::Iterable): Deleted.
+ (JSC::B3::Air::Liveness::Iterable::iterator::iterator): Deleted.
+ (JSC::B3::Air::Liveness::Iterable::iterator::operator*): Deleted.
+ (JSC::B3::Air::Liveness::Iterable::iterator::operator++): Deleted.
+ (JSC::B3::Air::Liveness::Iterable::iterator::operator==): Deleted.
+ (JSC::B3::Air::Liveness::Iterable::iterator::operator!=): Deleted.
+ (JSC::B3::Air::Liveness::Iterable::begin): Deleted.
+ (JSC::B3::Air::Liveness::Iterable::end): Deleted.
+ (JSC::B3::Air::Liveness::Iterable::contains): Deleted.
+ (JSC::B3::Air::Liveness::liveAtHead): Deleted.
+ (JSC::B3::Air::Liveness::liveAtTail): Deleted.
+ (JSC::B3::Air::Liveness::workset): Deleted.
+
2017-03-25 Filip Pizlo <[email protected]>
Air::Liveness shouldn't need HashSets
Modified: trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj (214409 => 214410)
--- trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2017-03-26 22:11:13 UTC (rev 214409)
+++ trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2017-03-27 04:17:52 UTC (rev 214410)
@@ -1007,6 +1007,9 @@
0FF427651591A1CE004CB9FF /* DFGDisassembler.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FF427621591A1C9004CB9FF /* DFGDisassembler.h */; };
0FF4B4BC1E88449700DBBE86 /* AirRegLiveness.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FF4B4BA1E88449500DBBE86 /* AirRegLiveness.cpp */; };
0FF4B4BD1E88449A00DBBE86 /* AirRegLiveness.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FF4B4BB1E88449500DBBE86 /* AirRegLiveness.h */; };
+ 0FF4B4C71E8893C500DBBE86 /* AirCFG.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FF4B4C61E8893BF00DBBE86 /* AirCFG.h */; };
+ 0FF4B4CA1E889D7B00DBBE86 /* B3VariableLiveness.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FF4B4C81E889D7800DBBE86 /* B3VariableLiveness.cpp */; };
+ 0FF4B4CB1E889D7E00DBBE86 /* B3VariableLiveness.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FF4B4C91E889D7800DBBE86 /* B3VariableLiveness.h */; };
0FF60AC216740F8300029779 /* ReduceWhitespace.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FF60AC016740F8100029779 /* ReduceWhitespace.h */; settings = {ATTRIBUTES = (Private, ); }; };
0FF60AC316740F8800029779 /* ReduceWhitespace.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FF60ABF16740F8100029779 /* ReduceWhitespace.cpp */; };
0FF7168C15A3B235008F5DAA /* PropertyOffset.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FF7168A15A3B231008F5DAA /* PropertyOffset.h */; settings = {ATTRIBUTES = (Private, ); }; };
@@ -3524,6 +3527,9 @@
0FF427621591A1C9004CB9FF /* DFGDisassembler.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGDisassembler.h; path = dfg/DFGDisassembler.h; sourceTree = "<group>"; };
0FF4B4BA1E88449500DBBE86 /* AirRegLiveness.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirRegLiveness.cpp; path = b3/air/AirRegLiveness.cpp; sourceTree = "<group>"; };
0FF4B4BB1E88449500DBBE86 /* AirRegLiveness.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirRegLiveness.h; path = b3/air/AirRegLiveness.h; sourceTree = "<group>"; };
+ 0FF4B4C61E8893BF00DBBE86 /* AirCFG.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirCFG.h; path = b3/air/AirCFG.h; sourceTree = "<group>"; };
+ 0FF4B4C81E889D7800DBBE86 /* B3VariableLiveness.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3VariableLiveness.cpp; path = b3/B3VariableLiveness.cpp; sourceTree = "<group>"; };
+ 0FF4B4C91E889D7800DBBE86 /* B3VariableLiveness.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3VariableLiveness.h; path = b3/B3VariableLiveness.h; sourceTree = "<group>"; };
0FF60ABF16740F8100029779 /* ReduceWhitespace.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ReduceWhitespace.cpp; sourceTree = "<group>"; };
0FF60AC016740F8100029779 /* ReduceWhitespace.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ReduceWhitespace.h; sourceTree = "<group>"; };
0FF7168A15A3B231008F5DAA /* PropertyOffset.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PropertyOffset.h; sourceTree = "<group>"; };
@@ -5504,6 +5510,8 @@
0FEC84FD1BDACDAC0080FF74 /* B3ValueRep.h */,
0F2BBD921C5FF3F50023EF23 /* B3Variable.cpp */,
0F2BBD931C5FF3F50023EF23 /* B3Variable.h */,
+ 0FF4B4C81E889D7800DBBE86 /* B3VariableLiveness.cpp */,
+ 0FF4B4C91E889D7800DBBE86 /* B3VariableLiveness.h */,
0F2BBD941C5FF3F50023EF23 /* B3VariableValue.cpp */,
0F2BBD951C5FF3F50023EF23 /* B3VariableValue.h */,
53D444DD1DAF09A000B92784 /* B3WasmAddressValue.cpp */,
@@ -5538,6 +5546,7 @@
0F6183211C45BF070072450B /* AirCCallingConvention.h */,
0FEC854E1BDACDC70080FF74 /* AirCCallSpecial.cpp */,
0FEC854F1BDACDC70080FF74 /* AirCCallSpecial.h */,
+ 0FF4B4C61E8893BF00DBBE86 /* AirCFG.h */,
0FEC85501BDACDC70080FF74 /* AirCode.cpp */,
0FEC85511BDACDC70080FF74 /* AirCode.h */,
0F6183221C45BF070072450B /* AirCustom.cpp */,
@@ -8547,6 +8556,7 @@
BC02E90F0E1839DB000F9297 /* ErrorPrototype.h in Headers */,
996B731B1BDA08D100331B84 /* ErrorPrototype.lut.h in Headers */,
14AD910C1DCA92940014F9FE /* EvalCodeBlock.h in Headers */,
+ 0FF4B4CB1E889D7E00DBBE86 /* B3VariableLiveness.h in Headers */,
147341D21DC02E2E00AA29BA /* EvalExecutable.h in Headers */,
A54982041891D0B00081E5B8 /* EventLoop.h in Headers */,
FE1C0FFD1B193E9800B53FCA /* Exception.h in Headers */,
@@ -8840,6 +8850,7 @@
BC18C41E0E16F5CD00B34460 /* JSContextRef.h in Headers */,
A5EA70EE19F5B5C40098F5EC /* JSContextRefInspectorSupport.h in Headers */,
A5D2E665195E174000A518E7 /* JSContextRefInternal.h in Headers */,
+ 0FF4B4C71E8893C500DBBE86 /* AirCFG.h in Headers */,
148CD1D8108CF902008163C6 /* JSContextRefPrivate.h in Headers */,
A72028B81797601E0098028C /* JSCTestRunnerUtils.h in Headers */,
72AAF7CE1D0D31B3005E60BE /* JSCustomGetterSetterFunction.h in Headers */,
@@ -9964,6 +9975,7 @@
795F099D1E03600500BBE37F /* B3Compile.cpp in Sources */,
0FEC850D1BDACDAC0080FF74 /* B3Const32Value.cpp in Sources */,
0FEC850F1BDACDAC0080FF74 /* B3Const64Value.cpp in Sources */,
+ 0FF4B4CA1E889D7B00DBBE86 /* B3VariableLiveness.cpp in Sources */,
0FEC85111BDACDAC0080FF74 /* B3ConstDoubleValue.cpp in Sources */,
43422A621C158E6A00E2EB98 /* B3ConstFloatValue.cpp in Sources */,
0F338DF51BE93D550013C88F /* B3ConstrainedValue.cpp in Sources */,
Modified: trunk/Source/_javascript_Core/b3/B3BasicBlock.h (214409 => 214410)
--- trunk/Source/_javascript_Core/b3/B3BasicBlock.h 2017-03-26 22:11:13 UTC (rev 214409)
+++ trunk/Source/_javascript_Core/b3/B3BasicBlock.h 2017-03-27 04:17:52 UTC (rev 214410)
@@ -64,6 +64,13 @@
size_t size() const { return m_values.size(); }
Value* at(size_t index) const { return m_values[index]; }
Value*& at(size_t index) { return m_values[index]; }
+
+ Value* get(size_t index) const
+ {
+ if (index >= size())
+ return nullptr;
+ return at(index);
+ }
Value* last() const { return m_values.last(); }
Value*& last() { return m_values.last(); }
Modified: trunk/Source/_javascript_Core/b3/B3FixSSA.cpp (214409 => 214410)
--- trunk/Source/_javascript_Core/b3/B3FixSSA.cpp 2017-03-26 22:11:13 UTC (rev 214409)
+++ trunk/Source/_javascript_Core/b3/B3FixSSA.cpp 2017-03-27 04:17:52 UTC (rev 214410)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2016 Apple Inc. All rights reserved.
+ * Copyright (C) 2016-2017 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -38,6 +38,7 @@
#include "B3UpsilonValue.h"
#include "B3ValueInlines.h"
#include "B3Variable.h"
+#include "B3VariableLiveness.h"
#include "B3VariableValue.h"
#include <wtf/CommaPrinter.h>
#include <wtf/IndexSet.h>
@@ -136,7 +137,10 @@
// We know that we have variables to optimize, so do that now.
breakCriticalEdges(proc);
-
+
+ VariableLiveness liveness(proc);
+ VariableLiveness::LiveAtHead liveAtHead = liveness.liveAtHead();
+
SSACalculator ssa(proc);
// Create a SSACalculator::Variable ("calcVar") for every variable.
@@ -167,6 +171,9 @@
ssa.computePhis(
[&] (SSACalculator::Variable* calcVar, BasicBlock* block) -> Value* {
Variable* variable = calcVarToVariable[calcVar->index()];
+ if (!liveAtHead.isLiveAtHead(block, variable))
+ return nullptr;
+
Value* phi = proc.add<Value>(Phi, variable->type(), block->at(0)->origin());
if (verbose) {
dataLog(
@@ -182,10 +189,8 @@
for (BasicBlock* block : proc.blocksInPreOrder()) {
mapping.clear();
- for (unsigned index = calcVarToVariable.size(); index--;) {
- Variable* variable = calcVarToVariable[index];
- SSACalculator::Variable* calcVar = ssa.variable(index);
-
+ for (Variable* variable : liveness.liveAtHead(block)) {
+ SSACalculator::Variable* calcVar = variableToCalcVar[variable];
SSACalculator::Def* def = ssa.reachingDefAtHead(block, calcVar);
if (def)
mapping[variable] = def->value();
Added: trunk/Source/_javascript_Core/b3/B3VariableLiveness.cpp (0 => 214410)
--- trunk/Source/_javascript_Core/b3/B3VariableLiveness.cpp (rev 0)
+++ trunk/Source/_javascript_Core/b3/B3VariableLiveness.cpp 2017-03-27 04:17:52 UTC (rev 214410)
@@ -0,0 +1,45 @@
+/*
+ * Copyright (C) 2017 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+#include "B3VariableLiveness.h"
+
+#if ENABLE(B3_JIT)
+
+namespace JSC { namespace B3 {
+
+VariableLiveness::VariableLiveness(Procedure& proc)
+ : WTF::Liveness<VariableLivenessAdapter>(proc.cfg(), proc)
+{
+}
+
+VariableLiveness::~VariableLiveness()
+{
+}
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
Added: trunk/Source/_javascript_Core/b3/B3VariableLiveness.h (0 => 214410)
--- trunk/Source/_javascript_Core/b3/B3VariableLiveness.h (rev 0)
+++ trunk/Source/_javascript_Core/b3/B3VariableLiveness.h 2017-03-27 04:17:52 UTC (rev 214410)
@@ -0,0 +1,107 @@
+/*
+ * Copyright (C) 2017 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#pragma once
+
+#if ENABLE(B3_JIT)
+
+#include "B3BasicBlock.h"
+#include "B3CFG.h"
+#include "B3Procedure.h"
+#include "B3ValueInlines.h"
+#include "B3Variable.h"
+#include "B3VariableValue.h"
+#include <wtf/Liveness.h>
+
+namespace JSC { namespace B3 {
+
+struct VariableLivenessAdapter {
+ static constexpr const char* name = "VariableLiveness";
+ typedef B3::CFG CFG;
+ typedef Variable* Thing;
+
+ VariableLivenessAdapter(Procedure& proc)
+ : proc(proc)
+ {
+ }
+
+ unsigned numIndices()
+ {
+ return proc.variables().size();
+ }
+
+ static unsigned valueToIndex(Variable* var) { return var->index(); }
+ Variable* indexToValue(unsigned index) { return proc.variables()[index]; }
+
+ unsigned blockSize(BasicBlock* block)
+ {
+ return block->size();
+ }
+
+ template<typename Func>
+ void forEachEarlyUse(BasicBlock* block, unsigned valueIndex, const Func& func)
+ {
+ Value* value = block->get(valueIndex);
+ if (!value)
+ return;
+ if (value->opcode() != Get)
+ return;
+ func(value->as<VariableValue>()->variable()->index());
+ }
+
+ template<typename Func>
+ void forEachLateUse(BasicBlock*, unsigned, const Func&)
+ {
+ }
+
+ template<typename Func>
+ void forEachEarlyDef(BasicBlock*, unsigned, const Func&)
+ {
+ }
+
+ template<typename Func>
+ void forEachLateDef(BasicBlock* block, unsigned valueIndex, const Func& func)
+ {
+ Value* value = block->get(valueIndex);
+ if (!value)
+ return;
+ if (value->opcode() != Set)
+ return;
+ func(value->as<VariableValue>()->variable()->index());
+ }
+
+ Procedure& proc;
+};
+
+class VariableLiveness : public WTF::Liveness<VariableLivenessAdapter> {
+public:
+ VariableLiveness(Procedure&);
+ ~VariableLiveness();
+};
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
Added: trunk/Source/_javascript_Core/b3/air/AirCFG.h (0 => 214410)
--- trunk/Source/_javascript_Core/b3/air/AirCFG.h (rev 0)
+++ trunk/Source/_javascript_Core/b3/air/AirCFG.h 2017-03-27 04:17:52 UTC (rev 214410)
@@ -0,0 +1,76 @@
+/*
+ * Copyright (C) 2017 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#pragma once
+
+#if ENABLE(B3_JIT)
+
+#include "AirBasicBlock.h"
+#include "AirCode.h"
+#include <wtf/IndexMap.h>
+#include <wtf/IndexSet.h>
+
+namespace JSC { namespace B3 { namespace Air {
+
+class CFG {
+ WTF_MAKE_NONCOPYABLE(CFG);
+ WTF_MAKE_FAST_ALLOCATED;
+public:
+ typedef BasicBlock* Node;
+ typedef IndexSet<BasicBlock> Set;
+ template<typename T> using Map = IndexMap<BasicBlock, T>;
+ typedef Vector<BasicBlock*, 4> List;
+
+ CFG(Code& code)
+ : m_code(code)
+ {
+ }
+
+ Node root() { return m_code[0]; }
+
+ template<typename T>
+ Map<T> newMap() { return IndexMap<JSC::B3::Air::BasicBlock, T>(m_code.size()); }
+
+ SuccessorCollection<BasicBlock, BasicBlock::SuccessorList> successors(Node node) { return node->successorBlocks(); }
+ BasicBlock::PredecessorList& predecessors(Node node) { return node->predecessors(); }
+
+ unsigned index(Node node) const { return node->index(); }
+ Node node(unsigned index) const { return m_code[index]; }
+ unsigned numNodes() const { return m_code.size(); }
+
+ PointerDump<BasicBlock> dump(Node node) const { return pointerDump(node); }
+
+ void dump(PrintStream& out) const
+ {
+ m_code.dump(out);
+ }
+
+private:
+ Code& m_code;
+};
+
+} } } // namespace JSC::B3::Air
+
+#endif // ENABLE(B3_JIT)
Modified: trunk/Source/_javascript_Core/b3/air/AirCode.cpp (214409 => 214410)
--- trunk/Source/_javascript_Core/b3/air/AirCode.cpp 2017-03-26 22:11:13 UTC (rev 214409)
+++ trunk/Source/_javascript_Core/b3/air/AirCode.cpp 2017-03-27 04:17:52 UTC (rev 214410)
@@ -29,6 +29,7 @@
#if ENABLE(B3_JIT)
#include "AirCCallSpecial.h"
+#include "AirCFG.h"
#include "B3BasicBlockUtils.h"
#include "B3Procedure.h"
#include "B3StackSlot.h"
@@ -38,6 +39,7 @@
Code::Code(Procedure& proc)
: m_proc(proc)
+ , m_cfg(new CFG(*this))
, m_lastPhaseName("initial")
{
// Come up with initial orderings of registers. The user may replace this with something else.
Modified: trunk/Source/_javascript_Core/b3/air/AirCode.h (214409 => 214410)
--- trunk/Source/_javascript_Core/b3/air/AirCode.h 2017-03-26 22:11:13 UTC (rev 214409)
+++ trunk/Source/_javascript_Core/b3/air/AirCode.h 2017-03-27 04:17:52 UTC (rev 214410)
@@ -52,6 +52,7 @@
class BlockInsertionSet;
class CCallSpecial;
+class CFG;
class Disassembler;
typedef void WasmBoundsCheckGeneratorFunction(CCallHelpers&, GPRReg, unsigned);
@@ -176,7 +177,7 @@
// Recomputes predecessors and deletes unreachable blocks.
void resetReachability();
-
+
JS_EXPORT_PRIVATE void dump(PrintStream&) const;
unsigned size() const { return m_blocks.size(); }
@@ -256,6 +257,8 @@
void addFastTmp(Tmp);
bool isFastTmp(Tmp tmp) const { return m_fastTmps.contains(tmp); }
+ CFG& cfg() const { return *m_cfg; }
+
void* addDataSection(size_t);
// The name has to be a string literal, since we don't do any memory management for the string.
@@ -304,6 +307,7 @@
SparseCollection<StackSlot> m_stackSlots;
Vector<std::unique_ptr<BasicBlock>> m_blocks;
SparseCollection<Special> m_specials;
+ std::unique_ptr<CFG> m_cfg;
HashSet<Tmp> m_fastTmps;
CCallSpecial* m_cCallSpecial { nullptr };
unsigned m_numGPTmps { 0 };
Modified: trunk/Source/_javascript_Core/b3/air/AirLiveness.h (214409 => 214410)
--- trunk/Source/_javascript_Core/b3/air/AirLiveness.h 2017-03-26 22:11:13 UTC (rev 214409)
+++ trunk/Source/_javascript_Core/b3/air/AirLiveness.h 2017-03-27 04:17:52 UTC (rev 214410)
@@ -28,27 +28,107 @@
#if ENABLE(B3_JIT)
#include "AirBasicBlock.h"
+#include "AirCFG.h"
#include "AirCode.h"
#include "AirInstInlines.h"
#include "AirStackSlot.h"
#include "AirTmpInlines.h"
-#include "B3TimingScope.h"
-#include <wtf/IndexMap.h>
-#include <wtf/IndexSparseSet.h>
-#include <wtf/ListDump.h>
+#include <wtf/Liveness.h>
namespace JSC { namespace B3 { namespace Air {
+template<typename Adapter>
+struct LivenessAdapter {
+ typedef Air::CFG CFG;
+
+ LivenessAdapter(Code& code)
+ : code(code)
+ {
+ }
+
+ unsigned blockSize(BasicBlock* block)
+ {
+ return block->size();
+ }
+
+ template<typename Func>
+ void forEachEarlyUse(BasicBlock* block, unsigned instIndex, const Func& func)
+ {
+ Inst* inst = block->get(instIndex);
+ if (!inst)
+ return;
+ inst->forEach<typename Adapter::Thing>(
+ [&] (typename Adapter::Thing& thing, Arg::Role role, Bank bank, Width) {
+ if (Arg::isEarlyUse(role)
+ && Adapter::acceptsBank(bank)
+ && Adapter::acceptsRole(role))
+ func(Adapter::valueToIndex(thing));
+ });
+ }
+
+ template<typename Func>
+ void forEachLateUse(BasicBlock* block, unsigned instIndex, const Func& func)
+ {
+ Inst* inst = block->get(instIndex);
+ if (!inst)
+ return;
+ inst->forEach<typename Adapter::Thing>(
+ [&] (typename Adapter::Thing& thing, Arg::Role role, Bank bank, Width) {
+ if (Arg::isLateUse(role)
+ && Adapter::acceptsBank(bank)
+ && Adapter::acceptsRole(role))
+ func(Adapter::valueToIndex(thing));
+ });
+ }
+
+ template<typename Func>
+ void forEachEarlyDef(BasicBlock* block, unsigned instIndex, const Func& func)
+ {
+ Inst* inst = block->get(instIndex);
+ if (!inst)
+ return;
+ inst->forEach<typename Adapter::Thing>(
+ [&] (typename Adapter::Thing& thing, Arg::Role role, Bank bank, Width) {
+ if (Arg::isEarlyDef(role)
+ && Adapter::acceptsBank(bank)
+ && Adapter::acceptsRole(role))
+ func(Adapter::valueToIndex(thing));
+ });
+ }
+
+ template<typename Func>
+ void forEachLateDef(BasicBlock* block, unsigned instIndex, const Func& func)
+ {
+ Inst* inst = block->get(instIndex);
+ if (!inst)
+ return;
+ inst->forEach<typename Adapter::Thing>(
+ [&] (typename Adapter::Thing& thing, Arg::Role role, Bank bank, Width) {
+ if (Arg::isLateDef(role)
+ && Adapter::acceptsBank(bank)
+ && Adapter::acceptsRole(role))
+ func(Adapter::valueToIndex(thing));
+ });
+ }
+
+ Code& code;
+};
+
template<Bank adapterBank, Arg::Temperature minimumTemperature = Arg::Cold>
-struct TmpLivenessAdapter {
+struct TmpLivenessAdapter : LivenessAdapter<TmpLivenessAdapter<adapterBank, minimumTemperature>> {
+ typedef LivenessAdapter<TmpLivenessAdapter<adapterBank, minimumTemperature>> Base;
+
static constexpr const char* name = "TmpLiveness";
typedef Tmp Thing;
- TmpLivenessAdapter(Code&) { }
+ TmpLivenessAdapter(Code& code)
+ : Base(code)
+ {
+ }
- static unsigned numIndices(Code& code)
+ unsigned numIndices()
{
- unsigned numTmps = code.numTmps(adapterBank);
+ unsigned numTmps = Base::code.numTmps(adapterBank);
return AbsoluteTmpMapper<adapterBank>::absoluteIndex(numTmps);
}
static bool acceptsBank(Bank bank) { return bank == adapterBank; }
@@ -57,16 +137,16 @@
static Tmp indexToValue(unsigned index) { return AbsoluteTmpMapper<adapterBank>::tmpFromAbsoluteIndex(index); }
};
-struct StackSlotLivenessAdapter {
+struct StackSlotLivenessAdapter : LivenessAdapter<StackSlotLivenessAdapter> {
static constexpr const char* name = "StackSlotLiveness";
typedef StackSlot* Thing;
StackSlotLivenessAdapter(Code& code)
- : m_code(code)
+ : LivenessAdapter(code)
{
}
- static unsigned numIndices(Code& code)
+ unsigned numIndices()
{
return code.stackSlots().size();
}
@@ -73,336 +153,16 @@
static bool acceptsBank(Bank) { return true; }
static bool acceptsRole(Arg::Role) { return true; }
static unsigned valueToIndex(StackSlot* stackSlot) { return stackSlot->index(); }
- StackSlot* indexToValue(unsigned index) { return m_code.stackSlots()[index]; }
-
-private:
- Code& m_code;
+ StackSlot* indexToValue(unsigned index) { return code.stackSlots()[index]; }
};
-// HEADS UP: The algorithm here is duplicated in AirRegLiveness.h.
template<typename Adapter>
-class Liveness : public Adapter {
- struct Workset;
+class Liveness : public WTF::Liveness<Adapter> {
public:
- typedef typename Adapter::Thing Thing;
- typedef Vector<unsigned, 4, UnsafeVectorOverflow> IndexVector;
-
Liveness(Code& code)
- : Adapter(code)
- , m_workset(Adapter::numIndices(code))
- , m_liveAtHead(code.size())
- , m_liveAtTail(code.size())
+ : WTF::Liveness<Adapter>(code.cfg(), code)
{
- TimingScope timingScope(Adapter::name);
-
- // The liveAtTail of each block automatically contains the LateUse's of the terminal.
- for (BasicBlock* block : code) {
- IndexVector& liveAtTail = m_liveAtTail[block];
-
- block->last().forEach<typename Adapter::Thing>(
- [&] (typename Adapter::Thing& thing, Arg::Role role, Bank bank, Width) {
- if (Arg::isLateUse(role)
- && Adapter::acceptsBank(bank)
- && Adapter::acceptsRole(role))
- liveAtTail.append(Adapter::valueToIndex(thing));
- });
-
- std::sort(liveAtTail.begin(), liveAtTail.end());
- removeRepeatedElements(liveAtTail);
- }
-
- // Blocks with new live values at tail.
- BitVector dirtyBlocks;
- for (size_t blockIndex = code.size(); blockIndex--;)
- dirtyBlocks.set(blockIndex);
-
- IndexVector mergeBuffer;
-
- bool changed;
- do {
- changed = false;
-
- for (size_t blockIndex = code.size(); blockIndex--;) {
- BasicBlock* block = code[blockIndex];
- if (!block)
- continue;
-
- if (!dirtyBlocks.quickClear(blockIndex))
- continue;
-
- LocalCalc localCalc(*this, block);
- for (size_t instIndex = block->size(); instIndex--;)
- localCalc.execute(instIndex);
-
- // Handle the early def's of the first instruction.
- block->at(0).forEach<typename Adapter::Thing>(
- [&] (typename Adapter::Thing& thing, Arg::Role role, Bank bank, Width) {
- if (Arg::isEarlyDef(role)
- && Adapter::acceptsBank(bank)
- && Adapter::acceptsRole(role))
- m_workset.remove(Adapter::valueToIndex(thing));
- });
-
- IndexVector& liveAtHead = m_liveAtHead[block];
-
- // We only care about Tmps that were discovered in this iteration. It is impossible
- // to remove a live value from the head.
- // We remove all the values we already knew about so that we only have to deal with
- // what is new in LiveAtHead.
- if (m_workset.size() == liveAtHead.size())
- m_workset.clear();
- else {
- for (unsigned liveIndexAtHead : liveAtHead)
- m_workset.remove(liveIndexAtHead);
- }
-
- if (m_workset.isEmpty())
- continue;
-
- liveAtHead.reserveCapacity(liveAtHead.size() + m_workset.size());
- for (unsigned newValue : m_workset)
- liveAtHead.uncheckedAppend(newValue);
-
- m_workset.sort();
-
- for (BasicBlock* predecessor : block->predecessors()) {
- IndexVector& liveAtTail = m_liveAtTail[predecessor];
-
- if (liveAtTail.isEmpty())
- liveAtTail = m_workset.values();
- else {
- mergeBuffer.resize(0);
- mergeBuffer.reserveCapacity(liveAtTail.size() + m_workset.size());
- auto iter = mergeDeduplicatedSorted(
- liveAtTail.begin(), liveAtTail.end(),
- m_workset.begin(), m_workset.end(),
- mergeBuffer.begin());
- mergeBuffer.resize(iter - mergeBuffer.begin());
-
- if (mergeBuffer.size() == liveAtTail.size())
- continue;
-
- RELEASE_ASSERT(mergeBuffer.size() > liveAtTail.size());
- liveAtTail = mergeBuffer;
- }
-
- dirtyBlocks.quickSet(predecessor->index());
- changed = true;
- }
- }
- } while (changed);
}
-
- // This calculator has to be run in reverse.
- class LocalCalc {
- public:
- LocalCalc(Liveness& liveness, BasicBlock* block)
- : m_liveness(liveness)
- , m_block(block)
- {
- auto& workset = liveness.m_workset;
- workset.clear();
- IndexVector& liveAtTail = liveness.m_liveAtTail[block];
- for (unsigned index : liveAtTail)
- workset.add(index);
- }
-
- class Iterable {
- public:
- Iterable(Liveness& liveness)
- : m_liveness(liveness)
- {
- }
-
- class iterator {
- public:
- iterator(Adapter& adapter, IndexSparseSet<UnsafeVectorOverflow>::const_iterator sparceSetIterator)
- : m_adapter(adapter)
- , m_sparceSetIterator(sparceSetIterator)
- {
- }
-
- iterator& operator++()
- {
- ++m_sparceSetIterator;
- return *this;
- }
-
- typename Adapter::Thing operator*() const
- {
- return m_adapter.indexToValue(*m_sparceSetIterator);
- }
-
- bool operator==(const iterator& other) { return m_sparceSetIterator == other.m_sparceSetIterator; }
- bool operator!=(const iterator& other) { return m_sparceSetIterator != other.m_sparceSetIterator; }
-
- private:
- Adapter& m_adapter;
- IndexSparseSet<UnsafeVectorOverflow>::const_iterator m_sparceSetIterator;
- };
-
- iterator begin() const { return iterator(m_liveness, m_liveness.m_workset.begin()); }
- iterator end() const { return iterator(m_liveness, m_liveness.m_workset.end()); }
-
- bool contains(const typename Adapter::Thing& thing) const
- {
- return m_liveness.m_workset.contains(Adapter::valueToIndex(thing));
- }
-
- private:
- Liveness& m_liveness;
- };
-
- Iterable live() const
- {
- return Iterable(m_liveness);
- }
-
- bool isLive(const typename Adapter::Thing& thing) const
- {
- return live().contains(thing);
- }
-
- void execute(unsigned instIndex)
- {
- Inst& inst = m_block->at(instIndex);
- auto& workset = m_liveness.m_workset;
-
- // First handle the early def's of the next instruction.
- if (instIndex + 1 < m_block->size()) {
- Inst& nextInst = m_block->at(instIndex + 1);
- nextInst.forEach<typename Adapter::Thing>(
- [&] (typename Adapter::Thing& thing, Arg::Role role, Bank bank, Width) {
- if (Arg::isEarlyDef(role)
- && Adapter::acceptsBank(bank)
- && Adapter::acceptsRole(role))
- workset.remove(Adapter::valueToIndex(thing));
- });
- }
-
- // Then handle def's.
- inst.forEach<typename Adapter::Thing>(
- [&] (typename Adapter::Thing& thing, Arg::Role role, Bank bank, Width) {
- if (Arg::isLateDef(role)
- && Adapter::acceptsBank(bank)
- && Adapter::acceptsRole(role))
- workset.remove(Adapter::valueToIndex(thing));
- });
-
- // Then handle use's.
- inst.forEach<typename Adapter::Thing>(
- [&] (typename Adapter::Thing& thing, Arg::Role role, Bank bank, Width) {
- if (Arg::isEarlyUse(role)
- && Adapter::acceptsBank(bank)
- && Adapter::acceptsRole(role))
- workset.add(Adapter::valueToIndex(thing));
- });
-
- // And finally, handle the late use's of the previous instruction.
- if (instIndex) {
- Inst& prevInst = m_block->at(instIndex - 1);
- prevInst.forEach<typename Adapter::Thing>(
- [&] (typename Adapter::Thing& thing, Arg::Role role, Bank bank, Width) {
- if (Arg::isLateUse(role)
- && Adapter::acceptsBank(bank)
- && Adapter::acceptsRole(role))
- workset.add(Adapter::valueToIndex(thing));
- });
- }
- }
-
- private:
- Liveness& m_liveness;
- BasicBlock* m_block;
- };
-
- const IndexVector& rawLiveAtHead(BasicBlock* block)
- {
- return m_liveAtHead[block];
- }
-
- template<typename UnderlyingIterable>
- class Iterable {
- public:
- Iterable(Liveness& liveness, const UnderlyingIterable& iterable)
- : m_liveness(liveness)
- , m_iterable(iterable)
- {
- }
-
- class iterator {
- public:
- iterator()
- : m_liveness(nullptr)
- , m_iter()
- {
- }
-
- iterator(Liveness& liveness, typename UnderlyingIterable::const_iterator iter)
- : m_liveness(&liveness)
- , m_iter(iter)
- {
- }
-
- typename Adapter::Thing operator*()
- {
- return m_liveness->indexToValue(*m_iter);
- }
-
- iterator& operator++()
- {
- ++m_iter;
- return *this;
- }
-
- bool operator==(const iterator& other) const
- {
- ASSERT(m_liveness == other.m_liveness);
- return m_iter == other.m_iter;
- }
-
- bool operator!=(const iterator& other) const
- {
- return !(*this == other);
- }
-
- private:
- Liveness* m_liveness;
- typename UnderlyingIterable::const_iterator m_iter;
- };
-
- iterator begin() const { return iterator(m_liveness, m_iterable.begin()); }
- iterator end() const { return iterator(m_liveness, m_iterable.end()); }
-
- bool contains(const typename Adapter::Thing& thing) const
- {
- return m_liveness.m_workset.contains(Adapter::valueToIndex(thing));
- }
-
- private:
- Liveness& m_liveness;
- const UnderlyingIterable& m_iterable;
- };
-
- Iterable<IndexVector> liveAtHead(BasicBlock* block)
- {
- return Iterable<IndexVector>(*this, m_liveAtHead[block]);
- }
-
- Iterable<IndexVector> liveAtTail(BasicBlock* block)
- {
- return Iterable<IndexVector>(*this, m_liveAtTail[block]);
- }
-
- IndexSparseSet<UnsafeVectorOverflow>& workset() { return m_workset; }
-
-private:
- friend class LocalCalc;
- friend class LocalCalc::Iterable;
-
- IndexSparseSet<UnsafeVectorOverflow> m_workset;
- IndexMap<BasicBlock, IndexVector> m_liveAtHead;
- IndexMap<BasicBlock, IndexVector> m_liveAtTail;
};
template<Bank bank, Arg::Temperature minimumTemperature = Arg::Cold>
Modified: trunk/Source/WTF/ChangeLog (214409 => 214410)
--- trunk/Source/WTF/ChangeLog 2017-03-26 22:11:13 UTC (rev 214409)
+++ trunk/Source/WTF/ChangeLog 2017-03-27 04:17:52 UTC (rev 214410)
@@ -1,3 +1,56 @@
+2017-03-26 Filip Pizlo <[email protected]>
+
+ B3::fixSSA should do liveness pruning
+ https://bugs.webkit.org/show_bug.cgi?id=170111
+
+ Reviewed by Saam Barati.
+
+ Move Air::Liveness<> to WTF::Liveness<>. This is pretty easy since Air::Liveness<> was
+ already fairly generic. It leverages the CFG concept so that it can understand many
+ different kinds of basic blocks. It doesn't try to understand the contents of basic
+ blocks; it just asks the adaptor for the block size and asks for the early/late
+ uses/defs of each thing in the block.
+
+ This makes it easy to create a B3::VariableLiveness, which fixSSA then uses for
+ pruning. One of the new features is the Liveness::LiveAtHead nested class, which you
+ instantiate if you want to perform liveAtHead queries, which SSA construction wants to
+ do.
+
+ This also fixes https://bugs.webkit.org/show_bug.cgi?id=170102#c12
+
+ * WTF.xcodeproj/project.pbxproj:
+ * wtf/CMakeLists.txt:
+ * wtf/Liveness.h: Added.
+ (WTF::Liveness::Liveness):
+ (WTF::Liveness::LocalCalc::LocalCalc):
+ (WTF::Liveness::LocalCalc::Iterable::Iterable):
+ (WTF::Liveness::LocalCalc::Iterable::iterator::iterator):
+ (WTF::Liveness::LocalCalc::Iterable::iterator::operator++):
+ (WTF::Liveness::LocalCalc::Iterable::iterator::operator*):
+ (WTF::Liveness::LocalCalc::Iterable::iterator::operator==):
+ (WTF::Liveness::LocalCalc::Iterable::iterator::operator!=):
+ (WTF::Liveness::LocalCalc::Iterable::begin):
+ (WTF::Liveness::LocalCalc::Iterable::end):
+ (WTF::Liveness::LocalCalc::Iterable::contains):
+ (WTF::Liveness::LocalCalc::live):
+ (WTF::Liveness::LocalCalc::isLive):
+ (WTF::Liveness::LocalCalc::execute):
+ (WTF::Liveness::rawLiveAtHead):
+ (WTF::Liveness::Iterable::Iterable):
+ (WTF::Liveness::Iterable::iterator::iterator):
+ (WTF::Liveness::Iterable::iterator::operator*):
+ (WTF::Liveness::Iterable::iterator::operator++):
+ (WTF::Liveness::Iterable::iterator::operator==):
+ (WTF::Liveness::Iterable::iterator::operator!=):
+ (WTF::Liveness::Iterable::begin):
+ (WTF::Liveness::Iterable::end):
+ (WTF::Liveness::Iterable::contains):
+ (WTF::Liveness::liveAtHead):
+ (WTF::Liveness::liveAtTail):
+ (WTF::Liveness::workset):
+ (WTF::Liveness::LiveAtHead::LiveAtHead):
+ (WTF::Liveness::LiveAtHead::isLiveAtHead):
+
2017-03-25 Filip Pizlo <[email protected]>
Air::Liveness shouldn't need HashSets
Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (214409 => 214410)
--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2017-03-26 22:11:13 UTC (rev 214409)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2017-03-27 04:17:52 UTC (rev 214410)
@@ -82,6 +82,7 @@
0FEC84AF1BD825310080FF74 /* GraphNodeWorklist.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC84AE1BD825310080FF74 /* GraphNodeWorklist.h */; };
0FEC84B11BDACD390080FF74 /* ScopedLambda.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC84B01BDACD390080FF74 /* ScopedLambda.h */; };
0FED67B61B22D4D80066CE15 /* TinyPtrSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FED67B51B22D4D80066CE15 /* TinyPtrSet.h */; };
+ 0FF4B4C51E88939C00DBBE86 /* Liveness.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FF4B4C41E88939C00DBBE86 /* Liveness.h */; };
0FF860951BCCBD740045127F /* PointerComparison.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FF860941BCCBD740045127F /* PointerComparison.h */; };
0FFF19DC1BB334EB00886D91 /* ParallelHelperPool.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FFF19DA1BB334EB00886D91 /* ParallelHelperPool.cpp */; };
0FFF19DD1BB334EB00886D91 /* ParallelHelperPool.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FFF19DB1BB334EB00886D91 /* ParallelHelperPool.h */; };
@@ -467,6 +468,7 @@
0FEC84AE1BD825310080FF74 /* GraphNodeWorklist.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = GraphNodeWorklist.h; sourceTree = "<group>"; };
0FEC84B01BDACD390080FF74 /* ScopedLambda.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ScopedLambda.h; sourceTree = "<group>"; };
0FED67B51B22D4D80066CE15 /* TinyPtrSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TinyPtrSet.h; sourceTree = "<group>"; };
+ 0FF4B4C41E88939C00DBBE86 /* Liveness.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Liveness.h; sourceTree = "<group>"; };
0FF860941BCCBD740045127F /* PointerComparison.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PointerComparison.h; sourceTree = "<group>"; };
0FFF19DA1BB334EB00886D91 /* ParallelHelperPool.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ParallelHelperPool.cpp; sourceTree = "<group>"; };
0FFF19DB1BB334EB00886D91 /* ParallelHelperPool.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ParallelHelperPool.h; sourceTree = "<group>"; };
@@ -1027,6 +1029,7 @@
539EB0621D55284200C82EF7 /* LEBDecoder.h */,
A70DA0831799F04D00529A9B /* ListDump.h */,
A8A472C1151A825A004123FF /* ListHashSet.h */,
+ 0FF4B4C41E88939C00DBBE86 /* Liveness.h */,
0FE164681B6FFC9600400E7C /* Lock.cpp */,
0FE164691B6FFC9600400E7C /* Lock.h */,
0F0FCDDD1DD167F900CCAB53 /* LockAlgorithm.h */,
@@ -1390,6 +1393,7 @@
9BD8F40B176C2B470002D865 /* AtomicStringTable.h in Headers */,
1469419C16EAB10A0024E146 /* AutodrainedPool.h in Headers */,
0F43D8F21DB5ADDC00108FB6 /* AutomaticThread.h in Headers */,
+ 0FF4B4C51E88939C00DBBE86 /* Liveness.h in Headers */,
DCEE22051CEB9869000C2396 /* BackwardsGraph.h in Headers */,
0FB14E19180FA218009B6B4D /* Bag.h in Headers */,
0FB14E1B1810E1DC009B6B4D /* BagToHashMap.h in Headers */,
Modified: trunk/Source/WTF/wtf/CMakeLists.txt (214409 => 214410)
--- trunk/Source/WTF/wtf/CMakeLists.txt 2017-03-26 22:11:13 UTC (rev 214409)
+++ trunk/Source/WTF/wtf/CMakeLists.txt 2017-03-27 04:17:52 UTC (rev 214410)
@@ -57,6 +57,7 @@
IteratorAdaptors.h
IteratorRange.h
ListHashSet.h
+ Liveness.h
Lock.h
LockAlgorithm.h
LockedPrintStream.h
Added: trunk/Source/WTF/wtf/Liveness.h (0 => 214410)
--- trunk/Source/WTF/wtf/Liveness.h (rev 0)
+++ trunk/Source/WTF/wtf/Liveness.h 2017-03-27 04:17:52 UTC (rev 214410)
@@ -0,0 +1,373 @@
+/*
+ * Copyright (C) 2015-2017 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#pragma once
+
+#include <wtf/BitVector.h>
+#include <wtf/IndexSparseSet.h>
+#include <wtf/ListDump.h>
+#include <wtf/StdLibExtras.h>
+
+namespace WTF {
+
+// HEADS UP: The algorithm here is duplicated in AirRegLiveness.h. That one uses sets rather
+// than fancy vectors, because that's better for register liveness analysis.
+template<typename Adapter>
+class Liveness : public Adapter {
+public:
+ typedef typename Adapter::CFG CFG;
+ typedef typename Adapter::Thing Thing;
+ typedef Vector<unsigned, 4, UnsafeVectorOverflow> IndexVector;
+
+ template<typename... Arguments>
+ Liveness(CFG& cfg, Arguments&&... arguments)
+ : Adapter(std::forward<Arguments>(arguments)...)
+ , m_cfg(cfg)
+ , m_workset(Adapter::numIndices())
+ , m_liveAtHead(cfg.template newMap<IndexVector>())
+ , m_liveAtTail(cfg.template newMap<IndexVector>())
+ {
+ // The liveAtTail of each block automatically contains the LateUse's of the terminal.
+ for (unsigned blockIndex = m_cfg.numNodes(); blockIndex--;) {
+ typename CFG::Node block = m_cfg.node(blockIndex);
+ if (!block)
+ continue;
+
+ IndexVector& liveAtTail = m_liveAtTail[block];
+
+ Adapter::forEachLateUse(
+ block, Adapter::blockSize(block) - 1,
+ [&] (unsigned index) {
+ liveAtTail.append(index);
+ });
+
+ std::sort(liveAtTail.begin(), liveAtTail.end());
+ removeRepeatedElements(liveAtTail);
+ }
+
+ // Blocks with new live values at tail.
+ BitVector dirtyBlocks;
+ for (size_t blockIndex = m_cfg.numNodes(); blockIndex--;)
+ dirtyBlocks.set(blockIndex);
+
+ IndexVector mergeBuffer;
+
+ bool changed;
+ do {
+ changed = false;
+
+ for (size_t blockIndex = m_cfg.numNodes(); blockIndex--;) {
+ typename CFG::Node block = m_cfg.node(blockIndex);
+ if (!block)
+ continue;
+
+ if (!dirtyBlocks.quickClear(blockIndex))
+ continue;
+
+ LocalCalc localCalc(*this, block);
+ for (size_t instIndex = Adapter::blockSize(block); instIndex--;)
+ localCalc.execute(instIndex);
+
+ // Handle the early def's of the first instruction.
+ Adapter::forEachEarlyDef(
+ block, 0,
+ [&] (unsigned index) {
+ m_workset.remove(index);
+ });
+
+ IndexVector& liveAtHead = m_liveAtHead[block];
+
+ // We only care about Tmps that were discovered in this iteration. It is impossible
+ // to remove a live value from the head.
+ // We remove all the values we already knew about so that we only have to deal with
+ // what is new in LiveAtHead.
+ if (m_workset.size() == liveAtHead.size())
+ m_workset.clear();
+ else {
+ for (unsigned liveIndexAtHead : liveAtHead)
+ m_workset.remove(liveIndexAtHead);
+ }
+
+ if (m_workset.isEmpty())
+ continue;
+
+ liveAtHead.reserveCapacity(liveAtHead.size() + m_workset.size());
+ for (unsigned newValue : m_workset)
+ liveAtHead.uncheckedAppend(newValue);
+
+ m_workset.sort();
+
+ for (typename CFG::Node predecessor : m_cfg.predecessors(block)) {
+ IndexVector& liveAtTail = m_liveAtTail[predecessor];
+
+ if (liveAtTail.isEmpty())
+ liveAtTail = m_workset.values();
+ else {
+ mergeBuffer.resize(liveAtTail.size() + m_workset.size());
+ auto iter = mergeDeduplicatedSorted(
+ liveAtTail.begin(), liveAtTail.end(),
+ m_workset.begin(), m_workset.end(),
+ mergeBuffer.begin());
+ mergeBuffer.resize(iter - mergeBuffer.begin());
+
+ if (mergeBuffer.size() == liveAtTail.size())
+ continue;
+
+ RELEASE_ASSERT(mergeBuffer.size() > liveAtTail.size());
+ liveAtTail = mergeBuffer;
+ }
+
+ dirtyBlocks.quickSet(predecessor->index());
+ changed = true;
+ }
+ }
+ } while (changed);
+ }
+
+ // This calculator has to be run in reverse.
+ class LocalCalc {
+ public:
+ LocalCalc(Liveness& liveness, typename CFG::Node block)
+ : m_liveness(liveness)
+ , m_block(block)
+ {
+ auto& workset = liveness.m_workset;
+ workset.clear();
+ IndexVector& liveAtTail = liveness.m_liveAtTail[block];
+ for (unsigned index : liveAtTail)
+ workset.add(index);
+ }
+
+ class Iterable {
+ public:
+ Iterable(Liveness& liveness)
+ : m_liveness(liveness)
+ {
+ }
+
+ class iterator {
+ public:
+ iterator(Adapter& adapter, IndexSparseSet<UnsafeVectorOverflow>::const_iterator sparceSetIterator)
+ : m_adapter(adapter)
+ , m_sparceSetIterator(sparceSetIterator)
+ {
+ }
+
+ iterator& operator++()
+ {
+ ++m_sparceSetIterator;
+ return *this;
+ }
+
+ typename Adapter::Thing operator*() const
+ {
+ return m_adapter.indexToValue(*m_sparceSetIterator);
+ }
+
+ bool operator==(const iterator& other) { return m_sparceSetIterator == other.m_sparceSetIterator; }
+ bool operator!=(const iterator& other) { return m_sparceSetIterator != other.m_sparceSetIterator; }
+
+ private:
+ Adapter& m_adapter;
+ IndexSparseSet<UnsafeVectorOverflow>::const_iterator m_sparceSetIterator;
+ };
+
+ iterator begin() const { return iterator(m_liveness, m_liveness.m_workset.begin()); }
+ iterator end() const { return iterator(m_liveness, m_liveness.m_workset.end()); }
+
+ bool contains(const typename Adapter::Thing& thing) const
+ {
+ return m_liveness.m_workset.contains(Adapter::valueToIndex(thing));
+ }
+
+ private:
+ Liveness& m_liveness;
+ };
+
+ Iterable live() const
+ {
+ return Iterable(m_liveness);
+ }
+
+ bool isLive(const typename Adapter::Thing& thing) const
+ {
+ return live().contains(thing);
+ }
+
+ void execute(unsigned instIndex)
+ {
+ auto& workset = m_liveness.m_workset;
+
+ // First handle the early def's of the next instruction.
+ m_liveness.forEachEarlyDef(
+ m_block, instIndex + 1,
+ [&] (unsigned index) {
+ workset.remove(index);
+ });
+
+ // Then handle def's.
+ m_liveness.forEachLateDef(
+ m_block, instIndex,
+ [&] (unsigned index) {
+ workset.remove(index);
+ });
+
+ // Then handle use's.
+ m_liveness.forEachEarlyUse(
+ m_block, instIndex,
+ [&] (unsigned index) {
+ workset.add(index);
+ });
+
+ // And finally, handle the late use's of the previous instruction.
+ m_liveness.forEachLateUse(
+ m_block, instIndex - 1,
+ [&] (unsigned index) {
+ workset.add(index);
+ });
+ }
+
+ private:
+ Liveness& m_liveness;
+ typename CFG::Node m_block;
+ };
+
+ const IndexVector& rawLiveAtHead(typename CFG::Node block)
+ {
+ return m_liveAtHead[block];
+ }
+
+ template<typename UnderlyingIterable>
+ class Iterable {
+ public:
+ Iterable(Liveness& liveness, const UnderlyingIterable& iterable)
+ : m_liveness(liveness)
+ , m_iterable(iterable)
+ {
+ }
+
+ class iterator {
+ public:
+ iterator()
+ : m_liveness(nullptr)
+ , m_iter()
+ {
+ }
+
+ iterator(Liveness& liveness, typename UnderlyingIterable::const_iterator iter)
+ : m_liveness(&liveness)
+ , m_iter(iter)
+ {
+ }
+
+ typename Adapter::Thing operator*()
+ {
+ return m_liveness->indexToValue(*m_iter);
+ }
+
+ iterator& operator++()
+ {
+ ++m_iter;
+ return *this;
+ }
+
+ bool operator==(const iterator& other) const
+ {
+ ASSERT(m_liveness == other.m_liveness);
+ return m_iter == other.m_iter;
+ }
+
+ bool operator!=(const iterator& other) const
+ {
+ return !(*this == other);
+ }
+
+ private:
+ Liveness* m_liveness;
+ typename UnderlyingIterable::const_iterator m_iter;
+ };
+
+ iterator begin() const { return iterator(m_liveness, m_iterable.begin()); }
+ iterator end() const { return iterator(m_liveness, m_iterable.end()); }
+
+ bool contains(const typename Adapter::Thing& thing) const
+ {
+ return m_liveness.m_workset.contains(Adapter::valueToIndex(thing));
+ }
+
+ private:
+ Liveness& m_liveness;
+ const UnderlyingIterable& m_iterable;
+ };
+
+ Iterable<IndexVector> liveAtHead(typename CFG::Node block)
+ {
+ return Iterable<IndexVector>(*this, m_liveAtHead[block]);
+ }
+
+ Iterable<IndexVector> liveAtTail(typename CFG::Node block)
+ {
+ return Iterable<IndexVector>(*this, m_liveAtTail[block]);
+ }
+
+ IndexSparseSet<UnsafeVectorOverflow>& workset() { return m_workset; }
+
+ class LiveAtHead {
+ public:
+ LiveAtHead(Liveness& liveness)
+ : m_liveness(liveness)
+ {
+ for (unsigned blockIndex = m_liveness.m_cfg.numNodes(); blockIndex--;) {
+ typename CFG::Node block = m_liveness.m_cfg.node(blockIndex);
+ if (!block)
+ continue;
+
+ std::sort(m_liveness.m_liveAtHead[block].begin(), m_liveness.m_liveAtHead[block].end());
+ }
+ }
+
+ bool isLiveAtHead(typename CFG::Node block, const typename Adapter::Thing& thing)
+ {
+ return !!tryBinarySearch<unsigned>(m_liveness.m_liveAtHead[block], m_liveness.m_liveAtHead[block].size(), m_liveness.valueToIndex(thing), [] (unsigned* value) { return *value; });
+ }
+
+ private:
+ Liveness& m_liveness;
+ };
+
+ LiveAtHead liveAtHead() { return LiveAtHead(*this); }
+
+private:
+ friend class LocalCalc;
+ friend class LocalCalc::Iterable;
+
+ CFG& m_cfg;
+ IndexSparseSet<UnsafeVectorOverflow> m_workset;
+ typename CFG::template Map<IndexVector> m_liveAtHead;
+ typename CFG::template Map<IndexVector> m_liveAtTail;
+};
+
+} // namespace WTF
+
