webkitgtk-2.12.3webkitgtk-2.12.3

1 files changed, 136 insertions, 39 deletions

diff --git a/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp b/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp
index 64651309e..f38a44021 100644
--- a/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp
+++ b/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2013 Apple Inc. All rights reserved.
+ * Copyright (C) 2013-2015 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,9 +36,10 @@
 #include "DFGEdgeDominates.h"
 #include "DFGGraph.h"
 #include "DFGInsertionSet.h"
+#include "DFGNaturalLoops.h"
 #include "DFGPhase.h"
 #include "DFGSafeToExecute.h"
-#include "Operations.h"
+#include "JSCInlines.h"
 
 namespace JSC { namespace DFG {
 
@@ -46,7 +47,7 @@ namespace {
 
 struct LoopData {
     LoopData()
-        : preHeader(0)
+        : preHeader(nullptr)
     {
     }
     
@@ -62,18 +63,24 @@ class LICMPhase : public Phase {
 public:
     LICMPhase(Graph& graph)
         : Phase(graph, "LICM")
+        , m_state(graph)
         , m_interpreter(graph, m_state)
     {
     }
     
     bool run()
     {
-        ASSERT(m_graph.m_form == SSA);
+        DFG_ASSERT(m_graph, nullptr, m_graph.m_form == SSA);
         
-        m_graph.m_dominators.computeIfNecessary(m_graph);
-        m_graph.m_naturalLoops.computeIfNecessary(m_graph);
+        m_graph.ensureDominators();
+        m_graph.ensureNaturalLoops();
+
+        if (verbose) {
+            dataLog("Graph before LICM:\n");
+            m_graph.dump();
+        }
         
-        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.
@@ -81,37 +88,83 @@ public:
             BasicBlock* block = m_graph.block(blockIndex);
             if (!block)
                 continue;
-            const NaturalLoop* loop = m_graph.m_naturalLoops.innerMostLoopOf(block);
+            
+            // 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);
             if (!loop)
                 continue;
             LoopData& data = m_data[loop->index()];
-            for (unsigned nodeIndex = block->size(); nodeIndex--;)
-                addWrites(m_graph, block->at(nodeIndex), data.writes);
+            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 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 = 0;
+            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);
+            
             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;
             }
-            
-            RELEASE_ASSERT(preHeader->last()->op() == Jump);
+
+            // 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;
             
             data.preHeader = preHeader;
         }
@@ -122,6 +175,7 @@ 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
@@ -133,17 +187,10 @@ 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 (
-            unsigned depthFirstIndex = 0;
-            depthFirstIndex < depthFirst.size();
-            ++depthFirstIndex) {
-            
-            BasicBlock* block = depthFirst[depthFirstIndex];
-            const NaturalLoop* loop = m_graph.m_naturalLoops.innerMostLoopOf(block);
+        for (BasicBlock* block : m_graph.blocksInPreOrder()) {
+            const NaturalLoop* loop = m_graph.m_naturalLoops->innerMostLoopOf(block);
             if (!loop)
                 continue;
             
@@ -151,7 +198,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
@@ -188,6 +235,12 @@ 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)
@@ -203,6 +256,47 @@ 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(
@@ -226,18 +320,21 @@ private:
                 "    Hoisting ", node, " from ", *fromBlock, " to ", *data.preHeader,
                 "\n");
         }
-        
-        data.preHeader->insertBeforeLast(node);
-        node->misc.owner = data.preHeader;
-        node->codeOriginForExitTarget = data.preHeader->last()->codeOriginForExitTarget;
+
+        // 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);
         
         // Modify the states at the end of the preHeader of the loop we hoisted to,
-        // 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.
+        // 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.
         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;
@@ -250,9 +347,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.
-        RELEASE_ASSERT(!(node->flags() & NodeHasVarArgs));
+        DFG_ASSERT(m_graph, node, !(node->flags() & NodeHasVarArgs));
         
-        nodeRef = m_graph.addNode(SpecNone, Phantom, node->codeOrigin, node->children);
+        nodeRef = m_graph.addNode(SpecNone, Check, originalOrigin, node->children);
         
         return true;
     }