webkitgtk-2.16.5HEADwebkitgtk-2.16.5master

1 files changed, 126 insertions, 40 deletions

diff --git a/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp b/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp
index 64651309e..75eefa9e7 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-2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -33,12 +33,15 @@
 #include "DFGBasicBlockInlines.h"
 #include "DFGClobberSet.h"
 #include "DFGClobberize.h"
+#include "DFGControlEquivalenceAnalysis.h"
 #include "DFGEdgeDominates.h"
 #include "DFGGraph.h"
 #include "DFGInsertionSet.h"
+#include "DFGMayExit.h"
+#include "DFGNaturalLoops.h"
 #include "DFGPhase.h"
 #include "DFGSafeToExecute.h"
-#include "Operations.h"
+#include "JSCInlines.h"
 
 namespace JSC { namespace DFG {
 
@@ -46,7 +49,7 @@ namespace {
 
 struct LoopData {
     LoopData()
-        : preHeader(0)
+        : preHeader(nullptr)
     {
     }
     
@@ -62,18 +65,25 @@ 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();
+        m_graph.ensureControlEquivalenceAnalysis();
+
+        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 +91,81 @@ 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 (auto* node : *block) {
+                // 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 +176,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 +188,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 +199,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 +236,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 +257,10 @@ 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
+        
         if (readsOverlap(m_graph, node, data.writes)) {
             if (verbose) {
                 dataLog(
@@ -221,26 +279,55 @@ private:
             return false;
         }
         
+        NodeOrigin originalOrigin = node->origin;
+
+        // NOTE: We could just use BackwardsDominators here directly, since we already know that the
+        // preHeader dominates fromBlock. But we wouldn't get anything from being so clever, since
+        // dominance checks are O(1) and only a few integer compares.
+        bool addsBlindSpeculation = mayExit(m_graph, node, m_state)
+            && !m_graph.m_controlEquivalenceAnalysis->dominatesEquivalently(data.preHeader, fromBlock);
+        
+        if (addsBlindSpeculation
+            && m_graph.baselineCodeBlockFor(originalOrigin.semantic)->hasExitSite(FrequentExitSite(HoistingFailed))) {
+            if (verbose) {
+                dataLog(
+                    "    Not hoisting ", node, " because it may exit and the pre-header (",
+                    *data.preHeader, ") is not control equivalent to the node's original block (",
+                    *fromBlock, ") and hoisting had previously failed.\n");
+            }
+            return false;
+        }
+        
         if (verbose) {
             dataLog(
                 "    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 terminalOrigin = data.preHeader->terminal()->origin;
+        node->origin = terminalOrigin.withSemantic(node->origin.semantic);
+        node->origin.wasHoisted |= addsBlindSpeculation;
         
         // 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;
+            // We may not have given this loop a pre-header because either it didn't have exitOK
+            // or the header had multiple predecessors that it did not dominate. In that case the
+            // loop wouldn't be a hoisting candidate anyway, so we don't have to do anything.
+            if (!subPreHeader)
+                continue;
+            // The pre-header's tail may be unreachable, in which case we have nothing to do.
             if (!subPreHeader->cfaDidFinish)
                 continue;
             m_state.initializeTo(subPreHeader);
@@ -250,9 +337,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(Check, originalOrigin, node->children);
         
         return true;
     }
@@ -264,7 +351,6 @@ private:
 
 bool performLICM(Graph& graph)
 {
-    SamplingRegion samplingRegion("DFG LICM Phase");
     return runPhase<LICMPhase>(graph);
 }