dfg/DFGLICMPhase.cpp

   1 /*
   2  * Copyright (C) 2013-2015 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "config.h"
  27 #include "DFGLICMPhase.h"
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "DFGAbstractInterpreterInlines.h"
  32 #include "DFGAtTailAbstractState.h"
  33 #include "DFGBasicBlockInlines.h"
  34 #include "DFGClobberSet.h"
  35 #include "DFGClobberize.h"
  36 #include "DFGEdgeDominates.h"
  37 #include "DFGGraph.h"
  38 #include "DFGInsertionSet.h"
  39 #include "DFGPhase.h"
  40 #include "DFGSafeToExecute.h"
  41 #include "JSCInlines.h"
  42
  43 namespace JSC { namespace DFG {
  44
  45 namespace {
  46
  47 struct LoopData {
  48     LoopData()
  49         : preHeader(0)
  50     {
  51     }
  52
  53     ClobberSet writes;
  54     BasicBlock* preHeader;
  55 };
  56
  57 } // anonymous namespace
  58
  59 class LICMPhase : public Phase {
  60     static const bool verbose = false;
  61
  62 public:
  63     LICMPhase(Graph& graph)
  64         : Phase(graph, "LICM")
  65         , m_state(graph)
  66         , m_interpreter(graph, m_state)
  67     {
  68     }
  69
  70     bool run()
  71     {
  72         DFG_ASSERT(m_graph, nullptr, m_graph.m_form == SSA);
  73
  74         m_graph.m_dominators.computeIfNecessary(m_graph);
  75         m_graph.m_naturalLoops.computeIfNecessary(m_graph);
  76
  77         m_data.resize(m_graph.m_naturalLoops.numLoops());
  78
  79         // Figure out the set of things each loop writes to, not including blocks that
  80         // belong to inner loops. We fix this later.
  81         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
  82             BasicBlock* block = m_graph.block(blockIndex);
  83             if (!block)
  84                 continue;
  85
  86             // Skip blocks that are proved to not execute.
  87             // FIXME: This shouldn't be needed.
  88             // https://bugs.webkit.org/show_bug.cgi?id=128584
  89             if (!block->cfaHasVisited)
  90                 continue;
  91
  92             const NaturalLoop* loop = m_graph.m_naturalLoops.innerMostLoopOf(block);
  93             if (!loop)
  94                 continue;
  95             LoopData& data = m_data[loop->index()];
  96             for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
  97                 Node* node = block->at(nodeIndex);
  98
  99                 // Don't look beyond parts of the code that definitely always exit.
 100                 // FIXME: This shouldn't be needed.
 101                 // https://bugs.webkit.org/show_bug.cgi?id=128584
 102                 if (node->op() == ForceOSRExit)
 103                     break;
 104
 105                 addWrites(m_graph, node, data.writes);
 106             }
 107         }
 108
 109         // For each loop:
 110         // - Identify its pre-header.
 111         // - Make sure its outer loops know what it clobbers.
 112         for (unsigned loopIndex = m_graph.m_naturalLoops.numLoops(); loopIndex--;) {
 113             const NaturalLoop& loop = m_graph.m_naturalLoops.loop(loopIndex);
 114             LoopData& data = m_data[loop.index()];
 115             for (
 116                 const NaturalLoop* outerLoop = m_graph.m_naturalLoops.innerMostOuterLoop(loop);
 117                 outerLoop;
 118                 outerLoop = m_graph.m_naturalLoops.innerMostOuterLoop(*outerLoop))
 119                 m_data[outerLoop->index()].writes.addAll(data.writes);
 120
 121             BasicBlock* header = loop.header();
 122             BasicBlock* preHeader = 0;
 123             for (unsigned i = header->predecessors.size(); i--;) {
 124                 BasicBlock* predecessor = header->predecessors[i];
 125                 if (m_graph.m_dominators.dominates(header, predecessor))
 126                     continue;
 127                 DFG_ASSERT(m_graph, nullptr, !preHeader || preHeader == predecessor);
 128                 preHeader = predecessor;
 129             }
 130
 131             DFG_ASSERT(m_graph, preHeader->terminal(), preHeader->terminal()->op() == Jump);
 132
 133             // We should validate the pre-header. If we placed forExit origins on nodes only if
 134             // at the top of that node it is legal to exit, then we would simply check if Jump
 135             // had a forExit. We should disable hoisting to pre-headers that don't validate.
 136             // Or, we could only allow hoisting of things that definitely don't exit.
 137             // FIXME: https://bugs.webkit.org/show_bug.cgi?id=145204
 138
 139             data.preHeader = preHeader;
 140         }
 141
 142         m_graph.initializeNodeOwners();
 143
 144         // Walk all basic blocks that belong to loops, looking for hoisting opportunities.
 145         // We try to hoist to the outer-most loop that permits it. Hoisting is valid if:
 146         // - The node doesn't write anything.
 147         // - The node doesn't read anything that the loop writes.
 148         // - The preHeader's state at tail makes the node safe to execute.
 149         // - The loop's children all belong to nodes that strictly dominate the loop header.
 150         // - The preHeader's state at tail is still valid. This is mostly to save compile
 151         //   time and preserve some kind of sanity, if we hoist something that must exit.
 152         //
 153         // Also, we need to remember to:
 154         // - Update the state-at-tail with the node we hoisted, so future hoist candidates
 155         //   know about any type checks we hoisted.
 156         //
 157         // For maximum profit, we walk blocks in DFS order to ensure that we generally
 158         // tend to hoist dominators before dominatees.
 159         Vector<const NaturalLoop*> loopStack;
 160         bool changed = false;
 161         for (BasicBlock* block : m_graph.blocksInPreOrder()) {
 162             const NaturalLoop* loop = m_graph.m_naturalLoops.innerMostLoopOf(block);
 163             if (!loop)
 164                 continue;
 165
 166             loopStack.resize(0);
 167             for (
 168                 const NaturalLoop* current = loop;
 169                 current;
 170                 current = m_graph.m_naturalLoops.innerMostOuterLoop(*current))
 171                 loopStack.append(current);
 172
 173             // Remember: the loop stack has the inner-most loop at index 0, so if we want
 174             // to bias hoisting to outer loops then we need to use a reverse loop.
 175
 176             if (verbose) {
 177                 dataLog(
 178                     "Attempting to hoist out of block ", *block, " in loops:\n");
 179                 for (unsigned stackIndex = loopStack.size(); stackIndex--;) {
 180                     dataLog(
 181                         "        ", *loopStack[stackIndex], ", which writes ",
 182                         m_data[loopStack[stackIndex]->index()].writes, "\n");
 183                 }
 184             }
 185
 186             for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
 187                 Node*& nodeRef = block->at(nodeIndex);
 188                 if (doesWrites(m_graph, nodeRef)) {
 189                     if (verbose)
 190                         dataLog("    Not hoisting ", nodeRef, " because it writes things.\n");
 191                     continue;
 192                 }
 193
 194                 for (unsigned stackIndex = loopStack.size(); stackIndex--;)
 195                     changed |= attemptHoist(block, nodeRef, loopStack[stackIndex]);
 196             }
 197         }
 198
 199         return changed;
 200     }
 201
 202 private:
 203     bool attemptHoist(BasicBlock* fromBlock, Node*& nodeRef, const NaturalLoop* loop)
 204     {
 205         Node* node = nodeRef;
 206         LoopData& data = m_data[loop->index()];
 207
 208         if (!data.preHeader->cfaDidFinish) {
 209             if (verbose)
 210                 dataLog("    Not hoisting ", node, " because CFA is invalid.\n");
 211             return false;
 212         }
 213
 214         if (!edgesDominate(m_graph, node, data.preHeader)) {
 215             if (verbose) {
 216                 dataLog(
 217                     "    Not hoisting ", node, " because it isn't loop invariant.\n");
 218             }
 219             return false;
 220         }
 221
 222         // FIXME: At this point if the hoisting of the full node fails but the node has type checks,
 223         // we could still hoist just the checks.
 224         // https://bugs.webkit.org/show_bug.cgi?id=144525
 225
 226         // FIXME: If a node has a type check - even something like a CheckStructure - then we should
 227         // only hoist the node if we know that it will execute on every loop iteration or if we know
 228         // that the type check will always succeed at the loop pre-header through some other means
 229         // (like looking at prediction propagation results). Otherwise, we might make a mistake like
 230         // this:
 231         //
 232         // var o = ...; // sometimes null and sometimes an object with structure S1.
 233         // for (...) {
 234         //     if (o)
 235         //         ... = o.f; // CheckStructure and GetByOffset, which we will currently hoist.
 236         // }
 237         //
 238         // When we encounter such code, we'll hoist the CheckStructure and GetByOffset and then we
 239         // will have a recompile. We'll then end up thinking that the get_by_id needs to be
 240         // polymorphic, which is false.
 241         //
 242         // We can counter this by either having a control flow equivalence check, or by consulting
 243         // prediction propagation to see if the check would always succeed. Prediction propagation
 244         // would not be enough for things like:
 245         //
 246         // var p = ...; // some boolean predicate
 247         // var o = {};
 248         // if (p)
 249         //     o.f = 42;
 250         // for (...) {
 251         //     if (p)
 252         //         ... = o.f;
 253         // }
 254         //
 255         // Prediction propagation can't tell us anything about the structure, and the CheckStructure
 256         // will appear to be hoistable because the loop doesn't clobber structures. The cell check
 257         // in the CheckStructure will be hoistable though, since prediction propagation can tell us
 258         // that o is always SpecFinalObject. In cases like this, control flow equivalence is the
 259         // only effective guard.
 260         //
 261         // https://bugs.webkit.org/show_bug.cgi?id=144527
 262
 263         if (readsOverlap(m_graph, node, data.writes)) {
 264             if (verbose) {
 265                 dataLog(
 266                     "    Not hoisting ", node,
 267                     " because it reads things that the loop writes.\n");
 268             }
 269             return false;
 270         }
 271
 272         m_state.initializeTo(data.preHeader);
 273         if (!safeToExecute(m_state, m_graph, node)) {
 274             if (verbose) {
 275                 dataLog(
 276                     "    Not hoisting ", node, " because it isn't safe to execute.\n");
 277             }
 278             return false;
 279         }
 280
 281         if (verbose) {
 282             dataLog(
 283                 "    Hoisting ", node, " from ", *fromBlock, " to ", *data.preHeader,
 284                 "\n");
 285         }
 286
 287         data.preHeader->insertBeforeTerminal(node);
 288         node->owner = data.preHeader;
 289         NodeOrigin originalOrigin = node->origin;
 290         node->origin.forExit = data.preHeader->terminal()->origin.forExit;
 291         if (!node->origin.semantic.isSet())
 292             node->origin.semantic = node->origin.forExit;
 293
 294         // Modify the states at the end of the preHeader of the loop we hoisted to,
 295         // and all pre-headers inside the loop.
 296         // FIXME: This could become a scalability bottleneck. Fortunately, most loops
 297         // are small and anyway we rapidly skip over basic blocks here.
 298         for (unsigned bodyIndex = loop->size(); bodyIndex--;) {
 299             BasicBlock* subBlock = loop->at(bodyIndex);
 300             const NaturalLoop* subLoop = m_graph.m_naturalLoops.headerOf(subBlock);
 301             if (!subLoop)
 302                 continue;
 303             BasicBlock* subPreHeader = m_data[subLoop->index()].preHeader;
 304             if (!subPreHeader->cfaDidFinish)
 305                 continue;
 306             m_state.initializeTo(subPreHeader);
 307             m_interpreter.execute(node);
 308         }
 309
 310         // It just so happens that all of the nodes we currently know how to hoist
 311         // don't have var-arg children. That may change and then we can fix this
 312         // code. But for now we just assert that's the case.
 313         DFG_ASSERT(m_graph, node, !(node->flags() & NodeHasVarArgs));
 314
 315         nodeRef = m_graph.addNode(SpecNone, Check, originalOrigin, node->children);
 316
 317         return true;
 318     }
 319
 320     AtTailAbstractState m_state;
 321     AbstractInterpreter<AtTailAbstractState> m_interpreter;
 322     Vector<LoopData> m_data;
 323 };
 324
 325 bool performLICM(Graph& graph)
 326 {
 327     SamplingRegion samplingRegion("DFG LICM Phase");
 328     return runPhase<LICMPhase>(graph);
 329 }
 330
 331 } } // namespace JSC::DFG
 332
 333 #endif // ENABLE(DFG_JIT)
 334