dfg/DFGSSAConversionPhase.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 "DFGSSAConversionPhase.h"
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "DFGBasicBlockInlines.h"
  32 #include "DFGGraph.h"
  33 #include "DFGInsertionSet.h"
  34 #include "DFGPhase.h"
  35 #include "DFGSSACalculator.h"
  36 #include "DFGVariableAccessDataDump.h"
  37 #include "JSCInlines.h"
  38
  39 namespace JSC { namespace DFG {
  40
  41 class SSAConversionPhase : public Phase {
  42     static const bool verbose = false;
  43
  44 public:
  45     SSAConversionPhase(Graph& graph)
  46         : Phase(graph, "SSA conversion")
  47         , m_calculator(graph)
  48         , m_insertionSet(graph)
  49     {
  50     }
  51
  52     bool run()
  53     {
  54         RELEASE_ASSERT(m_graph.m_form == ThreadedCPS);
  55
  56         m_graph.clearReplacements();
  57         m_graph.m_dominators.computeIfNecessary(m_graph);
  58
  59         if (verbose) {
  60             dataLog("Graph before SSA transformation:\n");
  61             m_graph.dump();
  62         }
  63
  64         // Create a SSACalculator::Variable for every root VariableAccessData.
  65         for (VariableAccessData& variable : m_graph.m_variableAccessData) {
  66             if (!variable.isRoot())
  67                 continue;
  68
  69             SSACalculator::Variable* ssaVariable = m_calculator.newVariable();
  70             ASSERT(ssaVariable->index() == m_variableForSSAIndex.size());
  71             m_variableForSSAIndex.append(&variable);
  72             m_ssaVariableForVariable.add(&variable, ssaVariable);
  73         }
  74
  75         // Find all SetLocals and create Defs for them. We handle SetArgument by creating a
  76         // GetLocal, and recording the flush format.
  77         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
  78             BasicBlock* block = m_graph.block(blockIndex);
  79             if (!block)
  80                 continue;
  81
  82             // Must process the block in forward direction because we want to see the last
  83             // assignment for every local.
  84             for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
  85                 Node* node = block->at(nodeIndex);
  86                 if (node->op() != SetLocal && node->op() != SetArgument)
  87                     continue;
  88
  89                 VariableAccessData* variable = node->variableAccessData();
  90
  91                 Node* childNode;
  92                 if (node->op() == SetLocal)
  93                     childNode = node->child1().node();
  94                 else {
  95                     ASSERT(node->op() == SetArgument);
  96                     childNode = m_insertionSet.insertNode(
  97                         nodeIndex, node->variableAccessData()->prediction(),
  98                         GetStack, node->origin,
  99                         OpInfo(m_graph.m_stackAccessData.add(variable->local(), variable->flushFormat())));
 100                     if (!ASSERT_DISABLED)
 101                         m_argumentGetters.add(childNode);
 102                     m_argumentMapping.add(node, childNode);
 103                 }
 104
 105                 m_calculator.newDef(
 106                     m_ssaVariableForVariable.get(variable), block, childNode);
 107             }
 108
 109             m_insertionSet.execute(block);
 110         }
 111
 112         // Decide where Phis are to be inserted. This creates the Phi's but doesn't insert them
 113         // yet. We will later know where to insert them because SSACalculator is such a bro.
 114         m_calculator.computePhis(
 115             [&] (SSACalculator::Variable* ssaVariable, BasicBlock* block) -> Node* {
 116                 VariableAccessData* variable = m_variableForSSAIndex[ssaVariable->index()];
 117
 118                 // Prune by liveness. This doesn't buy us much other than compile times.
 119                 Node* headNode = block->variablesAtHead.operand(variable->local());
 120                 if (!headNode)
 121                     return nullptr;
 122
 123                 // There is the possibiltiy of "rebirths". The SSA calculator will already prune
 124                 // rebirths for the same VariableAccessData. But it will not be able to prune
 125                 // rebirths that arose from the same local variable number but a different
 126                 // VariableAccessData. We do that pruning here.
 127                 //
 128                 // Here's an example of a rebirth that this would catch:
 129                 //
 130                 //     var x;
 131                 //     if (foo) {
 132                 //         if (bar) {
 133                 //             x = 42;
 134                 //         } else {
 135                 //             x = 43;
 136                 //         }
 137                 //         print(x);
 138                 //         x = 44;
 139                 //     } else {
 140                 //         x = 45;
 141                 //     }
 142                 //     print(x); // Without this check, we'd have a Phi for x = 42|43 here.
 143                 //
 144                 // FIXME: Consider feeding local variable numbers, not VariableAccessData*'s, as
 145                 // the "variables" for SSACalculator. That would allow us to eliminate this
 146                 // special case.
 147                 // https://bugs.webkit.org/show_bug.cgi?id=136641
 148                 if (headNode->variableAccessData() != variable)
 149                     return nullptr;
 150
 151                 Node* phiNode = m_graph.addNode(
 152                     variable->prediction(), Phi, NodeOrigin());
 153                 FlushFormat format = variable->flushFormat();
 154                 NodeFlags result = resultFor(format);
 155                 phiNode->mergeFlags(result);
 156                 return phiNode;
 157             });
 158
 159         if (verbose) {
 160             dataLog("Computed Phis, about to transform the graph.\n");
 161             dataLog("\n");
 162             dataLog("Graph:\n");
 163             m_graph.dump();
 164             dataLog("\n");
 165             dataLog("Mappings:\n");
 166             for (unsigned i = 0; i < m_variableForSSAIndex.size(); ++i)
 167                 dataLog("    ", i, ": ", VariableAccessDataDump(m_graph, m_variableForSSAIndex[i]), "\n");
 168             dataLog("\n");
 169             dataLog("SSA calculator: ", m_calculator, "\n");
 170         }
 171
 172         // Do the bulk of the SSA conversion. For each block, this tracks the operand->Node
 173         // mapping based on a combination of what the SSACalculator tells us, and us walking over
 174         // the block in forward order. We use our own data structure, valueForOperand, for
 175         // determining the local mapping, but we rely on SSACalculator for the non-local mapping.
 176         //
 177         // This does three things at once:
 178         //
 179         // - Inserts the Phis in all of the places where they need to go. We've already created
 180         //   them and they are accounted for in the SSACalculator's data structures, but we
 181         //   haven't inserted them yet, mostly because we want to insert all of a block's Phis in
 182         //   one go to amortize the cost of node insertion.
 183         //
 184         // - Create and insert Upsilons.
 185         //
 186         // - Convert all of the preexisting SSA nodes (other than the old CPS Phi nodes) into SSA
 187         //   form by replacing as follows:
 188         //
 189         //   - MovHint has KillLocal prepended to it.
 190         //
 191         //   - GetLocal die and get replaced with references to the node specified by
 192         //     valueForOperand.
 193         //
 194         //   - SetLocal turns into PutStack if it's flushed, or turns into a Check otherwise.
 195         //
 196         //   - Flush loses its children and turns into a Phantom.
 197         //
 198         //   - PhantomLocal becomes Phantom, and its child is whatever is specified by
 199         //     valueForOperand.
 200         //
 201         //   - SetArgument is removed. Note that GetStack nodes have already been inserted.
 202         Operands<Node*> valueForOperand(OperandsLike, m_graph.block(0)->variablesAtHead);
 203         for (BasicBlock* block : m_graph.blocksInPreOrder()) {
 204             valueForOperand.clear();
 205
 206             // CPS will claim that the root block has all arguments live. But we have already done
 207             // the first step of SSA conversion: argument locals are no longer live at head;
 208             // instead we have GetStack nodes for extracting the values of arguments. So, we
 209             // skip the at-head available value calculation for the root block.
 210             if (block != m_graph.block(0)) {
 211                 for (size_t i = valueForOperand.size(); i--;) {
 212                     Node* nodeAtHead = block->variablesAtHead[i];
 213                     if (!nodeAtHead)
 214                         continue;
 215
 216                     VariableAccessData* variable = nodeAtHead->variableAccessData();
 217
 218                     if (verbose)
 219                         dataLog("Considering live variable ", VariableAccessDataDump(m_graph, variable), " at head of block ", *block, "\n");
 220
 221                     SSACalculator::Variable* ssaVariable = m_ssaVariableForVariable.get(variable);
 222                     SSACalculator::Def* def = m_calculator.reachingDefAtHead(block, ssaVariable);
 223                     if (!def) {
 224                         // If we are required to insert a Phi, then we won't have a reaching def
 225                         // at head.
 226                         continue;
 227                     }
 228
 229                     Node* node = def->value();
 230                     if (node->replacement()) {
 231                         // This will occur when a SetLocal had a GetLocal as its source. The
 232                         // GetLocal would get replaced with an actual SSA value by the time we get
 233                         // here. Note that the SSA value with which the GetLocal got replaced
 234                         // would not in turn have a replacement.
 235                         node = node->replacement();
 236                         ASSERT(!node->replacement());
 237                     }
 238                     if (verbose)
 239                         dataLog("Mapping: ", VirtualRegister(valueForOperand.operandForIndex(i)), " -> ", node, "\n");
 240                     valueForOperand[i] = node;
 241                 }
 242             }
 243
 244             // Insert Phis by asking the calculator what phis there are in this block. Also update
 245             // valueForOperand with those Phis. For Phis associated with variables that are not
 246             // flushed, we also insert a MovHint.
 247             size_t phiInsertionPoint = 0;
 248             for (SSACalculator::Def* phiDef : m_calculator.phisForBlock(block)) {
 249                 VariableAccessData* variable = m_variableForSSAIndex[phiDef->variable()->index()];
 250
 251                 m_insertionSet.insert(phiInsertionPoint, phiDef->value());
 252                 valueForOperand.operand(variable->local()) = phiDef->value();
 253
 254                 m_insertionSet.insertNode(
 255                     phiInsertionPoint, SpecNone, MovHint, NodeOrigin(),
 256                     OpInfo(variable->local().offset()), phiDef->value()->defaultEdge());
 257             }
 258
 259             for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
 260                 Node* node = block->at(nodeIndex);
 261
 262                 if (verbose) {
 263                     dataLog("Processing node ", node, ":\n");
 264                     m_graph.dump(WTF::dataFile(), "    ", node);
 265                 }
 266
 267                 m_graph.performSubstitution(node);
 268
 269                 switch (node->op()) {
 270                 case MovHint: {
 271                     m_insertionSet.insertNode(
 272                         nodeIndex, SpecNone, KillStack, node->origin,
 273                         OpInfo(node->unlinkedLocal().offset()));
 274                     break;
 275                 }
 276
 277                 case SetLocal: {
 278                     VariableAccessData* variable = node->variableAccessData();
 279                     Node* child = node->child1().node();
 280
 281                     if (!!(node->flags() & NodeIsFlushed)) {
 282                         node->convertToPutStack(
 283                             m_graph.m_stackAccessData.add(
 284                                 variable->local(), variable->flushFormat()));
 285                     } else
 286                         node->remove();
 287
 288                     if (verbose)
 289                         dataLog("Mapping: ", variable->local(), " -> ", child, "\n");
 290                     valueForOperand.operand(variable->local()) = child;
 291                     break;
 292                 }
 293
 294                 case GetStack: {
 295                     ASSERT(m_argumentGetters.contains(node));
 296                     valueForOperand.operand(node->stackAccessData()->local) = node;
 297                     break;
 298                 }
 299
 300                 case GetLocal: {
 301                     VariableAccessData* variable = node->variableAccessData();
 302                     node->children.reset();
 303
 304                     node->remove();
 305                     if (verbose)
 306                         dataLog("Replacing node ", node, " with ", valueForOperand.operand(variable->local()), "\n");
 307                     node->setReplacement(valueForOperand.operand(variable->local()));
 308                     break;
 309                 }
 310
 311                 case Flush: {
 312                     node->children.reset();
 313                     node->remove();
 314                     break;
 315                 }
 316
 317                 case PhantomLocal: {
 318                     ASSERT(node->child1().useKind() == UntypedUse);
 319                     VariableAccessData* variable = node->variableAccessData();
 320                     node->child1() = valueForOperand.operand(variable->local())->defaultEdge();
 321                     node->remove();
 322                     break;
 323                 }
 324
 325                 case SetArgument: {
 326                     node->remove();
 327                     break;
 328                 }
 329
 330                 default:
 331                     break;
 332                 }
 333             }
 334
 335             // We want to insert Upsilons just before the end of the block. On the surface this
 336             // seems dangerous because the Upsilon will have a checking UseKind. But, we will not
 337             // actually be performing the check at the point of the Upsilon; the check will
 338             // already have been performed at the point where the original SetLocal was.
 339             NodeAndIndex terminal = block->findTerminal();
 340             size_t upsilonInsertionPoint = terminal.index;
 341             NodeOrigin upsilonOrigin = terminal.node->origin;
 342             for (unsigned successorIndex = block->numSuccessors(); successorIndex--;) {
 343                 BasicBlock* successorBlock = block->successor(successorIndex);
 344                 for (SSACalculator::Def* phiDef : m_calculator.phisForBlock(successorBlock)) {
 345                     Node* phiNode = phiDef->value();
 346                     SSACalculator::Variable* ssaVariable = phiDef->variable();
 347                     VariableAccessData* variable = m_variableForSSAIndex[ssaVariable->index()];
 348                     FlushFormat format = variable->flushFormat();
 349                     UseKind useKind = useKindFor(format);
 350
 351                     m_insertionSet.insertNode(
 352                         upsilonInsertionPoint, SpecNone, Upsilon, upsilonOrigin,
 353                         OpInfo(phiNode), Edge(
 354                             valueForOperand.operand(variable->local()),
 355                             useKind));
 356                 }
 357             }
 358
 359             m_insertionSet.execute(block);
 360         }
 361
 362         // Free all CPS phis and reset variables vectors.
 363         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
 364             BasicBlock* block = m_graph.block(blockIndex);
 365             if (!block)
 366                 continue;
 367             for (unsigned phiIndex = block->phis.size(); phiIndex--;)
 368                 m_graph.m_allocator.free(block->phis[phiIndex]);
 369             block->phis.clear();
 370             block->variablesAtHead.clear();
 371             block->variablesAtTail.clear();
 372             block->valuesAtHead.clear();
 373             block->valuesAtHead.clear();
 374             block->ssa = std::make_unique<BasicBlock::SSAData>(block);
 375         }
 376
 377         m_graph.m_argumentFormats.resize(m_graph.m_arguments.size());
 378         for (unsigned i = m_graph.m_arguments.size(); i--;) {
 379             FlushFormat format = FlushedJSValue;
 380
 381             Node* node = m_argumentMapping.get(m_graph.m_arguments[i]);
 382
 383             RELEASE_ASSERT(node);
 384             format = node->stackAccessData()->format;
 385
 386             m_graph.m_argumentFormats[i] = format;
 387             m_graph.m_arguments[i] = node; // Record the load that loads the arguments for the benefit of exit profiling.
 388         }
 389
 390         m_graph.m_form = SSA;
 391
 392         if (verbose) {
 393             dataLog("Graph after SSA transformation:\n");
 394             m_graph.dump();
 395         }
 396
 397         return true;
 398     }
 399
 400 private:
 401     SSACalculator m_calculator;
 402     InsertionSet m_insertionSet;
 403     HashMap<VariableAccessData*, SSACalculator::Variable*> m_ssaVariableForVariable;
 404     HashMap<Node*, Node*> m_argumentMapping;
 405     HashSet<Node*> m_argumentGetters;
 406     Vector<VariableAccessData*> m_variableForSSAIndex;
 407 };
 408
 409 bool performSSAConversion(Graph& graph)
 410 {
 411     SamplingRegion samplingRegion("DFG SSA Conversion Phase");
 412     return runPhase<SSAConversionPhase>(graph);
 413 }
 414
 415 } } // namespace JSC::DFG
 416
 417 #endif // ENABLE(DFG_JIT)
 418