LoopSimplify.cpp revision 9f879cfb0a93bf34818fb68e1dc209d47a7d24f3
1//===- LoopPreheaders.cpp - Loop Preheader Insertion Pass -----------------===// 2// 3// Insert Loop pre-headers and exit blocks into the CFG for each function in the 4// module. This pass updates loop information and dominator information. 5// 6// Loop pre-header insertion guarantees that there is a single, non-critical 7// entry edge from outside of the loop to the loop header. This simplifies a 8// number of analyses and transformations, such as LICM. 9// 10// Loop exit-block insertion guarantees that all exit blocks from the loop 11// (blocks which are outside of the loop that have predecessors inside of the 12// loop) are dominated by the loop header. This simplifies transformations such 13// as store-sinking that is built into LICM. 14// 15// Note that the simplifycfg pass will clean up blocks which are split out but 16// end up being unneccesary, so usage of this pass does not neccesarily 17// pessimize generated code. 18// 19//===----------------------------------------------------------------------===// 20 21#include "llvm/Transforms/Scalar.h" 22#include "llvm/Analysis/Dominators.h" 23#include "llvm/Analysis/LoopInfo.h" 24#include "llvm/Function.h" 25#include "llvm/iTerminators.h" 26#include "llvm/iPHINode.h" 27#include "llvm/Constant.h" 28#include "llvm/Support/CFG.h" 29#include "Support/SetOperations.h" 30#include "Support/Statistic.h" 31 32namespace { 33 Statistic<> NumInserted("preheaders", "Number of pre-header nodes inserted"); 34 35 struct Preheaders : public FunctionPass { 36 virtual bool runOnFunction(Function &F); 37 38 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 39 // We need loop information to identify the loops... 40 AU.addRequired<LoopInfo>(); 41 AU.addRequired<DominatorSet>(); 42 43 AU.addPreserved<LoopInfo>(); 44 AU.addPreserved<DominatorSet>(); 45 AU.addPreserved<ImmediateDominators>(); 46 AU.addPreserved<DominatorTree>(); 47 AU.addPreserved<DominanceFrontier>(); 48 AU.addPreservedID(BreakCriticalEdgesID); // No crit edges added.... 49 } 50 private: 51 bool ProcessLoop(Loop *L); 52 BasicBlock *SplitBlockPredecessors(BasicBlock *BB, const char *Suffix, 53 const std::vector<BasicBlock*> &Preds); 54 void RewriteLoopExitBlock(Loop *L, BasicBlock *Exit); 55 void InsertPreheaderForLoop(Loop *L); 56 }; 57 58 RegisterOpt<Preheaders> X("preheaders", "Natural loop pre-header insertion"); 59} 60 61// Publically exposed interface to pass... 62const PassInfo *LoopPreheadersID = X.getPassInfo(); 63Pass *createLoopPreheaderInsertionPass() { return new Preheaders(); } 64 65 66/// runOnFunction - Run down all loops in the CFG (recursively, but we could do 67/// it in any convenient order) inserting preheaders... 68/// 69bool Preheaders::runOnFunction(Function &F) { 70 bool Changed = false; 71 LoopInfo &LI = getAnalysis<LoopInfo>(); 72 73 for (unsigned i = 0, e = LI.getTopLevelLoops().size(); i != e; ++i) 74 Changed |= ProcessLoop(LI.getTopLevelLoops()[i]); 75 76 return Changed; 77} 78 79 80/// ProcessLoop - Walk the loop structure in depth first order, ensuring that 81/// all loops have preheaders. 82/// 83bool Preheaders::ProcessLoop(Loop *L) { 84 bool Changed = false; 85 86 // Does the loop already have a preheader? If so, don't modify the loop... 87 if (L->getLoopPreheader() == 0) { 88 InsertPreheaderForLoop(L); 89 NumInserted++; 90 Changed = true; 91 } 92 93 DominatorSet &DS = getAnalysis<DominatorSet>(); 94 BasicBlock *Header = L->getHeader(); 95 for (unsigned i = 0, e = L->getExitBlocks().size(); i != e; ++i) 96 if (!DS.dominates(Header, L->getExitBlocks()[i])) { 97 RewriteLoopExitBlock(L, L->getExitBlocks()[i]); 98 assert(DS.dominates(Header, L->getExitBlocks()[i]) && 99 "RewriteLoopExitBlock failed?"); 100 NumInserted++; 101 Changed = true; 102 } 103 104 const std::vector<Loop*> &SubLoops = L->getSubLoops(); 105 for (unsigned i = 0, e = SubLoops.size(); i != e; ++i) 106 Changed |= ProcessLoop(SubLoops[i]); 107 return Changed; 108} 109 110/// SplitBlockPredecessors - Split the specified block into two blocks. We want 111/// to move the predecessors specified in the Preds list to point to the new 112/// block, leaving the remaining predecessors pointing to BB. This method 113/// updates the SSA PHINode's, but no other analyses. 114/// 115BasicBlock *Preheaders::SplitBlockPredecessors(BasicBlock *BB, 116 const char *Suffix, 117 const std::vector<BasicBlock*> &Preds) { 118 119 // Create new basic block, insert right before the original block... 120 BasicBlock *NewBB = new BasicBlock(BB->getName()+Suffix, BB); 121 122 // The preheader first gets an unconditional branch to the loop header... 123 BranchInst *BI = new BranchInst(BB); 124 NewBB->getInstList().push_back(BI); 125 126 // For every PHI node in the block, insert a PHI node into NewBB where the 127 // incoming values from the out of loop edges are moved to NewBB. We have two 128 // possible cases here. If the loop is dead, we just insert dummy entries 129 // into the PHI nodes for the new edge. If the loop is not dead, we move the 130 // incoming edges in BB into new PHI nodes in NewBB. 131 // 132 if (!Preds.empty()) { // Is the loop not obviously dead? 133 for (BasicBlock::iterator I = BB->begin(); 134 PHINode *PN = dyn_cast<PHINode>(&*I); ++I) { 135 136 // Create the new PHI node, insert it into NewBB at the end of the block 137 PHINode *NewPHI = new PHINode(PN->getType(), PN->getName()+".ph", BI); 138 139 // Move all of the edges from blocks outside the loop to the new PHI 140 for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 141 Value *V = PN->removeIncomingValue(Preds[i]); 142 NewPHI->addIncoming(V, Preds[i]); 143 } 144 145 // Add an incoming value to the PHI node in the loop for the preheader 146 // edge 147 PN->addIncoming(NewPHI, NewBB); 148 } 149 150 // Now that the PHI nodes are updated, actually move the edges from 151 // Preds to point to NewBB instead of BB. 152 // 153 for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 154 TerminatorInst *TI = Preds[i]->getTerminator(); 155 for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) 156 if (TI->getSuccessor(s) == BB) 157 TI->setSuccessor(s, NewBB); 158 } 159 160 } else { // Otherwise the loop is dead... 161 for (BasicBlock::iterator I = BB->begin(); 162 PHINode *PN = dyn_cast<PHINode>(&*I); ++I) 163 // Insert dummy values as the incoming value... 164 PN->addIncoming(Constant::getNullValue(PN->getType()), NewBB); 165 } 166 return NewBB; 167} 168 169 170/// InsertPreheaderForLoop - Once we discover that a loop doesn't have a 171/// preheader, this method is called to insert one. This method has two phases: 172/// preheader insertion and analysis updating. 173/// 174void Preheaders::InsertPreheaderForLoop(Loop *L) { 175 BasicBlock *Header = L->getHeader(); 176 177 // Compute the set of predecessors of the loop that are not in the loop. 178 std::vector<BasicBlock*> OutsideBlocks; 179 for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header); 180 PI != PE; ++PI) 181 if (!L->contains(*PI)) // Coming in from outside the loop? 182 OutsideBlocks.push_back(*PI); // Keep track of it... 183 184 // Split out the loop pre-header 185 BasicBlock *NewBB = 186 SplitBlockPredecessors(Header, ".preheader", OutsideBlocks); 187 188 //===--------------------------------------------------------------------===// 189 // Update analysis results now that we have preformed the transformation 190 // 191 192 // We know that we have loop information to update... update it now. 193 if (Loop *Parent = L->getParentLoop()) 194 Parent->addBasicBlockToLoop(NewBB, getAnalysis<LoopInfo>()); 195 196 // If the header for the loop used to be an exit node for another loop, then 197 // we need to update this to know that the loop-preheader is now the exit 198 // node. Note that the only loop that could have our header as an exit node 199 // is a sibling loop, ie, one with the same parent loop. 200 const std::vector<Loop*> *ParentSubLoops; 201 if (Loop *Parent = L->getParentLoop()) 202 ParentSubLoops = &Parent->getSubLoops(); 203 else // Must check top-level loops... 204 ParentSubLoops = &getAnalysis<LoopInfo>().getTopLevelLoops(); 205 206 // Loop over all sibling loops, performing the substitution... 207 for (unsigned i = 0, e = ParentSubLoops->size(); i != e; ++i) 208 if ((*ParentSubLoops)[i]->hasExitBlock(Header)) 209 (*ParentSubLoops)[i]->changeExitBlock(Header, NewBB); 210 211 212 DominatorSet &DS = getAnalysis<DominatorSet>(); // Update dominator info 213 { 214 // The blocks that dominate NewBB are the blocks that dominate Header, 215 // minus Header, plus NewBB. 216 DominatorSet::DomSetType DomSet = DS.getDominators(Header); 217 DomSet.insert(NewBB); // We dominate ourself 218 DomSet.erase(Header); // Header does not dominate us... 219 DS.addBasicBlock(NewBB, DomSet); 220 221 // The newly created basic block dominates all nodes dominated by Header. 222 for (Function::iterator I = Header->getParent()->begin(), 223 E = Header->getParent()->end(); I != E; ++I) 224 if (DS.dominates(Header, I)) 225 DS.addDominator(I, NewBB); 226 } 227 228 // Update immediate dominator information if we have it... 229 if (ImmediateDominators *ID = getAnalysisToUpdate<ImmediateDominators>()) { 230 // Whatever i-dominated the header node now immediately dominates NewBB 231 ID->addNewBlock(NewBB, ID->get(Header)); 232 233 // The preheader now is the immediate dominator for the header node... 234 ID->setImmediateDominator(Header, NewBB); 235 } 236 237 // Update DominatorTree information if it is active. 238 if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>()) { 239 // The immediate dominator of the preheader is the immediate dominator of 240 // the old header. 241 // 242 DominatorTree::Node *HeaderNode = DT->getNode(Header); 243 DominatorTree::Node *PHNode = DT->createNewNode(NewBB, 244 HeaderNode->getIDom()); 245 246 // Change the header node so that PNHode is the new immediate dominator 247 DT->changeImmediateDominator(HeaderNode, PHNode); 248 } 249 250 // Update dominance frontier information... 251 if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) { 252 // The DF(NewBB) is just (DF(Header)-Header), because NewBB dominates 253 // everything that Header does, and it strictly dominates Header in 254 // addition. 255 assert(DF->find(Header) != DF->end() && "Header node doesn't have DF set?"); 256 DominanceFrontier::DomSetType NewDFSet = DF->find(Header)->second; 257 NewDFSet.erase(Header); 258 DF->addBasicBlock(NewBB, NewDFSet); 259 260 // Now we must loop over all of the dominance frontiers in the function, 261 // replacing occurances of Header with NewBB in some cases. If a block 262 // dominates a (now) predecessor of NewBB, but did not strictly dominate 263 // Header, it will have Header in it's DF set, but should now have NewBB in 264 // its set. 265 for (unsigned i = 0, e = OutsideBlocks.size(); i != e; ++i) { 266 // Get all of the dominators of the predecessor... 267 const DominatorSet::DomSetType &PredDoms = 268 DS.getDominators(OutsideBlocks[i]); 269 for (DominatorSet::DomSetType::const_iterator PDI = PredDoms.begin(), 270 PDE = PredDoms.end(); PDI != PDE; ++PDI) { 271 BasicBlock *PredDom = *PDI; 272 // If the loop header is in DF(PredDom), then PredDom didn't dominate 273 // the header but did dominate a predecessor outside of the loop. Now 274 // we change this entry to include the preheader in the DF instead of 275 // the header. 276 DominanceFrontier::iterator DFI = DF->find(PredDom); 277 assert(DFI != DF->end() && "No dominance frontier for node?"); 278 if (DFI->second.count(Header)) { 279 DF->removeFromFrontier(DFI, Header); 280 DF->addToFrontier(DFI, NewBB); 281 } 282 } 283 } 284 } 285} 286 287void Preheaders::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) { 288 DominatorSet &DS = getAnalysis<DominatorSet>(); 289 assert(!DS.dominates(L->getHeader(), Exit) && 290 "Loop already dominates exit block??"); 291 assert(std::find(L->getExitBlocks().begin(), L->getExitBlocks().end(), Exit) 292 != L->getExitBlocks().end() && "Not a current exit block!"); 293 294 std::vector<BasicBlock*> LoopBlocks; 295 for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) 296 if (L->contains(*I)) 297 LoopBlocks.push_back(*I); 298 299 assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?"); 300 BasicBlock *NewBB = SplitBlockPredecessors(Exit, ".loopexit", LoopBlocks); 301 302 // Update Loop Information - we know that the new block will be in the parent 303 // loop of L. 304 if (Loop *Parent = L->getParentLoop()) 305 Parent->addBasicBlockToLoop(NewBB, getAnalysis<LoopInfo>()); 306 L->changeExitBlock(Exit, NewBB); // Update exit block information 307 308 // Update dominator information... The blocks that dominate NewBB are the 309 // intersection of the dominators of predecessors, plus the block itself. 310 // The newly created basic block does not dominate anything except itself. 311 // 312 DominatorSet::DomSetType NewBBDomSet = DS.getDominators(LoopBlocks[0]); 313 for (unsigned i = 1, e = LoopBlocks.size(); i != e; ++i) 314 set_intersect(NewBBDomSet, DS.getDominators(LoopBlocks[i])); 315 NewBBDomSet.insert(NewBB); // All blocks dominate themselves... 316 DS.addBasicBlock(NewBB, NewBBDomSet); 317 318 // Update immediate dominator information if we have it... 319 BasicBlock *NewBBIDom = 0; 320 if (ImmediateDominators *ID = getAnalysisToUpdate<ImmediateDominators>()) { 321 // This block does not strictly dominate anything, so it is not an immediate 322 // dominator. To find the immediate dominator of the new exit node, we 323 // trace up the immediate dominators of a predecessor until we find a basic 324 // block that dominates the exit block. 325 // 326 BasicBlock *Dom = LoopBlocks[0]; // Some random predecessor... 327 while (!NewBBDomSet.count(Dom)) { // Loop until we find a dominator... 328 assert(Dom != 0 && "No shared dominator found???"); 329 Dom = ID->get(Dom); 330 } 331 332 // Set the immediate dominator now... 333 ID->addNewBlock(NewBB, Dom); 334 NewBBIDom = Dom; // Reuse this if calculating DominatorTree info... 335 } 336 337 // Update DominatorTree information if it is active. 338 if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>()) { 339 // NewBB doesn't dominate anything, so just create a node and link it into 340 // its immediate dominator. If we don't have ImmediateDominator info 341 // around, calculate the idom as above. 342 DominatorTree::Node *NewBBIDomNode; 343 if (NewBBIDom) { 344 NewBBIDomNode = DT->getNode(NewBBIDom); 345 } else { 346 NewBBIDomNode = DT->getNode(LoopBlocks[0]); // Random pred 347 while (!NewBBDomSet.count(NewBBIDomNode->getNode())) { 348 NewBBIDomNode = NewBBIDomNode->getIDom(); 349 assert(NewBBIDomNode && "No shared dominator found??"); 350 } 351 } 352 353 // Create the new dominator tree node... 354 DT->createNewNode(NewBB, NewBBIDomNode); 355 } 356 357 // Update dominance frontier information... 358 if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) { 359 // DF(NewBB) is {Exit} because NewBB does not strictly dominate Exit, but it 360 // does dominate itself (and there is an edge (NewBB -> Exit)). 361 DominanceFrontier::DomSetType NewDFSet; 362 NewDFSet.insert(Exit); 363 DF->addBasicBlock(NewBB, NewDFSet); 364 365 // Now we must loop over all of the dominance frontiers in the function, 366 // replacing occurances of Exit with NewBB in some cases. If a block 367 // dominates a (now) predecessor of NewBB, but did not strictly dominate 368 // Exit, it will have Exit in it's DF set, but should now have NewBB in its 369 // set. 370 for (unsigned i = 0, e = LoopBlocks.size(); i != e; ++i) { 371 // Get all of the dominators of the predecessor... 372 const DominatorSet::DomSetType &PredDoms =DS.getDominators(LoopBlocks[i]); 373 for (DominatorSet::DomSetType::const_iterator PDI = PredDoms.begin(), 374 PDE = PredDoms.end(); PDI != PDE; ++PDI) { 375 BasicBlock *PredDom = *PDI; 376 // Make sure to only rewrite blocks that are part of the loop... 377 if (L->contains(PredDom)) { 378 // If the exit node is in DF(PredDom), then PredDom didn't dominate 379 // Exit but did dominate a predecessor inside of the loop. Now we 380 // change this entry to include NewBB in the DF instead of Exit. 381 DominanceFrontier::iterator DFI = DF->find(PredDom); 382 assert(DFI != DF->end() && "No dominance frontier for node?"); 383 if (DFI->second.count(Exit)) { 384 DF->removeFromFrontier(DFI, Exit); 385 DF->addToFrontier(DFI, NewBB); 386 } 387 } 388 } 389 } 390 } 391} 392