Title: [153279] trunk/Source/_javascript_Core
Revision
153279
Author
[email protected]
Date
2013-07-24 21:04:55 -0700 (Wed, 24 Jul 2013)

Log 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.

* _javascript_Core.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/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj

Modified Paths

Added Paths

Diff

Modified: trunk/Source/_javascript_Core/ChangeLog (153278 => 153279)


--- trunk/Source/_javascript_Core/ChangeLog	2013-07-25 04:04:53 UTC (rev 153278)
+++ trunk/Source/_javascript_Core/ChangeLog	2013-07-25 04:04:55 UTC (rev 153279)
@@ -1,5 +1,62 @@
 2013-07-16  Filip Pizlo  <[email protected]>
 
+        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.
+        
+        * _javascript_Core.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):
+
+2013-07-16  Filip Pizlo  <[email protected]>
+
         fourthTier: Rationalize Node::replacement
         https://bugs.webkit.org/show_bug.cgi?id=118774
 

Modified: trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj (153278 => 153279)


--- trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj	2013-07-25 04:04:53 UTC (rev 153278)
+++ trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj	2013-07-25 04:04:55 UTC (rev 153279)
@@ -770,6 +770,8 @@
 		A74DE1D0120B875600D40D5B /* ARMv7Assembler.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A74DE1CB120B86D600D40D5B /* ARMv7Assembler.cpp */; };
 		A75706DE118A2BCF0057F88F /* JITArithmetic32_64.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A75706DD118A2BCF0057F88F /* JITArithmetic32_64.cpp */; };
 		A766B44F0EE8DCD1009518CA /* ExecutableAllocator.h in Headers */ = {isa = PBXBuildFile; fileRef = A7B48DB50EE74CFC00DCBDB6 /* ExecutableAllocator.h */; settings = {ATTRIBUTES = (Private, ); }; };
+		A767B5B517A0B9650063D940 /* DFGLoopPreHeaderCreationPhase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A767B5B317A0B9650063D940 /* DFGLoopPreHeaderCreationPhase.cpp */; };
+		A767B5B617A0B9650063D940 /* DFGLoopPreHeaderCreationPhase.h in Headers */ = {isa = PBXBuildFile; fileRef = A767B5B417A0B9650063D940 /* DFGLoopPreHeaderCreationPhase.h */; settings = {ATTRIBUTES = (Private, ); }; };
 		A76C51761182748D00715B05 /* JSInterfaceJIT.h in Headers */ = {isa = PBXBuildFile; fileRef = A76C51741182748D00715B05 /* JSInterfaceJIT.h */; settings = {ATTRIBUTES = (Private, ); }; };
 		A76F279415F13C9600517D67 /* UnlinkedCodeBlock.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A79E781E15EECBA80047C855 /* UnlinkedCodeBlock.cpp */; };
 		A76F54A313B28AAB00EF2BCE /* JITWriteBarrier.h in Headers */ = {isa = PBXBuildFile; fileRef = A76F54A213B28AAB00EF2BCE /* JITWriteBarrier.h */; settings = {ATTRIBUTES = (Private, ); }; };
