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