Source/JavaScriptCore/dfg/DFGLICMPhase.cpp

   1 /*
   2  * Copyright (C) 2013-2016 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 "DFGControlEquivalenceAnalysis.h"
  37 #include "DFGEdgeDominates.h"
  38 #include "DFGGraph.h"
  39 #include "DFGInsertionSet.h"
  40 #include "DFGMayExit.h"
  41 #include "DFGNaturalLoops.h"
  42 #include "DFGPhase.h"
  43 #include "DFGSafeToExecute.h"
  44 #include "JSCInlines.h"
  45
  46 namespace JSC { namespace DFG {
  47
  48 class LICMPhase : public Phase {
  49     static const bool verbose = false;
  50
  51     using NaturalLoop = SSANaturalLoop;
  52
  53     struct LoopData {
  54         ClobberSet writes;
  55         BasicBlock* preHeader { nullptr };
  56     };
  57
  58 public:
  59     LICMPhase(Graph& graph)
  60         : Phase(graph, "LICM")
  61         , m_state(graph)
  62         , m_interpreter(graph, m_state)
  63     {
  64     }
  65
  66     bool run()
  67     {
  68         DFG_ASSERT(m_graph, nullptr, m_graph.m_form == SSA);
  69
  70         m_graph.ensureSSADominators();
  71         m_graph.ensureSSANaturalLoops();
  72         m_graph.ensureControlEquivalenceAnalysis();
  73
  74         if (verbose) {
  75             dataLog("Graph before LICM:\n");
  76             m_graph.dump();
  77         }
  78
  79         m_data.resize(m_graph.m_ssaNaturalLoops->numLoops());
  80
  81         // Figure out the set of things each loop writes to, not including blocks that
  82         // belong to inner loops. We fix this later.
  83         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
  84             BasicBlock* block = m_graph.block(blockIndex);
  85             if (!block)
  86                 continue;
  87
  88             // Skip blocks that are proved to not execute.
  89             // FIXME: This shouldn't be needed.
  90             // https://bugs.webkit.org/show_bug.cgi?id=128584
  91             if (!block->cfaHasVisited)
  92                 continue;
  93
  94             const NaturalLoop* loop = m_graph.m_ssaNaturalLoops->innerMostLoopOf(block);
  95             if (!loop)
  96                 continue;
  97             LoopData& data = m_data[loop->index()];
  98             for (auto* node : *block) {
  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_ssaNaturalLoops->numLoops(); loopIndex--;) {
 113             const NaturalLoop& loop = m_graph.m_ssaNaturalLoops->loop(loopIndex);
 114             LoopData& data = m_data[loop.index()];
 115
 116             for (
 117                 const NaturalLoop* outerLoop = m_graph.m_ssaNaturalLoops->innerMostOuterLoop(loop);
 118                 outerLoop;
 119                 outerLoop = m_graph.m_ssaNaturalLoops->innerMostOuterLoop(*outerLoop))
 120                 m_data[outerLoop->index()].writes.addAll(data.writes);
 121
 122             BasicBlock* header = loop.header();
 123             BasicBlock* preHeader = nullptr;
 124             unsigned numberOfPreHeaders = 0; // We're cool if this is 1.
 125
 126             // This is guaranteed because we expect the CFG not to have unreachable code. Therefore, a
 127             // loop header must have a predecessor. (Also, we don't allow the root block to be a loop,
 128             // which cuts out the one other way of having a loop header with only one predecessor.)
 129             DFG_ASSERT(m_graph, header->at(0), header->predecessors.size() > 1);
 130
 131             for (unsigned i = header->predecessors.size(); i--;) {
 132                 BasicBlock* predecessor = header->predecessors[i];
 133                 if (m_graph.m_ssaDominators->dominates(header, predecessor))
 134                     continue;
 135
 136                 preHeader = predecessor;
 137                 ++numberOfPreHeaders;
 138             }
 139
 140             // We need to validate the pre-header. There are a bunch of things that could be wrong
 141             // about it:
 142             //
 143             // - There might be more than one. This means that pre-header creation either did not run,
 144             //   or some CFG transformation destroyed the pre-headers.
 145             //
 146             // - It may not be legal to exit at the pre-header. That would be a real bummer. Currently,
 147             //   LICM assumes that it can always hoist checks. See
 148             //   https://bugs.webkit.org/show_bug.cgi?id=148545. Though even with that fixed, we anyway
 149             //   would need to check if it's OK to exit at the pre-header since if we can't then we
 150             //   would have to restrict hoisting to non-exiting nodes.
 151
 152             if (numberOfPreHeaders != 1)
 153                 continue;
 154
 155             // This is guaranteed because the header has multiple predecessors and critical edges are
 156             // broken. Therefore the predecessors must all have one successor, which implies that they
 157             // must end in a Jump.
 158             DFG_ASSERT(m_graph, preHeader->terminal(), preHeader->terminal()->op() == Jump);
 159
 160             if (!preHeader->terminal()->origin.exitOK)
 161                 continue;
 162
 163             data.preHeader = preHeader;
 164         }
 165
 166         m_graph.initializeNodeOwners();
 167
 168         // Walk all basic blocks that belong to loops, looking for hoisting opportunities.
 169         // We try to hoist to the outer-most loop that permits it. Hoisting is valid if:
 170         // - The node doesn't write anything.
 171         // - The node doesn't read anything that the loop writes.
 172         // - The preHeader is valid (i.e. it passed the validation above).
 173         // - The preHeader's state at tail makes the node safe to execute.
 174         // - The loop's children all belong to nodes that strictly dominate the loop header.
 175         // - The preHeader's state at tail is still valid. This is mostly to save compile
 176         //   time and preserve some kind of sanity, if we hoist something that must exit.
 177         //
 178         // Also, we need to remember to:
 179         // - Update the state-at-tail with the node we hoisted, so future hoist candidates
 180         //   know about any type checks we hoisted.
 181         //
 182         // For maximum profit, we walk blocks in DFS order to ensure that we generally
 183         // tend to hoist dominators before dominatees.
 184         Vector<const NaturalLoop*> loopStack;
 185         bool changed = false;
 186         for (BasicBlock* block : m_graph.blocksInPreOrder()) {
 187             const NaturalLoop* loop = m_graph.m_ssaNaturalLoops->innerMostLoopOf(block);
 188             if (!loop)
 189                 continue;
 190
 191             loopStack.shrink(0);
 192             for (
 193                 const NaturalLoop* current = loop;
 194                 current;
 195                 current = m_graph.m_ssaNaturalLoops->innerMostOuterLoop(*current))
 196                 loopStack.append(current);
 197
 198             // Remember: the loop stack has the inner-most loop at index 0, so if we want
 199             // to bias hoisting to outer loops then we need to use a reverse loop.
 200
 201             if (verbose) {
 202                 dataLog(
 203                     "Attempting to hoist out of block ", *block, " in loops:\n");
 204                 for (unsigned stackIndex = loopStack.size(); stackIndex--;) {
 205                     dataLog(
 206                         "        ", *loopStack[stackIndex], ", which writes ",
 207                         m_data[loopStack[stackIndex]->index()].writes, "\n");
 208                 }
 209             }
 210
 211             for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
 212                 Node*& nodeRef = block->at(nodeIndex);
 213                 if (doesWrites(m_graph, nodeRef)) {
 214                     if (verbose)
 215                         dataLog("    Not hoisting ", nodeRef, " because it writes things.\n");
 216                     continue;
 217                 }
 218
 219                 for (unsigned stackIndex = loopStack.size(); stackIndex--;)
 220                     changed |= attemptHoist(block, nodeRef, loopStack[stackIndex]);
 221             }
 222         }
 223
 224         return changed;
 225     }
 226
 227 private:
 228     bool attemptHoist(BasicBlock* fromBlock, Node*& nodeRef, const NaturalLoop* loop)
 229     {
 230         Node* node = nodeRef;
 231         LoopData& data = m_data[loop->index()];
 232
 233         if (!data.preHeader) {
 234             if (verbose)
 235                 dataLog("    Not hoisting ", node, " because the pre-header is invalid.\n");
 236             return false;
 237         }
 238
 239         if (!data.preHeader->cfaDidFinish) {
 240             if (verbose)
 241                 dataLog("    Not hoisting ", node, " because CFA is invalid.\n");
 242             return false;
 243         }
 244
 245         if (!edgesDominate(m_graph, node, data.preHeader)) {
 246             if (verbose) {
 247                 dataLog(
 248                     "    Not hoisting ", node, " because it isn't loop invariant.\n");
 249             }
 250             return false;
 251         }
 252
 253         // FIXME: At this point if the hoisting of the full node fails but the node has type checks,
 254         // we could still hoist just the checks.
 255         // https://bugs.webkit.org/show_bug.cgi?id=144525
 256
 257         if (readsOverlap(m_graph, node, data.writes)) {
 258             if (verbose) {
 259                 dataLog(
 260                     "    Not hoisting ", node,
 261                     " because it reads things that the loop writes.\n");
 262             }
 263             return false;
 264         }
 265
 266         m_state.initializeTo(data.preHeader);
 267         if (!safeToExecute(m_state, m_graph, node)) {
 268             if (verbose) {
 269                 dataLog(
 270                     "    Not hoisting ", node, " because it isn't safe to execute.\n");
 271             }
 272             return false;
 273         }
 274
 275         NodeOrigin originalOrigin = node->origin;
 276
 277         // NOTE: We could just use BackwardsDominators here directly, since we already know that the
 278         // preHeader dominates fromBlock. But we wouldn't get anything from being so clever, since
 279         // dominance checks are O(1) and only a few integer compares.
 280         bool addsBlindSpeculation = mayExit(m_graph, node, m_state)
 281             && !m_graph.m_controlEquivalenceAnalysis->dominatesEquivalently(data.preHeader, fromBlock);
 282
 283         if (addsBlindSpeculation
 284             && m_graph.baselineCodeBlockFor(originalOrigin.semantic)->hasExitSite(FrequentExitSite(HoistingFailed))) {
 285             if (verbose) {
 286                 dataLog(
 287                     "    Not hoisting ", node, " because it may exit and the pre-header (",
 288                     *data.preHeader, ") is not control equivalent to the node's original block (",
 289                     *fromBlock, ") and hoisting had previously failed.\n");
 290             }
 291             return false;
 292         }
 293
 294         if (verbose) {
 295             dataLog(
 296                 "    Hoisting ", node, " from ", *fromBlock, " to ", *data.preHeader,
 297                 "\n");
 298         }
 299
 300         data.preHeader->insertBeforeTerminal(node);
 301         node->owner = data.preHeader;
 302         NodeOrigin terminalOrigin = data.preHeader->terminal()->origin;
 303         node->origin = terminalOrigin.withSemantic(node->origin.semantic);
 304         node->origin.wasHoisted |= addsBlindSpeculation;
 305
 306         // We can trust what AI proves about edge proof statuses when hoisting to the preheader.
 307         m_state.trustEdgeProofs();
 308         m_state.initializeTo(data.preHeader);
 309         m_interpreter.execute(node);
 310         // However, when walking various inner loops below, the proof status of
 311         // an edge may be trivially true, even if it's not true in the preheader
 312         // we hoist to. We don't allow the below node executions to change the
 313         // state of edge proofs. An example of where a proof is trivially true
 314         // is if we have two loops, L1 and L2, where L2 is nested inside L1. The
 315         // header for L1 dominates L2. We hoist a Check from L1's header into L1's
 316         // preheader. However, inside L2's preheader, we can't trust that AI will
 317         // tell us this edge is proven. It's proven in L2's preheader because L2
 318         // is dominated by L1's header. However, the edge is not guaranteed to be
 319         // proven inside L1's preheader.
 320         m_state.dontTrustEdgeProofs();
 321
 322         // Modify the states at the end of the preHeader of the loop we hoisted to,
 323         // and all pre-headers inside the loop. This isn't a stability bottleneck right now
 324         // because most loops are small and most blocks belong to few loops.
 325         for (unsigned bodyIndex = loop->size(); bodyIndex--;) {
 326             BasicBlock* subBlock = loop->at(bodyIndex);
 327             const NaturalLoop* subLoop = m_graph.m_ssaNaturalLoops->headerOf(subBlock);
 328             if (!subLoop)
 329                 continue;
 330             BasicBlock* subPreHeader = m_data[subLoop->index()].preHeader;
 331             // We may not have given this loop a pre-header because either it didn't have exitOK
 332             // or the header had multiple predecessors that it did not dominate. In that case the
 333             // loop wouldn't be a hoisting candidate anyway, so we don't have to do anything.
 334             if (!subPreHeader)
 335                 continue;
 336             // The pre-header's tail may be unreachable, in which case we have nothing to do.
 337             if (!subPreHeader->cfaDidFinish)
 338                 continue;
 339             // We handled this above.
 340             if (subPreHeader == data.preHeader)
 341                 continue;
 342             m_state.initializeTo(subPreHeader);
 343             m_interpreter.execute(node);
 344         }
 345
 346         // It just so happens that all of the nodes we currently know how to hoist
 347         // don't have var-arg children. That may change and then we can fix this
 348         // code. But for now we just assert that's the case.
 349         DFG_ASSERT(m_graph, node, !(node->flags() & NodeHasVarArgs));
 350
 351         nodeRef = m_graph.addNode(Check, originalOrigin, node->children);
 352
 353         return true;
 354     }
 355
 356     AtTailAbstractState m_state;
 357     AbstractInterpreter<AtTailAbstractState> m_interpreter;
 358     Vector<LoopData> m_data;
 359 };
 360
 361 bool performLICM(Graph& graph)
 362 {
 363     return runPhase<LICMPhase>(graph);
 364 }
 365
 366 } } // namespace JSC::DFG
 367
 368 #endif // ENABLE(DFG_JIT)
 369