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