SimplifyCFG.cpp revision dc3602bf0d27aac80e08ef8823967850acd05a14
1//===- SimplifyCFG.cpp - Code to perform CFG simplification ---------------===// 2// 3// Peephole optimize the CFG. 4// 5//===----------------------------------------------------------------------===// 6 7#include "llvm/Transforms/Utils/Local.h" 8#include "llvm/Constant.h" 9#include "llvm/Intrinsics.h" 10#include "llvm/iPHINode.h" 11#include "llvm/iTerminators.h" 12#include "llvm/iOther.h" 13#include "llvm/Support/CFG.h" 14#include <algorithm> 15#include <functional> 16 17// PropagatePredecessors - This gets "Succ" ready to have the predecessors from 18// "BB". This is a little tricky because "Succ" has PHI nodes, which need to 19// have extra slots added to them to hold the merge edges from BB's 20// predecessors, and BB itself might have had PHI nodes in it. This function 21// returns true (failure) if the Succ BB already has a predecessor that is a 22// predecessor of BB and incoming PHI arguments would not be discernable. 23// 24// Assumption: Succ is the single successor for BB. 25// 26static bool PropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { 27 assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); 28 29 if (!isa<PHINode>(Succ->front())) 30 return false; // We can make the transformation, no problem. 31 32 // If there is more than one predecessor, and there are PHI nodes in 33 // the successor, then we need to add incoming edges for the PHI nodes 34 // 35 const std::vector<BasicBlock*> BBPreds(pred_begin(BB), pred_end(BB)); 36 37 // Check to see if one of the predecessors of BB is already a predecessor of 38 // Succ. If so, we cannot do the transformation if there are any PHI nodes 39 // with incompatible values coming in from the two edges! 40 // 41 for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ); PI != PE; ++PI) 42 if (find(BBPreds.begin(), BBPreds.end(), *PI) != BBPreds.end()) { 43 // Loop over all of the PHI nodes checking to see if there are 44 // incompatible values coming in. 45 for (BasicBlock::iterator I = Succ->begin(); 46 PHINode *PN = dyn_cast<PHINode>(I); ++I) { 47 // Loop up the entries in the PHI node for BB and for *PI if the values 48 // coming in are non-equal, we cannot merge these two blocks (instead we 49 // should insert a conditional move or something, then merge the 50 // blocks). 51 int Idx1 = PN->getBasicBlockIndex(BB); 52 int Idx2 = PN->getBasicBlockIndex(*PI); 53 assert(Idx1 != -1 && Idx2 != -1 && 54 "Didn't have entries for my predecessors??"); 55 if (PN->getIncomingValue(Idx1) != PN->getIncomingValue(Idx2)) 56 return true; // Values are not equal... 57 } 58 } 59 60 // Loop over all of the PHI nodes in the successor BB 61 for (BasicBlock::iterator I = Succ->begin(); 62 PHINode *PN = dyn_cast<PHINode>(I); ++I) { 63 Value *OldVal = PN->removeIncomingValue(BB, false); 64 assert(OldVal && "No entry in PHI for Pred BB!"); 65 66 // If this incoming value is one of the PHI nodes in BB... 67 if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) { 68 PHINode *OldValPN = cast<PHINode>(OldVal); 69 for (std::vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(), 70 End = BBPreds.end(); PredI != End; ++PredI) { 71 PN->addIncoming(OldValPN->getIncomingValueForBlock(*PredI), *PredI); 72 } 73 } else { 74 for (std::vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(), 75 End = BBPreds.end(); PredI != End; ++PredI) { 76 // Add an incoming value for each of the new incoming values... 77 PN->addIncoming(OldVal, *PredI); 78 } 79 } 80 } 81 return false; 82} 83 84 85// SimplifyCFG - This function is used to do simplification of a CFG. For 86// example, it adjusts branches to branches to eliminate the extra hop, it 87// eliminates unreachable basic blocks, and does other "peephole" optimization 88// of the CFG. It returns true if a modification was made. 89// 90// WARNING: The entry node of a function may not be simplified. 91// 92bool SimplifyCFG(BasicBlock *BB) { 93 bool Changed = false; 94 Function *M = BB->getParent(); 95 96 assert(BB && BB->getParent() && "Block not embedded in function!"); 97 assert(BB->getTerminator() && "Degenerate basic block encountered!"); 98 assert(&BB->getParent()->front() != BB && "Can't Simplify entry block!"); 99 100 // Check to see if the first instruction in this block is just an 101 // 'llvm.unwind'. If so, replace any invoke instructions which use this as an 102 // exception destination with call instructions. 103 // 104 if (CallInst *CI = dyn_cast<CallInst>(&BB->front())) 105 if (Function *F = CI->getCalledFunction()) 106 if (F->getIntrinsicID() == LLVMIntrinsic::unwind) { 107 std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB)); 108 while (!Preds.empty()) { 109 BasicBlock *Pred = Preds.back(); 110 if (InvokeInst *II = dyn_cast<InvokeInst>(Pred->getTerminator())) 111 if (II->getExceptionalDest() == BB) { 112 // Insert a new branch instruction before the invoke, because this 113 // is now a fall through... 114 BranchInst *BI = new BranchInst(II->getNormalDest(), II); 115 Pred->getInstList().remove(II); // Take out of symbol table 116 117 // Insert the call now... 118 std::vector<Value*> Args(II->op_begin()+3, II->op_end()); 119 CallInst *CI = new CallInst(II->getCalledValue(), Args, 120 II->getName(), BI); 121 // If the invoke produced a value, the Call now does instead 122 II->replaceAllUsesWith(CI); 123 delete II; 124 Changed = true; 125 } 126 127 Preds.pop_back(); 128 } 129 } 130 131 // Remove basic blocks that have no predecessors... which are unreachable. 132 if (pred_begin(BB) == pred_end(BB) && 133 !BB->hasConstantReferences()) { 134 //cerr << "Removing BB: \n" << BB; 135 136 // Loop through all of our successors and make sure they know that one 137 // of their predecessors is going away. 138 for_each(succ_begin(BB), succ_end(BB), 139 std::bind2nd(std::mem_fun(&BasicBlock::removePredecessor), BB)); 140 141 while (!BB->empty()) { 142 Instruction &I = BB->back(); 143 // If this instruction is used, replace uses with an arbitrary 144 // constant value. Because control flow can't get here, we don't care 145 // what we replace the value with. Note that since this block is 146 // unreachable, and all values contained within it must dominate their 147 // uses, that all uses will eventually be removed. 148 if (!I.use_empty()) 149 // Make all users of this instruction reference the constant instead 150 I.replaceAllUsesWith(Constant::getNullValue(I.getType())); 151 152 // Remove the instruction from the basic block 153 BB->getInstList().pop_back(); 154 } 155 M->getBasicBlockList().erase(BB); 156 return true; 157 } 158 159 // Check to see if we can constant propagate this terminator instruction 160 // away... 161 Changed |= ConstantFoldTerminator(BB); 162 163 // Check to see if this block has no non-phi instructions and only a single 164 // successor. If so, replace references to this basic block with references 165 // to the successor. 166 succ_iterator SI(succ_begin(BB)); 167 if (SI != succ_end(BB) && ++SI == succ_end(BB)) { // One succ? 168 169 BasicBlock::iterator BBI = BB->begin(); // Skip over phi nodes... 170 while (isa<PHINode>(*BBI)) ++BBI; 171 172 if (BBI->isTerminator()) { // Terminator is the only non-phi instruction! 173 BasicBlock *Succ = *succ_begin(BB); // There is exactly one successor 174 175 if (Succ != BB) { // Arg, don't hurt infinite loops! 176 // If our successor has PHI nodes, then we need to update them to 177 // include entries for BB's predecessors, not for BB itself. 178 // Be careful though, if this transformation fails (returns true) then 179 // we cannot do this transformation! 180 // 181 if (!PropagatePredecessorsForPHIs(BB, Succ)) { 182 //cerr << "Killing Trivial BB: \n" << BB; 183 std::string OldName = BB->getName(); 184 185 std::vector<BasicBlock*> 186 OldSuccPreds(pred_begin(Succ), pred_end(Succ)); 187 188 // Move all PHI nodes in BB to Succ if they are alive, otherwise 189 // delete them. 190 while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) 191 if (PN->use_empty()) 192 BB->getInstList().erase(BB->begin()); // Nuke instruction... 193 else { 194 // The instruction is alive, so this means that Succ must have 195 // *ONLY* had BB as a predecessor, and the PHI node is still valid 196 // now. Simply move it into Succ, because we know that BB 197 // strictly dominated Succ. 198 BB->getInstList().remove(BB->begin()); 199 Succ->getInstList().push_front(PN); 200 201 // We need to add new entries for the PHI node to account for 202 // predecessors of Succ that the PHI node does not take into 203 // account. At this point, since we know that BB dominated succ, 204 // this means that we should any newly added incoming edges should 205 // use the PHI node as the value for these edges, because they are 206 // loop back edges. 207 208 for (unsigned i = 0, e = OldSuccPreds.size(); i != e; ++i) 209 if (OldSuccPreds[i] != BB) 210 PN->addIncoming(PN, OldSuccPreds[i]); 211 } 212 213 // Everything that jumped to BB now goes to Succ... 214 BB->replaceAllUsesWith(Succ); 215 216 // Delete the old basic block... 217 M->getBasicBlockList().erase(BB); 218 219 if (!OldName.empty() && !Succ->hasName()) // Transfer name if we can 220 Succ->setName(OldName); 221 222 //cerr << "Function after removal: \n" << M; 223 return true; 224 } 225 } 226 } 227 } 228 229 // Merge basic blocks into their predecessor if there is only one distinct 230 // pred, and if there is only one distinct successor of the predecessor, and 231 // if there are no PHI nodes. 232 // 233 if (!BB->hasConstantReferences()) { 234 pred_iterator PI(pred_begin(BB)), PE(pred_end(BB)); 235 BasicBlock *OnlyPred = *PI++; 236 for (; PI != PE; ++PI) // Search all predecessors, see if they are all same 237 if (*PI != OnlyPred) { 238 OnlyPred = 0; // There are multiple different predecessors... 239 break; 240 } 241 242 BasicBlock *OnlySucc = 0; 243 if (OnlyPred && OnlyPred != BB && // Don't break self loops 244 OnlyPred->getTerminator()->getOpcode() != Instruction::Invoke) { 245 // Check to see if there is only one distinct successor... 246 succ_iterator SI(succ_begin(OnlyPred)), SE(succ_end(OnlyPred)); 247 OnlySucc = BB; 248 for (; SI != SE; ++SI) 249 if (*SI != OnlySucc) { 250 OnlySucc = 0; // There are multiple distinct successors! 251 break; 252 } 253 } 254 255 if (OnlySucc) { 256 //cerr << "Merging: " << BB << "into: " << OnlyPred; 257 TerminatorInst *Term = OnlyPred->getTerminator(); 258 259 // Resolve any PHI nodes at the start of the block. They are all 260 // guaranteed to have exactly one entry if they exist, unless there are 261 // multiple duplicate (but guaranteed to be equal) entries for the 262 // incoming edges. This occurs when there are multiple edges from 263 // OnlyPred to OnlySucc. 264 // 265 while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { 266 PN->replaceAllUsesWith(PN->getIncomingValue(0)); 267 BB->getInstList().pop_front(); // Delete the phi node... 268 } 269 270 // Delete the unconditional branch from the predecessor... 271 OnlyPred->getInstList().pop_back(); 272 273 // Move all definitions in the succecessor to the predecessor... 274 OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList()); 275 276 // Make all PHI nodes that refered to BB now refer to Pred as their 277 // source... 278 BB->replaceAllUsesWith(OnlyPred); 279 280 std::string OldName = BB->getName(); 281 282 // Erase basic block from the function... 283 M->getBasicBlockList().erase(BB); 284 285 // Inherit predecessors name if it exists... 286 if (!OldName.empty() && !OnlyPred->hasName()) 287 OnlyPred->setName(OldName); 288 289 return true; 290 } 291 } 292 293 return Changed; 294} 295