OLD | NEW |
1 //===- subzero/src/IceCfg.cpp - Control flow graph implementation ---------===// | 1 //===- subzero/src/IceCfg.cpp - Control flow graph implementation ---------===// |
2 // | 2 // |
3 // The Subzero Code Generator | 3 // The Subzero Code Generator |
4 // | 4 // |
5 // This file is distributed under the University of Illinois Open Source | 5 // This file is distributed under the University of Illinois Open Source |
6 // License. See LICENSE.TXT for details. | 6 // License. See LICENSE.TXT for details. |
7 // | 7 // |
8 //===----------------------------------------------------------------------===// | 8 //===----------------------------------------------------------------------===// |
9 /// | 9 /// |
10 /// \file | 10 /// \file |
(...skipping 183 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
194 addCallToProfileSummary(); | 194 addCallToProfileSummary(); |
195 } | 195 } |
196 dump("Profiled CFG"); | 196 dump("Profiled CFG"); |
197 } | 197 } |
198 | 198 |
199 // Create the Hi and Lo variables where a split was needed | 199 // Create the Hi and Lo variables where a split was needed |
200 for (Variable *Var : Variables) | 200 for (Variable *Var : Variables) |
201 if (auto *Var64On32 = llvm::dyn_cast<Variable64On32>(Var)) | 201 if (auto *Var64On32 = llvm::dyn_cast<Variable64On32>(Var)) |
202 Var64On32->initHiLo(this); | 202 Var64On32->initHiLo(this); |
203 | 203 |
204 // Figure out which alloca instructions result in storage at known stack frame | 204 processAllocas(); |
205 // offsets. If this is true for all alloca instructions, then a stack pointer | |
206 // can still be used instead of a frame pointer, freeing up the frame pointer | |
207 // for normal register allocation. Additionally, for each such alloca, its | |
208 // address could be rematerialized at each use in terms of the stack/frame | |
209 // pointer, saving a stack slot and a load from that stack slot. | |
210 // | |
211 // This simple implementation is limited to alloca instructions at the start | |
212 // of the entry node. | |
213 for (Inst &Instr : getEntryNode()->getInsts()) { | |
214 if (auto *Alloca = llvm::dyn_cast<InstAlloca>(&Instr)) { | |
215 if (llvm::isa<Constant>(Alloca->getSizeInBytes())) { | |
216 Alloca->setKnownFrameOffset(); | |
217 continue; | |
218 } | |
219 } | |
220 // The first instruction that is not an alloca with a constant size stops | |
221 // the search. | |
222 break; | |
223 } | |
224 | 205 |
225 // The set of translation passes and their order are determined by the | 206 // The set of translation passes and their order are determined by the |
226 // target. | 207 // target. |
227 getTarget()->translate(); | 208 getTarget()->translate(); |
228 | 209 |
229 dump("Final output"); | 210 dump("Final output"); |
230 if (getFocusedTiming()) | 211 if (getFocusedTiming()) |
231 getContext()->dumpTimers(); | 212 getContext()->dumpTimers(); |
232 } | 213 } |
233 | 214 |
(...skipping 229 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
463 swapNodes(Shuffled); | 444 swapNodes(Shuffled); |
464 | 445 |
465 dump("After basic block shuffling"); | 446 dump("After basic block shuffling"); |
466 } | 447 } |
467 | 448 |
468 void Cfg::doArgLowering() { | 449 void Cfg::doArgLowering() { |
469 TimerMarker T(TimerStack::TT_doArgLowering, this); | 450 TimerMarker T(TimerStack::TT_doArgLowering, this); |
470 getTarget()->lowerArguments(); | 451 getTarget()->lowerArguments(); |
471 } | 452 } |
472 | 453 |
| 454 void Cfg::sortAllocas(CfgVector<Inst *> &Allocas, InstList &Insts, |
| 455 bool IsKnownFrameOffset) { |
| 456 if (Allocas.empty()) |
| 457 return; |
| 458 // Sort by decreasing alignment. This does not really matter at the moment, |
| 459 // but will allow compacting stack allocation when we fuse to one alloca. |
| 460 std::sort(Allocas.begin(), Allocas.end(), |
| 461 [](Inst *I1, Inst *I2) { |
| 462 auto *A1 = llvm::dyn_cast<InstAlloca>(I1); |
| 463 auto *A2 = llvm::dyn_cast<InstAlloca>(I2); |
| 464 return A1->getAlignInBytes() > A2->getAlignInBytes(); |
| 465 }); |
| 466 for (Inst *Instr: Allocas) { |
| 467 auto *Alloca = llvm::cast<InstAlloca>(Instr); |
| 468 // Move the alloca to its sorted position. |
| 469 InstAlloca *NewAlloca = InstAlloca::create(this, |
| 470 Alloca->getSizeInBytes(), |
| 471 Alloca->getAlignInBytes(), |
| 472 Alloca->getDest()); |
| 473 if (IsKnownFrameOffset) |
| 474 NewAlloca->setKnownFrameOffset(); |
| 475 Insts.push_front(NewAlloca); |
| 476 Alloca->setDeleted(); |
| 477 } |
| 478 } |
| 479 |
| 480 void Cfg::processAllocas() { |
| 481 const uint32_t StackAlignment = getTarget()->getStackAlignment(); |
| 482 CfgNode *EntryNode = getEntryNode(); |
| 483 // Allocas in the entry block that have constant size and alignment less |
| 484 // than or equal to the function's stack alignment. |
| 485 CfgVector<Inst *> FixedAllocas; |
| 486 // Allocas in the entry block that have constant size and alignment greater |
| 487 // than the function's stack alignment. |
| 488 CfgVector<Inst *> AlignedAllocas; |
| 489 // LLVM enforces power of 2 alignment. |
| 490 assert(llvm::isPowerOf2_32(StackAlignment)); |
| 491 // Collect the Allocas into the two vectors. |
| 492 bool RequiresFramePointer = false; |
| 493 for (Inst &Instr : EntryNode->getInsts()) { |
| 494 if (auto *Alloca = llvm::dyn_cast<InstAlloca>(&Instr)) { |
| 495 if (!llvm::isa<Constant>(Alloca->getSizeInBytes())) { |
| 496 // Variable-sized allocations require a frame pointer. |
| 497 RequiresFramePointer = true; |
| 498 continue; |
| 499 } |
| 500 uint32_t AlignmentParam = Alloca->getAlignInBytes(); |
| 501 // For default align=0, set it to the real value 1, to avoid any |
| 502 // bit-manipulation problems below. |
| 503 AlignmentParam = std::max(AlignmentParam, 1u); |
| 504 assert(llvm::isPowerOf2_32(AlignmentParam)); |
| 505 if (AlignmentParam > StackAlignment) { |
| 506 // Allocations aligned more than the stack require a frame pointer. |
| 507 RequiresFramePointer = true; |
| 508 AlignedAllocas.push_back(Alloca); |
| 509 } |
| 510 else |
| 511 FixedAllocas.push_back(Alloca); |
| 512 } |
| 513 } |
| 514 // Look for alloca instructions in other blocks |
| 515 for (CfgNode *Node : Nodes) { |
| 516 if (Node == EntryNode) |
| 517 continue; |
| 518 for (Inst &Instr : Node->getInsts()) { |
| 519 if (llvm::isa<InstAlloca>(&Instr)) { |
| 520 // Allocations outside the entry block require a frame pointer. |
| 521 RequiresFramePointer = true; |
| 522 break; |
| 523 } |
| 524 } |
| 525 if (RequiresFramePointer) |
| 526 break; |
| 527 } |
| 528 // Mark the target as requiring a frame pointer. |
| 529 if (RequiresFramePointer) |
| 530 getTarget()->setHasFramePointer(); |
| 531 // Add instructions to the head of the entry block in reverse order. |
| 532 InstList &Insts = getEntryNode()->getInsts(); |
| 533 // Fixed, large alignment alloca addresses do not have known offset. |
| 534 sortAllocas(AlignedAllocas, Insts, false); |
| 535 // Fixed, small alignment alloca addresses have known offset. |
| 536 sortAllocas(FixedAllocas, Insts, true); |
| 537 } |
| 538 |
473 void Cfg::doAddressOpt() { | 539 void Cfg::doAddressOpt() { |
474 TimerMarker T(TimerStack::TT_doAddressOpt, this); | 540 TimerMarker T(TimerStack::TT_doAddressOpt, this); |
475 for (CfgNode *Node : Nodes) | 541 for (CfgNode *Node : Nodes) |
476 Node->doAddressOpt(); | 542 Node->doAddressOpt(); |
477 } | 543 } |
478 | 544 |
479 void Cfg::doNopInsertion() { | 545 void Cfg::doNopInsertion() { |
480 if (!Ctx->getFlags().shouldDoNopInsertion()) | 546 if (!Ctx->getFlags().shouldDoNopInsertion()) |
481 return; | 547 return; |
482 TimerMarker T(TimerStack::TT_doNopInsertion, this); | 548 TimerMarker T(TimerStack::TT_doNopInsertion, this); |
(...skipping 349 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
832 } | 898 } |
833 } | 899 } |
834 // Print each basic block | 900 // Print each basic block |
835 for (CfgNode *Node : Nodes) | 901 for (CfgNode *Node : Nodes) |
836 Node->dump(this); | 902 Node->dump(this); |
837 if (isVerbose(IceV_Instructions)) | 903 if (isVerbose(IceV_Instructions)) |
838 Str << "}\n"; | 904 Str << "}\n"; |
839 } | 905 } |
840 | 906 |
841 } // end of namespace Ice | 907 } // end of namespace Ice |
OLD | NEW |