Diff
Modified: branches/dfgFourthTier/Source/_javascript_Core/ChangeLog (152138 => 152139)
--- branches/dfgFourthTier/Source/_javascript_Core/ChangeLog 2013-06-27 23:41:19 UTC (rev 152138)
+++ branches/dfgFourthTier/Source/_javascript_Core/ChangeLog 2013-06-28 00:02:12 UTC (rev 152139)
@@ -1,5 +1,71 @@
2013-06-27 Filip Pizlo <fpi...@apple.com>
+ fourthTier: DFG should know how to find natural loops
+ https://bugs.webkit.org/show_bug.cgi?id=118152
+
+ Reviewed by Mark Hahnenberg.
+
+ There are a bunch of things we can do when we know where the loops are.
+ Previously we didn't. With this patch, we do.
+
+ This patch adds the classic dominator based natural loop finder.
+
+ The only client of this right now is the DFG::Disassembler. It prints out
+ a summary of the analysis for each block.
+
+ This will become more important when I do
+ https://bugs.webkit.org/show_bug.cgi?id=118151, which definitely requires
+ this kind of analysis, at least if we want to do the optimization over
+ DFG IR (and I'm pretty sure we do).
+
+ * _javascript_Core.xcodeproj/project.pbxproj:
+ * dfg/DFGAnalysis.h: Added.
+ (DFG):
+ (Analysis):
+ (JSC::DFG::Analysis::Analysis):
+ (JSC::DFG::Analysis::invalidate):
+ (JSC::DFG::Analysis::computeIfNecessary):
+ (JSC::DFG::Analysis::isValid):
+ * dfg/DFGCFGSimplificationPhase.cpp:
+ (JSC::DFG::CFGSimplificationPhase::run):
+ * dfg/DFGDisassembler.cpp:
+ (JSC::DFG::Disassembler::createDumpList):
+ * dfg/DFGDominators.cpp:
+ (JSC::DFG::Dominators::Dominators):
+ (JSC::DFG::Dominators::compute):
+ * dfg/DFGDominators.h:
+ (Dominators):
+ * dfg/DFGGraph.cpp:
+ (JSC::DFG::Graph::dumpBlockHeader):
+ (JSC::DFG::Graph::invalidateCFG):
+ (DFG):
+ * dfg/DFGGraph.h:
+ (Graph):
+ * dfg/DFGNaturalLoops.cpp: Added.
+ (DFG):
+ (JSC::DFG::NaturalLoop::dump):
+ (JSC::DFG::NaturalLoops::NaturalLoops):
+ (JSC::DFG::NaturalLoops::~NaturalLoops):
+ (JSC::DFG::NaturalLoops::compute):
+ (JSC::DFG::NaturalLoops::loopsOf):
+ (JSC::DFG::NaturalLoops::dump):
+ * dfg/DFGNaturalLoops.h: Added.
+ (DFG):
+ (NaturalLoop):
+ (JSC::DFG::NaturalLoop::NaturalLoop):
+ (JSC::DFG::NaturalLoop::addBlock):
+ (JSC::DFG::NaturalLoop::header):
+ (JSC::DFG::NaturalLoop::size):
+ (JSC::DFG::NaturalLoop::at):
+ (JSC::DFG::NaturalLoop::operator[]):
+ (JSC::DFG::NaturalLoop::contains):
+ (NaturalLoops):
+ (JSC::DFG::NaturalLoops::numLoops):
+ (JSC::DFG::NaturalLoops::loop):
+ (JSC::DFG::NaturalLoops::headerOf):
+
+2013-06-27 Filip Pizlo <fpi...@apple.com>
+
fourthTier: JSC's disassembly infrastructure should be able to disassemble the code that LLVM generates
https://bugs.webkit.org/show_bug.cgi?id=118148
Modified: branches/dfgFourthTier/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj (152138 => 152139)
--- branches/dfgFourthTier/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2013-06-27 23:41:19 UTC (rev 152138)
+++ branches/dfgFourthTier/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2013-06-28 00:02:12 UTC (rev 152139)
@@ -170,6 +170,9 @@
0F46E6B9176F89DB00E1F755 /* FTLSwitchCase.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F46E6B7176F89D900E1F755 /* FTLSwitchCase.h */; settings = {ATTRIBUTES = (Private, ); }; };
0F46E6C5176F8A5E00E1F755 /* DFGLazyJSValue.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F46E6C2176F8A5B00E1F755 /* DFGLazyJSValue.cpp */; };
0F46E6C6176F8A6000E1F755 /* DFGLazyJSValue.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F46E6C3176F8A5B00E1F755 /* DFGLazyJSValue.h */; settings = {ATTRIBUTES = (Private, ); }; };
+ 0F46E6EF177CE95A00E1F755 /* DFGAnalysis.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F46E6EE177CE95A00E1F755 /* DFGAnalysis.h */; };
+ 0F46E6F3177CF0D200E1F755 /* DFGNaturalLoops.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F46E6F1177CF0D200E1F755 /* DFGNaturalLoops.cpp */; };
+ 0F46E6F4177CF0D200E1F755 /* DFGNaturalLoops.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F46E6F2177CF0D200E1F755 /* DFGNaturalLoops.h */; settings = {ATTRIBUTES = (Private, ); }; };
0F46E6D9177CB90000E1F755 /* LLVMDisassembler.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F46E6D7177CB8FC00E1F755 /* LLVMDisassembler.cpp */; };
0F46E6E3177CC36600E1F755 /* LLVMDisassembler.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F46E6E0177CC36600E1F755 /* LLVMDisassembler.h */; settings = {ATTRIBUTES = (Private, ); }; };
0F46E6E4177CC36600E1F755 /* UDis86Disassembler.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F46E6E1177CC36600E1F755 /* UDis86Disassembler.h */; settings = {ATTRIBUTES = (Private, ); }; };
@@ -1183,6 +1186,9 @@
0F46E6B7176F89D900E1F755 /* FTLSwitchCase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = FTLSwitchCase.h; path = ftl/FTLSwitchCase.h; sourceTree = "<group>"; };
0F46E6C2176F8A5B00E1F755 /* DFGLazyJSValue.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGLazyJSValue.cpp; path = dfg/DFGLazyJSValue.cpp; sourceTree = "<group>"; };
0F46E6C3176F8A5B00E1F755 /* DFGLazyJSValue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGLazyJSValue.h; path = dfg/DFGLazyJSValue.h; sourceTree = "<group>"; };
+ 0F46E6EE177CE95A00E1F755 /* DFGAnalysis.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGAnalysis.h; path = dfg/DFGAnalysis.h; sourceTree = "<group>"; };
+ 0F46E6F1177CF0D200E1F755 /* DFGNaturalLoops.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGNaturalLoops.cpp; path = dfg/DFGNaturalLoops.cpp; sourceTree = "<group>"; };
+ 0F46E6F2177CF0D200E1F755 /* DFGNaturalLoops.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGNaturalLoops.h; path = dfg/DFGNaturalLoops.h; sourceTree = "<group>"; };
0F46E6D7177CB8FC00E1F755 /* LLVMDisassembler.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = LLVMDisassembler.cpp; path = disassembler/LLVMDisassembler.cpp; sourceTree = "<group>"; };
0F46E6E0177CC36600E1F755 /* LLVMDisassembler.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = LLVMDisassembler.h; path = disassembler/LLVMDisassembler.h; sourceTree = "<group>"; };
0F46E6E1177CC36600E1F755 /* UDis86Disassembler.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = UDis86Disassembler.h; path = disassembler/UDis86Disassembler.h; sourceTree = "<group>"; };
@@ -2945,6 +2951,7 @@
0F62016F143FCD2F0068B77C /* DFGAbstractValue.h */,
0F66E16814DF3F1300B7B2E4 /* DFGAdjacencyList.h */,
0FB4B51916B62772003F696B /* DFGAllocator.h */,
+ 0F46E6EE177CE95A00E1F755 /* DFGAnalysis.h */,
0F1E3A431534CBAD000F9456 /* DFGArgumentPosition.h */,
0F16015A156198BF00C2587C /* DFGArgumentsSimplificationPhase.cpp */,
0F16015B156198BF00C2587C /* DFGArgumentsSimplificationPhase.h */,
@@ -3024,6 +3031,8 @@
0FB4B51016B3A964003F696B /* DFGMinifiedID.h */,
0F2BDC4C1522818300CD8910 /* DFGMinifiedNode.cpp */,
0F2BDC3E1522801700CD8910 /* DFGMinifiedNode.h */,
+ 0F46E6F1177CF0D200E1F755 /* DFGNaturalLoops.cpp */,
+ 0F46E6F2177CF0D200E1F755 /* DFGNaturalLoops.h */,
0FB4B51E16B62772003F696B /* DFGNode.cpp */,
86ECA3E9132DEF1C002B2AD7 /* DFGNode.h */,
0FB4B51F16B62772003F696B /* DFGNodeAllocator.h */,
@@ -3818,6 +3827,8 @@
0F5EE4E9175424AF009AE42D /* JSCTestRunnerUtils.h in Headers */,
0F46E6C6176F8A6000E1F755 /* DFGLazyJSValue.h in Headers */,
0F46E6B9176F89DB00E1F755 /* FTLSwitchCase.h in Headers */,
+ 0F46E6EF177CE95A00E1F755 /* DFGAnalysis.h in Headers */,
+ 0F46E6F4177CF0D200E1F755 /* DFGNaturalLoops.h in Headers */,
0F46E6E3177CC36600E1F755 /* LLVMDisassembler.h in Headers */,
0F46E6E4177CC36600E1F755 /* UDis86Disassembler.h in Headers */,
);
@@ -4511,6 +4522,7 @@
0F714CA416EA92F000F3EBEB /* DFGBackwardsPropagationPhase.cpp in Sources */,
0F5EE4E8175424AF009AE42D /* JSCTestRunnerUtils.cpp in Sources */,
0F46E6C5176F8A5E00E1F755 /* DFGLazyJSValue.cpp in Sources */,
+ 0F46E6F3177CF0D200E1F755 /* DFGNaturalLoops.cpp in Sources */,
0F46E6D9177CB90000E1F755 /* LLVMDisassembler.cpp in Sources */,
0F46E6E5177CC36600E1F755 /* X86Disassembler.cpp in Sources */,
);
Added: branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGAnalysis.h (0 => 152139)
--- branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGAnalysis.h (rev 0)
+++ branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGAnalysis.h 2013-06-28 00:02:12 UTC (rev 152139)
@@ -0,0 +1,73 @@
+/*
+ * Copyright (C) 2013 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
+
+#include <wtf/Platform.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;
+ static_cast<T*>(this)->compute(graph);
+ m_valid = true;
+ }
+
+ bool isValid() const { return m_valid; }
+
+private:
+ bool m_valid;
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGAnalysis_h
+
Modified: branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGCFGSimplificationPhase.cpp (152138 => 152139)
--- branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGCFGSimplificationPhase.cpp 2013-06-27 23:41:19 UTC (rev 152138)
+++ branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGCFGSimplificationPhase.cpp 2013-06-28 00:02:12 UTC (rev 152139)
@@ -280,6 +280,7 @@
// successors' Phi functions to remove any references from them into the
// removed block.
+ m_graph.invalidateCFG();
m_graph.resetReachability();
for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
Modified: branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGDisassembler.cpp (152138 => 152139)
--- branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGDisassembler.cpp 2013-06-27 23:41:19 UTC (rev 152138)
+++ branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGDisassembler.cpp 2013-06-28 00:02:12 UTC (rev 152139)
@@ -90,6 +90,7 @@
append(result, out, previousOrigin);
m_graph.m_dominators.computeIfNecessary(m_graph);
+ m_graph.m_naturalLoops.computeIfNecessary(m_graph);
const char* prefix = " ";
const char* disassemblyPrefix = " ";
Modified: branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGDominators.cpp (152138 => 152139)
--- branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGDominators.cpp 2013-06-27 23:41:19 UTC (rev 152138)
+++ branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGDominators.cpp 2013-06-28 00:02:12 UTC (rev 152139)
@@ -33,7 +33,6 @@
namespace JSC { namespace DFG {
Dominators::Dominators()
- : m_valid(false)
{
}
@@ -85,8 +84,6 @@
for (unsigned i = numBlocks; i-- > 1;)
changed |= iterateForBlock(graph, i);
} while (changed);
-
- m_valid = true;
}
bool Dominators::iterateForBlock(Graph& graph, BlockIndex i)
Modified: branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGDominators.h (152138 => 152139)
--- branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGDominators.h 2013-06-27 23:41:19 UTC (rev 152138)
+++ branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGDominators.h 2013-06-28 00:02:12 UTC (rev 152139)
@@ -30,6 +30,7 @@
#if ENABLE(DFG_JIT)
+#include "DFGAnalysis.h"
#include "DFGCommon.h"
#include <wtf/FastBitVector.h>
@@ -37,25 +38,13 @@
class Graph;
-class Dominators {
+class Dominators : public Analysis<Dominators> {
public:
Dominators();
~Dominators();
void compute(Graph& graph);
- void invalidate()
- {
- m_valid = false;
- }
- void computeIfNecessary(Graph& graph)
- {
- if (m_valid)
- return;
- compute(graph);
- }
- bool isValid() const { return m_valid; }
-
bool dominates(BlockIndex from, BlockIndex to) const
{
ASSERT(isValid());
@@ -67,7 +56,6 @@
Vector<FastBitVector> m_results;
FastBitVector m_scratch;
- bool m_valid;
};
} } // namespace JSC::DFG
Modified: branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGGraph.cpp (152138 => 152139)
--- branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGGraph.cpp 2013-06-27 23:41:19 UTC (rev 152138)
+++ branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGGraph.cpp 2013-06-28 00:02:12 UTC (rev 152139)
@@ -294,6 +294,27 @@
}
out.print("\n");
}
+ if (m_naturalLoops.isValid()) {
+ if (const NaturalLoop* loop = m_naturalLoops.headerOf(blockIndex)) {
+ out.print(prefix, " Loop header, contains:");
+ Vector<BlockIndex> sortedBlockList;
+ for (unsigned i = 0; i < loop->size(); ++i)
+ sortedBlockList.append(loop->at(i));
+ std::sort(sortedBlockList.begin(), sortedBlockList.end());
+ for (unsigned i = 0; i < sortedBlockList.size(); ++i)
+ out.print(" #", sortedBlockList[i]);
+ out.print("\n");
+ }
+
+ Vector<const NaturalLoop*> containingLoops =
+ m_naturalLoops.loopsOf(blockIndex);
+ if (!containingLoops.isEmpty()) {
+ out.print(prefix, " Containing loop headers:");
+ for (unsigned i = 0; i < containingLoops.size(); ++i)
+ out.print(" #", containingLoops[i]->header());
+ out.print("\n");
+ }
+ }
out.print(prefix, " Phi Nodes:");
for (size_t i = 0; i < block->phis.size(); ++i) {
Node* phiNode = block->phis[i];
@@ -423,6 +444,12 @@
}
}
+void Graph::invalidateCFG()
+{
+ m_dominators.invalidate();
+ m_naturalLoops.invalidate();
+}
+
} } // namespace JSC::DFG
#endif
Modified: branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGGraph.h (152138 => 152139)
--- branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGGraph.h 2013-06-27 23:41:19 UTC (rev 152138)
+++ branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGGraph.h 2013-06-28 00:02:12 UTC (rev 152139)
@@ -36,6 +36,7 @@
#include "DFGBasicBlock.h"
#include "DFGDominators.h"
#include "DFGLongLivedState.h"
+#include "DFGNaturalLoops.h"
#include "DFGNode.h"
#include "DFGNodeAllocator.h"
#include "DFGPlan.h"
@@ -676,6 +677,8 @@
}
}
+ void invalidateCFG();
+
Profiler::Compilation* compilation() { return m_plan.compilation.get(); }
DesiredIdentifiers& identifiers() { return m_plan.identifiers; }
@@ -703,6 +706,7 @@
HashSet<ExecutableBase*> m_executablesWhoseArgumentsEscaped;
BitVector m_preservedVars;
Dominators m_dominators;
+ NaturalLoops m_naturalLoops;
unsigned m_localVars;
unsigned m_parameterSlots;
Added: branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGNaturalLoops.cpp (0 => 152139)
--- branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGNaturalLoops.cpp (rev 0)
+++ branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGNaturalLoops.cpp 2013-06-28 00:02:12 UTC (rev 152139)
@@ -0,0 +1,160 @@
+/*
+ * Copyright (C) 2013 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 "DFGNaturalLoops.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGGraph.h"
+#include <wtf/CommaPrinter.h>
+
+namespace JSC { namespace DFG {
+
+void NaturalLoop::dump(PrintStream& out) const
+{
+ out.print("[Header: #", header(), ", Body:");
+ for (unsigned i = 0; i < m_body.size(); ++i)
+ out.print(" #", m_body[i]);
+ out.print("]");
+}
+
+NaturalLoops::NaturalLoops() { }
+NaturalLoops::~NaturalLoops() { }
+
+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
+ // then accumulate, for each loop header, multiple backward branching
+ // blocks. Then we backwards graph search from the backward branching
+ // blocks to their loop headers, which gives us all of the blocks in the
+ // loop body.
+
+ static const bool verbose = false;
+
+ graph.m_dominators.computeIfNecessary(graph);
+
+ m_loops.resize(0);
+
+ for (BlockIndex blockIndex = graph.m_blocks.size(); blockIndex--;) {
+ BasicBlock* block = graph.m_blocks[blockIndex].get();
+ if (!block)
+ continue;
+
+ for (unsigned i = graph.numSuccessors(block); i--;) {
+ BlockIndex successorIndex = graph.successor(block, i);
+ if (!graph.m_dominators.dominates(successorIndex, blockIndex))
+ continue;
+ bool found = false;
+ for (unsigned j = m_loops.size(); j--;) {
+ if (m_loops[i].header() == successorIndex) {
+ m_loops[i].addBlock(blockIndex);
+ found = true;
+ }
+ }
+ if (found)
+ continue;
+ NaturalLoop loop(successorIndex);
+ loop.addBlock(blockIndex);
+ m_loops.append(loop);
+ }
+ }
+
+ if (verbose)
+ dataLog("After bootstrap: ", *this, "\n");
+
+ FastBitVector seenBlocks;
+ Vector<BlockIndex, 4> blockWorklist;
+ seenBlocks.resize(graph.m_blocks.size());
+
+ for (unsigned i = m_loops.size(); i--;) {
+ NaturalLoop& loop = m_loops[i];
+
+ seenBlocks.clearAll();
+ ASSERT(blockWorklist.isEmpty());
+
+ if (verbose)
+ dataLog("Dealing with loop ", loop, "\n");
+
+ for (unsigned j = loop.size(); j--;) {
+ seenBlocks.set(loop[j]);
+ blockWorklist.append(loop[j]);
+ }
+
+ while (!blockWorklist.isEmpty()) {
+ BlockIndex blockIndex = blockWorklist.takeLast();
+
+ if (verbose)
+ dataLog(" Dealing with #", blockIndex, "\n");
+
+ if (blockIndex == loop.header())
+ continue;
+
+ BasicBlock* block = graph.m_blocks[blockIndex].get();
+ ASSERT(block);
+
+ for (unsigned j = block->m_predecessors.size(); j--;) {
+ BlockIndex predecessorIndex = block->m_predecessors[j];
+ if (seenBlocks.get(predecessorIndex))
+ continue;
+
+ loop.addBlock(predecessorIndex);
+ blockWorklist.append(predecessorIndex);
+ seenBlocks.set(predecessorIndex);
+ }
+ }
+ }
+
+ if (verbose)
+ dataLog("Results: ", *this, "\n");
+}
+
+Vector<const NaturalLoop*> NaturalLoops::loopsOf(BlockIndex blockIndex) const
+{
+ Vector<const NaturalLoop*> result;
+
+ for (unsigned i = m_loops.size(); i--;) {
+ if (m_loops[i].contains(blockIndex))
+ result.append(&m_loops[i]);
+ }
+
+ return result;
+}
+
+void NaturalLoops::dump(PrintStream& out) const
+{
+ out.print("NaturalLoops:{");
+ CommaPrinter comma;
+ for (unsigned i = 0; i < m_loops.size(); ++i)
+ out.print(comma, m_loops[i]);
+ out.print("}");
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
Added: branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGNaturalLoops.h (0 => 152139)
--- branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGNaturalLoops.h (rev 0)
+++ branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGNaturalLoops.h 2013-06-28 00:02:12 UTC (rev 152139)
@@ -0,0 +1,118 @@
+/*
+ * Copyright (C) 2013 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 DFGNaturalLoops_h
+#define DFGNaturalLoops_h
+
+#include <wtf/Platform.h>
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGAnalysis.h"
+#include "DFGCommon.h"
+
+namespace JSC { namespace DFG {
+
+class NaturalLoop {
+public:
+ NaturalLoop()
+ : m_header(NoBlock)
+ {
+ }
+
+ NaturalLoop(BlockIndex header)
+ : m_header(header)
+ {
+ }
+
+ void addBlock(BlockIndex block) { m_body.append(block); }
+
+ BlockIndex header() const { return m_header; }
+
+ unsigned size() const { return m_body.size(); }
+ BlockIndex at(unsigned i) const { return m_body[i]; }
+ BlockIndex operator[](unsigned i) const { return at(i); }
+
+ bool contains(BlockIndex block) const
+ {
+ for (unsigned i = m_body.size(); i--;) {
+ if (m_body[i] == block)
+ return true;
+ }
+ ASSERT(block != header()); // Header should be contained.
+ return false;
+ }
+
+ void dump(PrintStream&) const;
+private:
+ BlockIndex m_header;
+ Vector<BlockIndex, 4> m_body;
+};
+
+class NaturalLoops : public Analysis<NaturalLoops> {
+public:
+ NaturalLoops();
+ ~NaturalLoops();
+
+ void compute(Graph&);
+
+ unsigned numLoops() const
+ {
+ ASSERT(isValid());
+ return m_loops.size();
+ }
+ const NaturalLoop& loop(unsigned i) const
+ {
+ ASSERT(isValid());
+ return m_loops[i];
+ }
+
+ // Return either null if the block isn't a loop header, or the
+ // loop it belongs to.
+ const NaturalLoop* headerOf(BlockIndex blockIndex) const
+ {
+ for (unsigned i = m_loops.size(); i--;) {
+ if (m_loops[i].header() == blockIndex)
+ return &m_loops[i];
+ }
+ return 0;
+ }
+
+ // Return the indices of all loops this belongs to.
+ Vector<const NaturalLoop*> loopsOf(BlockIndex blockIndex) const;
+
+ void dump(PrintStream&) const;
+private:
+ // If we ever had a scalability problem in our natural loop finder, we could
+ // use some HashMap's here. But it just feels a heck of a lot less convenient.
+ Vector<NaturalLoop, 4> m_loops;
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGNaturalLoops_h
+
