Changeset 153279 in webkit for trunk/Source/JavaScriptCore/dfg/DFGNaturalLoops.h

Timestamp:

Jul 24, 2013, 9:04:55 PM (12 years ago)

Author:

[email protected]

Message:

fourthTier: Add a phase to create loop pre-headers
​https://bugs.webkit.org/show_bug.cgi?id=118778

Reviewed by Oliver Hunt.

Add a loop pre-header creation phase. Any loop that doesn't already have
just one predecessor that isn't part of the loop has a pre-header
prepended. All non-loop predecessors then jump to that pre-header.

Also fix a handful of bugs:

• DFG::Analysis should set m_valid before running the analysis, since that makes it easier to use ASSERT(m_valid) in the analysis' methods, which may be called by the analysis before the analysis completes. NaturalLoops does this with loopsOf().

• NaturalLoops::headerOf() was missing a check for innerMostLoopOf() returning 0, since that'll happen if the block isn't in any loop.

• Change BlockInsertionSet to dethread the graph, since anyone using it will want to do so.

• Change dethreading to ignore SSA form graphs.

This also adds NaturalLoops::belongsTo(), which I always used in the
pre-header creation phase. I didn't end up using it but I'll probably use
it in the near future.

• JavaScriptCore.xcodeproj/project.pbxproj:
• dfg/DFGAnalysis.h:

(JSC::DFG::Analysis::computeIfNecessary):

• dfg/DFGBlockInsertionSet.cpp:

(JSC::DFG::BlockInsertionSet::execute):

• dfg/DFGCriticalEdgeBreakingPhase.cpp:

(JSC::DFG::CriticalEdgeBreakingPhase::breakCriticalEdge):

• dfg/DFGGraph.cpp:

(JSC::DFG::Graph::dethread):

• dfg/DFGLoopPreHeaderCreationPhase.cpp: Added.

(DFG):
(LoopPreHeaderCreationPhase):
(JSC::DFG::LoopPreHeaderCreationPhase::LoopPreHeaderCreationPhase):
(JSC::DFG::LoopPreHeaderCreationPhase::run):
(JSC::DFG::performLoopPreHeaderCreation):

• dfg/DFGLoopPreHeaderCreationPhase.h: Added.

(DFG):

• dfg/DFGNaturalLoops.h:

(NaturalLoop):
(JSC::DFG::NaturalLoops::headerOf):
(JSC::DFG::NaturalLoops::innerMostLoopOf):
(JSC::DFG::NaturalLoops::innerMostOuterLoop):
(JSC::DFG::NaturalLoops::belongsTo):
(NaturalLoops):

• dfg/DFGPlan.cpp:

(JSC::DFG::Plan::compileInThreadImpl):

Conflicts:

Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj

File:

• trunk/Source/JavaScriptCore/dfg/DFGNaturalLoops.h (modified) (4 diffs)

trunk/Source/JavaScriptCore/dfg/DFGNaturalLoops.h

@@ -59 +59 @@
     BasicBlock* at(unsigned i) const { return m_body[i]; }
     BasicBlock* operator[](unsigned i) const { return at(i); }
-    
+
+    // This is the slower, but simpler, way of asking if a block belongs to
+    // a natural loop. It's faster to call NaturalLoops::belongsTo(), which
+    // tries to be O(loop depth) rather than O(loop size). Loop depth is
+    // almost always smaller than loop size. A *lot* smaller.
     bool contains(BasicBlock* block) const
     {
@@ -109 +113 @@
     const NaturalLoop* headerOf(BasicBlock* block) const
     {
+        ASSERT(isValid());
         const NaturalLoop* loop = innerMostLoopOf(block);
+        if (!loop)
+            return 0;
         if (loop->header() == block)
             return loop;
@@ -121 +128 @@
     const NaturalLoop* innerMostLoopOf(BasicBlock* block) const
     {
+        ASSERT(isValid());
         unsigned index = block->innerMostLoopIndices[0];
         if (index == UINT_MAX)
@@ -129 +137 @@
     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);
+        
+        for (const NaturalLoop* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop)) {
+            if (loop == &candidateLoop)
+                return true;
+        }
+        return false;
     }