Attachment 206817 Details for Bug 118750 – the patch

[patch] the patch

blah.patch (text/plain), 8.69 KB, created by Filip Pizlo on 2013-07-16 15:11:55 PDT

(hide)

Description:

Filename:

MIME Type:

Creator: Filip Pizlo

Created: 2013-07-16 15:11:55 PDT

Size: 8.69 KB

patch

obsolete

>Index: Source/JavaScriptCore/ChangeLog
>===================================================================
>--- Source/JavaScriptCore/ChangeLog	(revision 152744)
>+++ Source/JavaScriptCore/ChangeLog	(working copy)
>@@ -1,3 +1,29 @@
>+2013-07-16  Filip Pizlo  <fpizlo@apple.com>
>+
>+        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
>+
>+        Reviewed by NOBODY (OOPS!).
>+
>+        * 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):
>+
> 2013-07-16  Filip Pizlo  <fpizlo@apple.com>
> 
>         fourthTier: don't GC when shutting down the VM
>Index: Source/JavaScriptCore/dfg/DFGBasicBlock.h
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGBasicBlock.h	(revision 152744)
>+++ Source/JavaScriptCore/dfg/DFGBasicBlock.h	(working copy)
>@@ -127,6 +127,10 @@ struct BasicBlock : RefCounted<BasicBloc
>     Operands<AbstractValue> valuesAtHead;
>     Operands<AbstractValue> valuesAtTail;
>     
>+    // These fields are reserved for NaturalLoops.
>+    static const unsigned numberOfInnerMostLoopIndices = 2;
>+    unsigned innerMostLoopIndices[numberOfInnerMostLoopIndices];
>+
>     struct SSAData {
>         Operands<FlushFormat> flushFormatAtHead;
>         Operands<FlushFormat> flushFormatAtTail;
>Index: Source/JavaScriptCore/dfg/DFGNaturalLoops.cpp
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGNaturalLoops.cpp	(revision 152744)
>+++ Source/JavaScriptCore/dfg/DFGNaturalLoops.cpp	(working copy)
>@@ -84,7 +84,7 @@ void NaturalLoops::compute(Graph& graph)
>             }
>             if (found)
>                 continue;
>-            NaturalLoop loop(successor);
>+            NaturalLoop loop(successor, m_loops.size());
>             loop.addBlock(block);
>             m_loops.append(loop);
>         }
>@@ -131,6 +131,65 @@ void NaturalLoops::compute(Graph& graph)
>             }
>         }
>     }
>+
>+    // Figure out reverse mapping from blocks to loops.
>+    for (BlockIndex blockIndex = graph.numBlocks(); blockIndex--;) {
>+        BasicBlock* block = graph.block(blockIndex);
>+        if (!block)
>+            continue;
>+        for (unsigned i = BasicBlock::numberOfInnerMostLoopIndices; i--;)
>+            block->innerMostLoopIndices[i] = UINT_MAX;
>+    }
>+    for (unsigned i = m_loops.size(); i--;) {
>+        NaturalLoop& loop = m_loops[i];
>+        
>+        for (unsigned j = loop.size(); j--;) {
>+            BasicBlock* block = loop[j];
>+            
>+            for (unsigned k = 0; k < BasicBlock::numberOfInnerMostLoopIndices; ++k) {
>+                unsigned thisIndex = block->innerMostLoopIndices[k];
>+                if (thisIndex == UINT_MAX || loop.size() < m_loops[thisIndex].size()) {
>+                    for (unsigned l = BasicBlock::numberOfInnerMostLoopIndices; l-- > k + 1;)
>+                        block->innerMostLoopIndices[l] = block->innerMostLoopIndices[l - 1];
>+                    block->innerMostLoopIndices[k] = i;
>+                    break;
>+                }
>+            }
>+        }
>+    }
>+    
>+    // Now each block knows its inner-most loop and its next-to-inner-most loop. Use
>+    // this to figure out loop parenting.
>+    for (unsigned i = m_loops.size(); i--;) {
>+        NaturalLoop& loop = m_loops[i];
>+        RELEASE_ASSERT(loop.header()->innerMostLoopIndices[0] == i);
>+        
>+        loop.m_outerLoopIndex = loop.header()->innerMostLoopIndices[1];
>+    }
>+    
>+    if (validationEnabled()) {
>+        // Do some self-verification that we've done some of this correctly.
>+        
>+        for (BlockIndex blockIndex = graph.numBlocks(); blockIndex--;) {
>+            BasicBlock* block = graph.block(blockIndex);
>+            if (!block)
>+                continue;
>+            
>+            Vector<const NaturalLoop*> simpleLoopsOf;
>+            
>+            for (unsigned i = m_loops.size(); i--;) {
>+                if (m_loops[i].contains(block))
>+                    simpleLoopsOf.append(&m_loops[i]);
>+            }
>+            
>+            Vector<const NaturalLoop*> fancyLoopsOf = loopsOf(block);
>+            
>+            std::sort(simpleLoopsOf.begin(), simpleLoopsOf.end());
>+            std::sort(fancyLoopsOf.begin(), fancyLoopsOf.end());
>+            
>+            ASSERT(simpleLoopsOf == fancyLoopsOf);
>+        }
>+    }
>     
>     if (verbose)
>         dataLog("Results: ", *this, "\n");
>@@ -139,12 +198,8 @@ void NaturalLoops::compute(Graph& graph)
> Vector<const NaturalLoop*> NaturalLoops::loopsOf(BasicBlock* block) const
> {
>     Vector<const NaturalLoop*> result;
>-    
>-    for (unsigned i = m_loops.size(); i--;) {
>-        if (m_loops[i].contains(block))
>-            result.append(&m_loops[i]);
>-    }
>-    
>+    for (const NaturalLoop* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop))
>+        result.append(loop);
>     return result;
> }
> 
>Index: Source/JavaScriptCore/dfg/DFGNaturalLoops.h
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGNaturalLoops.h	(revision 152744)
>+++ Source/JavaScriptCore/dfg/DFGNaturalLoops.h	(working copy)
>@@ -36,20 +36,23 @@
> 
> 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; }
>     
>     unsigned size() const { return m_body.size(); }
>@@ -65,11 +68,22 @@ public:
>         ASSERT(block != header()); // Header should be contained.
>         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;
> };
> 
> class NaturalLoops : public Analysis<NaturalLoops> {
>@@ -94,13 +108,31 @@ public:
>     // loop it belongs to.
>     const NaturalLoop* headerOf(BasicBlock* block) const
>     {
>-        for (unsigned i = m_loops.size(); i--;) {
>-            if (m_loops[i].header() == block)
>-                return &m_loops[i];
>+        for (
>+            const NaturalLoop* loop = innerMostLoopOf(block);
>+            loop;
>+            loop = innerMostOuterLoop(*loop)) {
>+            if (loop->header() == block)
>+                return loop;
>         }
>         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];
>+    }
>+    
>     // Return the indices of all loops this belongs to.
>     Vector<const NaturalLoop*> loopsOf(BasicBlock*) const;
> 
>Index: Source/JavaScriptCore/dfg/DFGPlan.cpp
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGPlan.cpp	(revision 152744)
>+++ Source/JavaScriptCore/dfg/DFGPlan.cpp	(working copy)
>@@ -187,6 +187,13 @@ Plan::CompilationPath Plan::compileInThr
>     dfg.m_fixpointState = FixpointConverged;
> 
>     performStoreElimination(dfg);
>+    
>+    // 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);
>+    }
> 
> #if ENABLE(FTL_JIT)
>     if (Options::useExperimentalFTL()

Actions: View | Formatted Diff | Diff

Attachments on bug 118750: 206817 | 206819