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