webkitgtk-2.4.11webkitgtk-2.4.11

1 files changed, 39 insertions, 136 deletions

diff --git a/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp b/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp
index f38a44021..64651309e 100644
--- a/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp
+++ b/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2013-2015 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
@@ -36,10 +36,9 @@
 #include "DFGEdgeDominates.h"
 #include "DFGGraph.h"
 #include "DFGInsertionSet.h"
-#include "DFGNaturalLoops.h"
 #include "DFGPhase.h"
 #include "DFGSafeToExecute.h"
-#include "JSCInlines.h"
+#include "Operations.h"
 
 namespace JSC { namespace DFG {
 
@@ -47,7 +46,7 @@ namespace {
 
 struct LoopData {
     LoopData()
-        : preHeader(nullptr)
+        : preHeader(0)
     {
     }
     
@@ -63,24 +62,18 @@ class LICMPhase : public Phase {
 public:
     LICMPhase(Graph& graph)
         : Phase(graph, "LICM")
-        , m_state(graph)
         , m_interpreter(graph, m_state)
     {
     }
     
     bool run()
     {
-        DFG_ASSERT(m_graph, nullptr, m_graph.m_form == SSA);
+        ASSERT(m_graph.m_form == SSA);
         
-        m_graph.ensureDominators();
-        m_graph.ensureNaturalLoops();
-
-        if (verbose) {
-            dataLog("Graph before LICM:\n");
-            m_graph.dump();
-        }
+        m_graph.m_dominators.computeIfNecessary(m_graph);
+        m_graph.m_naturalLoops.computeIfNecessary(m_graph);
         
-        m_data.resize(m_graph.m_naturalLoops->numLoops());
+        m_data.resize(m_graph.m_naturalLoops.numLoops());
         
         // Figure out the set of things each loop writes to, not including blocks that
         // belong to inner loops. We fix this later.
@@ -88,83 +81,37 @@ public:
             BasicBlock* block = m_graph.block(blockIndex);
             if (!block)
                 continue;
-            
-            // Skip blocks that are proved to not execute.
-            // FIXME: This shouldn't be needed.
-            // https://bugs.webkit.org/show_bug.cgi?id=128584
-            if (!block->cfaHasVisited)
-                continue;
-            
-            const NaturalLoop* loop = m_graph.m_naturalLoops->innerMostLoopOf(block);
+            const NaturalLoop* loop = m_graph.m_naturalLoops.innerMostLoopOf(block);
             if (!loop)
                 continue;
             LoopData& data = m_data[loop->index()];
-            for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
-                Node* node = block->at(nodeIndex);
-                
-                // Don't look beyond parts of the code that definitely always exit.
-                // FIXME: This shouldn't be needed.
-                // https://bugs.webkit.org/show_bug.cgi?id=128584
-                if (node->op() == ForceOSRExit)
-                    break;
-
-                addWrites(m_graph, node, data.writes);
-            }
+            for (unsigned nodeIndex = block->size(); nodeIndex--;)
+                addWrites(m_graph, block->at(nodeIndex), data.writes);
         }
         
         // For each loop:
         // - Identify its pre-header.
         // - Make sure its outer loops know what it clobbers.
-        for (unsigned loopIndex = m_graph.m_naturalLoops->numLoops(); loopIndex--;) {
-            const NaturalLoop& loop = m_graph.m_naturalLoops->loop(loopIndex);
+        for (unsigned loopIndex = m_graph.m_naturalLoops.numLoops(); loopIndex--;) {
+            const NaturalLoop& loop = m_graph.m_naturalLoops.loop(loopIndex);
             LoopData& data = m_data[loop.index()];
-            
             for (
-                const NaturalLoop* outerLoop = m_graph.m_naturalLoops->innerMostOuterLoop(loop);
+                const NaturalLoop* outerLoop = m_graph.m_naturalLoops.innerMostOuterLoop(loop);
                 outerLoop;
-                outerLoop = m_graph.m_naturalLoops->innerMostOuterLoop(*outerLoop))
+                outerLoop = m_graph.m_naturalLoops.innerMostOuterLoop(*outerLoop))
                 m_data[outerLoop->index()].writes.addAll(data.writes);
             
             BasicBlock* header = loop.header();
-            BasicBlock* preHeader = nullptr;
-            unsigned numberOfPreHeaders = 0; // We're cool if this is 1.
-
-            // This is guaranteed because we expect the CFG not to have unreachable code. Therefore, a
-            // loop header must have a predecessor. (Also, we don't allow the root block to be a loop,
-            // which cuts out the one other way of having a loop header with only one predecessor.)
-            DFG_ASSERT(m_graph, header->at(0), header->predecessors.size() > 1);
-            
+            BasicBlock* preHeader = 0;
             for (unsigned i = header->predecessors.size(); i--;) {
                 BasicBlock* predecessor = header->predecessors[i];
-                if (m_graph.m_dominators->dominates(header, predecessor))
+                if (m_graph.m_dominators.dominates(header, predecessor))
                     continue;
-
+                RELEASE_ASSERT(!preHeader || preHeader == predecessor);
                 preHeader = predecessor;
-                ++numberOfPreHeaders;
             }
-
-            // We need to validate the pre-header. There are a bunch of things that could be wrong
-            // about it:
-            //
-            // - There might be more than one. This means that pre-header creation either did not run,
-            //   or some CFG transformation destroyed the pre-headers.
-            //
-            // - It may not be legal to exit at the pre-header. That would be a real bummer. Currently,
-            //   LICM assumes that it can always hoist checks. See
-            //   https://bugs.webkit.org/show_bug.cgi?id=148545. Though even with that fixed, we anyway
-            //   would need to check if it's OK to exit at the pre-header since if we can't then we
-            //   would have to restrict hoisting to non-exiting nodes.
-
-            if (numberOfPreHeaders != 1)
-                continue;
-
-            // This is guaranteed because the header has multiple predecessors and critical edges are
-            // broken. Therefore the predecessors must all have one successor, which implies that they
-            // must end in a Jump.
-            DFG_ASSERT(m_graph, preHeader->terminal(), preHeader->terminal()->op() == Jump);
-
-            if (!preHeader->terminal()->origin.exitOK)
-                continue;
+            
+            RELEASE_ASSERT(preHeader->last()->op() == Jump);
             
             data.preHeader = preHeader;
         }
@@ -175,7 +122,6 @@ public:
         // We try to hoist to the outer-most loop that permits it. Hoisting is valid if:
         // - The node doesn't write anything.
         // - The node doesn't read anything that the loop writes.
-        // - The preHeader is valid (i.e. it passed the validation above).
         // - The preHeader's state at tail makes the node safe to execute.
         // - The loop's children all belong to nodes that strictly dominate the loop header.
         // - The preHeader's state at tail is still valid. This is mostly to save compile
@@ -187,10 +133,17 @@ public:
         //
         // For maximum profit, we walk blocks in DFS order to ensure that we generally
         // tend to hoist dominators before dominatees.
+        Vector<BasicBlock*> depthFirst;
+        m_graph.getBlocksInDepthFirstOrder(depthFirst);
         Vector<const NaturalLoop*> loopStack;
         bool changed = false;
-        for (BasicBlock* block : m_graph.blocksInPreOrder()) {
-            const NaturalLoop* loop = m_graph.m_naturalLoops->innerMostLoopOf(block);
+        for (
+            unsigned depthFirstIndex = 0;
+            depthFirstIndex < depthFirst.size();
+            ++depthFirstIndex) {
+            
+            BasicBlock* block = depthFirst[depthFirstIndex];
+            const NaturalLoop* loop = m_graph.m_naturalLoops.innerMostLoopOf(block);
             if (!loop)
                 continue;
             
@@ -198,7 +151,7 @@ public:
             for (
                 const NaturalLoop* current = loop;
                 current;
-                current = m_graph.m_naturalLoops->innerMostOuterLoop(*current))
+                current = m_graph.m_naturalLoops.innerMostOuterLoop(*current))
                 loopStack.append(current);
             
             // Remember: the loop stack has the inner-most loop at index 0, so if we want
@@ -235,12 +188,6 @@ private:
     {
         Node* node = nodeRef;
         LoopData& data = m_data[loop->index()];
-
-        if (!data.preHeader) {
-            if (verbose)
-                dataLog("    Not hoisting ", node, " because the pre-header is invalid.\n");
-            return false;
-        }
         
         if (!data.preHeader->cfaDidFinish) {
             if (verbose)
@@ -256,47 +203,6 @@ private:
             return false;
         }
         
-        // FIXME: At this point if the hoisting of the full node fails but the node has type checks,
-        // we could still hoist just the checks.
-        // https://bugs.webkit.org/show_bug.cgi?id=144525
-        
-        // FIXME: If a node has a type check - even something like a CheckStructure - then we should
-        // only hoist the node if we know that it will execute on every loop iteration or if we know
-        // that the type check will always succeed at the loop pre-header through some other means
-        // (like looking at prediction propagation results). Otherwise, we might make a mistake like
-        // this:
-        //
-        // var o = ...; // sometimes null and sometimes an object with structure S1.
-        // for (...) {
-        //     if (o)
-        //         ... = o.f; // CheckStructure and GetByOffset, which we will currently hoist.
-        // }
-        //
-        // When we encounter such code, we'll hoist the CheckStructure and GetByOffset and then we
-        // will have a recompile. We'll then end up thinking that the get_by_id needs to be
-        // polymorphic, which is false.
-        //
-        // We can counter this by either having a control flow equivalence check, or by consulting
-        // prediction propagation to see if the check would always succeed. Prediction propagation
-        // would not be enough for things like:
-        //
-        // var p = ...; // some boolean predicate
-        // var o = {};
-        // if (p)
-        //     o.f = 42;
-        // for (...) {
-        //     if (p)
-        //         ... = o.f;
-        // }
-        //
-        // Prediction propagation can't tell us anything about the structure, and the CheckStructure
-        // will appear to be hoistable because the loop doesn't clobber structures. The cell check
-        // in the CheckStructure will be hoistable though, since prediction propagation can tell us
-        // that o is always SpecFinalObject. In cases like this, control flow equivalence is the
-        // only effective guard.
-        //
-        // https://bugs.webkit.org/show_bug.cgi?id=144527
-        
         if (readsOverlap(m_graph, node, data.writes)) {
             if (verbose) {
                 dataLog(
@@ -320,21 +226,18 @@ private:
                 "    Hoisting ", node, " from ", *fromBlock, " to ", *data.preHeader,
                 "\n");
         }
-
-        // FIXME: We should adjust the Check: flags on the edges of node. There are phases that assume
-        // that those flags are correct even if AI is stale.
-        // https://bugs.webkit.org/show_bug.cgi?id=148544
-        data.preHeader->insertBeforeTerminal(node);
-        node->owner = data.preHeader;
-        NodeOrigin originalOrigin = node->origin;
-        node->origin = data.preHeader->terminal()->origin.withSemantic(node->origin.semantic);
+        
+        data.preHeader->insertBeforeLast(node);
+        node->misc.owner = data.preHeader;
+        node->codeOriginForExitTarget = data.preHeader->last()->codeOriginForExitTarget;
         
         // Modify the states at the end of the preHeader of the loop we hoisted to,
-        // and all pre-headers inside the loop. This isn't a stability bottleneck right now
-        // because most loops are small and most blocks belong to few loops.
+        // and all pre-headers inside the loop.
+        // FIXME: This could become a scalability bottleneck. Fortunately, most loops
+        // are small and anyway we rapidly skip over basic blocks here.
         for (unsigned bodyIndex = loop->size(); bodyIndex--;) {
             BasicBlock* subBlock = loop->at(bodyIndex);
-            const NaturalLoop* subLoop = m_graph.m_naturalLoops->headerOf(subBlock);
+            const NaturalLoop* subLoop = m_graph.m_naturalLoops.headerOf(subBlock);
             if (!subLoop)
                 continue;
             BasicBlock* subPreHeader = m_data[subLoop->index()].preHeader;
@@ -347,9 +250,9 @@ private:
         // It just so happens that all of the nodes we currently know how to hoist
         // don't have var-arg children. That may change and then we can fix this
         // code. But for now we just assert that's the case.
-        DFG_ASSERT(m_graph, node, !(node->flags() & NodeHasVarArgs));
+        RELEASE_ASSERT(!(node->flags() & NodeHasVarArgs));
         
-        nodeRef = m_graph.addNode(SpecNone, Check, originalOrigin, node->children);
+        nodeRef = m_graph.addNode(SpecNone, Phantom, node->codeOrigin, node->children);
         
         return true;
     }