StructurizeCFG.cpp revision 263508
1353944Sdim//===-- StructurizeCFG.cpp ------------------------------------------------===// 2353944Sdim// 3353944Sdim// The LLVM Compiler Infrastructure 4353944Sdim// 5353944Sdim// This file is distributed under the University of Illinois Open Source 6353944Sdim// License. See LICENSE.TXT for details. 7353944Sdim// 8353944Sdim//===----------------------------------------------------------------------===// 9353944Sdim 10353944Sdim#define DEBUG_TYPE "structurizecfg" 11353944Sdim#include "llvm/Transforms/Scalar.h" 12353944Sdim#include "llvm/ADT/MapVector.h" 13353944Sdim#include "llvm/ADT/SCCIterator.h" 14353944Sdim#include "llvm/Analysis/RegionInfo.h" 15353944Sdim#include "llvm/Analysis/RegionIterator.h" 16353944Sdim#include "llvm/Analysis/RegionPass.h" 17353944Sdim#include "llvm/IR/Module.h" 18353944Sdim#include "llvm/Support/PatternMatch.h" 19353944Sdim#include "llvm/Transforms/Utils/SSAUpdater.h" 20353944Sdim 21353944Sdimusing namespace llvm; 22353944Sdimusing namespace llvm::PatternMatch; 23353944Sdim 24353944Sdimnamespace { 25353944Sdim 26353944Sdim// Definition of the complex types used in this pass. 27353944Sdim 28353944Sdimtypedef std::pair<BasicBlock *, Value *> BBValuePair; 29353944Sdim 30353944Sdimtypedef SmallVector<RegionNode*, 8> RNVector; 31353944Sdimtypedef SmallVector<BasicBlock*, 8> BBVector; 32353944Sdimtypedef SmallVector<BranchInst*, 8> BranchVector; 33353944Sdimtypedef SmallVector<BBValuePair, 2> BBValueVector; 34353944Sdim 35353944Sdimtypedef SmallPtrSet<BasicBlock *, 8> BBSet; 36353944Sdim 37353944Sdimtypedef MapVector<PHINode *, BBValueVector> PhiMap; 38353944Sdimtypedef MapVector<BasicBlock *, BBVector> BB2BBVecMap; 39353944Sdim 40353944Sdimtypedef DenseMap<DomTreeNode *, unsigned> DTN2UnsignedMap; 41353944Sdimtypedef DenseMap<BasicBlock *, PhiMap> BBPhiMap; 42353944Sdimtypedef DenseMap<BasicBlock *, Value *> BBPredicates; 43353944Sdimtypedef DenseMap<BasicBlock *, BBPredicates> PredMap; 44353944Sdimtypedef DenseMap<BasicBlock *, BasicBlock*> BB2BBMap; 45353944Sdim 46353944Sdim// The name for newly created blocks. 47353944Sdim 48353944Sdimstatic const char *const FlowBlockName = "Flow"; 49353944Sdim 50353944Sdim/// @brief Find the nearest common dominator for multiple BasicBlocks 51353944Sdim/// 52353944Sdim/// Helper class for StructurizeCFG 53353944Sdim/// TODO: Maybe move into common code 54353944Sdimclass NearestCommonDominator { 55353944Sdim DominatorTree *DT; 56353944Sdim 57353944Sdim DTN2UnsignedMap IndexMap; 58353944Sdim 59353944Sdim BasicBlock *Result; 60353944Sdim unsigned ResultIndex; 61353944Sdim bool ExplicitMentioned; 62353944Sdim 63353944Sdimpublic: 64353944Sdim /// \brief Start a new query 65353944Sdim NearestCommonDominator(DominatorTree *DomTree) { 66353944Sdim DT = DomTree; 67353944Sdim Result = 0; 68353944Sdim } 69353944Sdim 70353944Sdim /// \brief Add BB to the resulting dominator 71353944Sdim void addBlock(BasicBlock *BB, bool Remember = true) { 72353944Sdim DomTreeNode *Node = DT->getNode(BB); 73353944Sdim 74353944Sdim if (Result == 0) { 75353944Sdim unsigned Numbering = 0; 76353944Sdim for (;Node;Node = Node->getIDom()) 77353944Sdim IndexMap[Node] = ++Numbering; 78353944Sdim Result = BB; 79353944Sdim ResultIndex = 1; 80353944Sdim ExplicitMentioned = Remember; 81353944Sdim return; 82353944Sdim } 83353944Sdim 84353944Sdim for (;Node;Node = Node->getIDom()) 85353944Sdim if (IndexMap.count(Node)) 86353944Sdim break; 87353944Sdim else 88353944Sdim IndexMap[Node] = 0; 89353944Sdim 90353944Sdim assert(Node && "Dominator tree invalid!"); 91353944Sdim 92353944Sdim unsigned Numbering = IndexMap[Node]; 93353944Sdim if (Numbering > ResultIndex) { 94353944Sdim Result = Node->getBlock(); 95353944Sdim ResultIndex = Numbering; 96353944Sdim ExplicitMentioned = Remember && (Result == BB); 97353944Sdim } else if (Numbering == ResultIndex) { 98353944Sdim ExplicitMentioned |= Remember; 99353944Sdim } 100353944Sdim } 101353944Sdim 102353944Sdim /// \brief Is "Result" one of the BBs added with "Remember" = True? 103353944Sdim bool wasResultExplicitMentioned() { 104353944Sdim return ExplicitMentioned; 105353944Sdim } 106353944Sdim 107353944Sdim /// \brief Get the query result 108353944Sdim BasicBlock *getResult() { 109353944Sdim return Result; 110353944Sdim } 111353944Sdim}; 112353944Sdim 113353944Sdim/// @brief Transforms the control flow graph on one single entry/exit region 114353944Sdim/// at a time. 115353944Sdim/// 116353944Sdim/// After the transform all "If"/"Then"/"Else" style control flow looks like 117353944Sdim/// this: 118353944Sdim/// 119353944Sdim/// \verbatim 120353944Sdim/// 1 121353944Sdim/// || 122353944Sdim/// | | 123353944Sdim/// 2 | 124353944Sdim/// | / 125353944Sdim/// |/ 126353944Sdim/// 3 127353944Sdim/// || Where: 128353944Sdim/// | | 1 = "If" block, calculates the condition 129353944Sdim/// 4 | 2 = "Then" subregion, runs if the condition is true 130353944Sdim/// | / 3 = "Flow" blocks, newly inserted flow blocks, rejoins the flow 131353944Sdim/// |/ 4 = "Else" optional subregion, runs if the condition is false 132353944Sdim/// 5 5 = "End" block, also rejoins the control flow 133353944Sdim/// \endverbatim 134353944Sdim/// 135353944Sdim/// Control flow is expressed as a branch where the true exit goes into the 136353944Sdim/// "Then"/"Else" region, while the false exit skips the region 137353944Sdim/// The condition for the optional "Else" region is expressed as a PHI node. 138353944Sdim/// The incomming values of the PHI node are true for the "If" edge and false 139353944Sdim/// for the "Then" edge. 140353944Sdim/// 141353944Sdim/// Additionally to that even complicated loops look like this: 142353944Sdim/// 143353944Sdim/// \verbatim 144353944Sdim/// 1 145353944Sdim/// || 146353944Sdim/// | | 147353944Sdim/// 2 ^ Where: 148353944Sdim/// | / 1 = "Entry" block 149353944Sdim/// |/ 2 = "Loop" optional subregion, with all exits at "Flow" block 150353944Sdim/// 3 3 = "Flow" block, with back edge to entry block 151353944Sdim/// | 152353944Sdim/// \endverbatim 153353944Sdim/// 154353944Sdim/// The back edge of the "Flow" block is always on the false side of the branch 155353944Sdim/// while the true side continues the general flow. So the loop condition 156353944Sdim/// consist of a network of PHI nodes where the true incoming values expresses 157353944Sdim/// breaks and the false values expresses continue states. 158353944Sdimclass StructurizeCFG : public RegionPass { 159353944Sdim Type *Boolean; 160353944Sdim ConstantInt *BoolTrue; 161353944Sdim ConstantInt *BoolFalse; 162353944Sdim UndefValue *BoolUndef; 163353944Sdim 164353944Sdim Function *Func; 165353944Sdim Region *ParentRegion; 166353944Sdim 167353944Sdim DominatorTree *DT; 168353944Sdim 169353944Sdim RNVector Order; 170353944Sdim BBSet Visited; 171353944Sdim 172353944Sdim BBPhiMap DeletedPhis; 173353944Sdim BB2BBVecMap AddedPhis; 174353944Sdim 175353944Sdim PredMap Predicates; 176353944Sdim BranchVector Conditions; 177353944Sdim 178353944Sdim BB2BBMap Loops; 179353944Sdim PredMap LoopPreds; 180353944Sdim BranchVector LoopConds; 181353944Sdim 182353944Sdim RegionNode *PrevNode; 183353944Sdim 184353944Sdim void orderNodes(); 185353944Sdim 186353944Sdim void analyzeLoops(RegionNode *N); 187353944Sdim 188353944Sdim Value *invert(Value *Condition); 189353944Sdim 190353944Sdim Value *buildCondition(BranchInst *Term, unsigned Idx, bool Invert); 191353944Sdim 192353944Sdim void gatherPredicates(RegionNode *N); 193353944Sdim 194353944Sdim void collectInfos(); 195353944Sdim 196353944Sdim void insertConditions(bool Loops); 197353944Sdim 198353944Sdim void delPhiValues(BasicBlock *From, BasicBlock *To); 199353944Sdim 200353944Sdim void addPhiValues(BasicBlock *From, BasicBlock *To); 201353944Sdim 202353944Sdim void setPhiValues(); 203353944Sdim 204353944Sdim void killTerminator(BasicBlock *BB); 205353944Sdim 206353944Sdim void changeExit(RegionNode *Node, BasicBlock *NewExit, 207353944Sdim bool IncludeDominator); 208353944Sdim 209353944Sdim BasicBlock *getNextFlow(BasicBlock *Dominator); 210353944Sdim 211353944Sdim BasicBlock *needPrefix(bool NeedEmpty); 212353944Sdim 213353944Sdim BasicBlock *needPostfix(BasicBlock *Flow, bool ExitUseAllowed); 214353944Sdim 215353944Sdim void setPrevNode(BasicBlock *BB); 216353944Sdim 217353944Sdim bool dominatesPredicates(BasicBlock *BB, RegionNode *Node); 218353944Sdim 219353944Sdim bool isPredictableTrue(RegionNode *Node); 220353944Sdim 221353944Sdim void wireFlow(bool ExitUseAllowed, BasicBlock *LoopEnd); 222353944Sdim 223353944Sdim void handleLoops(bool ExitUseAllowed, BasicBlock *LoopEnd); 224353944Sdim 225353944Sdim void createFlow(); 226353944Sdim 227353944Sdim void rebuildSSA(); 228353944Sdim 229353944Sdimpublic: 230353944Sdim static char ID; 231353944Sdim 232353944Sdim StructurizeCFG() : 233353944Sdim RegionPass(ID) { 234353944Sdim initializeStructurizeCFGPass(*PassRegistry::getPassRegistry()); 235353944Sdim } 236353944Sdim 237353944Sdim using Pass::doInitialization; 238353944Sdim virtual bool doInitialization(Region *R, RGPassManager &RGM); 239353944Sdim 240353944Sdim virtual bool runOnRegion(Region *R, RGPassManager &RGM); 241353944Sdim 242353944Sdim virtual const char *getPassName() const { 243353944Sdim return "Structurize control flow"; 244353944Sdim } 245353944Sdim 246353944Sdim void getAnalysisUsage(AnalysisUsage &AU) const { 247353944Sdim AU.addRequiredID(LowerSwitchID); 248353944Sdim AU.addRequired<DominatorTree>(); 249353944Sdim AU.addPreserved<DominatorTree>(); 250353944Sdim RegionPass::getAnalysisUsage(AU); 251353944Sdim } 252353944Sdim}; 253353944Sdim 254353944Sdim} // end anonymous namespace 255353944Sdim 256353944Sdimchar StructurizeCFG::ID = 0; 257353944Sdim 258353944SdimINITIALIZE_PASS_BEGIN(StructurizeCFG, "structurizecfg", "Structurize the CFG", 259353944Sdim false, false) 260353944SdimINITIALIZE_PASS_DEPENDENCY(LowerSwitch) 261353944SdimINITIALIZE_PASS_DEPENDENCY(DominatorTree) 262353944SdimINITIALIZE_PASS_DEPENDENCY(RegionInfo) 263353944SdimINITIALIZE_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