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