@@ -1828,6 +1830,8 @@
 		A7482E37116A697B003B0712 /* JSWeakObjectMapRefInternal.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JSWeakObjectMapRefInternal.h; sourceTree = "<group>"; };
 		A74DE1CB120B86D600D40D5B /* ARMv7Assembler.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ARMv7Assembler.cpp; sourceTree = "<group>"; };
 		A75706DD118A2BCF0057F88F /* JITArithmetic32_64.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = JITArithmetic32_64.cpp; sourceTree = "<group>"; };
+		A767B5B317A0B9650063D940 /* DFGLoopPreHeaderCreationPhase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGLoopPreHeaderCreationPhase.cpp; path = dfg/DFGLoopPreHeaderCreationPhase.cpp; sourceTree = "<group>"; };
+		A767B5B417A0B9650063D940 /* DFGLoopPreHeaderCreationPhase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGLoopPreHeaderCreationPhase.h; path = dfg/DFGLoopPreHeaderCreationPhase.h; sourceTree = "<group>"; };
 		A767FF9F14F4502900789059 /* JSCTypedArrayStubs.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JSCTypedArrayStubs.h; sourceTree = "<group>"; };
 		A76C51741182748D00715B05 /* JSInterfaceJIT.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JSInterfaceJIT.h; sourceTree = "<group>"; };
 		A76F54A213B28AAB00EF2BCE /* JITWriteBarrier.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JITWriteBarrier.h; sourceTree = "<group>"; };
@@ -2155,9 +2159,9 @@
 		034768DFFF38A50411DB9C8B /* Products */ = {
 			isa = PBXGroup;
 			children = (
+				0FF922CF14F46B130041A24E /* JSCLLIntOffsetsExtractor */,
 				932F5BD90822A1C700736975 /* _javascript_Core.framework */,
 				932F5BE10822A1C700736975 /* jsc */,
-				0FF922CF14F46B130041A24E /* JSCLLIntOffsetsExtractor */,
 				141211200A48793C00480255 /* minidom */,
 				14BD59BF0A3E8F9000BAF59C /* testapi */,
 				6511230514046A4C002B101D /* testRegExp */,
@@ -3121,6 +3125,8 @@
 				A7D89CED17A0B8CC00773AD8 /* DFGLivenessAnalysisPhase.h */,
 				0FB4B51C16B62772003F696B /* DFGLongLivedState.cpp */,
 				0FB4B51D16B62772003F696B /* DFGLongLivedState.h */,
+				A767B5B317A0B9650063D940 /* DFGLoopPreHeaderCreationPhase.cpp */,
+				A767B5B417A0B9650063D940 /* DFGLoopPreHeaderCreationPhase.h */,
 				0F2BDC3D1522801700CD8910 /* DFGMinifiedGraph.h */,
 				0FB4B51016B3A964003F696B /* DFGMinifiedID.h */,
 				0F2BDC4C1522818300CD8910 /* DFGMinifiedNode.cpp */,
@@ -3524,6 +3530,7 @@
 				A73A535B1799CD5D00170C19 /* DFGLazyJSValue.h in Headers */,
 				A7D89CFC17A0B8CC00773AD8 /* DFGLivenessAnalysisPhase.h in Headers */,
 				0FF0F19B16B729FA005DF95B /* DFGLongLivedState.h in Headers */,
+				A767B5B617A0B9650063D940 /* DFGLoopPreHeaderCreationPhase.h in Headers */,
 				0F2BDC451522801B00CD8910 /* DFGMinifiedGraph.h in Headers */,
 				0F2E892D16D02BAF009E4FD2 /* DFGMinifiedID.h in Headers */,
 				0F2BDC461522802000CD8910 /* DFGMinifiedNode.h in Headers */,
@@ -4371,6 +4378,7 @@
 				A73A535A1799CD5D00170C19 /* DFGLazyJSValue.cpp in Sources */,
 				A7D89CFB17A0B8CC00773AD8 /* DFGLivenessAnalysisPhase.cpp in Sources */,
 				0FF0F19916B729F6005DF95B /* DFGLongLivedState.cpp in Sources */,
+				A767B5B517A0B9650063D940 /* DFGLoopPreHeaderCreationPhase.cpp in Sources */,
 				0F2BDC4D1522818600CD8910 /* DFGMinifiedNode.cpp in Sources */,
 				A737810D1799EA2E00817533 /* DFGNaturalLoops.cpp in Sources */,
 				0FF0F19C16B72A03005DF95B /* DFGNode.cpp in Sources */,

Modified: trunk/Source/_javascript_Core/dfg/DFGAnalysis.h (153278 => 153279)


--- trunk/Source/_javascript_Core/dfg/DFGAnalysis.h	2013-07-25 04:04:53 UTC (rev 153278)
+++ trunk/Source/_javascript_Core/dfg/DFGAnalysis.h	2013-07-25 04:04:55 UTC (rev 153279)
@@ -55,8 +55,10 @@
     {
         if (m_valid)
             return;
+        // Set to true early, since the analysis may choose to call its own methods in
+        // compute() and it may want to ASSERT() validity in those methods.
+        m_valid = true;
         static_cast<T*>(this)->compute(graph);
-        m_valid = true;
     }
     
     bool isValid() const { return m_valid; }

Modified: trunk/Source/_javascript_Core/dfg/DFGBlockInsertionSet.cpp (153278 => 153279)


--- trunk/Source/_javascript_Core/dfg/DFGBlockInsertionSet.cpp	2013-07-25 04:04:53 UTC (rev 153278)
+++ trunk/Source/_javascript_Core/dfg/DFGBlockInsertionSet.cpp	2013-07-25 04:04:55 UTC (rev 153279)
@@ -91,6 +91,7 @@
     
     // And finally, invalidate all analyses that rely on the CFG.
     m_graph.invalidateCFG();
+    m_graph.dethread();
     
     return true;
 }

Modified: trunk/Source/_javascript_Core/dfg/DFGCriticalEdgeBreakingPhase.cpp (153278 => 153279)


--- trunk/Source/_javascript_Core/dfg/DFGCriticalEdgeBreakingPhase.cpp	2013-07-25 04:04:53 UTC (rev 153278)
+++ trunk/Source/_javascript_Core/dfg/DFGCriticalEdgeBreakingPhase.cpp	2013-07-25 04:04:55 UTC (rev 153279)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2012, 2013 Apple Inc. All rights reserved.
+ * 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
@@ -73,8 +73,6 @@
 private:
     void breakCriticalEdge(BasicBlock* predecessor, BasicBlock** successor)
     {
-        m_graph.dethread();
-        
         BasicBlock* pad = m_insertionSet.insertBefore(*successor);
         pad->appendNode(
             m_graph, SpecNone, Jump, (*successor)->at(0)->codeOrigin, OpInfo(*successor));

Modified: trunk/Source/_javascript_Core/dfg/DFGGraph.cpp (153278 => 153279)


--- trunk/Source/_javascript_Core/dfg/DFGGraph.cpp	2013-07-25 04:04:53 UTC (rev 153278)
+++ trunk/Source/_javascript_Core/dfg/DFGGraph.cpp	2013-07-25 04:04:55 UTC (rev 153279)
@@ -419,7 +419,7 @@
 
 void Graph::dethread()
 {
-    if (m_form == LoadStore)
+    if (m_form == LoadStore || m_form == SSA)
         return;
     
     if (logCompilationChanges())

Added: trunk/Source/_javascript_Core/dfg/DFGLoopPreHeaderCreationPhase.cpp (0 => 153279)


--- trunk/Source/_javascript_Core/dfg/DFGLoopPreHeaderCreationPhase.cpp	                        (rev 0)
+++ trunk/Source/_javascript_Core/dfg/DFGLoopPreHeaderCreationPhase.cpp	2013-07-25 04:04:55 UTC (rev 153279)
@@ -0,0 +1,111 @@
+/*
+ * 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 "DFGLoopPreHeaderCreationPhase.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBasicBlockInlines.h"
+#include "DFGBlockInsertionSet.h"
+#include "DFGGraph.h"
+#include "DFGPhase.h"
+#include "Operations.h"
+#include <wtf/HashMap.h>
+
+namespace JSC { namespace DFG {
+
+class LoopPreHeaderCreationPhase : public Phase {
+public:
+    LoopPreHeaderCreationPhase(Graph& graph)
+        : Phase(graph, "loop pre-header creation")
+        , m_insertionSet(graph)
+    {
+    }
+    
+    bool run()
+    {
+        m_graph.m_dominators.computeIfNecessary(m_graph);
+        m_graph.m_naturalLoops.computeIfNecessary(m_graph);
+        
+        for (unsigned loopIndex = m_graph.m_naturalLoops.numLoops(); loopIndex--;) {
+            const NaturalLoop& loop = m_graph.m_naturalLoops.loop(loopIndex);
+            BasicBlock* existingPreHeader = 0;
+            bool needsNewPreHeader = false;
+            for (unsigned predecessorIndex = loop.header()->predecessors.size(); predecessorIndex--;) {
+                BasicBlock* predecessor = loop.header()->predecessors[predecessorIndex];
+                if (m_graph.m_dominators.dominates(loop.header(), predecessor))
+                    continue;
+                if (!existingPreHeader) {
+                    existingPreHeader = predecessor;
+                    continue;
+                }
+                if (existingPreHeader == predecessor)
+                    continue;
+                needsNewPreHeader = true;
+                break;
+            }
+            if (!needsNewPreHeader)
+                continue;
+            
+            BasicBlock* preHeader = m_insertionSet.insertBefore(loop.header());
+            preHeader->appendNode(
+                m_graph, SpecNone, Jump, loop.header()->at(0)->codeOrigin, OpInfo(loop.header()));
+            
+            for (unsigned predecessorIndex = 0; predecessorIndex < loop.header()->predecessors.size(); predecessorIndex++) {
+                BasicBlock* predecessor = loop.header()->predecessors[predecessorIndex];
+                if (m_graph.m_dominators.dominates(loop.header(), predecessor))
+                    continue;
+                loop.header()->predecessors[predecessorIndex--] = loop.header()->predecessors.last();
+                loop.header()->predecessors.takeLast();
+                for (unsigned successorIndex = predecessor->numSuccessors(); successorIndex--;) {
+                    BasicBlock*& successor = predecessor->successor(successorIndex);
+                    if (successor != loop.header())
+                        continue;
+                    successor = preHeader;
+                    preHeader->predecessors.append(predecessor);
+                }
+            }
+            
+            loop.header()->predecessors.append(preHeader);
+        }
+        
+        return m_insertionSet.execute();
+    }
+
+    BlockInsertionSet m_insertionSet;
+};
+
+bool performLoopPreHeaderCreation(Graph& graph)
+{
+    SamplingRegion samplingRegion("DFG Loop Pre-Header Creation Phase");
+    return runPhase<LoopPreHeaderCreationPhase>(graph);
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+

Copied: trunk/Source/_javascript_Core/dfg/DFGLoopPreHeaderCreationPhase.h (from rev 153278, trunk/Source/_javascript_Core/dfg/DFGAnalysis.h) (0 => 153279)


--- trunk/Source/_javascript_Core/dfg/DFGLoopPreHeaderCreationPhase.h	                        (rev 0)
+++ trunk/Source/_javascript_Core/dfg/DFGLoopPreHeaderCreationPhase.h	2013-07-25 04:04:55 UTC (rev 153279)
@@ -0,0 +1,47 @@
+/*
+ * 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 DFGLoopPreHeaderCreationPhase_h
+#define DFGLoopPreHeaderCreationPhase_h
+
+#include <wtf/Platform.h>
+
+#if ENABLE(DFG_JIT)
+
+namespace JSC { namespace DFG {
+
+class Graph;
+
+// Inserts dummy basic blocks before any loop headers that don't already have
+// a single non-loop predecessor.
+
+bool performLoopPreHeaderCreation(Graph&);
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGLoopPreHeaderCreationPhase_h
+

Modified: trunk/Source/_javascript_Core/dfg/DFGNaturalLoops.h (153278 => 153279)


--- trunk/Source/_javascript_Core/dfg/DFGNaturalLoops.h	2013-07-25 04:04:53 UTC (rev 153278)
+++ trunk/Source/_javascript_Core/dfg/DFGNaturalLoops.h	2013-07-25 04:04:55 UTC (rev 153279)
@@ -58,7 +58,11 @@
     unsigned size() const { return m_body.size(); }
     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
     {
         for (unsigned i = m_body.size(); i--;) {
@@ -108,7 +112,10 @@
     // loop it belongs to.
     const NaturalLoop* headerOf(BasicBlock* block) const
     {
+        ASSERT(isValid());
         const NaturalLoop* loop = innerMostLoopOf(block);
+        if (!loop)
+            return 0;
         if (loop->header() == block)
             return loop;
         if (!ASSERT_DISABLED) {
@@ -120,6 +127,7 @@
     
     const NaturalLoop* innerMostLoopOf(BasicBlock* block) const
     {
+        ASSERT(isValid());
         unsigned index = block->innerMostLoopIndices[0];
         if (index == UINT_MAX)
             return 0;
@@ -128,11 +136,26 @@
     
     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;
+    }
+    
     // Return the indices of all loops this belongs to.
     Vector<const NaturalLoop*> loopsOf(BasicBlock*) const;
 

Modified: trunk/Source/_javascript_Core/dfg/DFGPlan.cpp (153278 => 153279)


--- trunk/Source/_javascript_Core/dfg/DFGPlan.cpp	2013-07-25 04:04:53 UTC (rev 153278)
+++ trunk/Source/_javascript_Core/dfg/DFGPlan.cpp	2013-07-25 04:04:55 UTC (rev 153279)
@@ -43,6 +43,7 @@
 #include "DFGFixupPhase.h"
 #include "DFGJITCompiler.h"
 #include "DFGLivenessAnalysisPhase.h"
+#include "DFGLoopPreHeaderCreationPhase.h"
 #include "DFGOSRAvailabilityAnalysisPhase.h"
 #include "DFGPredictionInjectionPhase.h"
 #include "DFGPredictionPropagationPhase.h"
@@ -201,6 +202,7 @@
         && FTL::canCompile(dfg)) {
         
         performCriticalEdgeBreaking(dfg);
+        performLoopPreHeaderCreation(dfg);
         performCPSRethreading(dfg);
         performSSAConversion(dfg);
         performLivenessAnalysis(dfg);
_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes

Reply via email to