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 (BasicBlock *Succ : Term->successors()) 362 if (Visited.count(Succ)) 363 Loops[Succ] = BB; 364 } 365 } 366 367 /// \brief Invert the given condition 368 Value *StructurizeCFG::invert(Value *Condition) { 369 // First: Check if it's a constant 370 if (Condition == BoolTrue) 371 return BoolFalse; 372 373 if (Condition == BoolFalse) 374 return BoolTrue; 375 376 if (Condition == BoolUndef) 377 return BoolUndef; 378 379 // Second: If the condition is already inverted, return the original value 380 if (match(Condition, m_Not(m_Value(Condition)))) 381 return Condition; 382 383 if (Instruction *Inst = dyn_cast<Instruction>(Condition)) { 384 // Third: Check all the users for an invert 385 BasicBlock *Parent = Inst->getParent(); 386 for (User *U : Condition->users()) 387 if (Instruction *I = dyn_cast<Instruction>(U)) 388 if (I->getParent() == Parent && match(I, m_Not(m_Specific(Condition)))) 389 return I; 390 391 // Last option: Create a new instruction 392 return BinaryOperator::CreateNot(Condition, "", Parent->getTerminator()); 393 } 394 395 if (Argument *Arg = dyn_cast<Argument>(Condition)) { 396 BasicBlock &EntryBlock = Arg->getParent()->getEntryBlock(); 397 return BinaryOperator::CreateNot(Condition, 398 Arg->getName() + ".inv", 399 EntryBlock.getTerminator()); 400 } 401 402 llvm_unreachable("Unhandled condition to invert"); 403 } 404 405 /// \brief Build the condition for one edge 406 Value *StructurizeCFG::buildCondition(BranchInst *Term, unsigned Idx, 407 bool Invert) { 408 Value *Cond = Invert ? BoolFalse : BoolTrue; 409 if (Term->isConditional()) { 410 Cond = Term->getCondition(); 411 412 if (Idx != (unsigned)Invert) 413 Cond = invert(Cond); 414 } 415 return Cond; 416 } 417 418 /// \brief Analyze the predecessors of each block and build up predicates 419 void StructurizeCFG::gatherPredicates(RegionNode *N) { 420 RegionInfo *RI = ParentRegion->getRegionInfo(); 421 BasicBlock *BB = N->getEntry(); 422 BBPredicates &Pred = Predicates[BB]; 423 BBPredicates &LPred = LoopPreds[BB]; 424 425 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); 426 PI != PE; ++PI) { 427 428 // Ignore it if it's a branch from outside into our region entry 429 if (!ParentRegion->contains(*PI)) 430 continue; 431 432 Region *R = RI->getRegionFor(*PI); 433 if (R == ParentRegion) { 434 435 // It's a top level block in our region 436 BranchInst *Term = cast<BranchInst>((*PI)->getTerminator()); 437 for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) { 438 BasicBlock *Succ = Term->getSuccessor(i); 439 if (Succ != BB) 440 continue; 441 442 if (Visited.count(*PI)) { 443 // Normal forward edge 444 if (Term->isConditional()) { 445 // Try to treat it like an ELSE block 446 BasicBlock *Other = Term->getSuccessor(!i); 447 if (Visited.count(Other) && !Loops.count(Other) && 448 !Pred.count(Other) && !Pred.count(*PI)) { 449 450 Pred[Other] = BoolFalse; 451 Pred[*PI] = BoolTrue; 452 continue; 453 } 454 } 455 Pred[*PI] = buildCondition(Term, i, false); 456 457 } else { 458 // Back edge 459 LPred[*PI] = buildCondition(Term, i, true); 460 } 461 } 462 463 } else { 464 465 // It's an exit from a sub region 466 while (R->getParent() != ParentRegion) 467 R = R->getParent(); 468 469 // Edge from inside a subregion to its entry, ignore it 470 if (*R == *N) 471 continue; 472 473 BasicBlock *Entry = R->getEntry(); 474 if (Visited.count(Entry)) 475 Pred[Entry] = BoolTrue; 476 else 477 LPred[Entry] = BoolFalse; 478 } 479 } 480 } 481 482 /// \brief Collect various loop and predicate infos 483 void StructurizeCFG::collectInfos() { 484 // Reset predicate 485 Predicates.clear(); 486 487 // and loop infos 488 Loops.clear(); 489 LoopPreds.clear(); 490 491 // Reset the visited nodes 492 Visited.clear(); 493 494 for (RNVector::reverse_iterator OI = Order.rbegin(), OE = Order.rend(); 495 OI != OE; ++OI) { 496 497 DEBUG(dbgs() << "Visiting: " << 498 ((*OI)->isSubRegion() ? "SubRegion with entry: " : "") << 499 (*OI)->getEntry()->getName() << " Loop Depth: " << LI->getLoopDepth((*OI)->getEntry()) << "\n"); 500 501 // Analyze all the conditions leading to a node 502 gatherPredicates(*OI); 503 504 // Remember that we've seen this node 505 Visited.insert((*OI)->getEntry()); 506 507 // Find the last back edges 508 analyzeLoops(*OI); 509 } 510 } 511 512 /// \brief Insert the missing branch conditions 513 void StructurizeCFG::insertConditions(bool Loops) { 514 BranchVector &Conds = Loops ? LoopConds : Conditions; 515 Value *Default = Loops ? BoolTrue : BoolFalse; 516 SSAUpdater PhiInserter; 517 518 for (BranchInst *Term : Conds) { 519 assert(Term->isConditional()); 520 521 BasicBlock *Parent = Term->getParent(); 522 BasicBlock *SuccTrue = Term->getSuccessor(0); 523 BasicBlock *SuccFalse = Term->getSuccessor(1); 524 525 PhiInserter.Initialize(Boolean, ""); 526 PhiInserter.AddAvailableValue(&Func->getEntryBlock(), Default); 527 PhiInserter.AddAvailableValue(Loops ? SuccFalse : Parent, Default); 528 529 BBPredicates &Preds = Loops ? LoopPreds[SuccFalse] : Predicates[SuccTrue]; 530 531 NearestCommonDominator Dominator(DT); 532 Dominator.addBlock(Parent, false); 533 534 Value *ParentValue = nullptr; 535 for (BBPredicates::iterator PI = Preds.begin(), PE = Preds.end(); 536 PI != PE; ++PI) { 537 538 if (PI->first == Parent) { 539 ParentValue = PI->second; 540 break; 541 } 542 PhiInserter.AddAvailableValue(PI->first, PI->second); 543 Dominator.addBlock(PI->first); 544 } 545 546 if (ParentValue) { 547 Term->setCondition(ParentValue); 548 } else { 549 if (!Dominator.wasResultExplicitMentioned()) 550 PhiInserter.AddAvailableValue(Dominator.getResult(), Default); 551 552 Term->setCondition(PhiInserter.GetValueInMiddleOfBlock(Parent)); 553 } 554 } 555 } 556 557 /// \brief Remove all PHI values coming from "From" into "To" and remember 558 /// them in DeletedPhis 559 void StructurizeCFG::delPhiValues(BasicBlock *From, BasicBlock *To) { 560 PhiMap &Map = DeletedPhis[To]; 561 for (BasicBlock::iterator I = To->begin(), E = To->end(); 562 I != E && isa<PHINode>(*I);) { 563 564 PHINode &Phi = cast<PHINode>(*I++); 565 while (Phi.getBasicBlockIndex(From) != -1) { 566 Value *Deleted = Phi.removeIncomingValue(From, false); 567 Map[&Phi].push_back(std::make_pair(From, Deleted)); 568 } 569 } 570 } 571 572 /// \brief Add a dummy PHI value as soon as we knew the new predecessor 573 void StructurizeCFG::addPhiValues(BasicBlock *From, BasicBlock *To) { 574 for (BasicBlock::iterator I = To->begin(), E = To->end(); 575 I != E && isa<PHINode>(*I);) { 576 577 PHINode &Phi = cast<PHINode>(*I++); 578 Value *Undef = UndefValue::get(Phi.getType()); 579 Phi.addIncoming(Undef, From); 580 } 581 AddedPhis[To].push_back(From); 582 } 583 584 /// \brief Add the real PHI value as soon as everything is set up 585 void StructurizeCFG::setPhiValues() { 586 SSAUpdater Updater; 587 for (BB2BBVecMap::iterator AI = AddedPhis.begin(), AE = AddedPhis.end(); 588 AI != AE; ++AI) { 589 590 BasicBlock *To = AI->first; 591 BBVector &From = AI->second; 592 593 if (!DeletedPhis.count(To)) 594 continue; 595 596 PhiMap &Map = DeletedPhis[To]; 597 for (PhiMap::iterator PI = Map.begin(), PE = Map.end(); 598 PI != PE; ++PI) { 599 600 PHINode *Phi = PI->first; 601 Value *Undef = UndefValue::get(Phi->getType()); 602 Updater.Initialize(Phi->getType(), ""); 603 Updater.AddAvailableValue(&Func->getEntryBlock(), Undef); 604 Updater.AddAvailableValue(To, Undef); 605 606 NearestCommonDominator Dominator(DT); 607 Dominator.addBlock(To, false); 608 for (BBValueVector::iterator VI = PI->second.begin(), 609 VE = PI->second.end(); VI != VE; ++VI) { 610 611 Updater.AddAvailableValue(VI->first, VI->second); 612 Dominator.addBlock(VI->first); 613 } 614 615 if (!Dominator.wasResultExplicitMentioned()) 616 Updater.AddAvailableValue(Dominator.getResult(), Undef); 617 618 for (BBVector::iterator FI = From.begin(), FE = From.end(); 619 FI != FE; ++FI) { 620 621 int Idx = Phi->getBasicBlockIndex(*FI); 622 assert(Idx != -1); 623 Phi->setIncomingValue(Idx, Updater.GetValueAtEndOfBlock(*FI)); 624 } 625 } 626 627 DeletedPhis.erase(To); 628 } 629 assert(DeletedPhis.empty()); 630 } 631 632 /// \brief Remove phi values from all successors and then remove the terminator. 633 void StructurizeCFG::killTerminator(BasicBlock *BB) { 634 TerminatorInst *Term = BB->getTerminator(); 635 if (!Term) 636 return; 637 638 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); 639 SI != SE; ++SI) { 640 641 delPhiValues(BB, *SI); 642 } 643 644 Term->eraseFromParent(); 645 } 646 647 /// \brief Let node exit(s) point to NewExit 648 void StructurizeCFG::changeExit(RegionNode *Node, BasicBlock *NewExit, 649 bool IncludeDominator) { 650 if (Node->isSubRegion()) { 651 Region *SubRegion = Node->getNodeAs<Region>(); 652 BasicBlock *OldExit = SubRegion->getExit(); 653 BasicBlock *Dominator = nullptr; 654 655 // Find all the edges from the sub region to the exit 656 for (pred_iterator I = pred_begin(OldExit), E = pred_end(OldExit); 657 I != E;) { 658 659 BasicBlock *BB = *I++; 660 if (!SubRegion->contains(BB)) 661 continue; 662 663 // Modify the edges to point to the new exit 664 delPhiValues(BB, OldExit); 665 BB->getTerminator()->replaceUsesOfWith(OldExit, NewExit); 666 addPhiValues(BB, NewExit); 667 668 // Find the new dominator (if requested) 669 if (IncludeDominator) { 670 if (!Dominator) 671 Dominator = BB; 672 else 673 Dominator = DT->findNearestCommonDominator(Dominator, BB); 674 } 675 } 676 677 // Change the dominator (if requested) 678 if (Dominator) 679 DT->changeImmediateDominator(NewExit, Dominator); 680 681 // Update the region info 682 SubRegion->replaceExit(NewExit); 683 684 } else { 685 BasicBlock *BB = Node->getNodeAs<BasicBlock>(); 686 killTerminator(BB); 687 BranchInst::Create(NewExit, BB); 688 addPhiValues(BB, NewExit); 689 if (IncludeDominator) 690 DT->changeImmediateDominator(NewExit, BB); 691 } 692 } 693 694 /// \brief Create a new flow node and update dominator tree and region info 695 BasicBlock *StructurizeCFG::getNextFlow(BasicBlock *Dominator) { 696 LLVMContext &Context = Func->getContext(); 697 BasicBlock *Insert = Order.empty() ? ParentRegion->getExit() : 698 Order.back()->getEntry(); 699 BasicBlock *Flow = BasicBlock::Create(Context, FlowBlockName, 700 Func, Insert); 701 DT->addNewBlock(Flow, Dominator); 702 ParentRegion->getRegionInfo()->setRegionFor(Flow, ParentRegion); 703 return Flow; 704 } 705 706 /// \brief Create a new or reuse the previous node as flow node 707 BasicBlock *StructurizeCFG::needPrefix(bool NeedEmpty) { 708 BasicBlock *Entry = PrevNode->getEntry(); 709 710 if (!PrevNode->isSubRegion()) { 711 killTerminator(Entry); 712 if (!NeedEmpty || Entry->getFirstInsertionPt() == Entry->end()) 713 return Entry; 714 715 } 716 717 // create a new flow node 718 BasicBlock *Flow = getNextFlow(Entry); 719 720 // and wire it up 721 changeExit(PrevNode, Flow, true); 722 PrevNode = ParentRegion->getBBNode(Flow); 723 return Flow; 724 } 725 726 /// \brief Returns the region exit if possible, otherwise just a new flow node 727 BasicBlock *StructurizeCFG::needPostfix(BasicBlock *Flow, 728 bool ExitUseAllowed) { 729 if (Order.empty() && ExitUseAllowed) { 730 BasicBlock *Exit = ParentRegion->getExit(); 731 DT->changeImmediateDominator(Exit, Flow); 732 addPhiValues(Flow, Exit); 733 return Exit; 734 } 735 return getNextFlow(Flow); 736 } 737 738 /// \brief Set the previous node 739 void StructurizeCFG::setPrevNode(BasicBlock *BB) { 740 PrevNode = ParentRegion->contains(BB) ? ParentRegion->getBBNode(BB) 741 : nullptr; 742 } 743 744 /// \brief Does BB dominate all the predicates of Node ? 745 bool StructurizeCFG::dominatesPredicates(BasicBlock *BB, RegionNode *Node) { 746 BBPredicates &Preds = Predicates[Node->getEntry()]; 747 for (BBPredicates::iterator PI = Preds.begin(), PE = Preds.end(); 748 PI != PE; ++PI) { 749 750 if (!DT->dominates(BB, PI->first)) 751 return false; 752 } 753 return true; 754 } 755 756 /// \brief Can we predict that this node will always be called? 757 bool StructurizeCFG::isPredictableTrue(RegionNode *Node) { 758 BBPredicates &Preds = Predicates[Node->getEntry()]; 759 bool Dominated = false; 760 761 // Regionentry is always true 762 if (!PrevNode) 763 return true; 764 765 for (BBPredicates::iterator I = Preds.begin(), E = Preds.end(); 766 I != E; ++I) { 767 768 if (I->second != BoolTrue) 769 return false; 770 771 if (!Dominated && DT->dominates(I->first, PrevNode->getEntry())) 772 Dominated = true; 773 } 774 775 // TODO: The dominator check is too strict 776 return Dominated; 777 } 778 779 /// Take one node from the order vector and wire it up 780 void StructurizeCFG::wireFlow(bool ExitUseAllowed, 781 BasicBlock *LoopEnd) { 782 RegionNode *Node = Order.pop_back_val(); 783 Visited.insert(Node->getEntry()); 784 785 if (isPredictableTrue(Node)) { 786 // Just a linear flow 787 if (PrevNode) { 788 changeExit(PrevNode, Node->getEntry(), true); 789 } 790 PrevNode = Node; 791 792 } else { 793 // Insert extra prefix node (or reuse last one) 794 BasicBlock *Flow = needPrefix(false); 795 796 // Insert extra postfix node (or use exit instead) 797 BasicBlock *Entry = Node->getEntry(); 798 BasicBlock *Next = needPostfix(Flow, ExitUseAllowed); 799 800 // let it point to entry and next block 801 Conditions.push_back(BranchInst::Create(Entry, Next, BoolUndef, Flow)); 802 addPhiValues(Flow, Entry); 803 DT->changeImmediateDominator(Entry, Flow); 804 805 PrevNode = Node; 806 while (!Order.empty() && !Visited.count(LoopEnd) && 807 dominatesPredicates(Entry, Order.back())) { 808 handleLoops(false, LoopEnd); 809 } 810 811 changeExit(PrevNode, Next, false); 812 setPrevNode(Next); 813 } 814 } 815 816 void StructurizeCFG::handleLoops(bool ExitUseAllowed, 817 BasicBlock *LoopEnd) { 818 RegionNode *Node = Order.back(); 819 BasicBlock *LoopStart = Node->getEntry(); 820 821 if (!Loops.count(LoopStart)) { 822 wireFlow(ExitUseAllowed, LoopEnd); 823 return; 824 } 825 826 if (!isPredictableTrue(Node)) 827 LoopStart = needPrefix(true); 828 829 LoopEnd = Loops[Node->getEntry()]; 830 wireFlow(false, LoopEnd); 831 while (!Visited.count(LoopEnd)) { 832 handleLoops(false, LoopEnd); 833 } 834 835 // If the start of the loop is the entry block, we can't branch to it so 836 // insert a new dummy entry block. 837 Function *LoopFunc = LoopStart->getParent(); 838 if (LoopStart == &LoopFunc->getEntryBlock()) { 839 LoopStart->setName("entry.orig"); 840 841 BasicBlock *NewEntry = 842 BasicBlock::Create(LoopStart->getContext(), 843 "entry", 844 LoopFunc, 845 LoopStart); 846 BranchInst::Create(LoopStart, NewEntry); 847 } 848 849 // Create an extra loop end node 850 LoopEnd = needPrefix(false); 851 BasicBlock *Next = needPostfix(LoopEnd, ExitUseAllowed); 852 LoopConds.push_back(BranchInst::Create(Next, LoopStart, 853 BoolUndef, LoopEnd)); 854 addPhiValues(LoopEnd, LoopStart); 855 setPrevNode(Next); 856 } 857 858 /// After this function control flow looks like it should be, but 859 /// branches and PHI nodes only have undefined conditions. 860 void StructurizeCFG::createFlow() { 861 BasicBlock *Exit = ParentRegion->getExit(); 862 bool EntryDominatesExit = DT->dominates(ParentRegion->getEntry(), Exit); 863 864 DeletedPhis.clear(); 865 AddedPhis.clear(); 866 Conditions.clear(); 867 LoopConds.clear(); 868 869 PrevNode = nullptr; 870 Visited.clear(); 871 872 while (!Order.empty()) { 873 handleLoops(EntryDominatesExit, nullptr); 874 } 875 876 if (PrevNode) 877 changeExit(PrevNode, Exit, EntryDominatesExit); 878 else 879 assert(EntryDominatesExit); 880 } 881 882 /// Handle a rare case where the disintegrated nodes instructions 883 /// no longer dominate all their uses. Not sure if this is really nessasary 884 void StructurizeCFG::rebuildSSA() { 885 SSAUpdater Updater; 886 for (auto *BB : ParentRegion->blocks()) 887 for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); 888 II != IE; ++II) { 889 890 bool Initialized = false; 891 for (auto I = II->use_begin(), E = II->use_end(); I != E;) { 892 Use &U = *I++; 893 Instruction *User = cast<Instruction>(U.getUser()); 894 if (User->getParent() == BB) { 895 continue; 896 897 } else if (PHINode *UserPN = dyn_cast<PHINode>(User)) { 898 if (UserPN->getIncomingBlock(U) == BB) 899 continue; 900 } 901 902 if (DT->dominates(&*II, User)) 903 continue; 904 905 if (!Initialized) { 906 Value *Undef = UndefValue::get(II->getType()); 907 Updater.Initialize(II->getType(), ""); 908 Updater.AddAvailableValue(&Func->getEntryBlock(), Undef); 909 Updater.AddAvailableValue(BB, &*II); 910 Initialized = true; 911 } 912 Updater.RewriteUseAfterInsertions(U); 913 } 914 } 915 } 916 917 /// \brief Run the transformation for each region found 918 bool StructurizeCFG::runOnRegion(Region *R, RGPassManager &RGM) { 919 if (R->isTopLevelRegion()) 920 return false; 921 922 Func = R->getEntry()->getParent(); 923 ParentRegion = R; 924 925 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 926 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 927 928 orderNodes(); 929 collectInfos(); 930 createFlow(); 931 insertConditions(false); 932 insertConditions(true); 933 setPhiValues(); 934 rebuildSSA(); 935 936 // Cleanup 937 Order.clear(); 938 Visited.clear(); 939 DeletedPhis.clear(); 940 AddedPhis.clear(); 941 Predicates.clear(); 942 Conditions.clear(); 943 Loops.clear(); 944 LoopPreds.clear(); 945 LoopConds.clear(); 946 947 return true; 948 } 949 950 /// \brief Create the pass 951 Pass *llvm::createStructurizeCFGPass() { 952 return new StructurizeCFG(); 953 } 954