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