dfg/DFGDesiredWeakReferences.cpp
dfg/DFGDisassembler.cpp
dfg/DFGDoesGC.cpp
- dfg/DFGDominators.cpp
dfg/DFGDriver.cpp
dfg/DFGEdge.cpp
dfg/DFGEpoch.cpp
dfg/DFGMinifiedNode.cpp
dfg/DFGMovHintRemovalPhase.cpp
dfg/DFGMultiGetByOffsetData.cpp
- dfg/DFGNaiveDominators.cpp
dfg/DFGNaturalLoops.cpp
dfg/DFGNode.cpp
dfg/DFGNodeFlags.cpp
+2015-11-01 Filip Pizlo <fpizlo@apple.com>
+
+ Dominators should be factored out of the DFG
+ https://bugs.webkit.org/show_bug.cgi?id=150764
+
+ Reviewed by Geoffrey Garen.
+
+ Factored DFGDominators.h/DFGDominators.cpp into WTF. To do this, I made two changes to the
+ DFG:
+
+ 1) DFG now has a CFG abstraction called DFG::CFG. The cool thing about this is that in the
+ future if we wanted to support inverted dominators, we could do it by just creating a
+ DFG::BackwardCFG.
+
+ 2) Got rid of DFG::Analysis. From now on, an Analysis being invalidated is expressed by the
+ DFG::Graph having a null pointer for that analysis. When we "run" the analysis, we
+ just instantiate it. This makes it much more natural to integrate WTF::Dominators into
+ the DFG.
+
+ * CMakeLists.txt:
+ * JavaScriptCore.xcodeproj/project.pbxproj:
+ * dfg/DFGAnalysis.h: Removed.
+ * dfg/DFGCFG.h: Added.
+ (JSC::DFG::CFG::CFG):
+ (JSC::DFG::CFG::root):
+ (JSC::DFG::CFG::newMap<T>):
+ (JSC::DFG::CFG::successors):
+ (JSC::DFG::CFG::predecessors):
+ (JSC::DFG::CFG::index):
+ (JSC::DFG::CFG::node):
+ (JSC::DFG::CFG::numNodes):
+ (JSC::DFG::CFG::dump):
+ * dfg/DFGCSEPhase.cpp:
+ * dfg/DFGDisassembler.cpp:
+ (JSC::DFG::Disassembler::createDumpList):
+ * dfg/DFGDominators.cpp: Removed.
+ * dfg/DFGDominators.h:
+ (JSC::DFG::Dominators::Dominators):
+ (JSC::DFG::Dominators::strictlyDominates): Deleted.
+ (JSC::DFG::Dominators::dominates): Deleted.
+ (JSC::DFG::Dominators::immediateDominatorOf): Deleted.
+ (JSC::DFG::Dominators::forAllStrictDominatorsOf): Deleted.
+ (JSC::DFG::Dominators::forAllDominatorsOf): Deleted.
+ (JSC::DFG::Dominators::forAllBlocksStrictlyDominatedBy): Deleted.
+ (JSC::DFG::Dominators::forAllBlocksDominatedBy): Deleted.
+ (JSC::DFG::Dominators::forAllBlocksInDominanceFrontierOf): Deleted.
+ (JSC::DFG::Dominators::forAllBlocksInIteratedDominanceFrontierOf): Deleted.
+ (JSC::DFG::Dominators::forAllBlocksInPrunedIteratedDominanceFrontierOf): Deleted.
+ (JSC::DFG::Dominators::forAllBlocksInDominanceFrontierOfImpl): Deleted.
+ (JSC::DFG::Dominators::forAllBlocksInIteratedDominanceFrontierOfImpl): Deleted.
+ (JSC::DFG::Dominators::BlockData::BlockData): Deleted.
+ * dfg/DFGEdgeDominates.h:
+ (JSC::DFG::EdgeDominates::operator()):
+ * dfg/DFGGraph.cpp:
+ (JSC::DFG::Graph::Graph):
+ (JSC::DFG::Graph::dumpBlockHeader):
+ (JSC::DFG::Graph::invalidateCFG):
+ (JSC::DFG::Graph::substituteGetLocal):
+ (JSC::DFG::Graph::handleAssertionFailure):
+ (JSC::DFG::Graph::ensureDominators):
+ (JSC::DFG::Graph::ensurePrePostNumbering):
+ (JSC::DFG::Graph::ensureNaturalLoops):
+ (JSC::DFG::Graph::valueProfileFor):
+ * dfg/DFGGraph.h:
+ (JSC::DFG::Graph::hasDebuggerEnabled):
+ * dfg/DFGLICMPhase.cpp:
+ (JSC::DFG::LICMPhase::run):
+ (JSC::DFG::LICMPhase::attemptHoist):
+ * dfg/DFGLoopPreHeaderCreationPhase.cpp:
+ (JSC::DFG::createPreHeader):
+ (JSC::DFG::LoopPreHeaderCreationPhase::run):
+ * dfg/DFGNaturalLoops.cpp:
+ (JSC::DFG::NaturalLoop::dump):
+ (JSC::DFG::NaturalLoops::NaturalLoops):
+ (JSC::DFG::NaturalLoops::~NaturalLoops):
+ (JSC::DFG::NaturalLoops::loopsOf):
+ (JSC::DFG::NaturalLoops::computeDependencies): Deleted.
+ (JSC::DFG::NaturalLoops::compute): Deleted.
+ * dfg/DFGNaturalLoops.h:
+ (JSC::DFG::NaturalLoops::numLoops):
+ * dfg/DFGNode.h:
+ (JSC::DFG::Node::SuccessorsIterable::end):
+ (JSC::DFG::Node::SuccessorsIterable::size):
+ (JSC::DFG::Node::SuccessorsIterable::at):
+ (JSC::DFG::Node::SuccessorsIterable::operator[]):
+ * dfg/DFGOSREntrypointCreationPhase.cpp:
+ (JSC::DFG::OSREntrypointCreationPhase::run):
+ * dfg/DFGObjectAllocationSinkingPhase.cpp:
+ * dfg/DFGPlan.cpp:
+ (JSC::DFG::Plan::compileInThreadImpl):
+ * dfg/DFGPrePostNumbering.cpp:
+ (JSC::DFG::PrePostNumbering::PrePostNumbering):
+ (JSC::DFG::PrePostNumbering::~PrePostNumbering):
+ (JSC::DFG::PrePostNumbering::compute): Deleted.
+ * dfg/DFGPrePostNumbering.h:
+ (JSC::DFG::PrePostNumbering::preNumber):
+ (JSC::DFG::PrePostNumbering::postNumber):
+ * dfg/DFGPutStackSinkingPhase.cpp:
+ * dfg/DFGSSACalculator.cpp:
+ (JSC::DFG::SSACalculator::nonLocalReachingDef):
+ (JSC::DFG::SSACalculator::reachingDefAtTail):
+ * dfg/DFGSSACalculator.h:
+ (JSC::DFG::SSACalculator::computePhis):
+ * dfg/DFGSSAConversionPhase.cpp:
+ (JSC::DFG::SSAConversionPhase::run):
+ * ftl/FTLLink.cpp:
+ (JSC::FTL::link):
+ * ftl/FTLLowerDFGToLLVM.cpp:
+ (JSC::FTL::DFG::LowerDFGToLLVM::lower):
+ (JSC::FTL::DFG::LowerDFGToLLVM::safelyInvalidateAfterTermination):
+ (JSC::FTL::DFG::LowerDFGToLLVM::isValid):
+
2015-10-31 Filip Pizlo <fpizlo@apple.com>
B3::reduceStrength's DCE should be more agro and less wrong
0FC3CCFD19ADA410006AC72A /* DFGBlockMapInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCF619ADA410006AC72A /* DFGBlockMapInlines.h */; };
0FC3CCFE19ADA410006AC72A /* DFGBlockSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCF719ADA410006AC72A /* DFGBlockSet.h */; };
0FC3CD0019ADA410006AC72A /* DFGBlockWorklist.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCF919ADA410006AC72A /* DFGBlockWorklist.h */; };
- 0FC3CD0119ADA411006AC72A /* DFGNaiveDominators.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FC3CCFA19ADA410006AC72A /* DFGNaiveDominators.cpp */; };
- 0FC3CD0219ADA411006AC72A /* DFGNaiveDominators.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCFB19ADA410006AC72A /* DFGNaiveDominators.h */; };
0FC712DE17CD8779008CC93C /* DeferredCompilationCallback.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FC712DC17CD8778008CC93C /* DeferredCompilationCallback.cpp */; };
0FC712DF17CD877C008CC93C /* DeferredCompilationCallback.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC712DD17CD8778008CC93C /* DeferredCompilationCallback.h */; settings = {ATTRIBUTES = (Private, ); }; };
0FC712E217CD8791008CC93C /* JITToDFGDeferredCompilationCallback.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FC712E017CD878F008CC93C /* JITToDFGDeferredCompilationCallback.cpp */; };
0FD3E40C1B618B6600C80E1E /* ObjectPropertyConditionSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FD3E4061B618B6600C80E1E /* ObjectPropertyConditionSet.h */; settings = {ATTRIBUTES = (Private, ); }; };
0FD3E40D1B618B6600C80E1E /* PropertyCondition.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FD3E4071B618B6600C80E1E /* PropertyCondition.cpp */; };
0FD3E40E1B618B6600C80E1E /* PropertyCondition.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FD3E4081B618B6600C80E1E /* PropertyCondition.h */; settings = {ATTRIBUTES = (Private, ); }; };
- 0FD81AD2154FB4EE00983E72 /* DFGDominators.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FD81ACF154FB4EB00983E72 /* DFGDominators.cpp */; };
0FD81AD3154FB4F000983E72 /* DFGDominators.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FD81AD0154FB4EB00983E72 /* DFGDominators.h */; };
0FD82E2114172CE300179C94 /* DFGCapabilities.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FD82E1E14172C2F00179C94 /* DFGCapabilities.cpp */; };
0FD82E39141AB14D00179C94 /* CompactJITCodeMap.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FD82E37141AB14200179C94 /* CompactJITCodeMap.h */; settings = {ATTRIBUTES = (Private, ); }; };
A730B6121250068F009D25B1 /* StrictEvalActivation.h in Headers */ = {isa = PBXBuildFile; fileRef = A730B6101250068F009D25B1 /* StrictEvalActivation.h */; };
A730B6131250068F009D25B1 /* StrictEvalActivation.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A730B6111250068F009D25B1 /* StrictEvalActivation.cpp */; };
A731B25A130093880040A7FA /* Foundation.framework in Frameworks */ = {isa = PBXBuildFile; fileRef = 51F0EB6105C86C6B00E6DF1B /* Foundation.framework */; };
- A737810C1799EA2E00817533 /* DFGAnalysis.h in Headers */ = {isa = PBXBuildFile; fileRef = A73781091799EA2E00817533 /* DFGAnalysis.h */; };
A737810D1799EA2E00817533 /* DFGNaturalLoops.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A737810A1799EA2E00817533 /* DFGNaturalLoops.cpp */; };
A737810E1799EA2E00817533 /* DFGNaturalLoops.h in Headers */ = {isa = PBXBuildFile; fileRef = A737810B1799EA2E00817533 /* DFGNaturalLoops.h */; };
A7386554118697B400540279 /* SpecializedThunkJIT.h in Headers */ = {isa = PBXBuildFile; fileRef = A7386551118697B400540279 /* SpecializedThunkJIT.h */; };
0FC3CCF619ADA410006AC72A /* DFGBlockMapInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBlockMapInlines.h; path = dfg/DFGBlockMapInlines.h; sourceTree = "<group>"; };
0FC3CCF719ADA410006AC72A /* DFGBlockSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBlockSet.h; path = dfg/DFGBlockSet.h; sourceTree = "<group>"; };
0FC3CCF919ADA410006AC72A /* DFGBlockWorklist.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBlockWorklist.h; path = dfg/DFGBlockWorklist.h; sourceTree = "<group>"; };
- 0FC3CCFA19ADA410006AC72A /* DFGNaiveDominators.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGNaiveDominators.cpp; path = dfg/DFGNaiveDominators.cpp; sourceTree = "<group>"; };
- 0FC3CCFB19ADA410006AC72A /* DFGNaiveDominators.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGNaiveDominators.h; path = dfg/DFGNaiveDominators.h; sourceTree = "<group>"; };
0FC712DC17CD8778008CC93C /* DeferredCompilationCallback.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = DeferredCompilationCallback.cpp; sourceTree = "<group>"; };
0FC712DD17CD8778008CC93C /* DeferredCompilationCallback.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = DeferredCompilationCallback.h; sourceTree = "<group>"; };
0FC712E017CD878F008CC93C /* JITToDFGDeferredCompilationCallback.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = JITToDFGDeferredCompilationCallback.cpp; sourceTree = "<group>"; };
0FD3E4071B618B6600C80E1E /* PropertyCondition.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = PropertyCondition.cpp; sourceTree = "<group>"; };
0FD3E4081B618B6600C80E1E /* PropertyCondition.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PropertyCondition.h; sourceTree = "<group>"; };
0FD5652216AB780A00197653 /* DFGBasicBlockInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBasicBlockInlines.h; path = dfg/DFGBasicBlockInlines.h; sourceTree = "<group>"; };
- 0FD81ACF154FB4EB00983E72 /* DFGDominators.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGDominators.cpp; path = dfg/DFGDominators.cpp; sourceTree = "<group>"; };
0FD81AD0154FB4EB00983E72 /* DFGDominators.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGDominators.h; path = dfg/DFGDominators.h; sourceTree = "<group>"; };
0FD82E1E14172C2F00179C94 /* DFGCapabilities.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGCapabilities.cpp; path = dfg/DFGCapabilities.cpp; sourceTree = "<group>"; };
0FD82E1F14172C2F00179C94 /* DFGCapabilities.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGCapabilities.h; path = dfg/DFGCapabilities.h; sourceTree = "<group>"; };
A7299DA417D12858005F5FF9 /* SetConstructor.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SetConstructor.h; sourceTree = "<group>"; };
A730B6101250068F009D25B1 /* StrictEvalActivation.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StrictEvalActivation.h; sourceTree = "<group>"; };
A730B6111250068F009D25B1 /* StrictEvalActivation.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = StrictEvalActivation.cpp; sourceTree = "<group>"; };
- A73781091799EA2E00817533 /* DFGAnalysis.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGAnalysis.h; path = dfg/DFGAnalysis.h; sourceTree = "<group>"; };
A737810A1799EA2E00817533 /* DFGNaturalLoops.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGNaturalLoops.cpp; path = dfg/DFGNaturalLoops.cpp; sourceTree = "<group>"; };
A737810B1799EA2E00817533 /* DFGNaturalLoops.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGNaturalLoops.h; path = dfg/DFGNaturalLoops.h; sourceTree = "<group>"; };
A7386551118697B400540279 /* SpecializedThunkJIT.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SpecializedThunkJIT.h; sourceTree = "<group>"; };
0F18D3CE1B55A6E0002C5C9F /* DFGAdaptiveStructureWatchpoint.h */,
0F66E16814DF3F1300B7B2E4 /* DFGAdjacencyList.h */,
0FB4B51916B62772003F696B /* DFGAllocator.h */,
- A73781091799EA2E00817533 /* DFGAnalysis.h */,
0F1E3A431534CBAD000F9456 /* DFGArgumentPosition.h */,
0F2DD80C1AB3D8BE00BBB8E8 /* DFGArgumentsEliminationPhase.cpp */,
0F2DD80D1AB3D8BE00BBB8E8 /* DFGArgumentsEliminationPhase.h */,
0FF427621591A1C9004CB9FF /* DFGDisassembler.h */,
0F5A1271192D9FDF008764A3 /* DFGDoesGC.cpp */,
0F5A1272192D9FDF008764A3 /* DFGDoesGC.h */,
- 0FD81ACF154FB4EB00983E72 /* DFGDominators.cpp */,
0FD81AD0154FB4EB00983E72 /* DFGDominators.h */,
0F1E3A441534CBAD000F9456 /* DFGDoubleFormatState.h */,
0FD3C82014115CF800FD81CB /* DFGDriver.cpp */,
0F8F14321ADF090100ED792C /* DFGMovHintRemovalPhase.h */,
0FF2CD591B61A4F8004955A8 /* DFGMultiGetByOffsetData.cpp */,
0FF2CD5A1B61A4F8004955A8 /* DFGMultiGetByOffsetData.h */,
- 0FC3CCFA19ADA410006AC72A /* DFGNaiveDominators.cpp */,
- 0FC3CCFB19ADA410006AC72A /* DFGNaiveDominators.h */,
A737810A1799EA2E00817533 /* DFGNaturalLoops.cpp */,
A737810B1799EA2E00817533 /* DFGNaturalLoops.h */,
0FB4B51E16B62772003F696B /* DFGNode.cpp */,
0F18D3D01B55A6E0002C5C9F /* DFGAdaptiveStructureWatchpoint.h in Headers */,
0F66E16B14DF3F1600B7B2E4 /* DFGAdjacencyList.h in Headers */,
0FFB921816D02EB20055A5DB /* DFGAllocator.h in Headers */,
- A737810C1799EA2E00817533 /* DFGAnalysis.h in Headers */,
0F1E3A461534CBAF000F9456 /* DFGArgumentPosition.h in Headers */,
0F2DD8121AB3D8BE00BBB8E8 /* DFGArgumentsEliminationPhase.h in Headers */,
0F2DD8141AB3D8BE00BBB8E8 /* DFGArgumentsUtilities.h in Headers */,
0FEC85141BDACDAC0080FF74 /* B3ControlValue.h in Headers */,
0F8F14361ADF090100ED792C /* DFGMovHintRemovalPhase.h in Headers */,
0FF2CD5C1B61A4F8004955A8 /* DFGMultiGetByOffsetData.h in Headers */,
- 0FC3CD0219ADA411006AC72A /* DFGNaiveDominators.h in Headers */,
A737810E1799EA2E00817533 /* DFGNaturalLoops.h in Headers */,
86ECA3EA132DEF1C002B2AD7 /* DFGNode.h in Headers */,
0FFB921B16D02F010055A5DB /* DFGNodeAllocator.h in Headers */,
C2981FD817BAEE4B00A3BC98 /* DFGDesiredWeakReferences.cpp in Sources */,
0FF427641591A1CC004CB9FF /* DFGDisassembler.cpp in Sources */,
0F5A1273192D9FDF008764A3 /* DFGDoesGC.cpp in Sources */,
- 0FD81AD2154FB4EE00983E72 /* DFGDominators.cpp in Sources */,
0FD3C82614115D4000FD81CB /* DFGDriver.cpp in Sources */,
0FF0F19E16B72A0B005DF95B /* DFGEdge.cpp in Sources */,
0F8F14331ADF090100ED792C /* DFGEpoch.cpp in Sources */,
0F2BDC4D1522818600CD8910 /* DFGMinifiedNode.cpp in Sources */,
0F8F14351ADF090100ED792C /* DFGMovHintRemovalPhase.cpp in Sources */,
0FF2CD5B1B61A4F8004955A8 /* DFGMultiGetByOffsetData.cpp in Sources */,
- 0FC3CD0119ADA411006AC72A /* DFGNaiveDominators.cpp in Sources */,
A737810D1799EA2E00817533 /* DFGNaturalLoops.cpp in Sources */,
0FF0F19C16B72A03005DF95B /* DFGNode.cpp in Sources */,
0FA581BA150E952C00B9A2D9 /* DFGNodeFlags.cpp in Sources */,
+++ /dev/null
-/*
- * Copyright (C) 2013, 2014 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.
- */
-
-#ifndef DFGAnalysis_h
-#define DFGAnalysis_h
-
-#if ENABLE(DFG_JIT)
-
-namespace JSC { namespace DFG {
-
-class Graph;
-
-// Use this as a mixin for DFG analyses. The analysis itself implements a public
-// compute(Graph&) method. Clients call computeIfNecessary() when they want
-// results.
-
-template<typename T>
-class Analysis {
-public:
- Analysis()
- : m_valid(false)
- {
- }
-
- void invalidate()
- {
- m_valid = false;
- }
-
- void computeIfNecessary(Graph& graph)
- {
- if (m_valid)
- return;
- // It's best to run dependent analyses from this method.
- static_cast<T*>(this)->computeDependencies(graph);
- // Set to true early, since the analysis may choose to call its own methods in
- // compute() and it may want to ASSERT() validity in those methods.
- m_valid = true;
- static_cast<T*>(this)->compute(graph);
- }
-
- bool isValid() const { return m_valid; }
-
- // Override this to compute any dependent analyses. See
- // NaturalLoops::computeDependencies(Graph&) for an example. This isn't strictly necessary but
- // it makes debug dumps in cases of error work a bit better because this analysis wouldn't yet
- // be pretending to be valid.
- void computeDependencies(Graph&) { }
-
-private:
- bool m_valid;
-};
-
-} } // namespace JSC::DFG
-
-#endif // ENABLE(DFG_JIT)
-
-#endif // DFGAnalysis_h
-
/*
- * Copyright (C) 2011, 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2015 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
-#ifndef DFGNaiveDominators_h
-#define DFGNaiveDominators_h
+#ifndef DFGCFG_h
+#define DFGCFG_h
#if ENABLE(DFG_JIT)
#include "DFGBasicBlock.h"
-#include "DFGCommon.h"
-#include <wtf/FastBitVector.h>
+#include "DFGBlockMapInlines.h"
+#include "DFGBlockSet.h"
+#include "DFGGraph.h"
namespace JSC { namespace DFG {
-class Graph;
-
-// This class is only used for validating the real dominators implementation.
-
-class NaiveDominators {
+class CFG {
public:
- NaiveDominators();
- ~NaiveDominators();
-
- void compute(Graph&);
-
- bool dominates(BlockIndex from, BlockIndex to) const
+ typedef BasicBlock* Node;
+ typedef BlockSet Set;
+ template<typename T> using Map = BlockMap<T>;
+ typedef BlockList List;
+
+ CFG(Graph& graph)
+ : m_graph(graph)
{
- return m_results[to].get(from);
}
-
- bool dominates(BasicBlock* from, BasicBlock* to) const
+
+ Node root() { return m_graph.block(0); }
+
+ template<typename T>
+ Map<T> newMap() { return BlockMap<T>(m_graph); }
+
+ DFG::Node::SuccessorsIterable successors(Node node) { return node->successors(); }
+ PredecessorList& predecessors(Node node) { return node->predecessors; }
+
+ unsigned index(Node node) const { return node->index; }
+ Node node(unsigned index) const { return m_graph.block(index); }
+ unsigned numNodes() const { return m_graph.numBlocks(); }
+
+ PointerDump<BasicBlock> dump(Node node) const { return pointerDump(node); }
+
+ void dump(PrintStream& out) const
{
- return dominates(from->index, to->index);
+ m_graph.dump(out);
}
-
- void dump(Graph&, PrintStream&) const;
-
+
private:
- bool pruneDominators(Graph&, BlockIndex);
-
- Vector<FastBitVector> m_results; // For each block, the bitvector of blocks that dominate it.
- FastBitVector m_scratch; // A temporary bitvector with bit for each block. We recycle this to save new/deletes.
+ Graph& m_graph;
};
} } // namespace JSC::DFG
#endif // ENABLE(DFG_JIT)
-#endif // DFGNaiveDominators_h
+#endif // DFGCFG_h
+
#include "DFGBlockMapInlines.h"
#include "DFGClobberSet.h"
#include "DFGClobberize.h"
+#include "DFGDominators.h"
#include "DFGEdgeUsesStructure.h"
#include "DFGGraph.h"
#include "DFGPhase.h"
ASSERT(m_graph.m_form == SSA);
m_graph.initializeNodeOwners();
- m_graph.m_dominators.computeIfNecessary(m_graph);
+ m_graph.ensureDominators();
m_preOrder = m_graph.blocksInPreOrder();
for (unsigned i = result.iterator->value.size(); i--;) {
Node* candidate = result.iterator->value[i];
- if (m_graph.m_dominators.dominates(candidate->owner, m_block)) {
+ if (m_graph.m_dominators->dominates(candidate->owner, m_block)) {
m_node->replaceWith(candidate);
m_changed = true;
return;
// We require strict domination because this would only see things in our own block if
// they came *after* our position in the block. Clearly, while our block dominates
// itself, the things in the block after us don't dominate us.
- if (m_graph.m_dominators.strictlyDominates(block, m_block)) {
+ if (m_graph.m_dominators->strictlyDominates(block, m_block)) {
if (verbose)
dataLog(" It strictly dominates.\n");
DFG_ASSERT(m_graph, m_node, data.didVisit);
if (!result.isNewEntry) {
for (unsigned i = result.iterator->value.size(); i--;) {
Node* candidate = result.iterator->value[i];
- if (m_graph.m_dominators.dominates(candidate->owner, m_block)) {
+ if (m_graph.m_dominators->dominates(candidate->owner, m_block)) {
ASSERT(candidate);
match->replaceWith(candidate);
match.setNode(candidate);
dumpHeader(out, linkBuffer);
append(result, out, previousOrigin);
- m_graph.m_dominators.computeIfNecessary(m_graph);
- m_graph.m_naturalLoops.computeIfNecessary(m_graph);
+ m_graph.ensureDominators();
+ m_graph.ensureNaturalLoops();
const char* prefix = " ";
const char* disassemblyPrefix = " ";
+++ /dev/null
-/*
- * Copyright (C) 2011, 2014, 2015 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 "DFGDominators.h"
-
-#if ENABLE(DFG_JIT)
-
-#include "DFGBlockMapInlines.h"
-#include "DFGBlockWorklist.h"
-#include "DFGGraph.h"
-#include "DFGNaiveDominators.h"
-#include "JSCInlines.h"
-
-namespace JSC { namespace DFG {
-
-Dominators::Dominators()
-{
-}
-
-Dominators::~Dominators()
-{
-}
-
-namespace {
-
-// This implements Lengauer and Tarjan's "A Fast Algorithm for Finding Dominators in a Flowgraph"
-// (TOPLAS 1979). It uses the "simple" implementation of LINK and EVAL, which yields an O(n log n)
-// solution. The full paper is linked below; this code attempts to closely follow the algorithm as
-// it is presented in the paper; in particular sections 3 and 4 as well as appendix B.
-// https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/a%20fast%20algorithm%20for%20finding.pdf
-//
-// This code is very subtle. The Lengauer-Tarjan algorithm is incredibly deep to begin with. The
-// goal of this code is to follow the code in the paper, however our implementation must deviate
-// from the paper when it comes to recursion. The authors had used recursion to implement DFS, and
-// also to implement the "simple" EVAL. We convert both of those into worklist-based solutions.
-// Finally, once the algorithm gives us immediate dominators, we implement dominance tests by
-// walking the dominator tree and computing pre and post numbers. We then use the range inclusion
-// check trick that was first discovered by Paul F. Dietz in 1982 in "Maintaining order in a linked
-// list" (see http://dl.acm.org/citation.cfm?id=802184).
-
-class LengauerTarjan {
-public:
- LengauerTarjan(Graph& graph)
- : m_graph(graph)
- , m_data(graph)
- {
- for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
- BasicBlock* block = m_graph.block(blockIndex);
- if (!block)
- continue;
- m_data[block].label = block;
- }
- }
-
- void compute()
- {
- computeDepthFirstPreNumbering(); // Step 1.
- computeSemiDominatorsAndImplicitImmediateDominators(); // Steps 2 and 3.
- computeExplicitImmediateDominators(); // Step 4.
- }
-
- BasicBlock* immediateDominator(BasicBlock* block)
- {
- return m_data[block].dom;
- }
-
-private:
- void computeDepthFirstPreNumbering()
- {
- // Use a block worklist that also tracks the index inside the successor list. This is
- // necessary for ensuring that we don't attempt to visit a successor until the previous
- // successors that we had visited are fully processed. This ends up being revealed in the
- // output of this method because the first time we see an edge to a block, we set the
- // block's parent. So, if we have:
- //
- // A -> B
- // A -> C
- // B -> C
- //
- // And we're processing A, then we want to ensure that if we see A->B first (and hence set
- // B's prenumber before we set C's) then we also end up setting C's parent to B by virtue
- // of not noticing A->C until we're done processing B.
-
- ExtendedBlockWorklist<unsigned> worklist;
- worklist.push(m_graph.block(0), 0);
-
- while (BlockWith<unsigned> item = worklist.pop()) {
- BasicBlock* block = item.node;
- unsigned successorIndex = item.data;
-
- // We initially push with successorIndex = 0 regardless of whether or not we have any
- // successors. This is so that we can assign our prenumber. Subsequently we get pushed
- // with higher successorIndex values, but only if they are in range.
- ASSERT(!successorIndex || successorIndex < block->numSuccessors());
-
- if (!successorIndex) {
- m_data[block].semiNumber = m_blockByPreNumber.size();
- m_blockByPreNumber.append(block);
- }
-
- if (successorIndex < block->numSuccessors()) {
- unsigned nextSuccessorIndex = successorIndex + 1;
- if (nextSuccessorIndex < block->numSuccessors())
- worklist.forcePush(block, nextSuccessorIndex);
-
- BasicBlock* successorBlock = block->successor(successorIndex);
- if (worklist.push(successorBlock, 0))
- m_data[successorBlock].parent = block;
- }
- }
- }
-
- void computeSemiDominatorsAndImplicitImmediateDominators()
- {
- for (unsigned currentPreNumber = m_blockByPreNumber.size(); currentPreNumber-- > 1;) {
- BasicBlock* block = m_blockByPreNumber[currentPreNumber];
- BlockData& blockData = m_data[block];
-
- // Step 2:
- for (BasicBlock* predecessorBlock : block->predecessors) {
- BasicBlock* intermediateBlock = eval(predecessorBlock);
- blockData.semiNumber = std::min(
- m_data[intermediateBlock].semiNumber, blockData.semiNumber);
- }
- unsigned bucketPreNumber = blockData.semiNumber;
- ASSERT(bucketPreNumber <= currentPreNumber);
- m_data[m_blockByPreNumber[bucketPreNumber]].bucket.append(block);
- link(blockData.parent, block);
-
- // Step 3:
- for (BasicBlock* semiDominee : m_data[blockData.parent].bucket) {
- BasicBlock* possibleDominator = eval(semiDominee);
- BlockData& semiDomineeData = m_data[semiDominee];
- ASSERT(m_blockByPreNumber[semiDomineeData.semiNumber] == blockData.parent);
- BlockData& possibleDominatorData = m_data[possibleDominator];
- if (possibleDominatorData.semiNumber < semiDomineeData.semiNumber)
- semiDomineeData.dom = possibleDominator;
- else
- semiDomineeData.dom = blockData.parent;
- }
- m_data[blockData.parent].bucket.clear();
- }
- }
-
- void computeExplicitImmediateDominators()
- {
- for (unsigned currentPreNumber = 1; currentPreNumber < m_blockByPreNumber.size(); ++currentPreNumber) {
- BasicBlock* block = m_blockByPreNumber[currentPreNumber];
- BlockData& blockData = m_data[block];
-
- if (blockData.dom != m_blockByPreNumber[blockData.semiNumber])
- blockData.dom = m_data[blockData.dom].dom;
- }
- }
-
- void link(BasicBlock* from, BasicBlock* to)
- {
- m_data[to].ancestor = from;
- }
-
- BasicBlock* eval(BasicBlock* block)
- {
- if (!m_data[block].ancestor)
- return block;
-
- compress(block);
- return m_data[block].label;
- }
-
- void compress(BasicBlock* initialBlock)
- {
- // This was meant to be a recursive function, but we don't like recursion because we don't
- // want to blow the stack. The original function will call compress() recursively on the
- // ancestor of anything that has an ancestor. So, we populate our worklist with the
- // recursive ancestors of initialBlock. Then we process the list starting from the block
- // that is furthest up the ancestor chain.
-
- BasicBlock* ancestor = m_data[initialBlock].ancestor;
- ASSERT(ancestor);
- if (!m_data[ancestor].ancestor)
- return;
-
- Vector<BasicBlock*, 16> stack;
- for (BasicBlock* block = initialBlock; block; block = m_data[block].ancestor)
- stack.append(block);
-
- // We only care about blocks that have an ancestor that has an ancestor. The last two
- // elements in the stack won't satisfy this property.
- ASSERT(stack.size() >= 2);
- ASSERT(!m_data[stack[stack.size() - 1]].ancestor);
- ASSERT(!m_data[m_data[stack[stack.size() - 2]].ancestor].ancestor);
-
- for (unsigned i = stack.size() - 2; i--;) {
- BasicBlock* block = stack[i];
- BasicBlock*& labelOfBlock = m_data[block].label;
- BasicBlock*& ancestorOfBlock = m_data[block].ancestor;
- ASSERT(ancestorOfBlock);
- ASSERT(m_data[ancestorOfBlock].ancestor);
-
- BasicBlock* labelOfAncestorOfBlock = m_data[ancestorOfBlock].label;
-
- if (m_data[labelOfAncestorOfBlock].semiNumber < m_data[labelOfBlock].semiNumber)
- labelOfBlock = labelOfAncestorOfBlock;
- ancestorOfBlock = m_data[ancestorOfBlock].ancestor;
- }
- }
-
- struct BlockData {
- BlockData()
- : parent(nullptr)
- , preNumber(UINT_MAX)
- , semiNumber(UINT_MAX)
- , ancestor(nullptr)
- , label(nullptr)
- , dom(nullptr)
- {
- }
-
- BasicBlock* parent;
- unsigned preNumber;
- unsigned semiNumber;
- BasicBlock* ancestor;
- BasicBlock* label;
- Vector<BasicBlock*> bucket;
- BasicBlock* dom;
- };
-
- Graph& m_graph;
- BlockMap<BlockData> m_data;
- Vector<BasicBlock*> m_blockByPreNumber;
-};
-
-struct ValidationContext {
- ValidationContext(Graph& graph, Dominators& dominators)
- : graph(graph)
- , dominators(dominators)
- {
- }
-
- void reportError(BasicBlock* from, BasicBlock* to, const char* message)
- {
- Error error;
- error.from = from;
- error.to = to;
- error.message = message;
- errors.append(error);
- }
-
- void handleErrors()
- {
- if (errors.isEmpty())
- return;
-
- startCrashing();
- dataLog("DFG DOMINATOR VALIDATION FAILED:\n");
- dataLog("\n");
- dataLog("For block domination relationships:\n");
- for (unsigned i = 0; i < errors.size(); ++i) {
- dataLog(
- " ", pointerDump(errors[i].from), " -> ", pointerDump(errors[i].to),
- " (", errors[i].message, ")\n");
- }
- dataLog("\n");
- dataLog("Control flow graph:\n");
- for (BlockIndex blockIndex = 0; blockIndex < graph.numBlocks(); ++blockIndex) {
- BasicBlock* block = graph.block(blockIndex);
- if (!block)
- continue;
- dataLog(" Block #", blockIndex, ": successors = [");
- CommaPrinter comma;
- for (unsigned i = 0; i < block->numSuccessors(); ++i)
- dataLog(comma, *block->successor(i));
- dataLog("], predecessors = [");
- comma = CommaPrinter();
- for (unsigned i = 0; i < block->predecessors.size(); ++i)
- dataLog(comma, *block->predecessors[i]);
- dataLog("]\n");
- }
- dataLog("\n");
- dataLog("Lengauer-Tarjan Dominators:\n");
- dataLog(dominators);
- dataLog("\n");
- dataLog("Naive Dominators:\n");
- naiveDominators.dump(graph, WTF::dataFile());
- dataLog("\n");
- dataLog("Graph at time of failure:\n");
- graph.dump();
- dataLog("\n");
- dataLog("DFG DOMINATOR VALIDATION FAILIED!\n");
- CRASH();
- }
-
- Graph& graph;
- Dominators& dominators;
- NaiveDominators naiveDominators;
-
- struct Error {
- BasicBlock* from;
- BasicBlock* to;
- const char* message;
- };
-
- Vector<Error> errors;
-};
-
-} // anonymous namespace
-
-void Dominators::compute(Graph& graph)
-{
- LengauerTarjan lengauerTarjan(graph);
- lengauerTarjan.compute();
-
- m_data = BlockMap<BlockData>(graph);
-
- // From here we want to build a spanning tree with both upward and downward links and we want
- // to do a search over this tree to compute pre and post numbers that can be used for dominance
- // tests.
-
- for (BlockIndex blockIndex = graph.numBlocks(); blockIndex--;) {
- BasicBlock* block = graph.block(blockIndex);
- if (!block)
- continue;
-
- BasicBlock* idomBlock = lengauerTarjan.immediateDominator(block);
- m_data[block].idomParent = idomBlock;
- if (idomBlock)
- m_data[idomBlock].idomKids.append(block);
- }
-
- unsigned nextPreNumber = 0;
- unsigned nextPostNumber = 0;
-
- // Plain stack-based worklist because we are guaranteed to see each block exactly once anyway.
- Vector<BlockWithOrder> worklist;
- worklist.append(BlockWithOrder(graph.block(0), VisitOrder::Pre));
- while (!worklist.isEmpty()) {
- BlockWithOrder item = worklist.takeLast();
- switch (item.order) {
- case VisitOrder::Pre:
- m_data[item.node].preNumber = nextPreNumber++;
- worklist.append(BlockWithOrder(item.node, VisitOrder::Post));
- for (BasicBlock* kid : m_data[item.node].idomKids)
- worklist.append(BlockWithOrder(kid, VisitOrder::Pre));
- break;
- case VisitOrder::Post:
- m_data[item.node].postNumber = nextPostNumber++;
- break;
- }
- }
-
- if (validationEnabled()) {
- // Check our dominator calculation:
- // 1) Check that our range-based ancestry test is the same as a naive ancestry test.
- // 2) Check that our notion of who dominates whom is identical to a naive (not
- // Lengauer-Tarjan) dominator calculation.
-
- ValidationContext context(graph, *this);
- context.naiveDominators.compute(graph);
-
- for (BlockIndex fromBlockIndex = graph.numBlocks(); fromBlockIndex--;) {
- BasicBlock* fromBlock = graph.block(fromBlockIndex);
- if (!fromBlock || m_data[fromBlock].preNumber == UINT_MAX)
- continue;
- for (BlockIndex toBlockIndex = graph.numBlocks(); toBlockIndex--;) {
- BasicBlock* toBlock = graph.block(toBlockIndex);
- if (!toBlock || m_data[toBlock].preNumber == UINT_MAX)
- continue;
-
- if (dominates(fromBlock, toBlock) != naiveDominates(fromBlock, toBlock))
- context.reportError(fromBlock, toBlock, "Range-based domination check is broken");
- if (dominates(fromBlock, toBlock) != context.naiveDominators.dominates(fromBlock, toBlock))
- context.reportError(fromBlock, toBlock, "Lengauer-Tarjan domination is broken");
- }
- }
-
- context.handleErrors();
- }
-}
-
-BlockSet Dominators::strictDominatorsOf(BasicBlock* to) const
-{
- BlockSet result;
- forAllStrictDominatorsOf(to, BlockAdder(result));
- return result;
-}
-
-BlockSet Dominators::dominatorsOf(BasicBlock* to) const
-{
- BlockSet result;
- forAllDominatorsOf(to, BlockAdder(result));
- return result;
-}
-
-BlockSet Dominators::blocksStrictlyDominatedBy(BasicBlock* from) const
-{
- BlockSet result;
- forAllBlocksStrictlyDominatedBy(from, BlockAdder(result));
- return result;
-}
-
-BlockSet Dominators::blocksDominatedBy(BasicBlock* from) const
-{
- BlockSet result;
- forAllBlocksDominatedBy(from, BlockAdder(result));
- return result;
-}
-
-BlockSet Dominators::dominanceFrontierOf(BasicBlock* from) const
-{
- BlockSet result;
- forAllBlocksInDominanceFrontierOfImpl(from, BlockAdder(result));
- return result;
-}
-
-BlockSet Dominators::iteratedDominanceFrontierOf(const BlockList& from) const
-{
- BlockSet result;
- forAllBlocksInIteratedDominanceFrontierOfImpl(from, BlockAdder(result));
- return result;
-}
-
-bool Dominators::naiveDominates(BasicBlock* from, BasicBlock* to) const
-{
- for (BasicBlock* block = to; block; block = m_data[block].idomParent) {
- if (block == from)
- return true;
- }
- return false;
-}
-
-void Dominators::dump(PrintStream& out) const
-{
- if (!isValid()) {
- out.print(" Not Valid.\n");
- return;
- }
-
- for (BlockIndex blockIndex = 0; blockIndex < m_data.size(); ++blockIndex) {
- if (m_data[blockIndex].preNumber == UINT_MAX)
- continue;
-
- out.print(" Block #", blockIndex, ": idom = ", pointerDump(m_data[blockIndex].idomParent), ", idomKids = [");
- CommaPrinter comma;
- for (unsigned i = 0; i < m_data[blockIndex].idomKids.size(); ++i)
- out.print(comma, *m_data[blockIndex].idomKids[i]);
- out.print("], pre/post = ", m_data[blockIndex].preNumber, "/", m_data[blockIndex].postNumber, "\n");
- }
-}
-
-} } // namespace JSC::DFG
-
-#endif // ENABLE(DFG_JIT)
-
#if ENABLE(DFG_JIT)
-#include "DFGAnalysis.h"
#include "DFGBasicBlock.h"
#include "DFGBlockMap.h"
#include "DFGBlockSet.h"
+#include "DFGCFG.h"
#include "DFGCommon.h"
+#include "DFGGraph.h"
+#include <wtf/Dominators.h>
+#include <wtf/FastMalloc.h>
+#include <wtf/Noncopyable.h>
namespace JSC { namespace DFG {
-class Graph;
-
-class Dominators : public Analysis<Dominators> {
+class Dominators : public WTF::Dominators<CFG> {
+ WTF_MAKE_NONCOPYABLE(Dominators);
+ WTF_MAKE_FAST_ALLOCATED;
public:
- Dominators();
- ~Dominators();
-
- void compute(Graph&);
-
- bool strictlyDominates(BasicBlock* from, BasicBlock* to) const
- {
- ASSERT(isValid());
- return m_data[to].preNumber > m_data[from].preNumber
- && m_data[to].postNumber < m_data[from].postNumber;
- }
-
- bool dominates(BasicBlock* from, BasicBlock* to) const
- {
- return from == to || strictlyDominates(from, to);
- }
-
- BasicBlock* immediateDominatorOf(BasicBlock* block) const
- {
- return m_data[block].idomParent;
- }
-
- template<typename Functor>
- void forAllStrictDominatorsOf(BasicBlock* to, const Functor& functor) const
- {
- for (BasicBlock* block = m_data[to].idomParent; block; block = m_data[block].idomParent)
- functor(block);
- }
-
- template<typename Functor>
- void forAllDominatorsOf(BasicBlock* to, const Functor& functor) const
- {
- for (BasicBlock* block = to; block; block = m_data[block].idomParent)
- functor(block);
- }
-
- template<typename Functor>
- void forAllBlocksStrictlyDominatedBy(BasicBlock* from, const Functor& functor) const
- {
- Vector<BasicBlock*, 16> worklist;
- worklist.appendVector(m_data[from].idomKids);
- while (!worklist.isEmpty()) {
- BasicBlock* block = worklist.takeLast();
- functor(block);
- worklist.appendVector(m_data[block].idomKids);
- }
- }
-
- template<typename Functor>
- void forAllBlocksDominatedBy(BasicBlock* from, const Functor& functor) const
- {
- Vector<BasicBlock*, 16> worklist;
- worklist.append(from);
- while (!worklist.isEmpty()) {
- BasicBlock* block = worklist.takeLast();
- functor(block);
- worklist.appendVector(m_data[block].idomKids);
- }
- }
-
- BlockSet strictDominatorsOf(BasicBlock* to) const;
- BlockSet dominatorsOf(BasicBlock* to) const;
- BlockSet blocksStrictlyDominatedBy(BasicBlock* from) const;
- BlockSet blocksDominatedBy(BasicBlock* from) const;
-
- template<typename Functor>
- void forAllBlocksInDominanceFrontierOf(
- BasicBlock* from, const Functor& functor) const
- {
- BlockSet set;
- forAllBlocksInDominanceFrontierOfImpl(
- from,
- [&] (BasicBlock* block) {
- if (set.add(block))
- functor(block);
- });
- }
-
- BlockSet dominanceFrontierOf(BasicBlock* from) const;
-
- template<typename Functor>
- void forAllBlocksInIteratedDominanceFrontierOf(
- const BlockList& from, const Functor& functor)
- {
- forAllBlocksInPrunedIteratedDominanceFrontierOf(
- from,
- [&] (BasicBlock* block) -> bool {
- functor(block);
- return true;
- });
- }
-
- // This is a close relative of forAllBlocksInIteratedDominanceFrontierOf(), which allows the
- // given functor to return false to indicate that we don't wish to consider the given block.
- // Useful for computing pruned SSA form.
- template<typename Functor>
- void forAllBlocksInPrunedIteratedDominanceFrontierOf(
- const BlockList& from, const Functor& functor)
- {
- BlockSet set;
- forAllBlocksInIteratedDominanceFrontierOfImpl(
- from,
- [&] (BasicBlock* block) -> bool {
- if (!set.add(block))
- return false;
- return functor(block);
- });
- }
-
- BlockSet iteratedDominanceFrontierOf(const BlockList& from) const;
-
- void dump(PrintStream&) const;
-
-private:
- bool naiveDominates(BasicBlock* from, BasicBlock* to) const;
-
- template<typename Functor>
- void forAllBlocksInDominanceFrontierOfImpl(
- BasicBlock* from, const Functor& functor) const
- {
- // Paraphrasing from http://en.wikipedia.org/wiki/Dominator_(graph_theory):
- // "The dominance frontier of a block 'from' is the set of all blocks 'to' such that
- // 'from' dominates an immediate predecessor of 'to', but 'from' does not strictly
- // dominate 'to'."
- //
- // A useful corner case to remember: a block may be in its own dominance frontier if it has
- // a loop edge to itself, since it dominates itself and so it dominates its own immediate
- // predecessor, and a block never strictly dominates itself.
-
- forAllBlocksDominatedBy(
- from,
- [&] (BasicBlock* block) {
- for (unsigned successorIndex = block->numSuccessors(); successorIndex--;) {
- BasicBlock* to = block->successor(successorIndex);
- if (!strictlyDominates(from, to))
- functor(to);
- }
- });
- }
-
- template<typename Functor>
- void forAllBlocksInIteratedDominanceFrontierOfImpl(
- const BlockList& from, const Functor& functor) const
+ Dominators(Graph& graph)
+ : WTF::Dominators<CFG>(*graph.m_cfg, validationEnabled())
{
- BlockList worklist = from;
- while (!worklist.isEmpty()) {
- BasicBlock* block = worklist.takeLast();
- forAllBlocksInDominanceFrontierOfImpl(
- block,
- [&] (BasicBlock* otherBlock) {
- if (functor(otherBlock))
- worklist.append(otherBlock);
- });
- }
}
-
- struct BlockData {
- BlockData()
- : idomParent(nullptr)
- , preNumber(UINT_MAX)
- , postNumber(UINT_MAX)
- {
- }
-
- Vector<BasicBlock*> idomKids;
- BasicBlock* idomParent;
-
- unsigned preNumber;
- unsigned postNumber;
- };
-
- BlockMap<BlockData> m_data;
};
} } // namespace JSC::DFG
#if ENABLE(DFG_JIT)
+#include "DFGDominators.h"
#include "DFGGraph.h"
namespace JSC { namespace DFG {
void operator()(Node*, Edge edge)
{
- bool result = m_graph.m_dominators.dominates(edge.node()->owner, m_block);
+ bool result = m_graph.m_dominators->dominates(edge.node()->owner, m_block);
if (verbose) {
dataLog(
"Checking if ", edge, " in ", *edge.node()->owner,
#include "DFGBlockWorklist.h"
#include "DFGClobberSet.h"
#include "DFGClobbersExitState.h"
+#include "DFGCFG.h"
+#include "DFGDominators.h"
#include "DFGJITCode.h"
#include "DFGMayExit.h"
+#include "DFGNaturalLoops.h"
+#include "DFGPrePostNumbering.h"
#include "DFGVariableAccessDataDump.h"
#include "FullBytecodeLiveness.h"
#include "FunctionExecutableDump.h"
, m_codeBlock(m_plan.codeBlock)
, m_profiledBlock(m_codeBlock->alternative())
, m_allocator(longLivedState.m_allocator)
+ , m_cfg(std::make_unique<CFG>(*this))
, m_nextMachineLocal(0)
, m_fixpointState(BeforeFixpoint)
, m_structureRegistrationState(HaveNotStartedRegistering)
if (block->terminal()) {
for (BasicBlock* successor : block->successors()) {
out.print(" ", *successor);
- if (m_prePostNumbering.isValid())
- out.print(" (", m_prePostNumbering.edgeKind(block, successor), ")");
+ if (m_prePostNumbering)
+ out.print(" (", m_prePostNumbering->edgeKind(block, successor), ")");
}
} else
out.print(" <invalid>");
out.print("\n");
- if (m_dominators.isValid() && terminalsAreValid()) {
- out.print(prefix, " Dominated by: ", m_dominators.dominatorsOf(block), "\n");
- out.print(prefix, " Dominates: ", m_dominators.blocksDominatedBy(block), "\n");
- out.print(prefix, " Dominance Frontier: ", m_dominators.dominanceFrontierOf(block), "\n");
- out.print(prefix, " Iterated Dominance Frontier: ", m_dominators.iteratedDominanceFrontierOf(BlockList(1, block)), "\n");
+ if (m_dominators && terminalsAreValid()) {
+ out.print(prefix, " Dominated by: ", m_dominators->dominatorsOf(block), "\n");
+ out.print(prefix, " Dominates: ", m_dominators->blocksDominatedBy(block), "\n");
+ out.print(prefix, " Dominance Frontier: ", m_dominators->dominanceFrontierOf(block), "\n");
+ out.print(prefix, " Iterated Dominance Frontier: ", m_dominators->iteratedDominanceFrontierOf(BlockList(1, block)), "\n");
}
- if (m_prePostNumbering.isValid())
- out.print(prefix, " Pre/Post Numbering: ", m_prePostNumbering.preNumber(block), "/", m_prePostNumbering.postNumber(block), "\n");
- if (m_naturalLoops.isValid()) {
- if (const NaturalLoop* loop = m_naturalLoops.headerOf(block)) {
+ if (m_prePostNumbering)
+ out.print(prefix, " Pre/Post Numbering: ", m_prePostNumbering->preNumber(block), "/", m_prePostNumbering->postNumber(block), "\n");
+ if (m_naturalLoops) {
+ if (const NaturalLoop* loop = m_naturalLoops->headerOf(block)) {
out.print(prefix, " Loop header, contains:");
Vector<BlockIndex> sortedBlockList;
for (unsigned i = 0; i < loop->size(); ++i)
}
Vector<const NaturalLoop*> containingLoops =
- m_naturalLoops.loopsOf(block);
+ m_naturalLoops->loopsOf(block);
if (!containingLoops.isEmpty()) {
out.print(prefix, " Containing loop headers:");
for (unsigned i = 0; i < containingLoops.size(); ++i)
void Graph::invalidateCFG()
{
- m_dominators.invalidate();
- m_naturalLoops.invalidate();
- m_prePostNumbering.invalidate();
+ m_dominators = nullptr;
+ m_naturalLoops = nullptr;
+ m_prePostNumbering = nullptr;
}
void Graph::substituteGetLocal(BasicBlock& block, unsigned startIndexInBlock, VariableAccessData* variableAccessData, Node* newGetLocal)
crash(*this, toCString("While handling block ", pointerDump(block), "\n\n"), file, line, function, assertion);
}
+void Graph::ensureDominators()
+{
+ if (!m_dominators)
+ m_dominators = std::make_unique<Dominators>(*this);
+}
+
+void Graph::ensurePrePostNumbering()
+{
+ if (!m_prePostNumbering)
+ m_prePostNumbering = std::make_unique<PrePostNumbering>(*this);
+}
+
+void Graph::ensureNaturalLoops()
+{
+ ensureDominators();
+ if (!m_naturalLoops)
+ m_naturalLoops = std::make_unique<NaturalLoops>(*this);
+}
+
ValueProfile* Graph::valueProfileFor(Node* node)
{
if (!node)
#include "CodeBlock.h"
#include "DFGArgumentPosition.h"
#include "DFGBasicBlock.h"
-#include "DFGDominators.h"
#include "DFGFrozenValue.h"
#include "DFGLongLivedState.h"
-#include "DFGNaturalLoops.h"
#include "DFGNode.h"
#include "DFGNodeAllocator.h"
#include "DFGPlan.h"
-#include "DFGPrePostNumbering.h"
#include "DFGPropertyTypeKey.h"
#include "DFGScannable.h"
#include "FullBytecodeLiveness.h"
namespace DFG {
+class CFG;
+class Dominators;
+class NaturalLoops;
+class PrePostNumbering;
+
#define DFG_NODE_DO_TO_CHILDREN(graph, node, thingToDo) do { \
Node* _node = (node); \
if (_node->flags() & NodeHasVarArgs) { \
bool hasDebuggerEnabled() const { return m_hasDebuggerEnabled; }
+ void ensureDominators();
+ void ensurePrePostNumbering();
+ void ensureNaturalLoops();
+
VM& m_vm;
Plan& m_plan;
CodeBlock* m_codeBlock;
HashMap<CodeBlock*, std::unique_ptr<BytecodeKills>> m_bytecodeKills;
HashSet<std::pair<JSObject*, PropertyOffset>> m_safeToLoad;
HashMap<PropertyTypeKey, InferredType::Descriptor> m_inferredTypes;
- Dominators m_dominators;
- PrePostNumbering m_prePostNumbering;
- NaturalLoops m_naturalLoops;
+ std::unique_ptr<Dominators> m_dominators;
+ std::unique_ptr<PrePostNumbering> m_prePostNumbering;
+ std::unique_ptr<NaturalLoops> m_naturalLoops;
+ std::unique_ptr<CFG> m_cfg;
unsigned m_localVars;
unsigned m_nextMachineLocal;
unsigned m_parameterSlots;
#if ENABLE(DFG_JIT)
#include "DFGBlockMapInlines.h"
+#include "DFGBlockSet.h"
#include "DFGGraph.h"
#include "DFGInsertionSet.h"
#include "DFGPhase.h"
#include "DFGEdgeDominates.h"
#include "DFGGraph.h"
#include "DFGInsertionSet.h"
+#include "DFGNaturalLoops.h"
#include "DFGPhase.h"
#include "DFGSafeToExecute.h"
#include "JSCInlines.h"
{
DFG_ASSERT(m_graph, nullptr, m_graph.m_form == SSA);
- m_graph.m_dominators.computeIfNecessary(m_graph);
- m_graph.m_naturalLoops.computeIfNecessary(m_graph);
+ m_graph.ensureDominators();
+ m_graph.ensureNaturalLoops();
if (verbose) {
dataLog("Graph before LICM:\n");
m_graph.dump();
}
- m_data.resize(m_graph.m_naturalLoops.numLoops());
+ m_data.resize(m_graph.m_naturalLoops->numLoops());
// Figure out the set of things each loop writes to, not including blocks that
// belong to inner loops. We fix this later.
if (!block->cfaHasVisited)
continue;
- const NaturalLoop* loop = m_graph.m_naturalLoops.innerMostLoopOf(block);
+ const NaturalLoop* loop = m_graph.m_naturalLoops->innerMostLoopOf(block);
if (!loop)
continue;
LoopData& data = m_data[loop->index()];
// For each loop:
// - Identify its pre-header.
// - Make sure its outer loops know what it clobbers.
- for (unsigned loopIndex = m_graph.m_naturalLoops.numLoops(); loopIndex--;) {
- const NaturalLoop& loop = m_graph.m_naturalLoops.loop(loopIndex);
+ for (unsigned loopIndex = m_graph.m_naturalLoops->numLoops(); loopIndex--;) {
+ const NaturalLoop& loop = m_graph.m_naturalLoops->loop(loopIndex);
LoopData& data = m_data[loop.index()];
for (
- const NaturalLoop* outerLoop = m_graph.m_naturalLoops.innerMostOuterLoop(loop);
+ const NaturalLoop* outerLoop = m_graph.m_naturalLoops->innerMostOuterLoop(loop);
outerLoop;
- outerLoop = m_graph.m_naturalLoops.innerMostOuterLoop(*outerLoop))
+ outerLoop = m_graph.m_naturalLoops->innerMostOuterLoop(*outerLoop))
m_data[outerLoop->index()].writes.addAll(data.writes);
BasicBlock* header = loop.header();
for (unsigned i = header->predecessors.size(); i--;) {
BasicBlock* predecessor = header->predecessors[i];
- if (m_graph.m_dominators.dominates(header, predecessor))
+ if (m_graph.m_dominators->dominates(header, predecessor))
continue;
preHeader = predecessor;
Vector<const NaturalLoop*> loopStack;
bool changed = false;
for (BasicBlock* block : m_graph.blocksInPreOrder()) {
- const NaturalLoop* loop = m_graph.m_naturalLoops.innerMostLoopOf(block);
+ const NaturalLoop* loop = m_graph.m_naturalLoops->innerMostLoopOf(block);
if (!loop)
continue;
for (
const NaturalLoop* current = loop;
current;
- current = m_graph.m_naturalLoops.innerMostOuterLoop(*current))
+ current = m_graph.m_naturalLoops->innerMostOuterLoop(*current))
loopStack.append(current);
// Remember: the loop stack has the inner-most loop at index 0, so if we want
// because most loops are small and most blocks belong to few loops.
for (unsigned bodyIndex = loop->size(); bodyIndex--;) {
BasicBlock* subBlock = loop->at(bodyIndex);
- const NaturalLoop* subLoop = m_graph.m_naturalLoops.headerOf(subBlock);
+ const NaturalLoop* subLoop = m_graph.m_naturalLoops->headerOf(subBlock);
if (!subLoop)
continue;
BasicBlock* subPreHeader = m_data[subLoop->index()].preHeader;
#include "DFGBasicBlockInlines.h"
#include "DFGBlockInsertionSet.h"
+#include "DFGDominators.h"
#include "DFGGraph.h"
+#include "DFGNaturalLoops.h"
#include "DFGPhase.h"
#include "JSCInlines.h"
#include <wtf/HashMap.h>
for (unsigned predecessorIndex = 0; predecessorIndex < block->predecessors.size(); predecessorIndex++) {
BasicBlock* predecessor = block->predecessors[predecessorIndex];
- if (graph.m_dominators.dominates(block, predecessor))
+ if (graph.m_dominators->dominates(block, predecessor))
continue;
block->predecessors[predecessorIndex--] = block->predecessors.last();
block->predecessors.removeLast();
bool run()
{
- m_graph.m_dominators.computeIfNecessary(m_graph);
- m_graph.m_naturalLoops.computeIfNecessary(m_graph);
+ m_graph.ensureDominators();
+ m_graph.ensureNaturalLoops();
- for (unsigned loopIndex = m_graph.m_naturalLoops.numLoops(); loopIndex--;) {
- const NaturalLoop& loop = m_graph.m_naturalLoops.loop(loopIndex);
+ for (unsigned loopIndex = m_graph.m_naturalLoops->numLoops(); loopIndex--;) {
+ const NaturalLoop& loop = m_graph.m_naturalLoops->loop(loopIndex);
BasicBlock* existingPreHeader = 0;
bool needsNewPreHeader = false;
for (unsigned predecessorIndex = loop.header()->predecessors.size(); predecessorIndex--;) {
BasicBlock* predecessor = loop.header()->predecessors[predecessorIndex];
- if (m_graph.m_dominators.dominates(loop.header(), predecessor))
+ if (m_graph.m_dominators->dominates(loop.header(), predecessor))
continue;
if (!existingPreHeader) {
existingPreHeader = predecessor;
+++ /dev/null
-/*
- * Copyright (C) 2011, 2014 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 "DFGNaiveDominators.h"
-
-#if ENABLE(DFG_JIT)
-
-#include "DFGGraph.h"
-#include "JSCInlines.h"
-
-namespace JSC { namespace DFG {
-
-NaiveDominators::NaiveDominators()
-{
-}
-
-NaiveDominators::~NaiveDominators()
-{
-}
-
-void NaiveDominators::compute(Graph& graph)
-{
- // This implements a naive dominator solver.
-
- ASSERT(graph.block(0)->predecessors.isEmpty());
-
- unsigned numBlocks = graph.numBlocks();
-
- // Allocate storage for the dense dominance matrix.
- if (numBlocks > m_results.size()) {
- m_results.grow(numBlocks);
- for (unsigned i = numBlocks; i--;)
- m_results[i].resize(numBlocks);
- m_scratch.resize(numBlocks);
- }
-
- // We know that the entry block is only dominated by itself.
- m_results[0].clearAll();
- m_results[0].set(0);
-
- // Find all of the valid blocks.
- m_scratch.clearAll();
- for (unsigned i = numBlocks; i--;) {
- if (!graph.block(i))
- continue;
- m_scratch.set(i);
- }
-
- // Mark all nodes as dominated by everything.
- for (unsigned i = numBlocks; i-- > 1;) {
- if (!graph.block(i) || graph.block(i)->predecessors.isEmpty())
- m_results[i].clearAll();
- else
- m_results[i].set(m_scratch);
- }
-
- // Iteratively eliminate nodes that are not dominator.
- bool changed;
- do {
- changed = false;
- // Prune dominators in all non entry blocks: forward scan.
- for (unsigned i = 1; i < numBlocks; ++i)
- changed |= pruneDominators(graph, i);
-
- if (!changed)
- break;
-
- // Prune dominators in all non entry blocks: backward scan.
- changed = false;
- for (unsigned i = numBlocks; i-- > 1;)
- changed |= pruneDominators(graph, i);
- } while (changed);
-}
-
-bool NaiveDominators::pruneDominators(Graph& graph, BlockIndex idx)
-{
- BasicBlock* block = graph.block(idx);
-
- if (!block || block->predecessors.isEmpty())
- return false;
-
- // Find the intersection of dom(preds).
- m_scratch.set(m_results[block->predecessors[0]->index]);
- for (unsigned j = block->predecessors.size(); j-- > 1;)
- m_scratch.filter(m_results[block->predecessors[j]->index]);
-
- // The block is also dominated by itself.
- m_scratch.set(idx);
-
- return m_results[idx].setAndCheck(m_scratch);
-}
-
-void NaiveDominators::dump(Graph& graph, PrintStream& out) const
-{
- for (BlockIndex blockIndex = 0; blockIndex < graph.numBlocks(); ++blockIndex) {
- BasicBlock* block = graph.block(blockIndex);
- if (!block)
- continue;
- out.print(" Block ", *block, ":");
- for (BlockIndex otherIndex = 0; otherIndex < graph.numBlocks(); ++otherIndex) {
- if (!dominates(block->index, otherIndex))
- continue;
- out.print(" #", otherIndex);
- }
- out.print("\n");
- }
-}
-
-} } // namespace JSC::DFG
-
-#endif // ENABLE(DFG_JIT)
-
out.print("]");
}
-NaturalLoops::NaturalLoops() { }
-NaturalLoops::~NaturalLoops() { }
-
-void NaturalLoops::computeDependencies(Graph& graph)
+NaturalLoops::NaturalLoops(Graph& graph)
{
- graph.m_dominators.computeIfNecessary(graph);
-}
+ ASSERT(graph.m_dominators);
-void NaturalLoops::compute(Graph& graph)
-{
// Implement the classic dominator-based natural loop finder. The first
// step is to find all control flow edges A -> B where B dominates A.
// Then B is a loop header and A is a backward branching block. We will
if (verbose) {
dataLog("Dominators:\n");
- graph.m_dominators.dump(WTF::dataFile());
+ graph.m_dominators->dump(WTF::dataFile());
}
m_loops.resize(0);
for (unsigned i = block->numSuccessors(); i--;) {
BasicBlock* successor = block->successor(i);
- if (!graph.m_dominators.dominates(successor, block))
+ if (!graph.m_dominators->dominates(successor, block))
continue;
bool found = false;
for (unsigned j = m_loops.size(); j--;) {
dataLog("Results: ", *this, "\n");
}
+NaturalLoops::~NaturalLoops() { }
+
Vector<const NaturalLoop*> NaturalLoops::loopsOf(BasicBlock* block) const
{
Vector<const NaturalLoop*> result;
#if ENABLE(DFG_JIT)
-#include "DFGAnalysis.h"
#include "DFGBasicBlock.h"
#include "DFGCommon.h"
+#include "DFGDominators.h"
+#include <wtf/FastMalloc.h>
+#include <wtf/Noncopyable.h>
namespace JSC { namespace DFG {
unsigned m_index;
};
-class NaturalLoops : public Analysis<NaturalLoops> {
+class NaturalLoops {
+ WTF_MAKE_NONCOPYABLE(NaturalLoops);
+ WTF_MAKE_FAST_ALLOCATED;
public:
- NaturalLoops();
+ NaturalLoops(Graph&);
~NaturalLoops();
- void computeDependencies(Graph&);
- void compute(Graph&);
-
unsigned numLoops() const
{
- ASSERT(isValid());
return m_loops.size();
}
const NaturalLoop& loop(unsigned i) const
{
- ASSERT(isValid());
return m_loops[i];
}
// loop it belongs to.
const NaturalLoop* headerOf(BasicBlock* block) const
{
- ASSERT(isValid());
const NaturalLoop* loop = innerMostLoopOf(block);
if (!loop)
return 0;
const NaturalLoop* innerMostLoopOf(BasicBlock* block) const
{
- ASSERT(isValid());
unsigned index = block->innerMostLoopIndices[0];
if (index == UINT_MAX)
return 0;
const NaturalLoop* innerMostOuterLoop(const NaturalLoop& loop) const
{
- ASSERT(isValid());
if (loop.m_outerLoopIndex == UINT_MAX)
return 0;
return &m_loops[loop.m_outerLoopIndex];
bool belongsTo(BasicBlock* block, const NaturalLoop& candidateLoop) const
{
- ASSERT(isValid());
// It's faster to do this test using the loop itself, if it's small.
if (candidateLoop.size() < 4)
return candidateLoop.contains(block);
{
return iterator(m_terminal, m_terminal->numSuccessors());
}
+
+ size_t size() const { return m_terminal->numSuccessors(); }
+ BasicBlock* at(size_t index) const { return m_terminal->successor(index); }
+ BasicBlock* operator[](size_t index) const { return at(index); }
private:
Node* m_terminal;
RELEASE_ASSERT(bytecodeIndex != UINT_MAX);
// Needed by createPreHeader().
- m_graph.m_dominators.computeIfNecessary(m_graph);
+ m_graph.ensureDominators();
CodeBlock* baseline = m_graph.m_profiledBlock;
{
m_graph.computeRefCounts();
m_graph.initializeNodeOwners();
- m_graph.m_dominators.computeIfNecessary(m_graph);
+ m_graph.ensureDominators();
performLivenessAnalysis(m_graph);
performOSRAvailabilityAnalysis(m_graph);
m_combinedLiveness = CombinedLiveness(m_graph);
// If we're doing validation, then run some analyses, to give them an opportunity
// to self-validate. Now is as good a time as any to do this.
if (validationEnabled()) {
- dfg.m_dominators.computeIfNecessary(dfg);
- dfg.m_naturalLoops.computeIfNecessary(dfg);
- dfg.m_prePostNumbering.computeIfNecessary(dfg);
+ dfg.ensureDominators();
+ dfg.ensureNaturalLoops();
+ dfg.ensurePrePostNumbering();
}
switch (mode) {
namespace JSC { namespace DFG {
-PrePostNumbering::PrePostNumbering() { }
-PrePostNumbering::~PrePostNumbering() { }
-
-void PrePostNumbering::compute(Graph& graph)
+PrePostNumbering::PrePostNumbering(Graph& graph)
{
m_map = BlockMap<Numbering>(graph);
}
}
+PrePostNumbering::~PrePostNumbering() { }
+
} } // namespace JSC::DFG
namespace WTF {
#if ENABLE(DFG_JIT)
-#include "DFGAnalysis.h"
#include "DFGBasicBlock.h"
#include "DFGBlockMap.h"
+#include <wtf/FastMalloc.h>
+#include <wtf/Noncopyable.h>
namespace JSC { namespace DFG {
BackEdge
};
-class PrePostNumbering : public Analysis<PrePostNumbering> {
+class PrePostNumbering {
+ WTF_MAKE_NONCOPYABLE(PrePostNumbering);
+ WTF_MAKE_FAST_ALLOCATED;
public:
- PrePostNumbering();
+ PrePostNumbering(Graph&);
~PrePostNumbering();
- void compute(Graph&);
-
unsigned preNumber(BasicBlock* block) const { return m_map[block].m_preNumber; }
unsigned postNumber(BasicBlock* block) const { return m_map[block].m_postNumber; }
unsigned m_preNumber;
unsigned m_postNumber;
};
-
+
BlockMap<Numbering> m_map;
};
m_graph.dump();
}
- m_graph.m_dominators.computeIfNecessary(m_graph);
+ m_graph.ensureDominators();
SSACalculator ssaCalculator(m_graph);
InsertionSet insertionSet(m_graph);
SSACalculator::Def* SSACalculator::nonLocalReachingDef(BasicBlock* block, Variable* variable)
{
- return reachingDefAtTail(m_graph.m_dominators.immediateDominatorOf(block), variable);
+ return reachingDefAtTail(m_graph.m_dominators->immediateDominatorOf(block), variable);
}
SSACalculator::Def* SSACalculator::reachingDefAtTail(BasicBlock* block, Variable* variable)
{
- for (; block; block = m_graph.m_dominators.immediateDominatorOf(block)) {
+ for (; block; block = m_graph.m_dominators->immediateDominatorOf(block)) {
if (Def* def = m_data[block].m_defs.get(variable))
return def;
}
template<typename PhiInsertionFunctor>
void computePhis(const PhiInsertionFunctor& functor)
{
- DFG_ASSERT(m_graph, nullptr, m_graph.m_dominators.isValid());
+ DFG_ASSERT(m_graph, nullptr, m_graph.m_dominators);
for (Variable& variable : m_variables) {
- m_graph.m_dominators.forAllBlocksInPrunedIteratedDominanceFrontierOf(
+ m_graph.m_dominators->forAllBlocksInPrunedIteratedDominanceFrontierOf(
variable.m_blocksWithDefs,
[&] (BasicBlock* block) -> bool {
Node* phiNode = functor(&variable, block);
RELEASE_ASSERT(m_graph.m_form == ThreadedCPS);
m_graph.clearReplacements();
- m_graph.m_dominators.computeIfNecessary(m_graph);
+ m_graph.ensureDominators();
if (verbose) {
dataLog("Graph before SSA transformation:\n");
#include "DFGBasicBlockInlines.h"
#include "DFGGraph.h"
+#include "DFGNaturalLoops.h"
#include "DFGPhase.h"
#include "JSCInlines.h"
bool run()
{
- m_graph.m_naturalLoops.computeIfNecessary(m_graph);
+ m_graph.ensureNaturalLoops();
// Estimate basic block execution counts based on loop depth.
for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
if (!block)
continue;
- block->executionCount = pow(10, m_graph.m_naturalLoops.loopDepth(block));
+ block->executionCount = pow(10, m_graph.m_naturalLoops->loopDepth(block));
}
// Estimate branch weights based on execution counts. This isn't quite correct. It'll
#include "DFGGraph.h"
#include "DFGInsertionSet.h"
+#include "DFGNaturalLoops.h"
#include "DFGPhase.h"
#include "FTLCapabilities.h"
#include "JSCInlines.h"
// First we find all the loops that contain a LoopHint for which we cannot OSR enter.
// We use that information to decide if we need CheckTierUpAndOSREnter or CheckTierUpWithNestedTriggerAndOSREnter.
- NaturalLoops& naturalLoops = m_graph.m_naturalLoops;
- naturalLoops.computeIfNecessary(m_graph);
+ m_graph.ensureNaturalLoops();
+ NaturalLoops& naturalLoops = *m_graph.m_naturalLoops;
HashSet<const NaturalLoop*> loopsContainingLoopHintWithoutOSREnter = findLoopsContainingLoopHintWithoutOSREnter(naturalLoops, level);
Profiler::OriginStack(),
toCString("Generated FTL JIT code for ", CodeBlockWithJITType(codeBlock, JITCode::FTLJIT), ", instruction count = ", graph.m_codeBlock->instructionCount(), ":\n"));
- graph.m_dominators.computeIfNecessary(graph);
- graph.m_naturalLoops.computeIfNecessary(graph);
+ graph.ensureDominators();
+ graph.ensureNaturalLoops();
const char* prefix = " ";
#include "CodeBlockWithJITType.h"
#include "DFGAbstractInterpreterInlines.h"
+#include "DFGDominators.h"
#include "DFGInPlaceAbstractState.h"
#include "DFGOSRAvailabilityAnalysisPhase.h"
#include "DFGOSRExitFuzz.h"
} else
name = "jsBody";
- m_graph.m_dominators.computeIfNecessary(m_graph);
+ m_graph.ensureDominators();
m_ftlState.module =
moduleCreateWithNameInContext(name.data(), m_ftlState.context);
BasicBlock* target = m_graph.block(blockIndex);
if (!target)
continue;
- if (m_graph.m_dominators.dominates(m_highBlock, target)) {
+ if (m_graph.m_dominators->dominates(m_highBlock, target)) {
if (verboseCompilationEnabled())
dataLog("Block ", *target, " will bail also.\n");
target->cfaHasVisited = false;
{
if (!value)
return false;
- if (!m_graph.m_dominators.dominates(value.block(), m_highBlock))
+ if (!m_graph.m_dominators->dominates(value.block(), m_highBlock))
return false;
return true;
}
+2015-11-01 Filip Pizlo <fpizlo@apple.com>
+
+ Dominators should be factored out of the DFG
+ https://bugs.webkit.org/show_bug.cgi?id=150764
+
+ Reviewed by Geoffrey Garen.
+
+ This takes what used to be DFGDominators.h/DFGDominators.cpp and turns it into a generic
+ algorithm that can take any abstract graph. The idea is that you create Dominators<CFG> and
+ pass it a CFG object, which defines the types of graph nodes and methods for getting
+ successors, predecessors, etc. The DFG now defines a class called CFG, which is a wrapper for
+ DFG::Graph that conforms to the thing that wtf/Dominators.h expects.
+
+ When doing things to graphs, it's common to refer to the things in the graph as "nodes".
+ Because I intend to reuse the CFG abstraction with many graph algorithms, that abstraction uses
+ the term "node" to refer to a DFG basic block. But in Dominators, the method and variable names
+ still use "block". This is because although Dominators are applicable to any kind of directed
+ graph, it's super unlikely that we will ever use them for anything but compilers. Indeed, the
+ only reason why I'm factoring them out of the DFG is so that I can use them with B3 and Air.
+
+ This has the nice side effect that a user of WTF::Dominators<JSC::DFG::CFG> will see familiar
+ terminology like "blocksStrictlyDominatedBy(...)" instead of "nodesStrictlyDominatedBy(...)",
+ which would be super confusing.
+
+ Overall, wtf/Dominators.h is a combination of what used to be in DFGDominators.h,
+ DFGDominators.cpp, DFGNaiveDominators.h, and DFGNaiveDominators.cpp. I only changed code when I
+ had to in order to make it generic.
+
+ * WTF.xcodeproj/project.pbxproj:
+ * wtf/CMakeLists.txt:
+ * wtf/Dominators.h: Added.
+ (WTF::Dominators::Dominators):
+ (WTF::Dominators::compute):
+ (WTF::Dominators::strictlyDominates):
+ (WTF::Dominators::dominates):
+ (WTF::Dominators::immediateDominatorOf):
+ (WTF::Dominators::forAllStrictDominatorsOf):
+ (WTF::Dominators::forAllDominatorsOf):
+ (WTF::Dominators::forAllBlocksStrictlyDominatedBy):
+ (WTF::Dominators::forAllBlocksDominatedBy):
+ (WTF::Dominators::strictDominatorsOf):
+ (WTF::Dominators::dominatorsOf):
+ (WTF::Dominators::blocksStrictlyDominatedBy):
+ (WTF::Dominators::blocksDominatedBy):
+ (WTF::Dominators::forAllBlocksInDominanceFrontierOf):
+ (WTF::Dominators::dominanceFrontierOf):
+ (WTF::Dominators::forAllBlocksInIteratedDominanceFrontierOf):
+ (WTF::Dominators::forAllBlocksInPrunedIteratedDominanceFrontierOf):
+ (WTF::Dominators::iteratedDominanceFrontierOf):
+ (WTF::Dominators::dump):
+ (WTF::Dominators::LengauerTarjan::LengauerTarjan):
+ (WTF::Dominators::LengauerTarjan::compute):
+ (WTF::Dominators::LengauerTarjan::immediateDominator):
+ (WTF::Dominators::LengauerTarjan::computeDepthFirstPreNumbering):
+ (WTF::Dominators::LengauerTarjan::computeSemiDominatorsAndImplicitImmediateDominators):
+ (WTF::Dominators::LengauerTarjan::computeExplicitImmediateDominators):
+ (WTF::Dominators::LengauerTarjan::link):
+ (WTF::Dominators::LengauerTarjan::eval):
+ (WTF::Dominators::LengauerTarjan::compress):
+ (WTF::Dominators::LengauerTarjan::BlockData::BlockData):
+ (WTF::Dominators::NaiveDominators::NaiveDominators):
+ (WTF::Dominators::NaiveDominators::dominates):
+ (WTF::Dominators::NaiveDominators::dump):
+ (WTF::Dominators::NaiveDominators::pruneDominators):
+ (WTF::Dominators::ValidationContext::ValidationContext):
+ (WTF::Dominators::ValidationContext::reportError):
+ (WTF::Dominators::ValidationContext::handleErrors):
+ (WTF::Dominators::naiveDominates):
+ (WTF::Dominators::forAllBlocksInDominanceFrontierOfImpl):
+ (WTF::Dominators::forAllBlocksInIteratedDominanceFrontierOfImpl):
+ (WTF::Dominators::BlockData::BlockData):
+
2015-11-01 Darin Adler <darin@apple.com>
Remove some dead and unneeded code (ScrollbarThemeSafari, RenderThemeSafari, OPENCL, a little color space logic)
0F2B66A617B6B4FB00A7AE3F /* DeferrableRefCounted.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2B66A417B6B4F700A7AE3F /* DeferrableRefCounted.h */; };
0F2B66A717B6B4FD00A7AE3F /* FlipBytes.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2B66A517B6B4F700A7AE3F /* FlipBytes.h */; };
0F3501641BB258D500F0A2A3 /* WeakRandom.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F3501631BB258C800F0A2A3 /* WeakRandom.h */; };
+ 0F4570431BE5B58F0062A629 /* Dominators.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F4570421BE5B58F0062A629 /* Dominators.h */; };
0F824A681B7443A0002E345D /* ParkingLot.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F824A641B7443A0002E345D /* ParkingLot.cpp */; };
0F824A691B7443A0002E345D /* ParkingLot.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F824A651B7443A0002E345D /* ParkingLot.h */; };
0F87105A16643F190090B0AD /* RawPointer.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F87105916643F190090B0AD /* RawPointer.h */; };
0FE4479D1B7AAA03009498EB /* WordLock.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FE4479B1B7AAA03009498EB /* WordLock.h */; };
0FEB3DCF1BB5D684009D7AAD /* SharedTask.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEB3DCE1BB5D684009D7AAD /* SharedTask.h */; };
0FEB3DD11BB7366B009D7AAD /* ParallelVectorIterator.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEB3DD01BB7366B009D7AAD /* ParallelVectorIterator.h */; };
- 0FEC84B11BDACD390080FF74 /* ScopedLambda.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC84B01BDACD390080FF74 /* ScopedLambda.h */; };
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 */; };
0FF860951BCCBD740045127F /* PointerComparison.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FF860941BCCBD740045127F /* PointerComparison.h */; };
0FFF19DC1BB334EB00886D91 /* ParallelHelperPool.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FFF19DA1BB334EB00886D91 /* ParallelHelperPool.cpp */; };
0F2B66A517B6B4F700A7AE3F /* FlipBytes.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = FlipBytes.h; sourceTree = "<group>"; };
0F300B7D18AB48B400A6D72E /* HashMethod.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = HashMethod.h; sourceTree = "<group>"; };
0F3501631BB258C800F0A2A3 /* WeakRandom.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WeakRandom.h; sourceTree = "<group>"; };
+ 0F4570421BE5B58F0062A629 /* Dominators.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Dominators.h; sourceTree = "<group>"; };
0F824A641B7443A0002E345D /* ParkingLot.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ParkingLot.cpp; sourceTree = "<group>"; };
0F824A651B7443A0002E345D /* ParkingLot.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ParkingLot.h; sourceTree = "<group>"; };
0F87105916643F190090B0AD /* RawPointer.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RawPointer.h; sourceTree = "<group>"; };
0FE4479B1B7AAA03009498EB /* WordLock.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WordLock.h; sourceTree = "<group>"; };
0FEB3DCE1BB5D684009D7AAD /* SharedTask.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SharedTask.h; sourceTree = "<group>"; };
0FEB3DD01BB7366B009D7AAD /* ParallelVectorIterator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ParallelVectorIterator.h; sourceTree = "<group>"; };
- 0FEC84B01BDACD390080FF74 /* ScopedLambda.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ScopedLambda.h; sourceTree = "<group>"; };
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>"; };
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>"; };
0F2B66A417B6B4F700A7AE3F /* DeferrableRefCounted.h */,
A8A4727E151A825A004123FF /* Deque.h */,
A8A4727F151A825A004123FF /* DisallowCType.h */,
+ 0F4570421BE5B58F0062A629 /* Dominators.h */,
A8A47280151A825A004123FF /* DoublyLinkedList.h */,
A8A47297151A825A004123FF /* dtoa.cpp */,
A8A47298151A825A004123FF /* dtoa.h */,
1AFDE6531953B23D00C48FFA /* Optional.h in Headers */,
A8A473F6151A825B004123FF /* OSAllocator.h in Headers */,
7CBBA07419BB7FDC00BBF025 /* OSObjectPtr.h in Headers */,
+ 0F4570431BE5B58F0062A629 /* Dominators.h in Headers */,
A8A473FA151A825B004123FF /* OSRandomSource.h in Headers */,
A8A473FE151A825B004123FF /* PackedIntVector.h in Headers */,
A8A473FF151A825B004123FF /* PageAllocation.h in Headers */,
CurrentTime.h
DataLog.h
DateMath.h
+ Dominators.h
DecimalNumber.h
DeferrableRefCounted.h
Deque.h
--- /dev/null
+/*
+ * Copyright (C) 2011, 2014, 2015 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.
+ */
+
+#ifndef WTFDominators_h
+#define WTFDominators_h
+
+#include <wtf/GraphNodeWorklist.h>
+
+namespace WTF {
+
+// This is a utility for finding the dominators of a graph. Dominators are almost universally used
+// for control flow graph analysis, so this code will refer to the graph's "nodes" as "blocks". In
+// that regard this code is kind of specialized for the various JSC compilers, but you could use it
+// for non-compiler things if you are OK with referring to your "nodes" as "blocks".
+
+template<typename Graph>
+class Dominators {
+public:
+ Dominators(Graph& graph, bool selfCheck = false)
+ : m_graph(graph)
+ {
+ LengauerTarjan lengauerTarjan(m_graph);
+ lengauerTarjan.compute();
+
+ m_data = m_graph.template newMap<BlockData>();
+
+ // From here we want to build a spanning tree with both upward and downward links and we want
+ // to do a search over this tree to compute pre and post numbers that can be used for dominance
+ // tests.
+
+ for (unsigned blockIndex = m_graph.numNodes(); blockIndex--;) {
+ typename Graph::Node block = m_graph.node(blockIndex);
+ if (!block)
+ continue;
+
+ typename Graph::Node idomBlock = lengauerTarjan.immediateDominator(block);
+ m_data[block].idomParent = idomBlock;
+ if (idomBlock)
+ m_data[idomBlock].idomKids.append(block);
+ }
+
+ unsigned nextPreNumber = 0;
+ unsigned nextPostNumber = 0;
+
+ // Plain stack-based worklist because we are guaranteed to see each block exactly once anyway.
+ Vector<GraphNodeWithOrder<typename Graph::Node>> worklist;
+ worklist.append(GraphNodeWithOrder<typename Graph::Node>(m_graph.node(0), GraphVisitOrder::Pre));
+ while (!worklist.isEmpty()) {
+ GraphNodeWithOrder<typename Graph::Node> item = worklist.takeLast();
+ switch (item.order) {
+ case GraphVisitOrder::Pre:
+ m_data[item.node].preNumber = nextPreNumber++;
+ worklist.append(GraphNodeWithOrder<typename Graph::Node>(item.node, GraphVisitOrder::Post));
+ for (typename Graph::Node kid : m_data[item.node].idomKids)
+ worklist.append(GraphNodeWithOrder<typename Graph::Node>(kid, GraphVisitOrder::Pre));
+ break;
+ case GraphVisitOrder::Post:
+ m_data[item.node].postNumber = nextPostNumber++;
+ break;
+ }
+ }
+
+ if (selfCheck) {
+ // Check our dominator calculation:
+ // 1) Check that our range-based ancestry test is the same as a naive ancestry test.
+ // 2) Check that our notion of who dominates whom is identical to a naive (not
+ // Lengauer-Tarjan) dominator calculation.
+
+ ValidationContext context(m_graph, *this);
+
+ for (unsigned fromBlockIndex = m_graph.numNodes(); fromBlockIndex--;) {
+ typename Graph::Node fromBlock = m_graph.node(fromBlockIndex);
+ if (!fromBlock || m_data[fromBlock].preNumber == UINT_MAX)
+ continue;
+ for (unsigned toBlockIndex = m_graph.numNodes(); toBlockIndex--;) {
+ typename Graph::Node toBlock = m_graph.node(toBlockIndex);
+ if (!toBlock || m_data[toBlock].preNumber == UINT_MAX)
+ continue;
+
+ if (dominates(fromBlock, toBlock) != naiveDominates(fromBlock, toBlock))
+ context.reportError(fromBlock, toBlock, "Range-based domination check is broken");
+ if (dominates(fromBlock, toBlock) != context.naiveDominators.dominates(fromBlock, toBlock))
+ context.reportError(fromBlock, toBlock, "Lengauer-Tarjan domination is broken");
+ }
+ }
+
+ context.handleErrors();
+ }
+ }
+
+ bool strictlyDominates(typename Graph::Node from, typename Graph::Node to) const
+ {
+ return m_data[to].preNumber > m_data[from].preNumber
+ && m_data[to].postNumber < m_data[from].postNumber;
+ }
+
+ bool dominates(typename Graph::Node from, typename Graph::Node to) const
+ {
+ return from == to || strictlyDominates(from, to);
+ }
+
+ typename Graph::Node immediateDominatorOf(typename Graph::Node block) const
+ {
+ return m_data[block].idomParent;
+ }
+
+ template<typename Functor>
+ void forAllStrictDominatorsOf(typename Graph::Node to, const Functor& functor) const
+ {
+ for (typename Graph::Node block = m_data[to].idomParent; block; block = m_data[block].idomParent)
+ functor(block);
+ }
+
+ template<typename Functor>
+ void forAllDominatorsOf(typename Graph::Node to, const Functor& functor) const
+ {
+ for (typename Graph::Node block = to; block; block = m_data[block].idomParent)
+ functor(block);
+ }
+
+ template<typename Functor>
+ void forAllBlocksStrictlyDominatedBy(typename Graph::Node from, const Functor& functor) const
+ {
+ Vector<typename Graph::Node, 16> worklist;
+ worklist.appendVector(m_data[from].idomKids);
+ while (!worklist.isEmpty()) {
+ typename Graph::Node block = worklist.takeLast();
+ functor(block);
+ worklist.appendVector(m_data[block].idomKids);
+ }
+ }
+
+ template<typename Functor>
+ void forAllBlocksDominatedBy(typename Graph::Node from, const Functor& functor) const
+ {
+ Vector<typename Graph::Node, 16> worklist;
+ worklist.append(from);
+ while (!worklist.isEmpty()) {
+ typename Graph::Node block = worklist.takeLast();
+ functor(block);
+ worklist.appendVector(m_data[block].idomKids);
+ }
+ }
+
+ typename Graph::Set strictDominatorsOf(typename Graph::Node to) const
+ {
+ typename Graph::Set result;
+ forAllStrictDominatorsOf(
+ to,
+ [&] (typename Graph::Node node) {
+ result.add(node);
+ });
+ return result;
+ }
+
+ typename Graph::Set dominatorsOf(typename Graph::Node to) const
+ {
+ typename Graph::Set result;
+ forAllDominatorsOf(
+ to,
+ [&] (typename Graph::Node node) {
+ result.add(node);
+ });
+ return result;
+ }
+
+ typename Graph::Set blocksStrictlyDominatedBy(typename Graph::Node from) const
+ {
+ typename Graph::Set result;
+ forAllBlocksStrictlyDominatedBy(
+ from,
+ [&] (typename Graph::Node node) {
+ result.add(node);
+ });
+ return result;
+ }
+
+ typename Graph::Set blocksDominatedBy(typename Graph::Node from) const
+ {
+ typename Graph::Set result;
+ forAllBlocksDominatedBy(
+ from,
+ [&] (typename Graph::Node node) {
+ result.add(node);
+ });
+ return result;
+ }
+
+ template<typename Functor>
+ void forAllBlocksInDominanceFrontierOf(
+ typename Graph::Node from, const Functor& functor) const
+ {
+ typename Graph::Set set;
+ forAllBlocksInDominanceFrontierOfImpl(
+ from,
+ [&] (typename Graph::Node block) {
+ if (set.add(block))
+ functor(block);
+ });
+ }
+
+ typename Graph::Set dominanceFrontierOf(typename Graph::Node from) const
+ {
+ typename Graph::Set result;
+ forAllBlocksInDominanceFrontierOf(
+ from,
+ [&] (typename Graph::Node node) {
+ result.add(node);
+ });
+ return result;
+ }
+
+ template<typename Functor>
+ void forAllBlocksInIteratedDominanceFrontierOf(const typename Graph::List& from, const Functor& functor)
+ {
+ forAllBlocksInPrunedIteratedDominanceFrontierOf(
+ from,
+ [&] (typename Graph::Node block) -> bool {
+ functor(block);
+ return true;
+ });
+ }
+
+ // This is a close relative of forAllBlocksInIteratedDominanceFrontierOf(), which allows the
+ // given functor to return false to indicate that we don't wish to consider the given block.
+ // Useful for computing pruned SSA form.
+ template<typename Functor>
+ void forAllBlocksInPrunedIteratedDominanceFrontierOf(
+ const typename Graph::List& from, const Functor& functor)
+ {
+ typename Graph::Set set;
+ forAllBlocksInIteratedDominanceFrontierOfImpl(
+ from,
+ [&] (typename Graph::Node block) -> bool {
+ if (!set.add(block))
+ return false;
+ return functor(block);
+ });
+ }
+
+ typename Graph::Set iteratedDominanceFrontierOf(const typename Graph::List& from) const
+ {
+ typename Graph::Set result;
+ forAllBlocksInIteratedDominanceFrontierOfImpl(
+ from,
+ [&] (typename Graph::Node node) -> bool {
+ return result.add(node);
+ });
+ return result;
+ }
+
+ void dump(PrintStream& out) const
+ {
+ for (unsigned blockIndex = 0; blockIndex < m_data.size(); ++blockIndex) {
+ if (m_data[blockIndex].preNumber == UINT_MAX)
+ continue;
+
+ out.print(" Block #", blockIndex, ": idom = ", pointerDump(m_data[blockIndex].idomParent), ", idomKids = [");
+ CommaPrinter comma;
+ for (unsigned i = 0; i < m_data[blockIndex].idomKids.size(); ++i)
+ out.print(comma, *m_data[blockIndex].idomKids[i]);
+ out.print("], pre/post = ", m_data[blockIndex].preNumber, "/", m_data[blockIndex].postNumber, "\n");
+ }
+ }
+
+private:
+ // This implements Lengauer and Tarjan's "A Fast Algorithm for Finding Dominators in a Flowgraph"
+ // (TOPLAS 1979). It uses the "simple" implementation of LINK and EVAL, which yields an O(n log n)
+ // solution. The full paper is linked below; this code attempts to closely follow the algorithm as
+ // it is presented in the paper; in particular sections 3 and 4 as well as appendix B.
+ // https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/a%20fast%20algorithm%20for%20finding.pdf
+ //
+ // This code is very subtle. The Lengauer-Tarjan algorithm is incredibly deep to begin with. The
+ // goal of this code is to follow the code in the paper, however our implementation must deviate
+ // from the paper when it comes to recursion. The authors had used recursion to implement DFS, and
+ // also to implement the "simple" EVAL. We convert both of those into worklist-based solutions.
+ // Finally, once the algorithm gives us immediate dominators, we implement dominance tests by
+ // walking the dominator tree and computing pre and post numbers. We then use the range inclusion
+ // check trick that was first discovered by Paul F. Dietz in 1982 in "Maintaining order in a linked
+ // list" (see http://dl.acm.org/citation.cfm?id=802184).
+
+ class LengauerTarjan {
+ public:
+ LengauerTarjan(Graph& graph)
+ : m_graph(graph)
+ , m_data(graph.template newMap<BlockData>())
+ {
+ for (unsigned blockIndex = m_graph.numNodes(); blockIndex--;) {
+ typename Graph::Node block = m_graph.node(blockIndex);
+ if (!block)
+ continue;
+ m_data[block].label = block;
+ }
+ }
+
+ void compute()
+ {
+ computeDepthFirstPreNumbering(); // Step 1.
+ computeSemiDominatorsAndImplicitImmediateDominators(); // Steps 2 and 3.
+ computeExplicitImmediateDominators(); // Step 4.
+ }
+
+ typename Graph::Node immediateDominator(typename Graph::Node block)
+ {
+ return m_data[block].dom;
+ }
+
+ private:
+ void computeDepthFirstPreNumbering()
+ {
+ // Use a block worklist that also tracks the index inside the successor list. This is
+ // necessary for ensuring that we don't attempt to visit a successor until the previous
+ // successors that we had visited are fully processed. This ends up being revealed in the
+ // output of this method because the first time we see an edge to a block, we set the
+ // block's parent. So, if we have:
+ //
+ // A -> B
+ // A -> C
+ // B -> C
+ //
+ // And we're processing A, then we want to ensure that if we see A->B first (and hence set
+ // B's prenumber before we set C's) then we also end up setting C's parent to B by virtue
+ // of not noticing A->C until we're done processing B.
+
+ ExtendedGraphNodeWorklist<typename Graph::Node, unsigned, typename Graph::Set> worklist;
+ worklist.push(m_graph.node(0), 0);
+
+ while (GraphNodeWith<typename Graph::Node, unsigned> item = worklist.pop()) {
+ typename Graph::Node block = item.node;
+ unsigned successorIndex = item.data;
+
+ // We initially push with successorIndex = 0 regardless of whether or not we have any
+ // successors. This is so that we can assign our prenumber. Subsequently we get pushed
+ // with higher successorIndex values, but only if they are in range.
+ ASSERT(!successorIndex || successorIndex < m_graph.successors(block).size());
+
+ if (!successorIndex) {
+ m_data[block].semiNumber = m_blockByPreNumber.size();
+ m_blockByPreNumber.append(block);
+ }
+
+ if (successorIndex < m_graph.successors(block).size()) {
+ unsigned nextSuccessorIndex = successorIndex + 1;
+ if (nextSuccessorIndex < m_graph.successors(block).size())
+ worklist.forcePush(block, nextSuccessorIndex);
+
+ typename Graph::Node successorBlock = m_graph.successors(block)[successorIndex];
+ if (worklist.push(successorBlock, 0))
+ m_data[successorBlock].parent = block;
+ }
+ }
+ }
+
+ void computeSemiDominatorsAndImplicitImmediateDominators()
+ {
+ for (unsigned currentPreNumber = m_blockByPreNumber.size(); currentPreNumber-- > 1;) {
+ typename Graph::Node block = m_blockByPreNumber[currentPreNumber];
+ BlockData& blockData = m_data[block];
+
+ // Step 2:
+ for (typename Graph::Node predecessorBlock : m_graph.predecessors(block)) {
+ typename Graph::Node intermediateBlock = eval(predecessorBlock);
+ blockData.semiNumber = std::min(
+ m_data[intermediateBlock].semiNumber, blockData.semiNumber);
+ }
+ unsigned bucketPreNumber = blockData.semiNumber;
+ ASSERT(bucketPreNumber <= currentPreNumber);
+ m_data[m_blockByPreNumber[bucketPreNumber]].bucket.append(block);
+ link(blockData.parent, block);
+
+ // Step 3:
+ for (typename Graph::Node semiDominee : m_data[blockData.parent].bucket) {
+ typename Graph::Node possibleDominator = eval(semiDominee);
+ BlockData& semiDomineeData = m_data[semiDominee];
+ ASSERT(m_blockByPreNumber[semiDomineeData.semiNumber] == blockData.parent);
+ BlockData& possibleDominatorData = m_data[possibleDominator];
+ if (possibleDominatorData.semiNumber < semiDomineeData.semiNumber)
+ semiDomineeData.dom = possibleDominator;
+ else
+ semiDomineeData.dom = blockData.parent;
+ }
+ m_data[blockData.parent].bucket.clear();
+ }
+ }
+
+ void computeExplicitImmediateDominators()
+ {
+ for (unsigned currentPreNumber = 1; currentPreNumber < m_blockByPreNumber.size(); ++currentPreNumber) {
+ typename Graph::Node block = m_blockByPreNumber[currentPreNumber];
+ BlockData& blockData = m_data[block];
+
+ if (blockData.dom != m_blockByPreNumber[blockData.semiNumber])
+ blockData.dom = m_data[blockData.dom].dom;
+ }
+ }
+
+ void link(typename Graph::Node from, typename Graph::Node to)
+ {
+ m_data[to].ancestor = from;
+ }
+
+ typename Graph::Node eval(typename Graph::Node block)
+ {
+ if (!m_data[block].ancestor)
+ return block;
+
+ compress(block);
+ return m_data[block].label;
+ }
+
+ void compress(typename Graph::Node initialBlock)
+ {
+ // This was meant to be a recursive function, but we don't like recursion because we don't
+ // want to blow the stack. The original function will call compress() recursively on the
+ // ancestor of anything that has an ancestor. So, we populate our worklist with the
+ // recursive ancestors of initialBlock. Then we process the list starting from the block
+ // that is furthest up the ancestor chain.
+
+ typename Graph::Node ancestor = m_data[initialBlock].ancestor;
+ ASSERT(ancestor);
+ if (!m_data[ancestor].ancestor)
+ return;
+
+ Vector<typename Graph::Node, 16> stack;
+ for (typename Graph::Node block = initialBlock; block; block = m_data[block].ancestor)
+ stack.append(block);
+
+ // We only care about blocks that have an ancestor that has an ancestor. The last two
+ // elements in the stack won't satisfy this property.
+ ASSERT(stack.size() >= 2);
+ ASSERT(!m_data[stack[stack.size() - 1]].ancestor);
+ ASSERT(!m_data[m_data[stack[stack.size() - 2]].ancestor].ancestor);
+
+ for (unsigned i = stack.size() - 2; i--;) {
+ typename Graph::Node block = stack[i];
+ typename Graph::Node& labelOfBlock = m_data[block].label;
+ typename Graph::Node& ancestorOfBlock = m_data[block].ancestor;
+ ASSERT(ancestorOfBlock);
+ ASSERT(m_data[ancestorOfBlock].ancestor);
+
+ typename Graph::Node labelOfAncestorOfBlock = m_data[ancestorOfBlock].label;
+
+ if (m_data[labelOfAncestorOfBlock].semiNumber < m_data[labelOfBlock].semiNumber)
+ labelOfBlock = labelOfAncestorOfBlock;
+ ancestorOfBlock = m_data[ancestorOfBlock].ancestor;
+ }
+ }
+
+ struct BlockData {
+ BlockData()
+ : parent(nullptr)
+ , preNumber(UINT_MAX)
+ , semiNumber(UINT_MAX)
+ , ancestor(nullptr)
+ , label(nullptr)
+ , dom(nullptr)
+ {
+ }
+
+ typename Graph::Node parent;
+ unsigned preNumber;
+ unsigned semiNumber;
+ typename Graph::Node ancestor;
+ typename Graph::Node label;
+ Vector<typename Graph::Node> bucket;
+ typename Graph::Node dom;
+ };
+
+ Graph& m_graph;
+ typename Graph::template Map<BlockData> m_data;
+ Vector<typename Graph::Node> m_blockByPreNumber;
+ };
+
+ class NaiveDominators {
+ public:
+ NaiveDominators(Graph& graph)
+ : m_graph(graph)
+ {
+ // This implements a naive dominator solver.
+
+ ASSERT(!graph.predecessors(graph.root()).size());
+
+ unsigned numBlocks = graph.numNodes();
+
+ // Allocate storage for the dense dominance matrix.
+ m_results.grow(numBlocks);
+ for (unsigned i = numBlocks; i--;)
+ m_results[i].resize(numBlocks);
+ m_scratch.resize(numBlocks);
+
+ // We know that the entry block is only dominated by itself.
+ m_results[0].clearAll();
+ m_results[0].set(0);
+
+ // Find all of the valid blocks.
+ m_scratch.clearAll();
+ for (unsigned i = numBlocks; i--;) {
+ if (!graph.node(i))
+ continue;
+ m_scratch.set(i);
+ }
+
+ // Mark all nodes as dominated by everything.
+ for (unsigned i = numBlocks; i-- > 1;) {
+ if (!graph.node(i) || !graph.predecessors(graph.node(i)).size())
+ m_results[i].clearAll();
+ else
+ m_results[i].set(m_scratch);
+ }
+
+ // Iteratively eliminate nodes that are not dominator.
+ bool changed;
+ do {
+ changed = false;
+ // Prune dominators in all non entry blocks: forward scan.
+ for (unsigned i = 1; i < numBlocks; ++i)
+ changed |= pruneDominators(i);
+
+ if (!changed)
+ break;
+
+ // Prune dominators in all non entry blocks: backward scan.
+ changed = false;
+ for (unsigned i = numBlocks; i-- > 1;)
+ changed |= pruneDominators(i);
+ } while (changed);
+ }
+
+ bool dominates(unsigned from, unsigned to) const
+ {
+ return m_results[to].get(from);
+ }
+
+ bool dominates(typename Graph::Node from, typename Graph::Node to) const
+ {
+ return dominates(from->index, to->index);
+ }
+
+ void dump(PrintStream& out) const
+ {
+ for (unsigned blockIndex = 0; blockIndex < m_graph.numNodes(); ++blockIndex) {
+ typename Graph::Node block = m_graph.node(blockIndex);
+ if (!block)
+ continue;
+ out.print(" Block ", m_graph.dump(block), ":");
+ for (unsigned otherIndex = 0; otherIndex < m_graph.numNodes(); ++otherIndex) {
+ if (!dominates(m_graph.index(block), otherIndex))
+ continue;
+ out.print(" ", m_graph.dump(m_graph.node(otherIndex)));
+ }
+ out.print("\n");
+ }
+ }
+
+ private:
+ bool pruneDominators(unsigned idx)
+ {
+ typename Graph::Node block = m_graph.node(idx);
+
+ if (!block || !m_graph.predecessors(block).size())
+ return false;
+
+ // Find the intersection of dom(preds).
+ m_scratch.set(m_results[m_graph.index(m_graph.predecessors(block)[0])]);
+ for (unsigned j = m_graph.predecessors(block).size(); j-- > 1;)
+ m_scratch.filter(m_results[m_graph.index(m_graph.predecessors(block)[j])]);
+
+ // The block is also dominated by itself.
+ m_scratch.set(idx);
+
+ return m_results[idx].setAndCheck(m_scratch);
+ }
+
+ Graph m_graph;
+ Vector<FastBitVector> m_results; // For each block, the bitvector of blocks that dominate it.
+ FastBitVector m_scratch; // A temporary bitvector with bit for each block. We recycle this to save new/deletes.
+ };
+
+ struct ValidationContext {
+ ValidationContext(Graph& graph, Dominators& dominators)
+ : graph(graph)
+ , dominators(dominators)
+ , naiveDominators(graph)
+ {
+ }
+
+ void reportError(typename Graph::Node from, typename Graph::Node to, const char* message)
+ {
+ Error error;
+ error.from = from;
+ error.to = to;
+ error.message = message;
+ errors.append(error);
+ }
+
+ void handleErrors()
+ {
+ if (errors.isEmpty())
+ return;
+
+ dataLog("DFG DOMINATOR VALIDATION FAILED:\n");
+ dataLog("\n");
+ dataLog("For block domination relationships:\n");
+ for (unsigned i = 0; i < errors.size(); ++i) {
+ dataLog(
+ " ", graph.dump(errors[i].from), " -> ", graph.dump(errors[i].to),
+ " (", errors[i].message, ")\n");
+ }
+ dataLog("\n");
+ dataLog("Control flow graph:\n");
+ for (unsigned blockIndex = 0; blockIndex < graph.numNodes(); ++blockIndex) {
+ typename Graph::Node block = graph.node(blockIndex);
+ if (!block)
+ continue;
+ dataLog(" Block ", graph.dump(graph.node(blockIndex)), ": successors = [");
+ CommaPrinter comma;
+ for (unsigned i = 0; i < block->numSuccessors(); ++i)
+ dataLog(comma, graph.dump(block->successor(i)));
+ dataLog("], predecessors = [");
+ comma = CommaPrinter();
+ for (unsigned i = 0; i < block->predecessors.size(); ++i)
+ dataLog(comma, graph.dump(block->predecessors[i]));
+ dataLog("]\n");
+ }
+ dataLog("\n");
+ dataLog("Lengauer-Tarjan Dominators:\n");
+ dataLog(dominators);
+ dataLog("\n");
+ dataLog("Naive Dominators:\n");
+ naiveDominators.dump(WTF::dataFile());
+ dataLog("\n");
+ dataLog("Graph at time of failure:\n");
+ dataLog(graph);
+ dataLog("\n");
+ dataLog("DFG DOMINATOR VALIDATION FAILIED!\n");
+ CRASH();
+ }
+
+ Graph& graph;
+ Dominators& dominators;
+ NaiveDominators naiveDominators;
+
+ struct Error {
+ typename Graph::Node from;
+ typename Graph::Node to;
+ const char* message;
+ };
+
+ Vector<Error> errors;
+ };
+
+ bool naiveDominates(typename Graph::Node from, typename Graph::Node to) const
+ {
+ for (typename Graph::Node block = to; block; block = m_data[block].idomParent) {
+ if (block == from)
+ return true;
+ }
+ return false;
+ }
+
+ template<typename Functor>
+ void forAllBlocksInDominanceFrontierOfImpl(
+ typename Graph::Node from, const Functor& functor) const
+ {
+ // Paraphrasing from http://en.wikipedia.org/wiki/Dominator_(graph_theory):
+ // "The dominance frontier of a block 'from' is the set of all blocks 'to' such that
+ // 'from' dominates an immediate predecessor of 'to', but 'from' does not strictly
+ // dominate 'to'."
+ //
+ // A useful corner case to remember: a block may be in its own dominance frontier if it has
+ // a loop edge to itself, since it dominates itself and so it dominates its own immediate
+ // predecessor, and a block never strictly dominates itself.
+
+ forAllBlocksDominatedBy(
+ from,
+ [&] (typename Graph::Node block) {
+ for (typename Graph::Node to : m_graph.successors(block)) {
+ if (!strictlyDominates(from, to))
+ functor(to);
+ }
+ });
+ }
+
+ template<typename Functor>
+ void forAllBlocksInIteratedDominanceFrontierOfImpl(
+ const typename Graph::List& from, const Functor& functor) const
+ {
+ typename Graph::List worklist = from;
+ while (!worklist.isEmpty()) {
+ typename Graph::Node block = worklist.takeLast();
+ forAllBlocksInDominanceFrontierOfImpl(
+ block,
+ [&] (typename Graph::Node otherBlock) {
+ if (functor(otherBlock))
+ worklist.append(otherBlock);
+ });
+ }
+ }
+
+ struct BlockData {
+ BlockData()
+ : idomParent(nullptr)
+ , preNumber(UINT_MAX)
+ , postNumber(UINT_MAX)
+ {
+ }
+
+ Vector<typename Graph::Node> idomKids;
+ typename Graph::Node idomParent;
+
+ unsigned preNumber;
+ unsigned postNumber;
+ };
+
+ Graph& m_graph;
+ typename Graph::template Map<BlockData> m_data;
+};
+
+} // namespace WTF
+
+using WTF::Dominators;
+
+#endif // WTFDominators_h
+
git://git.webkit.org / WebKit-https.git / commitdiff