dfg/DFGPhantomInsertionPhase.cpp

   1 /*
   2  * Copyright (C) 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 "DFGPhantomInsertionPhase.h"
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "BytecodeLivenessAnalysisInlines.h"
  32 #include "DFGForAllKills.h"
  33 #include "DFGGraph.h"
  34 #include "DFGInsertionSet.h"
  35 #include "DFGMayExit.h"
  36 #include "DFGPhase.h"
  37 #include "DFGPredictionPropagationPhase.h"
  38 #include "DFGVariableAccessDataDump.h"
  39 #include "JSCInlines.h"
  40 #include "OperandsInlines.h"
  41
  42 namespace JSC { namespace DFG {
  43
  44 namespace {
  45
  46 bool verbose = false;
  47
  48 class PhantomInsertionPhase : public Phase {
  49 public:
  50     PhantomInsertionPhase(Graph& graph)
  51         : Phase(graph, "phantom insertion")
  52         , m_insertionSet(graph)
  53         , m_values(OperandsLike, graph.block(0)->variablesAtHead)
  54     {
  55     }
  56
  57     bool run()
  58     {
  59         // We assume that DCE has already run. If we run before DCE then we think that all
  60         // SetLocals execute, which is inaccurate. That causes us to insert too few Phantoms.
  61         DFG_ASSERT(m_graph, nullptr, m_graph.m_refCountState == ExactRefCount);
  62
  63         if (verbose) {
  64             dataLog("Graph before Phantom insertion:\n");
  65             m_graph.dump();
  66         }
  67
  68         m_graph.clearEpochs();
  69
  70         for (BasicBlock* block : m_graph.blocksInNaturalOrder())
  71             handleBlock(block);
  72
  73         if (verbose) {
  74             dataLog("Graph after Phantom insertion:\n");
  75             m_graph.dump();
  76         }
  77
  78         return true;
  79     }
  80
  81 private:
  82     void handleBlock(BasicBlock* block)
  83     {
  84         // FIXME: For blocks that have low register pressure, it would make the most sense to
  85         // simply insert Phantoms at the last point possible since that would obviate the need to
  86         // query bytecode liveness:
  87         //
  88         // - If we MovHint @x into loc42 then put a Phantom on the last MovHinted value in loc42.
  89         // - At the end of the block put Phantoms for each MovHinted value.
  90         //
  91         // This will definitely not work if there are any phantom allocations. For those blocks
  92         // where this would be legal, it remains to be seen how profitable it would be even if there
  93         // was high register pressure. After all, a Phantom would cause a spill but it wouldn't
  94         // cause a fill.
  95         //
  96         // https://bugs.webkit.org/show_bug.cgi?id=144524
  97
  98         m_values.fill(nullptr);
  99
 100         Epoch currentEpoch = Epoch::first();
 101         unsigned lastExitingIndex = 0;
 102         for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
 103             Node* node = block->at(nodeIndex);
 104             if (verbose)
 105                 dataLog("Considering ", node, "\n");
 106
 107             switch (node->op()) {
 108             case MovHint:
 109                 m_values.operand(node->unlinkedLocal()) = node->child1().node();
 110                 break;
 111
 112             case ZombieHint:
 113                 m_values.operand(node->unlinkedLocal()) = nullptr;
 114                 break;
 115
 116             case SetLocal:
 117             case GetLocal:
 118             case SetArgument:
 119                 m_values.operand(node->local()) = nullptr;
 120                 break;
 121
 122             default:
 123                 break;
 124             }
 125
 126             if (mayExit(m_graph, node)) {
 127                 currentEpoch.bump();
 128                 lastExitingIndex = nodeIndex;
 129             }
 130
 131             m_graph.doToChildren(
 132                 node,
 133                 [&] (Edge edge) {
 134                     edge->setEpoch(currentEpoch);
 135                 });
 136
 137             node->setEpoch(currentEpoch);
 138
 139             forAllKilledOperands(
 140                 m_graph, node, block->tryAt(nodeIndex + 1),
 141                 [&] (VirtualRegister reg) {
 142                     if (verbose)
 143                         dataLog("    Killed operand: ", reg, "\n");
 144
 145                     Node* killedNode = m_values.operand(reg);
 146                     if (!killedNode)
 147                         return;
 148
 149                     // We only need to insert a Phantom if the node hasn't been used since the last
 150                     // exit, and was born before the last exit.
 151                     if (killedNode->epoch() == currentEpoch)
 152                         return;
 153
 154                     if (verbose) {
 155                         dataLog(
 156                             "    Inserting Phantom on ", killedNode, " after ",
 157                             block->at(lastExitingIndex), "\n");
 158                     }
 159
 160                     // We have exact ref counts, so creating a new use means that we have to
 161                     // increment the ref count.
 162                     killedNode->postfixRef();
 163
 164                     m_insertionSet.insertNode(
 165                         lastExitingIndex + 1, SpecNone, Phantom,
 166                         block->at(lastExitingIndex)->origin, killedNode->defaultEdge());
 167             });
 168         }
 169
 170         m_insertionSet.execute(block);
 171     }
 172
 173     InsertionSet m_insertionSet;
 174     Operands<Node*> m_values;
 175 };
 176
 177 } // anonymous namespace
 178
 179 bool performPhantomInsertion(Graph& graph)
 180 {
 181     SamplingRegion samplingRegion("DFG Phantom Insertion Phase");
 182     return runPhase<PhantomInsertionPhase>(graph);
 183 }
 184
 185 } } // namespace JSC::DFG
 186
 187 #endif // ENABLE(DFG_JIT)
 188