lib/Transforms/Utils/BasicBlockUtils.cpp

   1 //===-- BasicBlockUtils.cpp - BasicBlock Utilities -------------------------==//
   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 // This family of functions perform manipulations on basic blocks, and
  11 // instructions contained within basic blocks.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  16 #include "llvm/Function.h"
  17 #include "llvm/Instructions.h"
  18 #include "llvm/IntrinsicInst.h"
  19 #include "llvm/Constant.h"
  20 #include "llvm/Type.h"
  21 #include "llvm/Analysis/AliasAnalysis.h"
  22 #include "llvm/Analysis/LoopInfo.h"
  23 #include "llvm/Analysis/DominanceFrontier.h"
  24 #include "llvm/Target/TargetData.h"
  25 #include "llvm/Transforms/Utils/Local.h"
  26 #include "llvm/Transforms/Scalar.h"
  27 #include "llvm/Support/ErrorHandling.h"
  28 #include "llvm/Support/ValueHandle.h"
  29 #include <algorithm>
  30 using namespace llvm;
  31
  32 /// DeleteDeadBlock - Delete the specified block, which must have no
  33 /// predecessors.
  34 void llvm::DeleteDeadBlock(BasicBlock *BB) {
  35   assert((pred_begin(BB) == pred_end(BB) ||
  36          // Can delete self loop.
  37          BB->getSinglePredecessor() == BB) && "Block is not dead!");
  38   TerminatorInst *BBTerm = BB->getTerminator();
  39
  40   // Loop through all of our successors and make sure they know that one
  41   // of their predecessors is going away.
  42   for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i)
  43     BBTerm->getSuccessor(i)->removePredecessor(BB);
  44
  45   // Zap all the instructions in the block.
  46   while (!BB->empty()) {
  47     Instruction &I = BB->back();
  48     // If this instruction is used, replace uses with an arbitrary value.
  49     // Because control flow can't get here, we don't care what we replace the
  50     // value with.  Note that since this block is unreachable, and all values
  51     // contained within it must dominate their uses, that all uses will
  52     // eventually be removed (they are themselves dead).
  53     if (!I.use_empty())
  54       I.replaceAllUsesWith(UndefValue::get(I.getType()));
  55     BB->getInstList().pop_back();
  56   }
  57
  58   // Zap the block!
  59   BB->eraseFromParent();
  60 }
  61
  62 /// FoldSingleEntryPHINodes - We know that BB has one predecessor.  If there are
  63 /// any single-entry PHI nodes in it, fold them away.  This handles the case
  64 /// when all entries to the PHI nodes in a block are guaranteed equal, such as
  65 /// when the block has exactly one predecessor.
  66 void llvm::FoldSingleEntryPHINodes(BasicBlock *BB) {
  67   while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {
  68     if (PN->getIncomingValue(0) != PN)
  69       PN->replaceAllUsesWith(PN->getIncomingValue(0));
  70     else
  71       PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
  72     PN->eraseFromParent();
  73   }
  74 }
  75
  76
  77 /// DeleteDeadPHIs - Examine each PHI in the given block and delete it if it
  78 /// is dead. Also recursively delete any operands that become dead as
  79 /// a result. This includes tracing the def-use list from the PHI to see if
  80 /// it is ultimately unused or if it reaches an unused cycle.
  81 bool llvm::DeleteDeadPHIs(BasicBlock *BB) {
  82   // Recursively deleting a PHI may cause multiple PHIs to be deleted
  83   // or RAUW'd undef, so use an array of WeakVH for the PHIs to delete.
  84   SmallVector<WeakVH, 8> PHIs;
  85   for (BasicBlock::iterator I = BB->begin();
  86        PHINode *PN = dyn_cast<PHINode>(I); ++I)
  87     PHIs.push_back(PN);
  88
  89   bool Changed = false;
  90   for (unsigned i = 0, e = PHIs.size(); i != e; ++i)
  91     if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i].operator Value*()))
  92       Changed |= RecursivelyDeleteDeadPHINode(PN);
  93
  94   return Changed;
  95 }
  96
  97 /// MergeBlockIntoPredecessor - Attempts to merge a block into its predecessor,
  98 /// if possible.  The return value indicates success or failure.
  99 bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, Pass *P) {
 100   // Don't merge away blocks who have their address taken.
 101   if (BB->hasAddressTaken()) return false;
 102
 103   // Can't merge if there are multiple predecessors, or no predecessors.
 104   BasicBlock *PredBB = BB->getUniquePredecessor();
 105   if (!PredBB) return false;
 106
 107   // Don't break self-loops.
 108   if (PredBB == BB) return false;
 109   // Don't break invokes.
 110   if (isa<InvokeInst>(PredBB->getTerminator())) return false;
 111
 112   succ_iterator SI(succ_begin(PredBB)), SE(succ_end(PredBB));
 113   BasicBlock* OnlySucc = BB;
 114   for (; SI != SE; ++SI)
 115     if (*SI != OnlySucc) {
 116       OnlySucc = 0;     // There are multiple distinct successors!
 117       break;
 118     }
 119
 120   // Can't merge if there are multiple successors.
 121   if (!OnlySucc) return false;
 122
 123   // Can't merge if there is PHI loop.
 124   for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE; ++BI) {
 125     if (PHINode *PN = dyn_cast<PHINode>(BI)) {
 126       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
 127         if (PN->getIncomingValue(i) == PN)
 128           return false;
 129     } else
 130       break;
 131   }
 132
 133   // Begin by getting rid of unneeded PHIs.
 134   while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
 135     PN->replaceAllUsesWith(PN->getIncomingValue(0));
 136     BB->getInstList().pop_front();  // Delete the phi node...
 137   }
 138
 139   // Delete the unconditional branch from the predecessor...
 140   PredBB->getInstList().pop_back();
 141
 142   // Move all definitions in the successor to the predecessor...
 143   PredBB->getInstList().splice(PredBB->end(), BB->getInstList());
 144
 145   // Make all PHI nodes that referred to BB now refer to Pred as their
 146   // source...
 147   BB->replaceAllUsesWith(PredBB);
 148
 149   // Inherit predecessors name if it exists.
 150   if (!PredBB->hasName())
 151     PredBB->takeName(BB);
 152
 153   // Finally, erase the old block and update dominator info.
 154   if (P) {
 155     if (DominatorTree* DT = P->getAnalysisIfAvailable<DominatorTree>()) {
 156       DomTreeNode* DTN = DT->getNode(BB);
 157       DomTreeNode* PredDTN = DT->getNode(PredBB);
 158
 159       if (DTN) {
 160         SmallPtrSet<DomTreeNode*, 8> Children(DTN->begin(), DTN->end());
 161         for (SmallPtrSet<DomTreeNode*, 8>::iterator DI = Children.begin(),
 162              DE = Children.end(); DI != DE; ++DI)
 163           DT->changeImmediateDominator(*DI, PredDTN);
 164
 165         DT->eraseNode(BB);
 166       }
 167     }
 168   }
 169
 170   BB->eraseFromParent();
 171
 172
 173   return true;
 174 }
 175
 176 /// ReplaceInstWithValue - Replace all uses of an instruction (specified by BI)
 177 /// with a value, then remove and delete the original instruction.
 178 ///
 179 void llvm::ReplaceInstWithValue(BasicBlock::InstListType &BIL,
 180                                 BasicBlock::iterator &BI, Value *V) {
 181   Instruction &I = *BI;
 182   // Replaces all of the uses of the instruction with uses of the value
 183   I.replaceAllUsesWith(V);
 184
 185   // Make sure to propagate a name if there is one already.
 186   if (I.hasName() && !V->hasName())
 187     V->takeName(&I);
 188
 189   // Delete the unnecessary instruction now...
 190   BI = BIL.erase(BI);
 191 }
 192
 193
 194 /// ReplaceInstWithInst - Replace the instruction specified by BI with the
 195 /// instruction specified by I.  The original instruction is deleted and BI is
 196 /// updated to point to the new instruction.
 197 ///
 198 void llvm::ReplaceInstWithInst(BasicBlock::InstListType &BIL,
 199                                BasicBlock::iterator &BI, Instruction *I) {
 200   assert(I->getParent() == 0 &&
 201          "ReplaceInstWithInst: Instruction already inserted into basic block!");
 202
 203   // Insert the new instruction into the basic block...
 204   BasicBlock::iterator New = BIL.insert(BI, I);
 205
 206   // Replace all uses of the old instruction, and delete it.
 207   ReplaceInstWithValue(BIL, BI, I);
 208
 209   // Move BI back to point to the newly inserted instruction
 210   BI = New;
 211 }
 212
 213 /// ReplaceInstWithInst - Replace the instruction specified by From with the
 214 /// instruction specified by To.
 215 ///
 216 void llvm::ReplaceInstWithInst(Instruction *From, Instruction *To) {
 217   BasicBlock::iterator BI(From);
 218   ReplaceInstWithInst(From->getParent()->getInstList(), BI, To);
 219 }
 220
 221 /// GetSuccessorNumber - Search for the specified successor of basic block BB
 222 /// and return its position in the terminator instruction's list of
 223 /// successors.  It is an error to call this with a block that is not a
 224 /// successor.
 225 unsigned llvm::GetSuccessorNumber(BasicBlock *BB, BasicBlock *Succ) {
 226   TerminatorInst *Term = BB->getTerminator();
 227 #ifndef NDEBUG
 228   unsigned e = Term->getNumSuccessors();
 229 #endif
 230   for (unsigned i = 0; ; ++i) {
 231     assert(i != e && "Didn't find edge?");
 232     if (Term->getSuccessor(i) == Succ)
 233       return i;
 234   }
 235   return 0;
 236 }
 237
 238 /// SplitEdge -  Split the edge connecting specified block. Pass P must
 239 /// not be NULL.
 240 BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, Pass *P) {
 241   unsigned SuccNum = GetSuccessorNumber(BB, Succ);
 242
 243   // If this is a critical edge, let SplitCriticalEdge do it.
 244   TerminatorInst *LatchTerm = BB->getTerminator();
 245   if (SplitCriticalEdge(LatchTerm, SuccNum, P))
 246     return LatchTerm->getSuccessor(SuccNum);
 247
 248   // If the edge isn't critical, then BB has a single successor or Succ has a
 249   // single pred.  Split the block.
 250   BasicBlock::iterator SplitPoint;
 251   if (BasicBlock *SP = Succ->getSinglePredecessor()) {
 252     // If the successor only has a single pred, split the top of the successor
 253     // block.
 254     assert(SP == BB && "CFG broken");
 255     SP = NULL;
 256     return SplitBlock(Succ, Succ->begin(), P);
 257   } else {
 258     // Otherwise, if BB has a single successor, split it at the bottom of the
 259     // block.
 260     assert(BB->getTerminator()->getNumSuccessors() == 1 &&
 261            "Should have a single succ!");
 262     return SplitBlock(BB, BB->getTerminator(), P);
 263   }
 264 }
 265
 266 /// SplitBlock - Split the specified block at the specified instruction - every
 267 /// thing before SplitPt stays in Old and everything starting with SplitPt moves
 268 /// to a new block.  The two blocks are joined by an unconditional branch and
 269 /// the loop info is updated.
 270 ///
 271 BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, Pass *P) {
 272   BasicBlock::iterator SplitIt = SplitPt;
 273   while (isa<PHINode>(SplitIt))
 274     ++SplitIt;
 275   BasicBlock *New = Old->splitBasicBlock(SplitIt, Old->getName()+".split");
 276
 277   // The new block lives in whichever loop the old one did. This preserves
 278   // LCSSA as well, because we force the split point to be after any PHI nodes.
 279   if (LoopInfo* LI = P->getAnalysisIfAvailable<LoopInfo>())
 280     if (Loop *L = LI->getLoopFor(Old))
 281       L->addBasicBlockToLoop(New, LI->getBase());
 282
 283   if (DominatorTree *DT = P->getAnalysisIfAvailable<DominatorTree>()) {
 284     // Old dominates New. New node dominates all other nodes dominated by Old.
 285     DomTreeNode *OldNode = DT->getNode(Old);
 286     std::vector<DomTreeNode *> Children;
 287     for (DomTreeNode::iterator I = OldNode->begin(), E = OldNode->end();
 288          I != E; ++I)
 289       Children.push_back(*I);
 290
 291       DomTreeNode *NewNode = DT->addNewBlock(New,Old);
 292       for (std::vector<DomTreeNode *>::iterator I = Children.begin(),
 293              E = Children.end(); I != E; ++I)
 294         DT->changeImmediateDominator(*I, NewNode);
 295   }
 296
 297   if (DominanceFrontier *DF = P->getAnalysisIfAvailable<DominanceFrontier>())
 298     DF->splitBlock(Old);
 299
 300   return New;
 301 }
 302
 303
 304 /// SplitBlockPredecessors - This method transforms BB by introducing a new
 305 /// basic block into the function, and moving some of the predecessors of BB to
 306 /// be predecessors of the new block.  The new predecessors are indicated by the
 307 /// Preds array, which has NumPreds elements in it.  The new block is given a
 308 /// suffix of 'Suffix'.
 309 ///
 310 /// This currently updates the LLVM IR, AliasAnalysis, DominatorTree,
 311 /// DominanceFrontier, LoopInfo, and LCCSA but no other analyses.
 312 /// In particular, it does not preserve LoopSimplify (because it's
 313 /// complicated to handle the case where one of the edges being split
 314 /// is an exit of a loop with other exits).
 315 ///
 316 BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB,
 317                                          BasicBlock *const *Preds,
 318                                          unsigned NumPreds, const char *Suffix,
 319                                          Pass *P) {
 320   // Create new basic block, insert right before the original block.
 321   BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), BB->getName()+Suffix,
 322                                          BB->getParent(), BB);
 323
 324   // The new block unconditionally branches to the old block.
 325   BranchInst *BI = BranchInst::Create(BB, NewBB);
 326
 327   LoopInfo *LI = P ? P->getAnalysisIfAvailable<LoopInfo>() : 0;
 328   Loop *L = LI ? LI->getLoopFor(BB) : 0;
 329   bool PreserveLCSSA = P->mustPreserveAnalysisID(LCSSAID);
 330
 331   // Move the edges from Preds to point to NewBB instead of BB.
 332   // While here, if we need to preserve loop analyses, collect
 333   // some information about how this split will affect loops.
 334   bool HasLoopExit = false;
 335   bool IsLoopEntry = !!L;
 336   bool SplitMakesNewLoopHeader = false;
 337   for (unsigned i = 0; i != NumPreds; ++i) {
 338     // This is slightly more strict than necessary; the minimum requirement
 339     // is that there be no more than one indirectbr branching to BB. And
 340     // all BlockAddress uses would need to be updated.
 341     assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) &&
 342            "Cannot split an edge from an IndirectBrInst");
 343
 344     Preds[i]->getTerminator()->replaceUsesOfWith(BB, NewBB);
 345
 346     if (LI) {
 347       // If we need to preserve LCSSA, determine if any of
 348       // the preds is a loop exit.
 349       if (PreserveLCSSA)
 350         if (Loop *PL = LI->getLoopFor(Preds[i]))
 351           if (!PL->contains(BB))
 352             HasLoopExit = true;
 353       // If we need to preserve LoopInfo, note whether any of the
 354       // preds crosses an interesting loop boundary.
 355       if (L) {
 356         if (L->contains(Preds[i]))
 357           IsLoopEntry = false;
 358         else
 359           SplitMakesNewLoopHeader = true;
 360       }
 361     }
 362   }
 363
 364   // Update dominator tree and dominator frontier if available.
 365   DominatorTree *DT = P ? P->getAnalysisIfAvailable<DominatorTree>() : 0;
 366   if (DT)
 367     DT->splitBlock(NewBB);
 368   if (DominanceFrontier *DF =
 369         P ? P->getAnalysisIfAvailable<DominanceFrontier>() : 0)
 370     DF->splitBlock(NewBB);
 371
 372   // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI
 373   // node becomes an incoming value for BB's phi node.  However, if the Preds
 374   // list is empty, we need to insert dummy entries into the PHI nodes in BB to
 375   // account for the newly created predecessor.
 376   if (NumPreds == 0) {
 377     // Insert dummy values as the incoming value.
 378     for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I)
 379       cast<PHINode>(I)->addIncoming(UndefValue::get(I->getType()), NewBB);
 380     return NewBB;
 381   }
 382
 383   AliasAnalysis *AA = P ? P->getAnalysisIfAvailable<AliasAnalysis>() : 0;
 384
 385   if (L) {
 386     if (IsLoopEntry) {
 387       // Add the new block to the nearest enclosing loop (and not an
 388       // adjacent loop). To find this, examine each of the predecessors and
 389       // determine which loops enclose them, and select the most-nested loop
 390       // which contains the loop containing the block being split.
 391       Loop *InnermostPredLoop = 0;
 392       for (unsigned i = 0; i != NumPreds; ++i)
 393         if (Loop *PredLoop = LI->getLoopFor(Preds[i])) {
 394           // Seek a loop which actually contains the block being split (to
 395           // avoid adjacent loops).
 396           while (PredLoop && !PredLoop->contains(BB))
 397             PredLoop = PredLoop->getParentLoop();
 398           // Select the most-nested of these loops which contains the block.
 399           if (PredLoop &&
 400               PredLoop->contains(BB) &&
 401               (!InnermostPredLoop ||
 402                InnermostPredLoop->getLoopDepth() < PredLoop->getLoopDepth()))
 403             InnermostPredLoop = PredLoop;
 404         }
 405       if (InnermostPredLoop)
 406         InnermostPredLoop->addBasicBlockToLoop(NewBB, LI->getBase());
 407     } else {
 408       L->addBasicBlockToLoop(NewBB, LI->getBase());
 409       if (SplitMakesNewLoopHeader)
 410         L->moveToHeader(NewBB);
 411     }
 412   }
 413
 414   // Otherwise, create a new PHI node in NewBB for each PHI node in BB.
 415   for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ) {
 416     PHINode *PN = cast<PHINode>(I++);
 417
 418     // Check to see if all of the values coming in are the same.  If so, we
 419     // don't need to create a new PHI node, unless it's needed for LCSSA.
 420     Value *InVal = 0;
 421     if (!HasLoopExit) {
 422       InVal = PN->getIncomingValueForBlock(Preds[0]);
 423       for (unsigned i = 1; i != NumPreds; ++i)
 424         if (InVal != PN->getIncomingValueForBlock(Preds[i])) {
 425           InVal = 0;
 426           break;
 427         }
 428     }
 429
 430     if (InVal) {
 431       // If all incoming values for the new PHI would be the same, just don't
 432       // make a new PHI.  Instead, just remove the incoming values from the old
 433       // PHI.
 434       for (unsigned i = 0; i != NumPreds; ++i)
 435         PN->removeIncomingValue(Preds[i], false);
 436     } else {
 437       // If the values coming into the block are not the same, we need a PHI.
 438       // Create the new PHI node, insert it into NewBB at the end of the block
 439       PHINode *NewPHI =
 440         PHINode::Create(PN->getType(), PN->getName()+".ph", BI);
 441       if (AA) AA->copyValue(PN, NewPHI);
 442
 443       // Move all of the PHI values for 'Preds' to the new PHI.
 444       for (unsigned i = 0; i != NumPreds; ++i) {
 445         Value *V = PN->removeIncomingValue(Preds[i], false);
 446         NewPHI->addIncoming(V, Preds[i]);
 447       }
 448       InVal = NewPHI;
 449     }
 450
 451     // Add an incoming value to the PHI node in the loop for the preheader
 452     // edge.
 453     PN->addIncoming(InVal, NewBB);
 454   }
 455
 456   return NewBB;
 457 }
 458
 459 /// FindFunctionBackedges - Analyze the specified function to find all of the
 460 /// loop backedges in the function and return them.  This is a relatively cheap
 461 /// (compared to computing dominators and loop info) analysis.
 462 ///
 463 /// The output is added to Result, as pairs of <from,to> edge info.
 464 void llvm::FindFunctionBackedges(const Function &F,
 465      SmallVectorImpl<std::pair<const BasicBlock*,const BasicBlock*> > &Result) {
 466   const BasicBlock *BB = &F.getEntryBlock();
 467   if (succ_begin(BB) == succ_end(BB))
 468     return;
 469
 470   SmallPtrSet<const BasicBlock*, 8> Visited;
 471   SmallVector<std::pair<const BasicBlock*, succ_const_iterator>, 8> VisitStack;
 472   SmallPtrSet<const BasicBlock*, 8> InStack;
 473
 474   Visited.insert(BB);
 475   VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
 476   InStack.insert(BB);
 477   do {
 478     std::pair<const BasicBlock*, succ_const_iterator> &Top = VisitStack.back();
 479     const BasicBlock *ParentBB = Top.first;
 480     succ_const_iterator &I = Top.second;
 481
 482     bool FoundNew = false;
 483     while (I != succ_end(ParentBB)) {
 484       BB = *I++;
 485       if (Visited.insert(BB)) {
 486         FoundNew = true;
 487         break;
 488       }
 489       // Successor is in VisitStack, it's a back edge.
 490       if (InStack.count(BB))
 491         Result.push_back(std::make_pair(ParentBB, BB));
 492     }
 493
 494     if (FoundNew) {
 495       // Go down one level if there is a unvisited successor.
 496       InStack.insert(BB);
 497       VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
 498     } else {
 499       // Go up one level.
 500       InStack.erase(VisitStack.pop_back_val().first);
 501     }
 502   } while (!VisitStack.empty());
 503
 504
 505 }