Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (153256 => 153257)
--- trunk/Source/_javascript_Core/ChangeLog 2013-07-25 04:04:05 UTC (rev 153256)
+++ trunk/Source/_javascript_Core/ChangeLog 2013-07-25 04:04:08 UTC (rev 153257)
@@ -1,5 +1,71 @@
2013-06-27 Filip Pizlo <[email protected]>
+ 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 <[email protected]>
+
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: trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj (153256 => 153257)
--- trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2013-07-25 04:04:05 UTC (rev 153256)
+++ trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2013-07-25 04:04:08 UTC (rev 153257)
@@ -754,6 +754,9 @@
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 */; settings = {ATTRIBUTES = (Private, ); }; };
+ A737810D1799EA2E00817533 /* DFGNaturalLoops.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A737810A1799EA2E00817533 /* DFGNaturalLoops.cpp */; };
+ A737810E1799EA2E00817533 /* DFGNaturalLoops.h in Headers */ = {isa = PBXBuildFile; fileRef = A737810B1799EA2E00817533 /* DFGNaturalLoops.h */; settings = {ATTRIBUTES = (Private, ); }; };
A7386554118697B400540279 /* SpecializedThunkJIT.h in Headers */ = {isa = PBXBuildFile; fileRef = A7386551118697B400540279 /* SpecializedThunkJIT.h */; };
A7386555118697B400540279 /* ThunkGenerators.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A7386552118697B400540279 /* ThunkGenerators.cpp */; };
A7386556118697B400540279 /* ThunkGenerators.h in Headers */ = {isa = PBXBuildFile; fileRef = A7386553118697B400540279 /* ThunkGenerators.h */; settings = {ATTRIBUTES = (Private, ); }; };
@@ -1794,6 +1797,9 @@
A729009B17976C6000317298 /* MacroAssemblerARMv7.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = MacroAssemblerARMv7.cpp; 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>"; };
A7386552118697B400540279 /* ThunkGenerators.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ThunkGenerators.cpp; sourceTree = "<group>"; };
A7386553118697B400540279 /* ThunkGenerators.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ThunkGenerators.h; sourceTree = "<group>"; };
@@ -2117,9 +2123,9 @@
034768DFFF38A50411DB9C8B /* Products */ = {
isa = PBXGroup;
children = (
- 932F5BE10822A1C700736975 /* jsc */,
0FF922CF14F46B130041A24E /* JSCLLIntOffsetsExtractor */,
932F5BD90822A1C700736975 /* _javascript_Core.framework */,
+ 932F5BE10822A1C700736975 /* jsc */,
141211200A48793C00480255 /* minidom */,
14BD59BF0A3E8F9000BAF59C /* testapi */,
6511230514046A4C002B101D /* testRegExp */,
@@ -2995,6 +3001,7 @@
0F62016F143FCD2F0068B77C /* DFGAbstractValue.h */,
0F66E16814DF3F1300B7B2E4 /* DFGAdjacencyList.h */,
0FB4B51916B62772003F696B /* DFGAllocator.h */,
+ A73781091799EA2E00817533 /* DFGAnalysis.h */,
0F1E3A431534CBAD000F9456 /* DFGArgumentPosition.h */,
0F16015A156198BF00C2587C /* DFGArgumentsSimplificationPhase.cpp */,
0F16015B156198BF00C2587C /* DFGArgumentsSimplificationPhase.h */,
@@ -3074,6 +3081,8 @@
0FB4B51016B3A964003F696B /* DFGMinifiedID.h */,
0F2BDC4C1522818300CD8910 /* DFGMinifiedNode.cpp */,
0F2BDC3E1522801700CD8910 /* DFGMinifiedNode.h */,
+ A737810A1799EA2E00817533 /* DFGNaturalLoops.cpp */,
+ A737810B1799EA2E00817533 /* DFGNaturalLoops.h */,
0FB4B51E16B62772003F696B /* DFGNode.cpp */,
86ECA3E9132DEF1C002B2AD7 /* DFGNode.h */,
0FB4B51F16B62772003F696B /* DFGNodeAllocator.h */,
@@ -3415,6 +3424,7 @@
0F620177143FCD3F0068B77C /* DFGAbstractValue.h in Headers */,
0F66E16B14DF3F1600B7B2E4 /* DFGAdjacencyList.h in Headers */,
0FFB921816D02EB20055A5DB /* DFGAllocator.h in Headers */,
+ A737810C1799EA2E00817533 /* DFGAnalysis.h in Headers */,
0F1E3A461534CBAF000F9456 /* DFGArgumentPosition.h in Headers */,
0F16015E156198C900C2587C /* DFGArgumentsSimplificationPhase.h in Headers */,
0F05C3B41683CF9200BAF45B /* DFGArrayifySlowPathGenerator.h in Headers */,
@@ -3464,6 +3474,7 @@
0F2BDC451522801B00CD8910 /* DFGMinifiedGraph.h in Headers */,
0F2E892D16D02BAF009E4FD2 /* DFGMinifiedID.h in Headers */,
0F2BDC461522802000CD8910 /* DFGMinifiedNode.h in Headers */,
+ A737810E1799EA2E00817533 /* DFGNaturalLoops.h in Headers */,
86ECA3EA132DEF1C002B2AD7 /* DFGNode.h in Headers */,
0FFB921B16D02F010055A5DB /* DFGNodeAllocator.h in Headers */,
0FA581BB150E953000B9A2D9 /* DFGNodeFlags.h in Headers */,
@@ -4299,6 +4310,7 @@
A73A535A1799CD5D00170C19 /* DFGLazyJSValue.cpp in Sources */,
0FF0F19916B729F6005DF95B /* DFGLongLivedState.cpp in Sources */,
0F2BDC4D1522818600CD8910 /* DFGMinifiedNode.cpp in Sources */,
+ A737810D1799EA2E00817533 /* DFGNaturalLoops.cpp in Sources */,
0FF0F19C16B72A03005DF95B /* DFGNode.cpp in Sources */,
0FA581BA150E952C00B9A2D9 /* DFGNodeFlags.cpp in Sources */,
86EC9DCF1328DF82002B2AD7 /* DFGOperations.cpp in Sources */,
Copied: trunk/Source/_javascript_Core/dfg/DFGAnalysis.h (from rev 153256, trunk/Source/_javascript_Core/dfg/DFGDominators.h) (0 => 153257)
--- trunk/Source/_javascript_Core/dfg/DFGAnalysis.h (rev 0)
+++ trunk/Source/_javascript_Core/dfg/DFGAnalysis.h 2013-07-25 04:04:08 UTC (rev 153257)
@@ -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: trunk/Source/_javascript_Core/dfg/DFGCFGSimplificationPhase.cpp (153256 => 153257)
--- trunk/Source/_javascript_Core/dfg/DFGCFGSimplificationPhase.cpp 2013-07-25 04:04:05 UTC (rev 153256)
+++ trunk/Source/_javascript_Core/dfg/DFGCFGSimplificationPhase.cpp 2013-07-25 04:04:08 UTC (rev 153257)
@@ -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: trunk/Source/_javascript_Core/dfg/DFGDisassembler.cpp (153256 => 153257)
--- trunk/Source/_javascript_Core/dfg/DFGDisassembler.cpp 2013-07-25 04:04:05 UTC (rev 153256)
+++ trunk/Source/_javascript_Core/dfg/DFGDisassembler.cpp 2013-07-25 04:04:08 UTC (rev 153257)
@@ -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: trunk/Source/_javascript_Core/dfg/DFGDominators.cpp (153256 => 153257)
--- trunk/Source/_javascript_Core/dfg/DFGDominators.cpp 2013-07-25 04:04:05 UTC (rev 153256)
+++ trunk/Source/_javascript_Core/dfg/DFGDominators.cpp 2013-07-25 04:04:08 UTC (rev 153257)
@@ -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: trunk/Source/_javascript_Core/dfg/DFGDominators.h (153256 => 153257)
--- trunk/Source/_javascript_Core/dfg/DFGDominators.h 2013-07-25 04:04:05 UTC (rev 153256)
+++ trunk/Source/_javascript_Core/dfg/DFGDominators.h 2013-07-25 04:04:08 UTC (rev 153257)
@@ -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: trunk/Source/_javascript_Core/dfg/DFGGraph.cpp (153256 => 153257)
--- trunk/Source/_javascript_Core/dfg/DFGGraph.cpp 2013-07-25 04:04:05 UTC (rev 153256)
+++ trunk/Source/_javascript_Core/dfg/DFGGraph.cpp 2013-07-25 04:04:08 UTC (rev 153257)
@@ -302,6 +302,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];
@@ -438,6 +459,12 @@
}
}
+void Graph::invalidateCFG()
+{
+ m_dominators.invalidate();
+ m_naturalLoops.invalidate();
+}
+
} } // namespace JSC::DFG
#endif
Modified: trunk/Source/_javascript_Core/dfg/DFGGraph.h (153256 => 153257)
--- trunk/Source/_javascript_Core/dfg/DFGGraph.h 2013-07-25 04:04:05 UTC (rev 153256)
+++ trunk/Source/_javascript_Core/dfg/DFGGraph.h 2013-07-25 04:04:08 UTC (rev 153257)
@@ -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"
@@ -681,6 +682,8 @@
}
}
+ void invalidateCFG();
+
Profiler::Compilation* compilation() { return m_plan.compilation.get(); }
DesiredIdentifiers& identifiers() { return m_plan.identifiers; }
@@ -708,6 +711,7 @@
HashSet<ExecutableBase*> m_executablesWhoseArgumentsEscaped;
BitVector m_preservedVars;
Dominators m_dominators;
+ NaturalLoops m_naturalLoops;
unsigned m_localVars;
unsigned m_parameterSlots;
Added: trunk/Source/_javascript_Core/dfg/DFGNaturalLoops.cpp (0 => 153257)
--- trunk/Source/_javascript_Core/dfg/DFGNaturalLoops.cpp (rev 0)
+++ trunk/Source/_javascript_Core/dfg/DFGNaturalLoops.cpp 2013-07-25 04:04:08 UTC (rev 153257)
@@ -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: trunk/Source/_javascript_Core/dfg/DFGNaturalLoops.h (0 => 153257)
--- trunk/Source/_javascript_Core/dfg/DFGNaturalLoops.h (rev 0)
+++ trunk/Source/_javascript_Core/dfg/DFGNaturalLoops.h 2013-07-25 04:04:08 UTC (rev 153257)
@@ -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
+