LLVM API Documentation
00001 //===-- BasicBlock.cpp - Implement BasicBlock related methods -------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements the BasicBlock class for the VMCore library. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #include "llvm/BasicBlock.h" 00015 #include "llvm/Constants.h" 00016 #include "llvm/Instructions.h" 00017 #include "llvm/LLVMContext.h" 00018 #include "llvm/Type.h" 00019 #include "llvm/ADT/STLExtras.h" 00020 #include "llvm/Support/CFG.h" 00021 #include "llvm/Support/LeakDetector.h" 00022 #include "SymbolTableListTraitsImpl.h" 00023 #include <algorithm> 00024 using namespace llvm; 00025 00026 ValueSymbolTable *BasicBlock::getValueSymbolTable() { 00027 if (Function *F = getParent()) 00028 return &F->getValueSymbolTable(); 00029 return 0; 00030 } 00031 00032 LLVMContext &BasicBlock::getContext() const { 00033 return getType()->getContext(); 00034 } 00035 00036 // Explicit instantiation of SymbolTableListTraits since some of the methods 00037 // are not in the public header file... 00038 template class SymbolTableListTraits<Instruction, BasicBlock>; 00039 00040 00041 BasicBlock::BasicBlock(LLVMContext &C, const Twine &Name, Function *NewParent, 00042 BasicBlock *InsertBefore) 00043 : Value(Type::getLabelTy(C), Value::BasicBlockVal), Parent(0) { 00044 00045 // Make sure that we get added to a function 00046 LeakDetector::addGarbageObject(this); 00047 00048 if (InsertBefore) { 00049 assert(NewParent && 00050 "Cannot insert block before another block with no function!"); 00051 NewParent->getBasicBlockList().insert(InsertBefore, this); 00052 } else if (NewParent) { 00053 NewParent->getBasicBlockList().push_back(this); 00054 } 00055 00056 setName(Name); 00057 } 00058 00059 00060 BasicBlock::~BasicBlock() { 00061 assert(getParent() == 0 && "BasicBlock still linked into the program!"); 00062 dropAllReferences(); 00063 InstList.clear(); 00064 } 00065 00066 void BasicBlock::setParent(Function *parent) { 00067 if (getParent()) 00068 LeakDetector::addGarbageObject(this); 00069 00070 // Set Parent=parent, updating instruction symtab entries as appropriate. 00071 InstList.setSymTabObject(&Parent, parent); 00072 00073 if (getParent()) 00074 LeakDetector::removeGarbageObject(this); 00075 } 00076 00077 void BasicBlock::removeFromParent() { 00078 getParent()->getBasicBlockList().remove(this); 00079 } 00080 00081 void BasicBlock::eraseFromParent() { 00082 getParent()->getBasicBlockList().erase(this); 00083 } 00084 00085 /// moveBefore - Unlink this basic block from its current function and 00086 /// insert it into the function that MovePos lives in, right before MovePos. 00087 void BasicBlock::moveBefore(BasicBlock *MovePos) { 00088 MovePos->getParent()->getBasicBlockList().splice(MovePos, 00089 getParent()->getBasicBlockList(), this); 00090 } 00091 00092 /// moveAfter - Unlink this basic block from its current function and 00093 /// insert it into the function that MovePos lives in, right after MovePos. 00094 void BasicBlock::moveAfter(BasicBlock *MovePos) { 00095 Function::iterator I = MovePos; 00096 MovePos->getParent()->getBasicBlockList().splice(++I, 00097 getParent()->getBasicBlockList(), this); 00098 } 00099 00100 00101 TerminatorInst *BasicBlock::getTerminator() { 00102 if (InstList.empty()) return 0; 00103 return dyn_cast<TerminatorInst>(&InstList.back()); 00104 } 00105 00106 const TerminatorInst *BasicBlock::getTerminator() const { 00107 if (InstList.empty()) return 0; 00108 return dyn_cast<TerminatorInst>(&InstList.back()); 00109 } 00110 00111 Instruction* BasicBlock::getFirstNonPHI() { 00112 BasicBlock::iterator i = begin(); 00113 // All valid basic blocks should have a terminator, 00114 // which is not a PHINode. If we have an invalid basic 00115 // block we'll get an assertion failure when dereferencing 00116 // a past-the-end iterator. 00117 while (isa<PHINode>(i)) ++i; 00118 return &*i; 00119 } 00120 00121 void BasicBlock::dropAllReferences() { 00122 for(iterator I = begin(), E = end(); I != E; ++I) 00123 I->dropAllReferences(); 00124 } 00125 00126 /// getSinglePredecessor - If this basic block has a single predecessor block, 00127 /// return the block, otherwise return a null pointer. 00128 BasicBlock *BasicBlock::getSinglePredecessor() { 00129 pred_iterator PI = pred_begin(this), E = pred_end(this); 00130 if (PI == E) return 0; // No preds. 00131 BasicBlock *ThePred = *PI; 00132 ++PI; 00133 return (PI == E) ? ThePred : 0 /*multiple preds*/; 00134 } 00135 00136 /// getUniquePredecessor - If this basic block has a unique predecessor block, 00137 /// return the block, otherwise return a null pointer. 00138 /// Note that unique predecessor doesn't mean single edge, there can be 00139 /// multiple edges from the unique predecessor to this block (for example 00140 /// a switch statement with multiple cases having the same destination). 00141 BasicBlock *BasicBlock::getUniquePredecessor() { 00142 pred_iterator PI = pred_begin(this), E = pred_end(this); 00143 if (PI == E) return 0; // No preds. 00144 BasicBlock *PredBB = *PI; 00145 ++PI; 00146 for (;PI != E; ++PI) { 00147 if (*PI != PredBB) 00148 return 0; 00149 // The same predecessor appears multiple times in the predecessor list. 00150 // This is OK. 00151 } 00152 return PredBB; 00153 } 00154 00155 /// removePredecessor - This method is used to notify a BasicBlock that the 00156 /// specified Predecessor of the block is no longer able to reach it. This is 00157 /// actually not used to update the Predecessor list, but is actually used to 00158 /// update the PHI nodes that reside in the block. Note that this should be 00159 /// called while the predecessor still refers to this block. 00160 /// 00161 void BasicBlock::removePredecessor(BasicBlock *Pred, 00162 bool DontDeleteUselessPHIs) { 00163 assert((hasNUsesOrMore(16)||// Reduce cost of this assertion for complex CFGs. 00164 find(pred_begin(this), pred_end(this), Pred) != pred_end(this)) && 00165 "removePredecessor: BB is not a predecessor!"); 00166 00167 if (InstList.empty()) return; 00168 PHINode *APN = dyn_cast<PHINode>(&front()); 00169 if (!APN) return; // Quick exit. 00170 00171 // If there are exactly two predecessors, then we want to nuke the PHI nodes 00172 // altogether. However, we cannot do this, if this in this case: 00173 // 00174 // Loop: 00175 // %x = phi [X, Loop] 00176 // %x2 = add %x, 1 ;; This would become %x2 = add %x2, 1 00177 // br Loop ;; %x2 does not dominate all uses 00178 // 00179 // This is because the PHI node input is actually taken from the predecessor 00180 // basic block. The only case this can happen is with a self loop, so we 00181 // check for this case explicitly now. 00182 // 00183 unsigned max_idx = APN->getNumIncomingValues(); 00184 assert(max_idx != 0 && "PHI Node in block with 0 predecessors!?!?!"); 00185 if (max_idx == 2) { 00186 BasicBlock *Other = APN->getIncomingBlock(APN->getIncomingBlock(0) == Pred); 00187 00188 // Disable PHI elimination! 00189 if (this == Other) max_idx = 3; 00190 } 00191 00192 // <= Two predecessors BEFORE I remove one? 00193 if (max_idx <= 2 && !DontDeleteUselessPHIs) { 00194 // Yup, loop through and nuke the PHI nodes 00195 while (PHINode *PN = dyn_cast<PHINode>(&front())) { 00196 // Remove the predecessor first. 00197 PN->removeIncomingValue(Pred, !DontDeleteUselessPHIs); 00198 00199 // If the PHI _HAD_ two uses, replace PHI node with its now *single* value 00200 if (max_idx == 2) { 00201 if (PN->getOperand(0) != PN) 00202 PN->replaceAllUsesWith(PN->getOperand(0)); 00203 else 00204 // We are left with an infinite loop with no entries: kill the PHI. 00205 PN->replaceAllUsesWith(UndefValue::get(PN->getType())); 00206 getInstList().pop_front(); // Remove the PHI node 00207 } 00208 00209 // If the PHI node already only had one entry, it got deleted by 00210 // removeIncomingValue. 00211 } 00212 } else { 00213 // Okay, now we know that we need to remove predecessor #pred_idx from all 00214 // PHI nodes. Iterate over each PHI node fixing them up 00215 PHINode *PN; 00216 for (iterator II = begin(); (PN = dyn_cast<PHINode>(II)); ) { 00217 ++II; 00218 PN->removeIncomingValue(Pred, false); 00219 // If all incoming values to the Phi are the same, we can replace the Phi 00220 // with that value. 00221 Value* PNV = 0; 00222 if (!DontDeleteUselessPHIs && (PNV = PN->hasConstantValue())) { 00223 PN->replaceAllUsesWith(PNV); 00224 PN->eraseFromParent(); 00225 } 00226 } 00227 } 00228 } 00229 00230 00231 /// splitBasicBlock - This splits a basic block into two at the specified 00232 /// instruction. Note that all instructions BEFORE the specified iterator stay 00233 /// as part of the original basic block, an unconditional branch is added to 00234 /// the new BB, and the rest of the instructions in the BB are moved to the new 00235 /// BB, including the old terminator. This invalidates the iterator. 00236 /// 00237 /// Note that this only works on well formed basic blocks (must have a 00238 /// terminator), and 'I' must not be the end of instruction list (which would 00239 /// cause a degenerate basic block to be formed, having a terminator inside of 00240 /// the basic block). 00241 /// 00242 BasicBlock *BasicBlock::splitBasicBlock(iterator I, const Twine &BBName) { 00243 assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!"); 00244 assert(I != InstList.end() && 00245 "Trying to get me to create degenerate basic block!"); 00246 00247 BasicBlock *InsertBefore = next(Function::iterator(this)) 00248 .getNodePtrUnchecked(); 00249 BasicBlock *New = BasicBlock::Create(getContext(), BBName, 00250 getParent(), InsertBefore); 00251 00252 // Move all of the specified instructions from the original basic block into 00253 // the new basic block. 00254 New->getInstList().splice(New->end(), this->getInstList(), I, end()); 00255 00256 // Add a branch instruction to the newly formed basic block. 00257 BranchInst::Create(New, this); 00258 00259 // Now we must loop through all of the successors of the New block (which 00260 // _were_ the successors of the 'this' block), and update any PHI nodes in 00261 // successors. If there were PHI nodes in the successors, then they need to 00262 // know that incoming branches will be from New, not from Old. 00263 // 00264 for (succ_iterator I = succ_begin(New), E = succ_end(New); I != E; ++I) { 00265 // Loop over any phi nodes in the basic block, updating the BB field of 00266 // incoming values... 00267 BasicBlock *Successor = *I; 00268 PHINode *PN; 00269 for (BasicBlock::iterator II = Successor->begin(); 00270 (PN = dyn_cast<PHINode>(II)); ++II) { 00271 int IDX = PN->getBasicBlockIndex(this); 00272 while (IDX != -1) { 00273 PN->setIncomingBlock((unsigned)IDX, New); 00274 IDX = PN->getBasicBlockIndex(this); 00275 } 00276 } 00277 } 00278 return New; 00279 }