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

Timestamp:

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

Author:

[email protected]

Message:

fourthTier: NaturalLoops should be able to quickly answer questions like "what loops own this basic block"
​https://bugs.webkit.org/show_bug.cgi?id=118750

Source/JavaScriptCore:

Reviewed by Mark Hahnenberg.

• dfg/DFGBasicBlock.h:

(BasicBlock):

• dfg/DFGNaturalLoops.cpp:

(JSC::DFG::NaturalLoops::compute):
(JSC::DFG::NaturalLoops::loopsOf):

• dfg/DFGNaturalLoops.h:

(DFG):
(JSC::DFG::NaturalLoop::NaturalLoop):
(NaturalLoop):
(JSC::DFG::NaturalLoop::index):
(JSC::DFG::NaturalLoop::isOuterMostLoop):
(JSC::DFG::NaturalLoop::addBlock):
(JSC::DFG::NaturalLoops::headerOf):
(JSC::DFG::NaturalLoops::innerMostLoopOf):
(NaturalLoops):
(JSC::DFG::NaturalLoops::innerMostOuterLoop):

• dfg/DFGPlan.cpp:

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

Source/WTF:

Reviewed by Mark Hahnenberg.

Add a utility function for inserting an element into a vector that has bounded size,
and where the insertion causes things to drop off the end.

• wtf/StdLibExtras.h:

(WTF):
(WTF::insertIntoBoundedVector):

File:

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

trunk/Source/JavaScriptCore/dfg/DFGNaturalLoops.h

@@ -37 +37 @@
 namespace JSC { namespace DFG {
 
+class NaturalLoops;
+
 class NaturalLoop {
 public:
     NaturalLoop()
         : m_header(0)
+        , m_outerLoopIndex(UINT_MAX)
     {
     }
     
-    NaturalLoop(BasicBlock* header)
+    NaturalLoop(BasicBlock* header, unsigned index)
         : m_header(header)
+        , m_outerLoopIndex(UINT_MAX)
+        , m_index(index)
     {
     }
-    
-    void addBlock(BasicBlock* block) { m_body.append(block); }
     
     BasicBlock* header() const { return m_header; }
@@ -66 +69 @@
         return false;
     }
+
+    // The index of this loop in NaturalLoops.
+    unsigned index() const { return m_index; }
+    
+    bool isOuterMostLoop() const { return m_outerLoopIndex == UINT_MAX; }
     
     void dump(PrintStream&) const;
 private:
+    friend class NaturalLoops;
+    
+    void addBlock(BasicBlock* block) { m_body.append(block); }
+    
     BasicBlock* m_header;
     Vector<BasicBlock*, 4> m_body;
+    unsigned m_outerLoopIndex;
+    unsigned m_index;
 };
 
@@ -95 +109 @@
     const NaturalLoop* headerOf(BasicBlock* block) const
     {
-        for (unsigned i = m_loops.size(); i--;) {
-            if (m_loops[i].header() == block)
-                return &m_loops[i];
+        const NaturalLoop* loop = innerMostLoopOf(block);
+        if (loop->header() == block)
+            return loop;
+        if (!ASSERT_DISABLED) {
+            for (; loop; loop = innerMostOuterLoop(*loop))
+                ASSERT(loop->header() != block);
         }
         return 0;
+    }
+    
+    const NaturalLoop* innerMostLoopOf(BasicBlock* block) const
+    {
+        unsigned index = block->innerMostLoopIndices[0];
+        if (index == UINT_MAX)
+            return 0;
+        return &m_loops[index];
+    }
+    
+    const NaturalLoop* innerMostOuterLoop(const NaturalLoop& loop) const
+    {
+        if (loop.m_outerLoopIndex == UINT_MAX)
+            return 0;
+        return &m_loops[loop.m_outerLoopIndex];
     }