1 //===-- StructurizeCFG.cpp ------------------------------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 #include "llvm/Transforms/Scalar.h" 11 #include "llvm/ADT/MapVector.h" 12 #include "llvm/ADT/PostOrderIterator.h" 13 #include "llvm/ADT/SCCIterator.h" 14 #include "llvm/Analysis/LoopInfo.h" 15 #include "llvm/Analysis/RegionInfo.h" 16 #include "llvm/Analysis/RegionIterator.h" 17 #include "llvm/Analysis/RegionPass.h" 18 #include "llvm/IR/Module.h" 19 #include "llvm/IR/PatternMatch.h" 20 #include "llvm/Support/Debug.h" 21 #include "llvm/Support/raw_ostream.h" 22 #include "llvm/Transforms/Utils/SSAUpdater.h" 23 24 using namespace llvm; 25 using namespace llvm::PatternMatch; 26 27 #define DEBUG_TYPE "structurizecfg" 28 29 namespace { 30 31 // Definition of the complex types used in this pass. 32 33 typedef std::pair<BasicBlock *, Value *> BBValuePair; 34 35 typedef SmallVector<RegionNode*, 8> RNVector; 36 typedef SmallVector<BasicBlock*, 8> BBVector; 37 typedef SmallVector<BranchInst*, 8> BranchVector; 38 typedef SmallVector<BBValuePair, 2> BBValueVector; 39 40 typedef SmallPtrSet<BasicBlock *, 8> BBSet; 41 42 typedef MapVector<PHINode *, BBValueVector> PhiMap; 43 typedef MapVector<BasicBlock *, BBVector> BB2BBVecMap; 44 45 typedef DenseMap<DomTreeNode *, unsigned> DTN2UnsignedMap; 46 typedef DenseMap<BasicBlock *, PhiMap> BBPhiMap; 47 typedef DenseMap<BasicBlock *, Value *> BBPredicates; 48 typedef DenseMap<BasicBlock *, BBPredicates> PredMap; 49 typedef DenseMap<BasicBlock *, BasicBlock*> BB2BBMap; 50 51 // The name for newly created blocks. 52 53 static const char *const FlowBlockName = "Flow"; 54 55 /// @brief Find the nearest common dominator for multiple BasicBlocks 56 /// 57 /// Helper class for StructurizeCFG 58 /// TODO: Maybe move into common code 59 class NearestCommonDominator { 60 DominatorTree *DT; 61 62 DTN2UnsignedMap IndexMap; 63 64 BasicBlock *Result; 65 unsigned ResultIndex; 66 bool ExplicitMentioned; 67 68 public: 69 /// \brief Start a new query 70 NearestCommonDominator(DominatorTree *DomTree) { 71 DT = DomTree; 72 Result = nullptr; 73 } 74 75 /// \brief Add BB to the resulting dominator 76 void addBlock(BasicBlock *BB, bool Remember = true) { 77 DomTreeNode *Node = DT->getNode(BB); 78 79 if (!Result) { 80 unsigned Numbering = 0; 81 for (;Node;Node = Node->getIDom()) 82 IndexMap[Node] = ++Numbering; 83 Result = BB; 84 ResultIndex = 1; 85 ExplicitMentioned = Remember; 86 return; 87 } 88 89 for (;Node;Node = Node->getIDom()) 90 if (IndexMap.count(Node)) 91 break; 92 else 93 IndexMap[Node] = 0; 94 95 assert(Node && "Dominator tree invalid!"); 96 97 unsigned Numbering = IndexMap[Node]; 98 if (Numbering > ResultIndex) { 99 Result = Node->getBlock(); 100 ResultIndex = Numbering; 101 ExplicitMentioned = Remember && (Result == BB); 102 } else if (Numbering == ResultIndex) { 103 ExplicitMentioned |= Remember; 104 } 105 } 106 107 /// \brief Is "Result" one of the BBs added with "Remember" = True? 108 bool wasResultExplicitMentioned() { 109 return ExplicitMentioned; 110 } 111 112 /// \brief Get the query result 113 BasicBlock *getResult() { 114 return Result; 115 } 116 }; 117 118 /// @brief Transforms the control flow graph on one single entry/exit region 119 /// at a time. 120 /// 121 /// After the transform all "If"/"Then"/"Else" style control flow looks like 122 /// this: 123 /// 124 /// \verbatim 125 /// 1 126 /// || 127 /// | | 128 /// 2 | 129 /// | / 130 /// |/ 131 /// 3 132 /// || Where: 133 /// | | 1 = "If" block, calculates the condition 134 /// 4 | 2 = "Then" subregion, runs if the condition is true 135 /// | / 3 = "Flow" blocks, newly inserted flow blocks, rejoins the flow 136 /// |/ 4 = "Else" optional subregion, runs if the condition is false 137 /// 5 5 = "End" block, also rejoins the control flow 138 /// \endverbatim 139 /// 140 /// Control flow is expressed as a branch where the true exit goes into the 141 /// "Then"/"Else" region, while the false exit skips the region 142 /// The condition for the optional "Else" region is expressed as a PHI node. 143 /// The incomming values of the PHI node are true for the "If" edge and false 144 /// for the "Then" edge. 145 /// 146 /// Additionally to that even complicated loops look like this: 147 /// 148 /// \verbatim 149 /// 1 150 /// || 151 /// | | 152 /// 2 ^ Where: 153 /// | / 1 = "Entry" block 154 /// |/ 2 = "Loop" optional subregion, with all exits at "Flow" block 155 /// 3 3 = "Flow" block, with back edge to entry block 156 /// | 157 /// \endverbatim 158 /// 159 /// The back edge of the "Flow" block is always on the false side of the branch 160 /// while the true side continues the general flow. So the loop condition 161 /// consist of a network of PHI nodes where the true incoming values expresses 162 /// breaks and the false values expresses continue states. 163 class StructurizeCFG : public RegionPass { 164 Type *Boolean; 165 ConstantInt *BoolTrue; 166 ConstantInt *BoolFalse; 167 UndefValue *BoolUndef; 168 169 Function *Func; 170 Region *ParentRegion; 171 172 DominatorTree *DT; 173 LoopInfo *LI; 174 175 RNVector Order; 176 BBSet Visited; 177 178 BBPhiMap DeletedPhis; 179 BB2BBVecMap AddedPhis; 180 181 PredMap Predicates; 182 BranchVector Conditions; 183 184 BB2BBMap Loops; 185 PredMap LoopPreds; 186 BranchVector LoopConds; 187 188 RegionNode *PrevNode; 189 190 void orderNodes(); 191 192 void analyzeLoops(RegionNode *N); 193 194 Value *invert(Value *Condition); 195 196 Value *buildCondition(BranchInst *Term, unsigned Idx, bool Invert); 197 198 void gatherPredicates(RegionNode *N); 199 200 void collectInfos(); 201 202 void insertConditions(bool Loops); 203 204 void delPhiValues(BasicBlock *From, BasicBlock *To); 205 206 void addPhiValues(BasicBlock *From, BasicBlock *To); 207 208 void setPhiValues(); 209 210 void killTerminator(BasicBlock *BB); 211 212 void changeExit(RegionNode *Node, BasicBlock *NewExit, 213 bool IncludeDominator); 214 215 BasicBlock *getNextFlow(BasicBlock *Dominator); 216 217 BasicBlock *needPrefix(bool NeedEmpty); 218 219 BasicBlock *needPostfix(BasicBlock *Flow, bool ExitUseAllowed); 220 221 void setPrevNode(BasicBlock *BB); 222 223 bool dominatesPredicates(BasicBlock *BB, RegionNode *Node); 224 225 bool isPredictableTrue(RegionNode *Node); 226 227 void wireFlow(bool ExitUseAllowed, BasicBlock *LoopEnd); 228 229 void handleLoops(bool ExitUseAllowed, BasicBlock *LoopEnd); 230 231 void createFlow(); 232 233 void rebuildSSA(); 234 235 public: 236 static char ID; 237 238 StructurizeCFG() : 239 RegionPass(ID) { 240 initializeStructurizeCFGPass(*PassRegistry::getPassRegistry()); 241 } 242 243 using Pass::doInitialization; 244 bool doInitialization(Region *R, RGPassManager &RGM) override; 245 246 bool runOnRegion(Region *R, RGPassManager &RGM) override; 247 248 const char *getPassName() const override { 249 return "Structurize control flow"; 250 } 251 252 void getAnalysisUsage(AnalysisUsage &AU) const override { 253 AU.addRequiredID(LowerSwitchID); 254 AU.addRequired<DominatorTreeWrapperPass>(); 255 AU.addRequired<LoopInfoWrapperPass>(); 256 AU.addPreserved<DominatorTreeWrapperPass>(); 257 RegionPass::getAnalysisUsage(AU); 258 } 259 }; 260 261 } // end anonymous namespace 262 263 char StructurizeCFG::ID = 0; 264 265 INITIALIZE_PASS_BEGIN(StructurizeCFG, "structurizecfg", "Structurize the CFG", 266 false, false) 267 INITIALIZE_PASS_DEPENDENCY(LowerSwitch) 268 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 269 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass) 270 INITIALIZE_PASS_END(StructurizeCFG, "structurizecfg", "Structurize the CFG", 271 false, false) 272 273 /// \brief Initialize the types and constants used in the pass 274 bool StructurizeCFG::doInitialization(Region *R, RGPassManager &RGM) { 275 LLVMContext &Context = R->getEntry()->getContext(); 276 277 Boolean = Type::getInt1Ty(Context); 278 BoolTrue = ConstantInt::getTrue(Context); 279 BoolFalse = ConstantInt::getFalse(Context); 280 BoolUndef = UndefValue::get(Boolean); 281 282 return false; 283 } 284 285 /// \brief Build up the general order of nodes 286 void StructurizeCFG::orderNodes() { 287 RNVector TempOrder; 288 ReversePostOrderTraversal<Region*> RPOT(ParentRegion); 289 TempOrder.append(RPOT.begin(), RPOT.end()); 290 291 std::map<Loop*, unsigned> LoopBlocks; 292 293 294 // The reverse post-order traversal of the list gives us an ordering close 295 // to what we want. The only problem with it is that sometimes backedges 296 // for outer loops will be visited before backedges for inner loops. 297 for (RegionNode *RN : TempOrder) { 298 BasicBlock *BB = RN->getEntry(); 299 Loop *Loop = LI->getLoopFor(BB); 300 if (!LoopBlocks.count(Loop)) { 301 LoopBlocks[Loop] = 1; 302 continue; 303 } 304 LoopBlocks[Loop]++; 305 } 306 307 unsigned CurrentLoopDepth = 0; 308 Loop *CurrentLoop = nullptr; 309 BBSet TempVisited; 310 for (RNVector::iterator I = TempOrder.begin(), E = TempOrder.end(); I != E; ++I) { 311 BasicBlock *BB = (*I)->getEntry(); 312 unsigned LoopDepth = LI->getLoopDepth(BB); 313 314 if (std::find(Order.begin(), Order.end(), *I) != Order.end()) 315 continue; 316 317 if (LoopDepth < CurrentLoopDepth) { 318 // Make sure we have visited all blocks in this loop before moving back to 319 // the outer loop. 320 321 RNVector::iterator LoopI = I; 322 while(LoopBlocks[CurrentLoop]) { 323 LoopI++; 324 BasicBlock *LoopBB = (*LoopI)->getEntry(); 325 if (LI->getLoopFor(LoopBB) == CurrentLoop) { 326 LoopBlocks[CurrentLoop]--; 327 Order.push_back(*LoopI); 328 } 329 } 330 } 331 332 CurrentLoop = LI->getLoopFor(BB); 333 if (CurrentLoop) { 334 LoopBlocks[CurrentLoop]--; 335 } 336 337 CurrentLoopDepth = LoopDepth; 338 Order.push_back(*I); 339 } 340 341 // This pass originally used a post-order traversal and then operated on 342 // the list in reverse. Now that we are using a reverse post-order traversal 343 // rather than re-working the whole pass to operate on the list in order, 344 // we just reverse the list and continue to operate on it in reverse. 345 std::reverse(Order.begin(), Order.end()); 346 } 347 348 /// \brief Determine the end of the loops 349 void StructurizeCFG::analyzeLoops(RegionNode *N) { 350 if (N->isSubRegion()) { 351 // Test for exit as back edge 352 BasicBlock *Exit = N->getNodeAs<Region>()->getExit(); 353 if (Visited.count(Exit)) 354 Loops[Exit] = N->getEntry(); 355 356 } else { 357 // Test for sucessors as back edge 358 BasicBlock *BB = N->getNodeAs<BasicBlock>(); 359 BranchInst *Term = cast<BranchInst>(BB->getTerminator()); 360 361 for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) { 362 BasicBlock *Succ = Term->getSuccessor(i); 363 364 if (Visited.count(Succ)) { 365 Loops[Succ] = BB; 366 } 367 } 368 } 369 } 370 371 /// \brief Invert the given condition 372 Value *StructurizeCFG::invert(Value *Condition) { 373 // First: Check if it's a constant 374 if (Condition == BoolTrue) 375 return BoolFalse; 376 377 if (Condition == BoolFalse) 378 return BoolTrue; 379 380 if (Condition == BoolUndef) 381 return BoolUndef; 382 383 // Second: If the condition is already inverted, return the original value 384 if (match(Condition, m_Not(m_Value(Condition)))) 385 return Condition; 386 387 if (Instruction *Inst = dyn_cast<Instruction>(Condition)) { 388 // Third: Check all the users for an invert 389 BasicBlock *Parent = Inst->getParent(); 390 for (User *U : Condition->users()) 391 if (Instruction *I = dyn_cast<Instruction>(U)) 392 if (I->getParent() == Parent && match(I, m_Not(m_Specific(Condition)))) 393 return I; 394 395 // Last option: Create a new instruction 396 return BinaryOperator::CreateNot(Condition, "", Parent->getTerminator()); 397 } 398 399 if (Argument *Arg = dyn_cast<Argument>(Condition)) { 400 BasicBlock &EntryBlock = Arg->getParent()->getEntryBlock(); 401 return BinaryOperator::CreateNot(Condition, 402 Arg->getName() + ".inv", 403 EntryBlock.getTerminator()); 404 } 405 406 llvm_unreachable("Unhandled condition to invert"); 407 } 408 409 /// \brief Build the condition for one edge 410 Value *StructurizeCFG::buildCondition(BranchInst *Term, unsigned Idx, 411 bool Invert) { 412 Value *Cond = Invert ? BoolFalse : BoolTrue; 413 if (Term->isConditional()) { 414 Cond = Term->getCondition(); 415 416 if (Idx != (unsigned)Invert) 417 Cond = invert(Cond); 418 } 419 return Cond; 420 } 421 422 /// \brief Analyze the predecessors of each block and build up predicates 423 void StructurizeCFG::gatherPredicates(RegionNode *N) { 424 RegionInfo *RI = ParentRegion->getRegionInfo(); 425 BasicBlock *BB = N->getEntry(); 426 BBPredicates &Pred = Predicates[BB]; 427 BBPredicates &LPred = LoopPreds[BB]; 428 429 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); 430 PI != PE; ++PI) { 431 432 // Ignore it if it's a branch from outside into our region entry 433 if (!ParentRegion->contains(*PI)) 434 continue; 435 436 Region *R = RI->getRegionFor(*PI); 437 if (R == ParentRegion) { 438 439 // It's a top level block in our region 440 BranchInst *Term = cast<BranchInst>((*PI)->getTerminator()); 441 for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) { 442 BasicBlock *Succ = Term->getSuccessor(i); 443 if (Succ != BB) 444 continue; 445 446 if (Visited.count(*PI)) { 447 // Normal forward edge 448 if (Term->isConditional()) { 449 // Try to treat it like an ELSE block 450 BasicBlock *Other = Term->getSuccessor(!i); 451 if (Visited.count(Other) && !Loops.count(Other) && 452 !Pred.count(Other) && !Pred.count(*PI)) { 453 454 Pred[Other] = BoolFalse; 455 Pred[*PI] = BoolTrue; 456 continue; 457 } 458 } 459 Pred[*PI] = buildCondition(Term, i, false); 460 461 } else { 462 // Back edge 463 LPred[*PI] = buildCondition(Term, i, true); 464 } 465 } 466 467 } else { 468 469 // It's an exit from a sub region 470 while (R->getParent() != ParentRegion) 471 R = R->getParent(); 472 473 // Edge from inside a subregion to its entry, ignore it 474 if (*R == *N) 475 continue; 476 477 BasicBlock *Entry = R->getEntry(); 478 if (Visited.count(Entry)) 479 Pred[Entry] = BoolTrue; 480 else 481 LPred[Entry] = BoolFalse; 482 } 483 } 484 } 485 486 /// \brief Collect various loop and predicate infos 487 void StructurizeCFG::collectInfos() { 488 // Reset predicate 489 Predicates.clear(); 490 491 // and loop infos 492 Loops.clear(); 493 LoopPreds.clear(); 494 495 // Reset the visited nodes 496 Visited.clear(); 497 498 for (RNVector::reverse_iterator OI = Order.rbegin(), OE = Order.rend(); 499 OI != OE; ++OI) { 500 501 DEBUG(dbgs() << "Visiting: " << 502 ((*OI)->isSubRegion() ? "SubRegion with entry: " : "") << 503 (*OI)->getEntry()->getName() << " Loop Depth: " << LI->getLoopDepth((*OI)->getEntry()) << "\n"); 504 505 // Analyze all the conditions leading to a node 506 gatherPredicates(*OI); 507 508 // Remember that we've seen this node 509 Visited.insert((*OI)->getEntry()); 510 511 // Find the last back edges 512 analyzeLoops(*OI); 513 } 514 } 515 516 /// \brief Insert the missing branch conditions 517 void StructurizeCFG::insertConditions(bool Loops) { 518 BranchVector &Conds = Loops ? LoopConds : Conditions; 519 Value *Default = Loops ? BoolTrue : BoolFalse; 520 SSAUpdater PhiInserter; 521 522 for (BranchInst *Term : Conds) { 523 assert(Term->isConditional()); 524 525 BasicBlock *Parent = Term->getParent(); 526 BasicBlock *SuccTrue = Term->getSuccessor(0); 527 BasicBlock *SuccFalse = Term->getSuccessor(1); 528 529 PhiInserter.Initialize(Boolean, ""); 530 PhiInserter.AddAvailableValue(&Func->getEntryBlock(), Default); 531 PhiInserter.AddAvailableValue(Loops ? SuccFalse : Parent, Default); 532 533 BBPredicates &Preds = Loops ? LoopPreds[SuccFalse] : Predicates[SuccTrue]; 534 535 NearestCommonDominator Dominator(DT); 536 Dominator.addBlock(Parent, false); 537 538 Value *ParentValue = nullptr; 539 for (BBPredicates::iterator PI = Preds.begin(), PE = Preds.end(); 540 PI != PE; ++PI) { 541 542 if (PI->first == Parent) { 543 ParentValue = PI->second; 544 break; 545 } 546 PhiInserter.AddAvailableValue(PI->first, PI->second); 547 Dominator.addBlock(PI->first); 548 } 549 550 if (ParentValue) { 551 Term->setCondition(ParentValue); 552 } else { 553 if (!Dominator.wasResultExplicitMentioned()) 554 PhiInserter.AddAvailableValue(Dominator.getResult(), Default); 555 556 Term->setCondition(PhiInserter.GetValueInMiddleOfBlock(Parent)); 557 } 558 } 559 } 560 561 /// \brief Remove all PHI values coming from "From" into "To" and remember 562 /// them in DeletedPhis 563 void StructurizeCFG::delPhiValues(BasicBlock *From, BasicBlock *To) { 564 PhiMap &Map = DeletedPhis[To]; 565 for (BasicBlock::iterator I = To->begin(), E = To->end(); 566 I != E && isa<PHINode>(*I);) { 567 568 PHINode &Phi = cast<PHINode>(*I++); 569 while (Phi.getBasicBlockIndex(From) != -1) { 570 Value *Deleted = Phi.removeIncomingValue(From, false); 571 Map[&Phi].push_back(std::make_pair(From, Deleted)); 572 } 573 } 574 } 575 576 /// \brief Add a dummy PHI value as soon as we knew the new predecessor 577 void StructurizeCFG::addPhiValues(BasicBlock *From, BasicBlock *To) { 578 for (BasicBlock::iterator I = To->begin(), E = To->end(); 579 I != E && isa<PHINode>(*I);) { 580 581 PHINode &Phi = cast<PHINode>(*I++); 582 Value *Undef = UndefValue::get(Phi.getType()); 583 Phi.addIncoming(Undef, From); 584 } 585 AddedPhis[To].push_back(From); 586 } 587 588 /// \brief Add the real PHI value as soon as everything is set up 589 void StructurizeCFG::setPhiValues() { 590 SSAUpdater Updater; 591 for (BB2BBVecMap::iterator AI = AddedPhis.begin(), AE = AddedPhis.end(); 592 AI != AE; ++AI) { 593 594 BasicBlock *To = AI->first; 595 BBVector &From = AI->second; 596 597 if (!DeletedPhis.count(To)) 598 continue; 599 600 PhiMap &Map = DeletedPhis[To]; 601 for (PhiMap::iterator PI = Map.begin(), PE = Map.end(); 602 PI != PE; ++PI) { 603 604 PHINode *Phi = PI->first; 605 Value *Undef = UndefValue::get(Phi->getType()); 606 Updater.Initialize(Phi->getType(), ""); 607 Updater.AddAvailableValue(&Func->getEntryBlock(), Undef); 608 Updater.AddAvailableValue(To, Undef); 609 610 NearestCommonDominator Dominator(DT); 611 Dominator.addBlock(To, false); 612 for (BBValueVector::iterator VI = PI->second.begin(), 613 VE = PI->second.end(); VI != VE; ++VI) { 614 615 Updater.AddAvailableValue(VI->first, VI->second); 616 Dominator.addBlock(VI->first); 617 } 618 619 if (!Dominator.wasResultExplicitMentioned()) 620 Updater.AddAvailableValue(Dominator.getResult(), Undef); 621 622 for (BBVector::iterator FI = From.begin(), FE = From.end(); 623 FI != FE; ++FI) { 624 625 int Idx = Phi->getBasicBlockIndex(*FI); 626 assert(Idx != -1); 627 Phi->setIncomingValue(Idx, Updater.GetValueAtEndOfBlock(*FI)); 628 } 629 } 630 631 DeletedPhis.erase(To); 632 } 633 assert(DeletedPhis.empty()); 634 } 635 636 /// \brief Remove phi values from all successors and then remove the terminator. 637 void StructurizeCFG::killTerminator(BasicBlock *BB) { 638 TerminatorInst *Term = BB->getTerminator(); 639 if (!Term) 640 return; 641 642 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); 643 SI != SE; ++SI) { 644 645 delPhiValues(BB, *SI); 646 } 647 648 Term->eraseFromParent(); 649 } 650 651 /// \brief Let node exit(s) point to NewExit 652 void StructurizeCFG::changeExit(RegionNode *Node, BasicBlock *NewExit, 653 bool IncludeDominator) { 654 if (Node->isSubRegion()) { 655 Region *SubRegion = Node->getNodeAs<Region>(); 656 BasicBlock *OldExit = SubRegion->getExit(); 657 BasicBlock *Dominator = nullptr; 658 659 // Find all the edges from the sub region to the exit 660 for (pred_iterator I = pred_begin(OldExit), E = pred_end(OldExit); 661 I != E;) { 662 663 BasicBlock *BB = *I++; 664 if (!SubRegion->contains(BB)) 665 continue; 666 667 // Modify the edges to point to the new exit 668 delPhiValues(BB, OldExit); 669 BB->getTerminator()->replaceUsesOfWith(OldExit, NewExit); 670 addPhiValues(BB, NewExit); 671 672 // Find the new dominator (if requested) 673 if (IncludeDominator) { 674 if (!Dominator) 675 Dominator = BB; 676 else 677 Dominator = DT->findNearestCommonDominator(Dominator, BB); 678 } 679 } 680 681 // Change the dominator (if requested) 682 if (Dominator) 683 DT->changeImmediateDominator(NewExit, Dominator); 684 685 // Update the region info 686 SubRegion->replaceExit(NewExit); 687 688 } else { 689 BasicBlock *BB = Node->getNodeAs<BasicBlock>(); 690 killTerminator(BB); 691 BranchInst::Create(NewExit, BB); 692 addPhiValues(BB, NewExit); 693 if (IncludeDominator) 694 DT->changeImmediateDominator(NewExit, BB); 695 } 696 } 697 698 /// \brief Create a new flow node and update dominator tree and region info 699 BasicBlock *StructurizeCFG::getNextFlow(BasicBlock *Dominator) { 700 LLVMContext &Context = Func->getContext(); 701 BasicBlock *Insert = Order.empty() ? ParentRegion->getExit() : 702 Order.back()->getEntry(); 703 BasicBlock *Flow = BasicBlock::Create(Context, FlowBlockName, 704 Func, Insert); 705 DT->addNewBlock(Flow, Dominator); 706 ParentRegion->getRegionInfo()->setRegionFor(Flow, ParentRegion); 707 return Flow; 708 } 709 710 /// \brief Create a new or reuse the previous node as flow node 711 BasicBlock *StructurizeCFG::needPrefix(bool NeedEmpty) { 712 BasicBlock *Entry = PrevNode->getEntry(); 713 714 if (!PrevNode->isSubRegion()) { 715 killTerminator(Entry); 716 if (!NeedEmpty || Entry->getFirstInsertionPt() == Entry->end()) 717 return Entry; 718 719 } 720 721 // create a new flow node 722 BasicBlock *Flow = getNextFlow(Entry); 723 724 // and wire it up 725 changeExit(PrevNode, Flow, true); 726 PrevNode = ParentRegion->getBBNode(Flow); 727 return Flow; 728 } 729 730 /// \brief Returns the region exit if possible, otherwise just a new flow node 731 BasicBlock *StructurizeCFG::needPostfix(BasicBlock *Flow, 732 bool ExitUseAllowed) { 733 if (Order.empty() && ExitUseAllowed) { 734 BasicBlock *Exit = ParentRegion->getExit(); 735 DT->changeImmediateDominator(Exit, Flow); 736 addPhiValues(Flow, Exit); 737 return Exit; 738 } 739 return getNextFlow(Flow); 740 } 741 742 /// \brief Set the previous node 743 void StructurizeCFG::setPrevNode(BasicBlock *BB) { 744 PrevNode = ParentRegion->contains(BB) ? ParentRegion->getBBNode(BB) 745 : nullptr; 746 } 747 748 /// \brief Does BB dominate all the predicates of Node ? 749 bool StructurizeCFG::dominatesPredicates(BasicBlock *BB, RegionNode *Node) { 750 BBPredicates &Preds = Predicates[Node->getEntry()]; 751 for (BBPredicates::iterator PI = Preds.begin(), PE = Preds.end(); 752 PI != PE; ++PI) { 753 754 if (!DT->dominates(BB, PI->first)) 755 return false; 756 } 757 return true; 758 } 759 760 /// \brief Can we predict that this node will always be called? 761 bool StructurizeCFG::isPredictableTrue(RegionNode *Node) { 762 BBPredicates &Preds = Predicates[Node->getEntry()]; 763 bool Dominated = false; 764 765 // Regionentry is always true 766 if (!PrevNode) 767 return true; 768 769 for (BBPredicates::iterator I = Preds.begin(), E = Preds.end(); 770 I != E; ++I) { 771 772 if (I->second != BoolTrue) 773 return false; 774 775 if (!Dominated && DT->dominates(I->first, PrevNode->getEntry())) 776 Dominated = true; 777 } 778 779 // TODO: The dominator check is too strict 780 return Dominated; 781 } 782 783 /// Take one node from the order vector and wire it up 784 void StructurizeCFG::wireFlow(bool ExitUseAllowed, 785 BasicBlock *LoopEnd) { 786 RegionNode *Node = Order.pop_back_val(); 787 Visited.insert(Node->getEntry()); 788 789 if (isPredictableTrue(Node)) { 790 // Just a linear flow 791 if (PrevNode) { 792 changeExit(PrevNode, Node->getEntry(), true); 793 } 794 PrevNode = Node; 795 796 } else { 797 // Insert extra prefix node (or reuse last one) 798 BasicBlock *Flow = needPrefix(false); 799 800 // Insert extra postfix node (or use exit instead) 801 BasicBlock *Entry = Node->getEntry(); 802 BasicBlock *Next = needPostfix(Flow, ExitUseAllowed); 803 804 // let it point to entry and next block 805 Conditions.push_back(BranchInst::Create(Entry, Next, BoolUndef, Flow)); 806 addPhiValues(Flow, Entry); 807 DT->changeImmediateDominator(Entry, Flow); 808 809 PrevNode = Node; 810 while (!Order.empty() && !Visited.count(LoopEnd) && 811 dominatesPredicates(Entry, Order.back())) { 812 handleLoops(false, LoopEnd); 813 } 814 815 changeExit(PrevNode, Next, false); 816 setPrevNode(Next); 817 } 818 } 819 820 void StructurizeCFG::handleLoops(bool ExitUseAllowed, 821 BasicBlock *LoopEnd) { 822 RegionNode *Node = Order.back(); 823 BasicBlock *LoopStart = Node->getEntry(); 824 825 if (!Loops.count(LoopStart)) { 826 wireFlow(ExitUseAllowed, LoopEnd); 827 return; 828 } 829 830 if (!isPredictableTrue(Node)) 831 LoopStart = needPrefix(true); 832 833 LoopEnd = Loops[Node->getEntry()]; 834 wireFlow(false, LoopEnd); 835 while (!Visited.count(LoopEnd)) { 836 handleLoops(false, LoopEnd); 837 } 838 839 // If the start of the loop is the entry block, we can't branch to it so 840 // insert a new dummy entry block. 841 Function *LoopFunc = LoopStart->getParent(); 842 if (LoopStart == &LoopFunc->getEntryBlock()) { 843 LoopStart->setName("entry.orig"); 844 845 BasicBlock *NewEntry = 846 BasicBlock::Create(LoopStart->getContext(), 847 "entry", 848 LoopFunc, 849 LoopStart); 850 BranchInst::Create(LoopStart, NewEntry); 851 } 852 853 // Create an extra loop end node 854 LoopEnd = needPrefix(false); 855 BasicBlock *Next = needPostfix(LoopEnd, ExitUseAllowed); 856 LoopConds.push_back(BranchInst::Create(Next, LoopStart, 857 BoolUndef, LoopEnd)); 858 addPhiValues(LoopEnd, LoopStart); 859 setPrevNode(Next); 860 } 861 862 /// After this function control flow looks like it should be, but 863 /// branches and PHI nodes only have undefined conditions. 864 void StructurizeCFG::createFlow() { 865 BasicBlock *Exit = ParentRegion->getExit(); 866 bool EntryDominatesExit = DT->dominates(ParentRegion->getEntry(), Exit); 867 868 DeletedPhis.clear(); 869 AddedPhis.clear(); 870 Conditions.clear(); 871 LoopConds.clear(); 872 873 PrevNode = nullptr; 874 Visited.clear(); 875 876 while (!Order.empty()) { 877 handleLoops(EntryDominatesExit, nullptr); 878 } 879 880 if (PrevNode) 881 changeExit(PrevNode, Exit, EntryDominatesExit); 882 else 883 assert(EntryDominatesExit); 884 } 885 886 /// Handle a rare case where the disintegrated nodes instructions 887 /// no longer dominate all their uses. Not sure if this is really nessasary 888 void StructurizeCFG::rebuildSSA() { 889 SSAUpdater Updater; 890 for (auto *BB : ParentRegion->blocks()) 891 for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); 892 II != IE; ++II) { 893 894 bool Initialized = false; 895 for (auto I = II->use_begin(), E = II->use_end(); I != E;) { 896 Use &U = *I++; 897 Instruction *User = cast<Instruction>(U.getUser()); 898 if (User->getParent() == BB) { 899 continue; 900 901 } else if (PHINode *UserPN = dyn_cast<PHINode>(User)) { 902 if (UserPN->getIncomingBlock(U) == BB) 903 continue; 904 } 905 906 if (DT->dominates(II, User)) 907 continue; 908 909 if (!Initialized) { 910 Value *Undef = UndefValue::get(II->getType()); 911 Updater.Initialize(II->getType(), ""); 912 Updater.AddAvailableValue(&Func->getEntryBlock(), Undef); 913 Updater.AddAvailableValue(BB, II); 914 Initialized = true; 915 } 916 Updater.RewriteUseAfterInsertions(U); 917 } 918 } 919 } 920 921 /// \brief Run the transformation for each region found 922 bool StructurizeCFG::runOnRegion(Region *R, RGPassManager &RGM) { 923 if (R->isTopLevelRegion()) 924 return false; 925 926 Func = R->getEntry()->getParent(); 927 ParentRegion = R; 928 929 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 930 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 931 932 orderNodes(); 933 collectInfos(); 934 createFlow(); 935 insertConditions(false); 936 insertConditions(true); 937 setPhiValues(); 938 rebuildSSA(); 939 940 // Cleanup 941 Order.clear(); 942 Visited.clear(); 943 DeletedPhis.clear(); 944 AddedPhis.clear(); 945 Predicates.clear(); 946 Conditions.clear(); 947 Loops.clear(); 948 LoopPreds.clear(); 949 LoopConds.clear(); 950 951 return true; 952 } 953 954 /// \brief Create the pass 955 Pass *llvm::createStructurizeCFGPass() { 956 return new StructurizeCFG(); 957 } 958