BasicBlockUtils.cpp revision 52c95856b4a40ccae6c4b0e13b2a04101e1f79c9
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/Constant.h" 19#include "llvm/Type.h" 20#include "llvm/Analysis/AliasAnalysis.h" 21#include "llvm/Analysis/LoopInfo.h" 22#include "llvm/Analysis/Dominators.h" 23#include <algorithm> 24using namespace llvm; 25 26/// MergeBlockIntoPredecessor - Attempts to merge a block into its predecessor, 27/// if possible. The return value indicates success or failure. 28bool llvm::MergeBlockIntoPredecessor(BasicBlock* BB, Pass* P) { 29 pred_iterator PI(pred_begin(BB)), PE(pred_end(BB)); 30 // Can't merge the entry block. 31 if (pred_begin(BB) == pred_end(BB)) return false; 32 33 BasicBlock *PredBB = *PI++; 34 for (; PI != PE; ++PI) // Search all predecessors, see if they are all same 35 if (*PI != PredBB) { 36 PredBB = 0; // There are multiple different predecessors... 37 break; 38 } 39 40 // Can't merge if there are multiple predecessors. 41 if (!PredBB) return false; 42 // Don't break self-loops. 43 if (PredBB == BB) return false; 44 // Don't break invokes. 45 if (isa<InvokeInst>(PredBB->getTerminator())) return false; 46 47 succ_iterator SI(succ_begin(PredBB)), SE(succ_end(PredBB)); 48 BasicBlock* OnlySucc = BB; 49 for (; SI != SE; ++SI) 50 if (*SI != OnlySucc) { 51 OnlySucc = 0; // There are multiple distinct successors! 52 break; 53 } 54 55 // Can't merge if there are multiple successors. 56 if (!OnlySucc) return false; 57 58 // Can't merge if there is PHI loop. 59 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE; ++BI) { 60 if (PHINode *PN = dyn_cast<PHINode>(BI)) { 61 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 62 if (PN->getIncomingValue(i) == PN) 63 return false; 64 } else 65 break; 66 } 67 68 // Begin by getting rid of unneeded PHIs. 69 while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { 70 PN->replaceAllUsesWith(PN->getIncomingValue(0)); 71 BB->getInstList().pop_front(); // Delete the phi node... 72 } 73 74 // Delete the unconditional branch from the predecessor... 75 PredBB->getInstList().pop_back(); 76 77 // Move all definitions in the successor to the predecessor... 78 PredBB->getInstList().splice(PredBB->end(), BB->getInstList()); 79 80 // Make all PHI nodes that referred to BB now refer to Pred as their 81 // source... 82 BB->replaceAllUsesWith(PredBB); 83 84 // Inherit predecessors name if it exists. 85 if (!PredBB->hasName()) 86 PredBB->takeName(BB); 87 88 // Finally, erase the old block and update dominator info. 89 if (P) { 90 if (DominatorTree* DT = P->getAnalysisToUpdate<DominatorTree>()) { 91 DomTreeNode* DTN = DT->getNode(BB); 92 DomTreeNode* PredDTN = DT->getNode(PredBB); 93 94 if (DTN) { 95 SmallPtrSet<DomTreeNode*, 8> Children(DTN->begin(), DTN->end()); 96 for (SmallPtrSet<DomTreeNode*, 8>::iterator DI = Children.begin(), 97 DE = Children.end(); DI != DE; ++DI) 98 DT->changeImmediateDominator(*DI, PredDTN); 99 100 DT->eraseNode(BB); 101 } 102 } 103 } 104 105 BB->eraseFromParent(); 106 107 108 return true; 109} 110 111/// ReplaceInstWithValue - Replace all uses of an instruction (specified by BI) 112/// with a value, then remove and delete the original instruction. 113/// 114void llvm::ReplaceInstWithValue(BasicBlock::InstListType &BIL, 115 BasicBlock::iterator &BI, Value *V) { 116 Instruction &I = *BI; 117 // Replaces all of the uses of the instruction with uses of the value 118 I.replaceAllUsesWith(V); 119 120 // Make sure to propagate a name if there is one already. 121 if (I.hasName() && !V->hasName()) 122 V->takeName(&I); 123 124 // Delete the unnecessary instruction now... 125 BI = BIL.erase(BI); 126} 127 128 129/// ReplaceInstWithInst - Replace the instruction specified by BI with the 130/// instruction specified by I. The original instruction is deleted and BI is 131/// updated to point to the new instruction. 132/// 133void llvm::ReplaceInstWithInst(BasicBlock::InstListType &BIL, 134 BasicBlock::iterator &BI, Instruction *I) { 135 assert(I->getParent() == 0 && 136 "ReplaceInstWithInst: Instruction already inserted into basic block!"); 137 138 // Insert the new instruction into the basic block... 139 BasicBlock::iterator New = BIL.insert(BI, I); 140 141 // Replace all uses of the old instruction, and delete it. 142 ReplaceInstWithValue(BIL, BI, I); 143 144 // Move BI back to point to the newly inserted instruction 145 BI = New; 146} 147 148/// ReplaceInstWithInst - Replace the instruction specified by From with the 149/// instruction specified by To. 150/// 151void llvm::ReplaceInstWithInst(Instruction *From, Instruction *To) { 152 BasicBlock::iterator BI(From); 153 ReplaceInstWithInst(From->getParent()->getInstList(), BI, To); 154} 155 156/// RemoveSuccessor - Change the specified terminator instruction such that its 157/// successor SuccNum no longer exists. Because this reduces the outgoing 158/// degree of the current basic block, the actual terminator instruction itself 159/// may have to be changed. In the case where the last successor of the block 160/// is deleted, a return instruction is inserted in its place which can cause a 161/// surprising change in program behavior if it is not expected. 162/// 163void llvm::RemoveSuccessor(TerminatorInst *TI, unsigned SuccNum) { 164 assert(SuccNum < TI->getNumSuccessors() && 165 "Trying to remove a nonexistant successor!"); 166 167 // If our old successor block contains any PHI nodes, remove the entry in the 168 // PHI nodes that comes from this branch... 169 // 170 BasicBlock *BB = TI->getParent(); 171 TI->getSuccessor(SuccNum)->removePredecessor(BB); 172 173 TerminatorInst *NewTI = 0; 174 switch (TI->getOpcode()) { 175 case Instruction::Br: 176 // If this is a conditional branch... convert to unconditional branch. 177 if (TI->getNumSuccessors() == 2) { 178 cast<BranchInst>(TI)->setUnconditionalDest(TI->getSuccessor(1-SuccNum)); 179 } else { // Otherwise convert to a return instruction... 180 Value *RetVal = 0; 181 182 // Create a value to return... if the function doesn't return null... 183 if (BB->getParent()->getReturnType() != Type::VoidTy) 184 RetVal = Constant::getNullValue(BB->getParent()->getReturnType()); 185 186 // Create the return... 187 NewTI = ReturnInst::Create(RetVal); 188 } 189 break; 190 191 case Instruction::Invoke: // Should convert to call 192 case Instruction::Switch: // Should remove entry 193 default: 194 case Instruction::Ret: // Cannot happen, has no successors! 195 assert(0 && "Unhandled terminator instruction type in RemoveSuccessor!"); 196 abort(); 197 } 198 199 if (NewTI) // If it's a different instruction, replace. 200 ReplaceInstWithInst(TI, NewTI); 201} 202 203/// SplitEdge - Split the edge connecting specified block. Pass P must 204/// not be NULL. 205BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, Pass *P) { 206 TerminatorInst *LatchTerm = BB->getTerminator(); 207 unsigned SuccNum = 0; 208#ifndef NDEBUG 209 unsigned e = LatchTerm->getNumSuccessors(); 210#endif 211 for (unsigned i = 0; ; ++i) { 212 assert(i != e && "Didn't find edge?"); 213 if (LatchTerm->getSuccessor(i) == Succ) { 214 SuccNum = i; 215 break; 216 } 217 } 218 219 // If this is a critical edge, let SplitCriticalEdge do it. 220 if (SplitCriticalEdge(BB->getTerminator(), SuccNum, P)) 221 return LatchTerm->getSuccessor(SuccNum); 222 223 // If the edge isn't critical, then BB has a single successor or Succ has a 224 // single pred. Split the block. 225 BasicBlock::iterator SplitPoint; 226 if (BasicBlock *SP = Succ->getSinglePredecessor()) { 227 // If the successor only has a single pred, split the top of the successor 228 // block. 229 assert(SP == BB && "CFG broken"); 230 SP = NULL; 231 return SplitBlock(Succ, Succ->begin(), P); 232 } else { 233 // Otherwise, if BB has a single successor, split it at the bottom of the 234 // block. 235 assert(BB->getTerminator()->getNumSuccessors() == 1 && 236 "Should have a single succ!"); 237 return SplitBlock(BB, BB->getTerminator(), P); 238 } 239} 240 241/// SplitBlock - Split the specified block at the specified instruction - every 242/// thing before SplitPt stays in Old and everything starting with SplitPt moves 243/// to a new block. The two blocks are joined by an unconditional branch and 244/// the loop info is updated. 245/// 246BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, Pass *P) { 247 BasicBlock::iterator SplitIt = SplitPt; 248 while (isa<PHINode>(SplitIt)) 249 ++SplitIt; 250 BasicBlock *New = Old->splitBasicBlock(SplitIt, Old->getName()+".split"); 251 252 // The new block lives in whichever loop the old one did. 253 if (LoopInfo* LI = P->getAnalysisToUpdate<LoopInfo>()) 254 if (Loop *L = LI->getLoopFor(Old)) 255 L->addBasicBlockToLoop(New, LI->getBase()); 256 257 if (DominatorTree *DT = P->getAnalysisToUpdate<DominatorTree>()) 258 { 259 // Old dominates New. New node domiantes all other nodes dominated by Old. 260 DomTreeNode *OldNode = DT->getNode(Old); 261 std::vector<DomTreeNode *> Children; 262 for (DomTreeNode::iterator I = OldNode->begin(), E = OldNode->end(); 263 I != E; ++I) 264 Children.push_back(*I); 265 266 DomTreeNode *NewNode = DT->addNewBlock(New,Old); 267 268 for (std::vector<DomTreeNode *>::iterator I = Children.begin(), 269 E = Children.end(); I != E; ++I) 270 DT->changeImmediateDominator(*I, NewNode); 271 } 272 273 if (DominanceFrontier *DF = P->getAnalysisToUpdate<DominanceFrontier>()) 274 DF->splitBlock(Old); 275 276 return New; 277} 278 279 280/// SplitBlockPredecessors - This method transforms BB by introducing a new 281/// basic block into the function, and moving some of the predecessors of BB to 282/// be predecessors of the new block. The new predecessors are indicated by the 283/// Preds array, which has NumPreds elements in it. The new block is given a 284/// suffix of 'Suffix'. 285/// 286/// This currently updates the LLVM IR, AliasAnalysis, DominatorTree and 287/// DominanceFrontier, but no other analyses. 288BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, 289 BasicBlock *const *Preds, 290 unsigned NumPreds, const char *Suffix, 291 Pass *P) { 292 // Create new basic block, insert right before the original block. 293 BasicBlock *NewBB = 294 BasicBlock::Create(BB->getName()+Suffix, BB->getParent(), BB); 295 296 // The new block unconditionally branches to the old block. 297 BranchInst *BI = BranchInst::Create(BB, NewBB); 298 299 // Move the edges from Preds to point to NewBB instead of BB. 300 for (unsigned i = 0; i != NumPreds; ++i) 301 Preds[i]->getTerminator()->replaceUsesOfWith(BB, NewBB); 302 303 // Update dominator tree and dominator frontier if available. 304 DominatorTree *DT = P ? P->getAnalysisToUpdate<DominatorTree>() : 0; 305 if (DT) 306 DT->splitBlock(NewBB); 307 if (DominanceFrontier *DF = P ? P->getAnalysisToUpdate<DominanceFrontier>():0) 308 DF->splitBlock(NewBB); 309 AliasAnalysis *AA = P ? P->getAnalysisToUpdate<AliasAnalysis>() : 0; 310 311 312 // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI 313 // node becomes an incoming value for BB's phi node. However, if the Preds 314 // list is empty, we need to insert dummy entries into the PHI nodes in BB to 315 // account for the newly created predecessor. 316 if (NumPreds == 0) { 317 // Insert dummy values as the incoming value. 318 for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I) 319 cast<PHINode>(I)->addIncoming(UndefValue::get(I->getType()), NewBB); 320 return NewBB; 321 } 322 323 // Otherwise, create a new PHI node in NewBB for each PHI node in BB. 324 for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ) { 325 PHINode *PN = cast<PHINode>(I++); 326 327 // Check to see if all of the values coming in are the same. If so, we 328 // don't need to create a new PHI node. 329 Value *InVal = PN->getIncomingValueForBlock(Preds[0]); 330 for (unsigned i = 1; i != NumPreds; ++i) 331 if (InVal != PN->getIncomingValueForBlock(Preds[i])) { 332 InVal = 0; 333 break; 334 } 335 336 if (InVal) { 337 // If all incoming values for the new PHI would be the same, just don't 338 // make a new PHI. Instead, just remove the incoming values from the old 339 // PHI. 340 for (unsigned i = 0; i != NumPreds; ++i) 341 PN->removeIncomingValue(Preds[i], false); 342 } else { 343 // If the values coming into the block are not the same, we need a PHI. 344 // Create the new PHI node, insert it into NewBB at the end of the block 345 PHINode *NewPHI = 346 PHINode::Create(PN->getType(), PN->getName()+".ph", BI); 347 if (AA) AA->copyValue(PN, NewPHI); 348 349 // Move all of the PHI values for 'Preds' to the new PHI. 350 for (unsigned i = 0; i != NumPreds; ++i) { 351 Value *V = PN->removeIncomingValue(Preds[i], false); 352 NewPHI->addIncoming(V, Preds[i]); 353 } 354 InVal = NewPHI; 355 } 356 357 // Add an incoming value to the PHI node in the loop for the preheader 358 // edge. 359 PN->addIncoming(InVal, NewBB); 360 361 // Check to see if we can eliminate this phi node. 362 if (Value *V = PN->hasConstantValue(DT != 0)) { 363 Instruction *I = dyn_cast<Instruction>(V); 364 if (!I || DT == 0 || DT->dominates(I, PN)) { 365 PN->replaceAllUsesWith(V); 366 if (AA) AA->deleteValue(PN); 367 PN->eraseFromParent(); 368 } 369 } 370 } 371 372 return NewBB; 373} 374 375/// FindAvailableLoadedValue - Scan the ScanBB block backwards (starting at the 376/// instruction before ScanFrom) checking to see if we have the value at the 377/// memory address *Ptr locally available within a small number of instructions. 378/// If the value is available, return it. 379/// 380/// If not, return the iterator for the last validated instruction that the 381/// value would be live through. If we scanned the entire block and didn't find 382/// something that invalidates *Ptr or provides it, ScanFrom would be left at 383/// begin() and this returns null. ScanFrom could also be left 384/// 385/// MaxInstsToScan specifies the maximum instructions to scan in the block. If 386/// it is set to 0, it will scan the whole block. You can also optionally 387/// specify an alias analysis implementation, which makes this more precise. 388Value *llvm::FindAvailableLoadedValue(Value *Ptr, BasicBlock *ScanBB, 389 BasicBlock::iterator &ScanFrom, 390 unsigned MaxInstsToScan, 391 AliasAnalysis *AA) { 392 if (MaxInstsToScan == 0) MaxInstsToScan = ~0U; 393 394 while (ScanFrom != ScanBB->begin()) { 395 // Don't scan huge blocks. 396 if (MaxInstsToScan-- == 0) return 0; 397 398 Instruction *Inst = --ScanFrom; 399 400 // If this is a load of Ptr, the loaded value is available. 401 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) 402 if (LI->getOperand(0) == Ptr) 403 return LI; 404 405 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 406 // If this is a store through Ptr, the value is available! 407 if (SI->getOperand(1) == Ptr) 408 return SI->getOperand(0); 409 410 // If Ptr is an alloca and this is a store to a different alloca, ignore 411 // the store. This is a trivial form of alias analysis that is important 412 // for reg2mem'd code. 413 if ((isa<AllocaInst>(Ptr) || isa<GlobalVariable>(Ptr)) && 414 (isa<AllocaInst>(SI->getOperand(1)) || 415 isa<GlobalVariable>(SI->getOperand(1)))) 416 continue; 417 418 // Otherwise the store that may or may not alias the pointer, bail out. 419 ++ScanFrom; 420 return 0; 421 } 422 423 424 // If this is some other instruction that may clobber Ptr, bail out. 425 if (Inst->mayWriteToMemory()) { 426 // May modify the pointer, bail out. 427 ++ScanFrom; 428 return 0; 429 } 430 } 431 432 // Got to the start of the block, we didn't find it, but are done for this 433 // block. 434 return 0; 435} 436