dfg/DFGCPSRethreadingPhase.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 "DFGCPSRethreadingPhase.h"
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "DFGBasicBlockInlines.h"
  32 #include "DFGGraph.h"
  33 #include "DFGPhase.h"
  34 #include "JSCInlines.h"
  35
  36 namespace JSC { namespace DFG {
  37
  38 class CPSRethreadingPhase : public Phase {
  39 public:
  40     CPSRethreadingPhase(Graph& graph)
  41         : Phase(graph, "CPS rethreading")
  42     {
  43     }
  44
  45     bool run()
  46     {
  47         RELEASE_ASSERT(m_graph.m_refCountState == EverythingIsLive);
  48
  49         if (m_graph.m_form == ThreadedCPS)
  50             return false;
  51
  52         clearIsLoadedFrom();
  53         freeUnnecessaryNodes();
  54         m_graph.clearReplacements();
  55         canonicalizeLocalsInBlocks();
  56         propagatePhis<LocalOperand>();
  57         propagatePhis<ArgumentOperand>();
  58         computeIsFlushed();
  59
  60         m_graph.m_form = ThreadedCPS;
  61         return true;
  62     }
  63
  64 private:
  65
  66     void clearIsLoadedFrom()
  67     {
  68         for (unsigned i = 0; i < m_graph.m_variableAccessData.size(); ++i)
  69             m_graph.m_variableAccessData[i].setIsLoadedFrom(false);
  70     }
  71
  72     void freeUnnecessaryNodes()
  73     {
  74         SamplingRegion samplingRegion("DFG CPS Rethreading: freeUnnecessaryNodes");
  75
  76         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
  77             BasicBlock* block = m_graph.block(blockIndex);
  78             if (!block)
  79                 continue;
  80             ASSERT(block->isReachable);
  81
  82             unsigned fromIndex = 0;
  83             unsigned toIndex = 0;
  84             while (fromIndex < block->size()) {
  85                 Node* node = block->at(fromIndex++);
  86                 switch (node->op()) {
  87                 case GetLocal:
  88                 case Flush:
  89                 case PhantomLocal:
  90                     node->children.setChild1(Edge());
  91                     break;
  92                 case Phantom:
  93                     if (!node->child1())
  94                         continue;
  95                     switch (node->child1()->op()) {
  96                     case Phi:
  97                     case SetArgument:
  98                     case SetLocal:
  99                         node->convertToPhantomLocal();
 100                         break;
 101                     default:
 102                         ASSERT(node->child1()->hasResult());
 103                         break;
 104                     }
 105                     break;
 106                 default:
 107                     break;
 108                 }
 109                 block->at(toIndex++) = node;
 110             }
 111             block->resize(toIndex);
 112
 113             for (unsigned phiIndex = block->phis.size(); phiIndex--;)
 114                 m_graph.m_allocator.free(block->phis[phiIndex]);
 115             block->phis.resize(0);
 116         }
 117     }
 118
 119     template<OperandKind operandKind>
 120     void clearVariablesAtHeadAndTail()
 121     {
 122         ASSERT(
 123             m_block->variablesAtHead.sizeFor<operandKind>()
 124             == m_block->variablesAtTail.sizeFor<operandKind>());
 125
 126         for (unsigned i = m_block->variablesAtHead.sizeFor<operandKind>(); i--;) {
 127             m_block->variablesAtHead.atFor<operandKind>(i) = 0;
 128             m_block->variablesAtTail.atFor<operandKind>(i) = 0;
 129         }
 130     }
 131
 132     ALWAYS_INLINE Node* addPhiSilently(BasicBlock* block, const NodeOrigin& origin, VariableAccessData* variable)
 133     {
 134         Node* result = m_graph.addNode(SpecNone, Phi, origin, OpInfo(variable));
 135         block->phis.append(result);
 136         return result;
 137     }
 138
 139     template<OperandKind operandKind>
 140     ALWAYS_INLINE Node* addPhi(BasicBlock* block, const NodeOrigin& origin, VariableAccessData* variable, size_t index)
 141     {
 142         Node* result = addPhiSilently(block, origin, variable);
 143         phiStackFor<operandKind>().append(PhiStackEntry(block, index, result));
 144         return result;
 145     }
 146
 147     template<OperandKind operandKind>
 148     ALWAYS_INLINE Node* addPhi(const NodeOrigin& origin, VariableAccessData* variable, size_t index)
 149     {
 150         return addPhi<operandKind>(m_block, origin, variable, index);
 151     }
 152
 153     template<OperandKind operandKind>
 154     void canonicalizeGetLocalFor(Node* node, VariableAccessData* variable, size_t idx)
 155     {
 156         ASSERT(!node->child1());
 157
 158         if (Node* otherNode = m_block->variablesAtTail.atFor<operandKind>(idx)) {
 159             ASSERT(otherNode->variableAccessData() == variable);
 160
 161             switch (otherNode->op()) {
 162             case Flush:
 163             case PhantomLocal:
 164                 otherNode = otherNode->child1().node();
 165                 if (otherNode->op() == Phi) {
 166                     // We need to have a GetLocal, so this might as well be the one.
 167                     node->children.setChild1(Edge(otherNode));
 168                     m_block->variablesAtTail.atFor<operandKind>(idx) = node;
 169                     return;
 170                 }
 171                 ASSERT(otherNode->op() == SetLocal || otherNode->op() == SetArgument);
 172                 break;
 173             default:
 174                 break;
 175             }
 176
 177             ASSERT(otherNode->op() == SetLocal || otherNode->op() == SetArgument || otherNode->op() == GetLocal);
 178             ASSERT(otherNode->variableAccessData() == variable);
 179
 180             if (otherNode->op() == SetArgument) {
 181                 variable->setIsLoadedFrom(true);
 182                 node->children.setChild1(Edge(otherNode));
 183                 m_block->variablesAtTail.atFor<operandKind>(idx) = node;
 184                 return;
 185             }
 186
 187             if (variable->isCaptured()) {
 188                 variable->setIsLoadedFrom(true);
 189                 if (otherNode->op() == GetLocal)
 190                     otherNode = otherNode->child1().node();
 191                 else
 192                     ASSERT(otherNode->op() == SetLocal || otherNode->op() == SetArgument);
 193
 194                 ASSERT(otherNode->op() == Phi || otherNode->op() == SetLocal || otherNode->op() == SetArgument);
 195
 196                 // Keep this GetLocal but link it to the prior ones.
 197                 node->children.setChild1(Edge(otherNode));
 198                 m_block->variablesAtTail.atFor<operandKind>(idx) = node;
 199                 return;
 200             }
 201
 202             if (otherNode->op() == GetLocal) {
 203                 // Replace all references to this GetLocal with otherNode.
 204                 node->misc.replacement = otherNode;
 205                 return;
 206             }
 207
 208             ASSERT(otherNode->op() == SetLocal);
 209             node->misc.replacement = otherNode->child1().node();
 210             return;
 211         }
 212
 213         variable->setIsLoadedFrom(true);
 214         Node* phi = addPhi<operandKind>(node->origin, variable, idx);
 215         node->children.setChild1(Edge(phi));
 216         m_block->variablesAtHead.atFor<operandKind>(idx) = phi;
 217         m_block->variablesAtTail.atFor<operandKind>(idx) = node;
 218     }
 219
 220     void canonicalizeGetLocal(Node* node)
 221     {
 222         VariableAccessData* variable = node->variableAccessData();
 223         if (variable->local().isArgument())
 224             canonicalizeGetLocalFor<ArgumentOperand>(node, variable, variable->local().toArgument());
 225         else
 226             canonicalizeGetLocalFor<LocalOperand>(node, variable, variable->local().toLocal());
 227     }
 228
 229     void canonicalizeSetLocal(Node* node)
 230     {
 231         m_block->variablesAtTail.setOperand(node->local(), node);
 232     }
 233
 234     template<NodeType nodeType, OperandKind operandKind>
 235     void canonicalizeFlushOrPhantomLocalFor(Node* node, VariableAccessData* variable, size_t idx)
 236     {
 237         ASSERT(!node->child1());
 238
 239         if (Node* otherNode = m_block->variablesAtTail.atFor<operandKind>(idx)) {
 240             ASSERT(otherNode->variableAccessData() == variable);
 241
 242             switch (otherNode->op()) {
 243             case Flush:
 244             case PhantomLocal:
 245             case GetLocal:
 246                 otherNode = otherNode->child1().node();
 247                 break;
 248             default:
 249                 break;
 250             }
 251
 252             ASSERT(otherNode->op() == Phi || otherNode->op() == SetLocal || otherNode->op() == SetArgument);
 253
 254             if (nodeType == PhantomLocal && otherNode->op() == SetLocal) {
 255                 // PhantomLocal(SetLocal) doesn't make sense. PhantomLocal means: at this
 256                 // point I know I would have been interested in the value of this variable
 257                 // for the purpose of OSR. PhantomLocal(SetLocal) means: at this point I
 258                 // know that I would have read the value written by that SetLocal. This is
 259                 // redundant and inefficient, since really it just means that we want to
 260                 // be keeping the operand to the SetLocal alive. The SetLocal may die, and
 261                 // we'll be fine because OSR tracks dead SetLocals.
 262
 263                 // So we turn this into a Phantom on the child of the SetLocal.
 264
 265                 node->convertToPhantom();
 266                 node->children.setChild1(otherNode->child1());
 267                 return;
 268             }
 269
 270             variable->setIsLoadedFrom(true);
 271             // There is nothing wrong with having redundant Flush's. It just needs to
 272             // be linked appropriately. Note that if there had already been a previous
 273             // use at tail then we don't override it. It's fine for variablesAtTail to
 274             // omit Flushes and PhantomLocals. On the other hand, having it refer to a
 275             // Flush or a PhantomLocal if just before it the last use was a GetLocal would
 276             // seriously confuse the CFA.
 277             node->children.setChild1(Edge(otherNode));
 278             return;
 279         }
 280
 281         variable->setIsLoadedFrom(true);
 282         node->children.setChild1(Edge(addPhi<operandKind>(node->origin, variable, idx)));
 283         m_block->variablesAtHead.atFor<operandKind>(idx) = node;
 284         m_block->variablesAtTail.atFor<operandKind>(idx) = node;
 285     }
 286
 287     template<NodeType nodeType>
 288     void canonicalizeFlushOrPhantomLocal(Node* node)
 289     {
 290         VariableAccessData* variable = node->variableAccessData();
 291         if (variable->local().isArgument())
 292             canonicalizeFlushOrPhantomLocalFor<nodeType, ArgumentOperand>(node, variable, variable->local().toArgument());
 293         else
 294             canonicalizeFlushOrPhantomLocalFor<nodeType, LocalOperand>(node, variable, variable->local().toLocal());
 295     }
 296
 297     void canonicalizeSetArgument(Node* node)
 298     {
 299         VirtualRegister local = node->local();
 300         ASSERT(local.isArgument());
 301         int argument = local.toArgument();
 302         m_block->variablesAtHead.setArgumentFirstTime(argument, node);
 303         m_block->variablesAtTail.setArgumentFirstTime(argument, node);
 304     }
 305
 306     void canonicalizeLocalsInBlock()
 307     {
 308         if (!m_block)
 309             return;
 310         ASSERT(m_block->isReachable);
 311
 312         clearVariablesAtHeadAndTail<ArgumentOperand>();
 313         clearVariablesAtHeadAndTail<LocalOperand>();
 314
 315         // Assumes that all phi references have been removed. Assumes that things that
 316         // should be live have a non-zero ref count, but doesn't assume that the ref
 317         // counts are correct beyond that (more formally !!logicalRefCount == !!actualRefCount
 318         // but not logicalRefCount == actualRefCount). Assumes that it can break ref
 319         // counts.
 320
 321         for (unsigned nodeIndex = 0; nodeIndex < m_block->size(); ++nodeIndex) {
 322             Node* node = m_block->at(nodeIndex);
 323
 324             m_graph.performSubstitution(node);
 325
 326             // The rules for threaded CPS form:
 327             //
 328             // Head variable: describes what is live at the head of the basic block.
 329             // Head variable links may refer to Flush, PhantomLocal, Phi, or SetArgument.
 330             // SetArgument may only appear in the root block.
 331             //
 332             // Tail variable: the last thing that happened to the variable in the block.
 333             // It may be a Flush, PhantomLocal, GetLocal, SetLocal, SetArgument, or Phi.
 334             // SetArgument may only appear in the root block. Note that if there ever
 335             // was a GetLocal to the variable, and it was followed by PhantomLocals and
 336             // Flushes but not SetLocals, then the tail variable will be the GetLocal.
 337             // This reflects the fact that you only care that the tail variable is a
 338             // Flush or PhantomLocal if nothing else interesting happened. Likewise, if
 339             // there ever was a SetLocal and it was followed by Flushes, then the tail
 340             // variable will be a SetLocal and not those subsequent Flushes.
 341             //
 342             // Child of GetLocal: the operation that the GetLocal keeps alive. For
 343             // uncaptured locals, it may be a Phi from the current block. For arguments,
 344             // it may be a SetArgument. For captured locals and arguments it may also be
 345             // a SetLocal.
 346             //
 347             // Child of SetLocal: must be a value producing node.
 348             //
 349             // Child of Flush: it may be a Phi from the current block or a SetLocal. For
 350             // arguments it may also be a SetArgument.
 351             //
 352             // Child of PhantomLocal: it may be a Phi from the current block. For
 353             // arguments it may also be a SetArgument.
 354             //
 355             // Children of Phi: other Phis in the same basic block, or any of the
 356             // following from predecessor blocks: SetLocal, Phi, or SetArgument. These
 357             // are computed by looking at the tail variables of the predecessor  blocks
 358             // and either using it directly (if it's a SetLocal, Phi, or SetArgument) or
 359             // loading that nodes child (if it's a GetLocal, PhanomLocal, or Flush - all
 360             // of these will have children that are SetLocal, Phi, or SetArgument).
 361
 362             switch (node->op()) {
 363             case GetLocal:
 364                 canonicalizeGetLocal(node);
 365                 break;
 366
 367             case SetLocal:
 368                 canonicalizeSetLocal(node);
 369                 break;
 370
 371             case Flush:
 372                 canonicalizeFlushOrPhantomLocal<Flush>(node);
 373                 break;
 374
 375             case PhantomLocal:
 376                 canonicalizeFlushOrPhantomLocal<PhantomLocal>(node);
 377                 break;
 378
 379             case SetArgument:
 380                 canonicalizeSetArgument(node);
 381                 break;
 382
 383             default:
 384                 break;
 385             }
 386         }
 387     }
 388
 389     void canonicalizeLocalsInBlocks()
 390     {
 391         SamplingRegion samplingRegion("DFG CPS Rethreading: canonicalizeLocalsInBlocks");
 392
 393         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
 394             m_block = m_graph.block(blockIndex);
 395             canonicalizeLocalsInBlock();
 396         }
 397     }
 398
 399     template<OperandKind operandKind>
 400     void propagatePhis()
 401     {
 402         Vector<PhiStackEntry, 128>& phiStack = operandKind == ArgumentOperand ? m_argumentPhiStack : m_localPhiStack;
 403
 404         SamplingRegion samplingRegion("DFG CPS Rethreading: propagatePhis");
 405
 406         // Ensure that attempts to use this fail instantly.
 407         m_block = 0;
 408
 409         while (!phiStack.isEmpty()) {
 410             PhiStackEntry entry = phiStack.last();
 411             phiStack.removeLast();
 412
 413             BasicBlock* block = entry.m_block;
 414             PredecessorList& predecessors = block->predecessors;
 415             Node* currentPhi = entry.m_phi;
 416             VariableAccessData* variable = currentPhi->variableAccessData();
 417             size_t index = entry.m_index;
 418
 419             for (size_t i = predecessors.size(); i--;) {
 420                 BasicBlock* predecessorBlock = predecessors[i];
 421
 422                 Node* variableInPrevious = predecessorBlock->variablesAtTail.atFor<operandKind>(index);
 423                 if (!variableInPrevious) {
 424                     variableInPrevious = addPhi<operandKind>(predecessorBlock, currentPhi->origin, variable, index);
 425                     predecessorBlock->variablesAtTail.atFor<operandKind>(index) = variableInPrevious;
 426                     predecessorBlock->variablesAtHead.atFor<operandKind>(index) = variableInPrevious;
 427                 } else {
 428                     switch (variableInPrevious->op()) {
 429                     case GetLocal:
 430                     case PhantomLocal:
 431                     case Flush:
 432                         ASSERT(variableInPrevious->variableAccessData() == variableInPrevious->child1()->variableAccessData());
 433                         variableInPrevious = variableInPrevious->child1().node();
 434                         break;
 435                     default:
 436                         break;
 437                     }
 438                 }
 439
 440                 ASSERT(
 441                     variableInPrevious->op() == SetLocal
 442                     || variableInPrevious->op() == Phi
 443                     || variableInPrevious->op() == SetArgument);
 444
 445                 if (!currentPhi->child1()) {
 446                     currentPhi->children.setChild1(Edge(variableInPrevious));
 447                     continue;
 448                 }
 449                 if (!currentPhi->child2()) {
 450                     currentPhi->children.setChild2(Edge(variableInPrevious));
 451                     continue;
 452                 }
 453                 if (!currentPhi->child3()) {
 454                     currentPhi->children.setChild3(Edge(variableInPrevious));
 455                     continue;
 456                 }
 457
 458                 Node* newPhi = addPhiSilently(block, currentPhi->origin, variable);
 459                 newPhi->children = currentPhi->children;
 460                 currentPhi->children.initialize(newPhi, variableInPrevious, 0);
 461             }
 462         }
 463     }
 464
 465     struct PhiStackEntry {
 466         PhiStackEntry(BasicBlock* block, size_t index, Node* phi)
 467             : m_block(block)
 468             , m_index(index)
 469             , m_phi(phi)
 470         {
 471         }
 472
 473         BasicBlock* m_block;
 474         size_t m_index;
 475         Node* m_phi;
 476     };
 477
 478     template<OperandKind operandKind>
 479     Vector<PhiStackEntry, 128>& phiStackFor()
 480     {
 481         if (operandKind == ArgumentOperand)
 482             return m_argumentPhiStack;
 483         return m_localPhiStack;
 484     }
 485
 486     void computeIsFlushed()
 487     {
 488         m_graph.clearFlagsOnAllNodes(NodeIsFlushed);
 489
 490         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
 491             BasicBlock* block = m_graph.block(blockIndex);
 492             if (!block)
 493                 continue;
 494             for (unsigned nodeIndex = block->size(); nodeIndex--;) {
 495                 Node* node = block->at(nodeIndex);
 496                 if (node->op() != Flush)
 497                     continue;
 498                 addFlushedLocalOp(node);
 499             }
 500         }
 501         while (!m_flushedLocalOpWorklist.isEmpty()) {
 502             Node* node = m_flushedLocalOpWorklist.takeLast();
 503             ASSERT(node->flags() & NodeIsFlushed);
 504             DFG_NODE_DO_TO_CHILDREN(m_graph, node, addFlushedLocalEdge);
 505         }
 506     }
 507
 508     void addFlushedLocalOp(Node* node)
 509     {
 510         if (node->mergeFlags(NodeIsFlushed))
 511             m_flushedLocalOpWorklist.append(node);
 512     }
 513
 514     void addFlushedLocalEdge(Node*, Edge edge)
 515     {
 516         addFlushedLocalOp(edge.node());
 517     }
 518
 519     BasicBlock* m_block;
 520     Vector<PhiStackEntry, 128> m_argumentPhiStack;
 521     Vector<PhiStackEntry, 128> m_localPhiStack;
 522     Vector<Node*, 128> m_flushedLocalOpWorklist;
 523 };
 524
 525 bool performCPSRethreading(Graph& graph)
 526 {
 527     SamplingRegion samplingRegion("DFG CPS Rethreading Phase");
 528     return runPhase<CPSRethreadingPhase>(graph);
 529 }
 530
 531 } } // namespace JSC::DFG
 532
 533 #endif // ENABLE(DFG_JIT)
 534