dfg/DFGSSAConversionPhase.cpp

   1 /*
   2  * Copyright (C) 2013, 2014 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 "JSCInlines.h"
  36
  37 namespace JSC { namespace DFG {
  38
  39 class SSAConversionPhase : public Phase {
  40     static const bool verbose = false;
  41     static const bool dumpGraph = false;
  42
  43 public:
  44     SSAConversionPhase(Graph& graph)
  45         : Phase(graph, "SSA conversion")
  46         , m_insertionSet(graph)
  47         , m_changed(false)
  48     {
  49     }
  50
  51     bool run()
  52     {
  53         RELEASE_ASSERT(m_graph.m_form == ThreadedCPS);
  54
  55         if (dumpGraph) {
  56             dataLog("Graph dump at top of SSA conversion:\n");
  57             m_graph.dump();
  58         }
  59
  60         // Eliminate all duplicate or self-pointing Phi edges. This means that
  61         // we transform:
  62         //
  63         // p: Phi(@n1, @n2, @n3)
  64         //
  65         // into:
  66         //
  67         // p: Phi(@x)
  68         //
  69         // if each @ni in {@n1, @n2, @n3} is either equal to @p to is equal
  70         // to @x, for exactly one other @x. Additionally, trivial Phis (i.e.
  71         // p: Phi(@x)) are forwarded, so that if have an edge to such @p, we
  72         // replace it with @x. This loop does this for Phis only; later we do
  73         // such forwarding for Phi references found in other nodes.
  74         //
  75         // See Aycock and Horspool in CC'00 for a better description of what
  76         // we're doing here.
  77         do {
  78             m_changed = false;
  79             for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
  80                 BasicBlock* block = m_graph.block(blockIndex);
  81                 if (!block)
  82                     continue;
  83                 for (unsigned phiIndex = block->phis.size(); phiIndex--;) {
  84                     Node* phi = block->phis[phiIndex];
  85                     if (phi->variableAccessData()->isCaptured())
  86                         continue;
  87                     forwardPhiChildren(phi);
  88                     deduplicateChildren(phi);
  89                 }
  90             }
  91         } while (m_changed);
  92
  93         // For each basic block, for each local live at the head of that block,
  94         // figure out what node we should be referring to instead of that local.
  95         // If it turns out to be a non-trivial Phi, make sure that we create an
  96         // SSA Phi and Upsilons in predecessor blocks. We reuse
  97         // BasicBlock::variablesAtHead for tracking which nodes to refer to.
  98         Operands<bool> nonTrivialPhis(OperandsLike, m_graph.block(0)->variablesAtHead);
  99         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
 100             BasicBlock* block = m_graph.block(blockIndex);
 101             if (!block)
 102                 continue;
 103
 104             nonTrivialPhis.fill(false);
 105             for (unsigned i = block->phis.size(); i--;) {
 106                 Node* phi = block->phis[i];
 107                 if (!phi->children.justOneChild())
 108                     nonTrivialPhis.operand(phi->local()) = true;
 109             }
 110
 111             for (unsigned i = block->variablesAtHead.size(); i--;) {
 112                 Node* node = block->variablesAtHead[i];
 113                 if (!node)
 114                     continue;
 115
 116                 if (verbose)
 117                     dataLog("At block #", blockIndex, " for operand r", block->variablesAtHead.operandForIndex(i), " have node ", node, "\n");
 118
 119                 VariableAccessData* variable = node->variableAccessData();
 120                 if (variable->isCaptured()) {
 121                     // Poison this entry in variablesAtHead because we don't
 122                     // want anyone to try to refer to it, if the variable is
 123                     // captured.
 124                     block->variablesAtHead[i] = 0;
 125                     continue;
 126                 }
 127
 128                 switch (node->op()) {
 129                 case Phi:
 130                 case SetArgument:
 131                     break;
 132                 case Flush:
 133                 case GetLocal:
 134                 case PhantomLocal:
 135                     node = node->child1().node();
 136                     break;
 137                 default:
 138                     RELEASE_ASSERT_NOT_REACHED();
 139                 }
 140                 RELEASE_ASSERT(node->op() == Phi || node->op() == SetArgument);
 141
 142                 bool isFlushed = !!(node->flags() & NodeIsFlushed);
 143
 144                 if (node->op() == Phi) {
 145                     if (!nonTrivialPhis.operand(node->local())) {
 146                         Edge edge = node->children.justOneChild();
 147                         ASSERT(edge);
 148                         if (verbose)
 149                             dataLog("    One child: ", edge, ", ", RawPointer(edge.node()), "\n");
 150                         node = edge.node(); // It's something from a different basic block.
 151                     } else {
 152                         if (verbose)
 153                             dataLog("    Non-trivial.\n");
 154                         // It's a non-trivial Phi.
 155                         FlushFormat format = variable->flushFormat();
 156                         NodeFlags result = resultFor(format);
 157                         UseKind useKind = useKindFor(format);
 158
 159                         node = m_insertionSet.insertNode(0, SpecNone, Phi, NodeOrigin());
 160                         if (verbose)
 161                             dataLog("    Inserted new node: ", node, "\n");
 162                         node->mergeFlags(result);
 163                         RELEASE_ASSERT((node->flags() & NodeResultMask) == result);
 164
 165                         for (unsigned j = block->predecessors.size(); j--;) {
 166                             BasicBlock* predecessor = block->predecessors[j];
 167                             predecessor->appendNonTerminal(
 168                                 m_graph, SpecNone, Upsilon, predecessor->last()->origin,
 169                                 OpInfo(node), Edge(predecessor->variablesAtTail[i], useKind));
 170                         }
 171
 172                         if (isFlushed) {
 173                             // Do nothing. For multiple reasons.
 174
 175                             // Reason #1: If the local is flushed then we don't need to bother
 176                             // with a MovHint since every path to this point in the code will
 177                             // have flushed the bytecode variable using a SetLocal and hence
 178                             // the Availability::flushedAt() will agree, and that will be
 179                             // sufficient for figuring out how to recover the variable's value.
 180
 181                             // Reason #2: If we had inserted a MovHint and the Phi function had
 182                             // died (because the only user of the value was the "flush" - i.e.
 183                             // some asynchronous runtime thingy) then the MovHint would turn
 184                             // into a ZombieHint, which would fool us into thinking that the
 185                             // variable is dead.
 186
 187                             // Reason #3: If we had inserted a MovHint then even if the Phi
 188                             // stayed alive, we would still end up generating inefficient code
 189                             // since we would be telling the OSR exit compiler to use some SSA
 190                             // value for the bytecode variable rather than just telling it that
 191                             // the value was already on the stack.
 192                         } else {
 193                             m_insertionSet.insertNode(
 194                                 0, SpecNone, MovHint, NodeOrigin(),
 195                                 OpInfo(variable->local().offset()), node->defaultEdge());
 196                         }
 197                     }
 198                 }
 199
 200                 block->variablesAtHead[i] = node;
 201             }
 202
 203             m_insertionSet.execute(block);
 204         }
 205
 206         if (verbose) {
 207             dataLog("Variables at head after SSA Phi insertion:\n");
 208             for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
 209                 BasicBlock* block = m_graph.block(blockIndex);
 210                 if (!block)
 211                     continue;
 212                 dataLog("    ", *block, ": ", block->variablesAtHead, "\n");
 213             }
 214         }
 215
 216         // At this point variablesAtHead in each block refers to either:
 217         //
 218         // 1) A new SSA phi in the current block.
 219         // 2) A SetArgument, which will soon get converted into a GetArgument.
 220         // 3) An old CPS phi in a different block.
 221         //
 222         // We don't have to do anything for (1) and (2), but we do need to
 223         // do a replacement for (3).
 224
 225         // Clear all replacements, since other phases may have used them.
 226         m_graph.clearReplacements();
 227
 228         if (dumpGraph) {
 229             dataLog("Graph just before identifying replacements:\n");
 230             m_graph.dump();
 231         }
 232
 233         // For all of the old CPS Phis, figure out what they correspond to in SSA.
 234         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
 235             BasicBlock* block = m_graph.block(blockIndex);
 236             if (!block)
 237                 continue;
 238             if (verbose)
 239                 dataLog("Dealing with block #", blockIndex, "\n");
 240             for (unsigned phiIndex = block->phis.size(); phiIndex--;) {
 241                 Node* phi = block->phis[phiIndex];
 242                 if (verbose) {
 243                     dataLog(
 244                         "Considering ", phi, " (", RawPointer(phi), "), for r",
 245                         phi->local(), ", and its replacement in ", *block, ", ",
 246                         block->variablesAtHead.operand(phi->local()), "\n");
 247                 }
 248                 ASSERT(phi != block->variablesAtHead.operand(phi->local()));
 249                 phi->misc.replacement = block->variablesAtHead.operand(phi->local());
 250             }
 251         }
 252
 253         // Now make sure that all variablesAtHead in each block points to the
 254         // canonical SSA value. Prior to this, variablesAtHead[local] may point to
 255         // an old CPS Phi in a different block.
 256         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
 257             BasicBlock* block = m_graph.block(blockIndex);
 258             if (!block)
 259                 continue;
 260             for (size_t i = block->variablesAtHead.size(); i--;) {
 261                 Node* node = block->variablesAtHead[i];
 262                 if (!node)
 263                     continue;
 264                 while (node->misc.replacement) {
 265                     ASSERT(node != node->misc.replacement);
 266                     node = node->misc.replacement;
 267                 }
 268                 block->variablesAtHead[i] = node;
 269             }
 270         }
 271
 272         if (verbose) {
 273             dataLog("Variables at head after convergence:\n");
 274             for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
 275                 BasicBlock* block = m_graph.block(blockIndex);
 276                 if (!block)
 277                     continue;
 278                 dataLog("    ", *block, ": ", block->variablesAtHead, "\n");
 279             }
 280         }
 281
 282         // Convert operations over locals into operations over SSA nodes.
 283         // - GetLocal over captured variables lose their phis.
 284         // - GetLocal over uncaptured variables die and get replaced with references
 285         //   to the node specified by variablesAtHead.
 286         // - SetLocal gets NodeMustGenerate if it's flushed, or turns into a
 287         //   Check otherwise.
 288         // - Flush loses its children and turns into a Phantom.
 289         // - PhantomLocal becomes Phantom, and its child is whatever is specified
 290         //   by variablesAtHead.
 291         // - SetArgument turns into GetArgument unless it's a captured variable.
 292         // - Upsilons get their children fixed to refer to the true value of that local
 293         //   at the end of the block. Prior to this loop, Upsilons will refer to
 294         //   variableAtTail[operand], which may be any of Flush, PhantomLocal, GetLocal,
 295         //   SetLocal, SetArgument, or Phi. We accomplish this by setting the
 296         //   replacement pointers of all of those nodes to refer to either
 297         //   variablesAtHead[operand], or the child of the SetLocal.
 298         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
 299             BasicBlock* block = m_graph.block(blockIndex);
 300             if (!block)
 301                 continue;
 302
 303             for (unsigned phiIndex = block->phis.size(); phiIndex--;) {
 304                 block->phis[phiIndex]->misc.replacement =
 305                     block->variablesAtHead.operand(block->phis[phiIndex]->local());
 306             }
 307             for (unsigned nodeIndex = block->size(); nodeIndex--;)
 308                 ASSERT(!block->at(nodeIndex)->misc.replacement);
 309
 310             for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
 311                 Node* node = block->at(nodeIndex);
 312
 313                 m_graph.performSubstitution(node);
 314
 315                 switch (node->op()) {
 316                 case SetLocal: {
 317                     VariableAccessData* variable = node->variableAccessData();
 318                     if (variable->isCaptured() || !!(node->flags() & NodeIsFlushed))
 319                         node->mergeFlags(NodeMustGenerate);
 320                     else
 321                         node->setOpAndDefaultFlags(Check);
 322                     node->misc.replacement = node->child1().node(); // Only for Upsilons.
 323                     break;
 324                 }
 325
 326                 case GetLocal: {
 327                     // It seems tempting to just do forwardPhi(GetLocal), except that we
 328                     // could have created a new (SSA) Phi, and the GetLocal could still be
 329                     // referring to an old (CPS) Phi. Uses variablesAtHead to tell us what
 330                     // to refer to.
 331                     node->children.reset();
 332                     VariableAccessData* variable = node->variableAccessData();
 333                     if (variable->isCaptured())
 334                         break;
 335                     node->convertToPhantom();
 336                     node->misc.replacement = block->variablesAtHead.operand(variable->local());
 337                     break;
 338                 }
 339
 340                 case Flush: {
 341                     node->children.reset();
 342                     node->convertToPhantom();
 343                     // This is only for Upsilons. An Upsilon will only refer to a Flush if
 344                     // there were no SetLocals or GetLocals in the block.
 345                     node->misc.replacement = block->variablesAtHead.operand(node->local());
 346                     break;
 347                 }
 348
 349                 case PhantomLocal: {
 350                     ASSERT(node->child1().useKind() == UntypedUse);
 351                     VariableAccessData* variable = node->variableAccessData();
 352                     if (variable->isCaptured()) {
 353                         // This is a fun case. We could have a captured variable that had some
 354                         // or all of its uses strength reduced to phantoms rather than flushes.
 355                         // SSA conversion will currently still treat it as flushed, in the sense
 356                         // that it will just keep the SetLocal. Therefore, there is nothing that
 357                         // needs to be done here: we don't need to also keep the source value
 358                         // alive. And even if we did want to keep the source value alive, we
 359                         // wouldn't be able to, because the variablesAtHead value for a captured
 360                         // local wouldn't have been computed by the Phi reduction algorithm
 361                         // above.
 362                         node->children.reset();
 363                     } else {
 364                         node->child1() =
 365                             block->variablesAtHead.operand(variable->local())->defaultEdge();
 366                     }
 367                     node->convertToPhantom();
 368                     // This is only for Upsilons. An Upsilon will only refer to a
 369                     // PhantomLocal if there were no SetLocals or GetLocals in the block.
 370                     node->misc.replacement = block->variablesAtHead.operand(variable->local());
 371                     break;
 372                 }
 373
 374                 case SetArgument: {
 375                     VariableAccessData* variable = node->variableAccessData();
 376                     if (variable->isCaptured())
 377                         break;
 378                     node->setOpAndDefaultFlags(GetArgument);
 379                     node->setResult(resultFor(node->variableAccessData()->flushFormat()));
 380                     break;
 381                 }
 382
 383                 default:
 384                     break;
 385                 }
 386             }
 387         }
 388
 389         // Free all CPS phis and reset variables vectors.
 390         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
 391             BasicBlock* block = m_graph.block(blockIndex);
 392             if (!block)
 393                 continue;
 394             for (unsigned phiIndex = block->phis.size(); phiIndex--;)
 395                 m_graph.m_allocator.free(block->phis[phiIndex]);
 396             block->phis.clear();
 397             block->variablesAtHead.clear();
 398             block->variablesAtTail.clear();
 399             block->valuesAtHead.clear();
 400             block->valuesAtHead.clear();
 401             block->ssa = adoptPtr(new BasicBlock::SSAData(block));
 402         }
 403
 404         m_graph.m_arguments.clear();
 405
 406         m_graph.m_form = SSA;
 407         return true;
 408     }
 409
 410 private:
 411     void forwardPhiChildren(Node* node)
 412     {
 413         for (unsigned i = 0; i < AdjacencyList::Size; ++i) {
 414             Edge& edge = node->children.child(i);
 415             if (!edge)
 416                 break;
 417             m_changed |= forwardPhiEdge(edge);
 418         }
 419     }
 420
 421     Node* forwardPhi(Node* node)
 422     {
 423         for (;;) {
 424             switch (node->op()) {
 425             case Phi: {
 426                 Edge edge = node->children.justOneChild();
 427                 if (!edge)
 428                     return node;
 429                 node = edge.node();
 430                 break;
 431             }
 432             case GetLocal:
 433             case SetLocal:
 434                 if (node->variableAccessData()->isCaptured())
 435                     return node;
 436                 node = node->child1().node();
 437                 break;
 438             default:
 439                 return node;
 440             }
 441         }
 442     }
 443
 444     bool forwardPhiEdge(Edge& edge)
 445     {
 446         Node* newNode = forwardPhi(edge.node());
 447         if (newNode == edge.node())
 448             return false;
 449         edge.setNode(newNode);
 450         return true;
 451     }
 452
 453     void deduplicateChildren(Node* node)
 454     {
 455         for (unsigned i = 0; i < AdjacencyList::Size; ++i) {
 456             Edge edge = node->children.child(i);
 457             if (!edge)
 458                 break;
 459             if (edge == node) {
 460                 node->children.removeEdge(i--);
 461                 m_changed = true;
 462                 continue;
 463             }
 464             for (unsigned j = i + 1; j < AdjacencyList::Size; ++j) {
 465                 if (node->children.child(j) == edge) {
 466                     node->children.removeEdge(j--);
 467                     m_changed = true;
 468                 }
 469             }
 470         }
 471     }
 472
 473     InsertionSet m_insertionSet;
 474     bool m_changed;
 475 };
 476
 477 bool performSSAConversion(Graph& graph)
 478 {
 479     SamplingRegion samplingRegion("DFG SSA Conversion Phase");
 480     return runPhase<SSAConversionPhase>(graph);
 481 }
 482
 483 } } // namespace JSC::DFG
 484
 485 #endif // ENABLE(DFG_JIT)
 486