1 //===-- BasicBlockUtils.cpp - BasicBlock Utilities -------------------------==//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This family of functions perform manipulations on basic blocks, and
11 // instructions contained within basic blocks.
13 //===----------------------------------------------------------------------===//
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/LoopInfo.h"
21 #include "llvm/Analysis/Dominators.h"
25 /// ReplaceInstWithValue - Replace all uses of an instruction (specified by BI)
26 /// with a value, then remove and delete the original instruction.
28 void llvm::ReplaceInstWithValue(BasicBlock::InstListType &BIL,
29 BasicBlock::iterator &BI, Value *V) {
31 // Replaces all of the uses of the instruction with uses of the value
32 I.replaceAllUsesWith(V);
34 // Make sure to propagate a name if there is one already.
35 if (I.hasName() && !V->hasName())
38 // Delete the unnecessary instruction now...
43 /// ReplaceInstWithInst - Replace the instruction specified by BI with the
44 /// instruction specified by I. The original instruction is deleted and BI is
45 /// updated to point to the new instruction.
47 void llvm::ReplaceInstWithInst(BasicBlock::InstListType &BIL,
48 BasicBlock::iterator &BI, Instruction *I) {
49 assert(I->getParent() == 0 &&
50 "ReplaceInstWithInst: Instruction already inserted into basic block!");
52 // Insert the new instruction into the basic block...
53 BasicBlock::iterator New = BIL.insert(BI, I);
55 // Replace all uses of the old instruction, and delete it.
56 ReplaceInstWithValue(BIL, BI, I);
58 // Move BI back to point to the newly inserted instruction
62 /// ReplaceInstWithInst - Replace the instruction specified by From with the
63 /// instruction specified by To.
65 void llvm::ReplaceInstWithInst(Instruction *From, Instruction *To) {
66 BasicBlock::iterator BI(From);
67 ReplaceInstWithInst(From->getParent()->getInstList(), BI, To);
70 /// RemoveSuccessor - Change the specified terminator instruction such that its
71 /// successor SuccNum no longer exists. Because this reduces the outgoing
72 /// degree of the current basic block, the actual terminator instruction itself
73 /// may have to be changed. In the case where the last successor of the block
74 /// is deleted, a return instruction is inserted in its place which can cause a
75 /// surprising change in program behavior if it is not expected.
77 void llvm::RemoveSuccessor(TerminatorInst *TI, unsigned SuccNum) {
78 assert(SuccNum < TI->getNumSuccessors() &&
79 "Trying to remove a nonexistant successor!");
81 // If our old successor block contains any PHI nodes, remove the entry in the
82 // PHI nodes that comes from this branch...
84 BasicBlock *BB = TI->getParent();
85 TI->getSuccessor(SuccNum)->removePredecessor(BB);
87 TerminatorInst *NewTI = 0;
88 switch (TI->getOpcode()) {
90 // If this is a conditional branch... convert to unconditional branch.
91 if (TI->getNumSuccessors() == 2) {
92 cast<BranchInst>(TI)->setUnconditionalDest(TI->getSuccessor(1-SuccNum));
93 } else { // Otherwise convert to a return instruction...
96 // Create a value to return... if the function doesn't return null...
97 if (BB->getParent()->getReturnType() != Type::VoidTy)
98 RetVal = Constant::getNullValue(BB->getParent()->getReturnType());
100 // Create the return...
101 NewTI = new ReturnInst(RetVal);
105 case Instruction::Invoke: // Should convert to call
106 case Instruction::Switch: // Should remove entry
108 case Instruction::Ret: // Cannot happen, has no successors!
109 assert(0 && "Unhandled terminator instruction type in RemoveSuccessor!");
113 if (NewTI) // If it's a different instruction, replace.
114 ReplaceInstWithInst(TI, NewTI);
117 /// SplitEdge - Split the edge connecting specified block. Pass P must
119 BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, Pass *P) {
120 TerminatorInst *LatchTerm = BB->getTerminator();
121 unsigned SuccNum = 0;
122 for (unsigned i = 0, e = LatchTerm->getNumSuccessors(); ; ++i) {
123 assert(i != e && "Didn't find edge?");
124 if (LatchTerm->getSuccessor(i) == Succ) {
130 // If this is a critical edge, let SplitCriticalEdge do it.
131 if (SplitCriticalEdge(BB->getTerminator(), SuccNum, P))
132 return LatchTerm->getSuccessor(SuccNum);
134 // If the edge isn't critical, then BB has a single successor or Succ has a
135 // single pred. Split the block.
136 BasicBlock::iterator SplitPoint;
137 if (BasicBlock *SP = Succ->getSinglePredecessor()) {
138 // If the successor only has a single pred, split the top of the successor
140 assert(SP == BB && "CFG broken");
141 return SplitBlock(Succ, Succ->begin(), P);
143 // Otherwise, if BB has a single successor, split it at the bottom of the
145 assert(BB->getTerminator()->getNumSuccessors() == 1 &&
146 "Should have a single succ!");
147 return SplitBlock(BB, BB->getTerminator(), P);
151 /// SplitBlock - Split the specified block at the specified instruction - every
152 /// thing before SplitPt stays in Old and everything starting with SplitPt moves
153 /// to a new block. The two blocks are joined by an unconditional branch and
154 /// the loop info is updated.
156 BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, Pass *P) {
158 LoopInfo &LI = P->getAnalysis<LoopInfo>();
159 BasicBlock::iterator SplitIt = SplitPt;
160 while (isa<PHINode>(SplitIt))
162 BasicBlock *New = Old->splitBasicBlock(SplitIt, Old->getName()+".split");
164 // The new block lives in whichever loop the old one did.
165 if (Loop *L = LI.getLoopFor(Old))
166 L->addBasicBlockToLoop(New, LI.getBase());
168 if (DominatorTree *DT = P->getAnalysisToUpdate<DominatorTree>())
170 // Old dominates New. New node domiantes all other nodes dominated by Old.
171 DomTreeNode *OldNode = DT->getNode(Old);
172 std::vector<DomTreeNode *> Children;
173 for (DomTreeNode::iterator I = OldNode->begin(), E = OldNode->end();
175 Children.push_back(*I);
177 DomTreeNode *NewNode = DT->addNewBlock(New,Old);
179 for (std::vector<DomTreeNode *>::iterator I = Children.begin(),
180 E = Children.end(); I != E; ++I)
181 DT->changeImmediateDominator(*I, NewNode);
184 if (DominanceFrontier *DF = P->getAnalysisToUpdate<DominanceFrontier>())