Source/JavaScriptCore/dfg/DFGCFAPhase.cpp

   1 /*
   2  * Copyright (C) 2011-2018 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 "DFGCFAPhase.h"
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "DFGAbstractInterpreterInlines.h"
  32 #include "DFGBlockSet.h"
  33 #include "DFGClobberSet.h"
  34 #include "DFGGraph.h"
  35 #include "DFGInPlaceAbstractState.h"
  36 #include "DFGPhase.h"
  37 #include "DFGSafeToExecute.h"
  38 #include "OperandsInlines.h"
  39 #include "JSCInlines.h"
  40
  41 namespace JSC { namespace DFG {
  42
  43 class CFAPhase : public Phase {
  44 public:
  45     CFAPhase(Graph& graph)
  46         : Phase(graph, "control flow analysis")
  47         , m_state(graph)
  48         , m_interpreter(graph, m_state)
  49         , m_verbose(Options::verboseCFA())
  50     {
  51     }
  52
  53     bool run()
  54     {
  55         ASSERT(m_graph.m_form == ThreadedCPS || m_graph.m_form == SSA);
  56         ASSERT(m_graph.m_unificationState == GloballyUnified);
  57         ASSERT(m_graph.m_refCountState == EverythingIsLive);
  58
  59         m_count = 0;
  60
  61         if (m_verbose && !shouldDumpGraphAtEachPhase(m_graph.m_plan.mode())) {
  62             dataLog("Graph before CFA:\n");
  63             m_graph.dump();
  64         }
  65
  66         // This implements a pseudo-worklist-based forward CFA, except that the visit order
  67         // of blocks is the bytecode program order (which is nearly topological), and
  68         // instead of a worklist we just walk all basic blocks checking if cfaShouldRevisit
  69         // is set to true. This is likely to balance the efficiency properties of both
  70         // worklist-based and forward fixpoint-based approaches. Like a worklist-based
  71         // approach, it won't visit code if it's meaningless to do so (nothing changed at
  72         // the head of the block or the predecessors have not been visited). Like a forward
  73         // fixpoint-based approach, it has a high probability of only visiting a block
  74         // after all predecessors have been visited. Only loops will cause this analysis to
  75         // revisit blocks, and the amount of revisiting is proportional to loop depth.
  76
  77         m_state.initialize();
  78
  79         if (m_graph.m_form != SSA) {
  80             if (m_verbose)
  81                 dataLog("   Widening state at OSR entry block.\n");
  82
  83             // Widen the abstract values at the block that serves as the must-handle OSR entry.
  84             for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
  85                 BasicBlock* block = m_graph.block(blockIndex);
  86                 if (!block)
  87                     continue;
  88
  89                 if (!block->isOSRTarget)
  90                     continue;
  91                 if (block->bytecodeBegin != m_graph.m_plan.osrEntryBytecodeIndex())
  92                     continue;
  93
  94                 // We record that the block needs some OSR stuff, but we don't do that yet. We want to
  95                 // handle OSR entry data at the right time in order to get the best compile times. If we
  96                 // simply injected OSR data right now, then we'd potentially cause a loop body to be
  97                 // interpreted with just the constants we feed it, which is more expensive than if we
  98                 // interpreted it with non-constant values. If we always injected this data after the
  99                 // main pass of CFA ran, then we would potentially spend a bunch of time rerunning CFA
 100                 // after convergence. So, we try very hard to inject OSR data for a block when we first
 101                 // naturally come to see it - see the m_blocksWithOSR check in performBlockCFA(). This
 102                 // way, we:
 103                 //
 104                 // - Reduce the likelihood of interpreting the block with constants, since we will inject
 105                 //   the OSR entry constants on top of whatever abstract values we got for that block on
 106                 //   the first pass. The mix of those two things is likely to not be constant.
 107                 //
 108                 // - Reduce the total number of CFA reexecutions since we inject the OSR data as part of
 109                 //   the normal flow of CFA instead of having to do a second fixpoint. We may still have
 110                 //   to do a second fixpoint if we don't even reach the OSR entry block during the main
 111                 //   run of CFA, but in that case at least we're not being redundant.
 112                 m_blocksWithOSR.add(block);
 113             }
 114         }
 115
 116         do {
 117             m_changed = false;
 118             performForwardCFA();
 119         } while (m_changed);
 120
 121         if (m_graph.m_form != SSA) {
 122             for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
 123                 BasicBlock* block = m_graph.block(blockIndex);
 124                 if (!block)
 125                     continue;
 126
 127                 if (m_blocksWithOSR.remove(block))
 128                     m_changed |= injectOSR(block);
 129             }
 130
 131             while (m_changed) {
 132                 m_changed = false;
 133                 performForwardCFA();
 134             }
 135
 136             // Make sure we record the intersection of all proofs that we ever allowed the
 137             // compiler to rely upon.
 138             for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
 139                 BasicBlock* block = m_graph.block(blockIndex);
 140                 if (!block)
 141                     continue;
 142
 143                 block->intersectionOfCFAHasVisited &= block->cfaHasVisited;
 144                 for (unsigned i = block->intersectionOfPastValuesAtHead.size(); i--;) {
 145                     AbstractValue value = block->valuesAtHead[i];
 146                     // We need to guarantee that when we do an OSR entry, we validate the incoming
 147                     // value as if it could be live past an invalidation point. Otherwise, we may
 148                     // OSR enter with a value with the wrong structure, and an InvalidationPoint's
 149                     // promise of filtering the structure set of certain values is no longer upheld.
 150                     value.m_structure.observeInvalidationPoint();
 151                     block->intersectionOfPastValuesAtHead[i].filter(value);
 152                 }
 153             }
 154         }
 155
 156         return true;
 157     }
 158
 159 private:
 160     bool injectOSR(BasicBlock* block)
 161     {
 162         if (m_verbose)
 163             dataLog("   Found must-handle block: ", *block, "\n");
 164
 165         bool changed = false;
 166         const Operands<JSValue>& mustHandleValues = m_graph.m_plan.mustHandleValues();
 167         for (size_t i = mustHandleValues.size(); i--;) {
 168             int operand = mustHandleValues.operandForIndex(i);
 169             JSValue value = mustHandleValues[i];
 170             Node* node = block->variablesAtHead.operand(operand);
 171             if (!node) {
 172                 if (m_verbose)
 173                     dataLog("   Not live: ", VirtualRegister(operand), "\n");
 174                 continue;
 175             }
 176
 177             if (m_verbose)
 178                 dataLog("   Widening ", VirtualRegister(operand), " with ", value, "\n");
 179
 180             AbstractValue& target = block->valuesAtHead.operand(operand);
 181             changed |= target.mergeOSREntryValue(m_graph, value);
 182             target.fixTypeForRepresentation(
 183                 m_graph, resultFor(node->variableAccessData()->flushFormat()));
 184         }
 185
 186         if (changed || !block->cfaHasVisited) {
 187             block->cfaShouldRevisit = true;
 188             return true;
 189         }
 190
 191         return false;
 192     }
 193
 194     void performBlockCFA(BasicBlock* block)
 195     {
 196         if (!block)
 197             return;
 198         if (!block->cfaShouldRevisit)
 199             return;
 200         if (m_verbose)
 201             dataLog("   Block ", *block, ":\n");
 202
 203         if (m_blocksWithOSR.remove(block))
 204             injectOSR(block);
 205
 206         m_state.beginBasicBlock(block);
 207         if (m_verbose) {
 208             dataLog("      head vars: ", block->valuesAtHead, "\n");
 209             if (m_graph.m_form == SSA)
 210                 dataLog("      head regs: ", nodeValuePairListDump(block->ssa->valuesAtHead), "\n");
 211         }
 212         for (unsigned i = 0; i < block->size(); ++i) {
 213             Node* node = block->at(i);
 214             if (m_verbose) {
 215                 dataLogF("      %s @%u: ", Graph::opName(node->op()), node->index());
 216
 217                 if (!safeToExecute(m_state, m_graph, node))
 218                     dataLog("(UNSAFE) ");
 219
 220                 dataLog(m_state.variablesForDebugging(), " ", m_interpreter);
 221
 222                 dataLogF("\n");
 223             }
 224             if (!m_interpreter.execute(i)) {
 225                 if (m_verbose)
 226                     dataLogF("         Expect OSR exit.\n");
 227                 break;
 228             }
 229
 230             if (!ASSERT_DISABLED
 231                 && m_state.didClobberOrFolded() != writesOverlap(m_graph, node, JSCell_structureID))
 232                 DFG_CRASH(m_graph, node, toCString("AI-clobberize disagreement; AI says ", m_state.clobberState(), " while clobberize says ", writeSet(m_graph, node)).data());
 233         }
 234         if (m_verbose) {
 235             dataLogF("      tail regs: ");
 236             m_interpreter.dump(WTF::dataFile());
 237             dataLogF("\n");
 238         }
 239         m_changed |= m_state.endBasicBlock();
 240
 241         if (m_verbose) {
 242             dataLog("      tail vars: ", block->valuesAtTail, "\n");
 243             if (m_graph.m_form == SSA)
 244                 dataLog("      head regs: ", nodeValuePairListDump(block->ssa->valuesAtTail), "\n");
 245         }
 246     }
 247
 248     void performForwardCFA()
 249     {
 250         ++m_count;
 251         if (m_verbose)
 252             dataLogF("CFA [%u]\n", m_count);
 253
 254         for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex)
 255             performBlockCFA(m_graph.block(blockIndex));
 256     }
 257
 258 private:
 259     InPlaceAbstractState m_state;
 260     AbstractInterpreter<InPlaceAbstractState> m_interpreter;
 261     BlockSet m_blocksWithOSR;
 262
 263     bool m_verbose;
 264
 265     bool m_changed;
 266     unsigned m_count;
 267 };
 268
 269 bool performCFA(Graph& graph)
 270 {
 271     return runPhase<CFAPhase>(graph);
 272 }
 273
 274 } } // namespace JSC::DFG
 275
 276 #endif // ENABLE(DFG_JIT)