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 36namespace JSC { namespace DFG { 37 38class CPSRethreadingPhase : public Phase { 39public: 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 64private: 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 525bool 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 535