1//===- LoopSimplify.cpp - Loop Canonicalization Pass ----------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This pass performs several transformations to transform natural loops into a 11// simpler form, which makes subsequent analyses and transformations simpler and 12// more effective. 13// 14// Loop pre-header insertion guarantees that there is a single, non-critical 15// entry edge from outside of the loop to the loop header. This simplifies a 16// number of analyses and transformations, such as LICM. 17// 18// Loop exit-block insertion guarantees that all exit blocks from the loop 19// (blocks which are outside of the loop that have predecessors inside of the 20// loop) only have predecessors from inside of the loop (and are thus dominated 21// by the loop header). This simplifies transformations such as store-sinking 22// that are built into LICM. 23// 24// This pass also guarantees that loops will have exactly one backedge. 25// 26// Indirectbr instructions introduce several complications. If the loop 27// contains or is entered by an indirectbr instruction, it may not be possible 28// to transform the loop and make these guarantees. Client code should check 29// that these conditions are true before relying on them. 30// 31// Note that the simplifycfg pass will clean up blocks which are split out but 32// end up being unnecessary, so usage of this pass should not pessimize 33// generated code. 34// 35// This pass obviously modifies the CFG, but updates loop information and 36// dominator information. 37// 38//===----------------------------------------------------------------------===// 39 40#define DEBUG_TYPE "loopsimplify" 41#include "llvm/Transforms/Scalar.h" 42#include "llvm/Constants.h" 43#include "llvm/Instructions.h" 44#include "llvm/Function.h" 45#include "llvm/LLVMContext.h" 46#include "llvm/Type.h" 47#include "llvm/Analysis/AliasAnalysis.h" 48#include "llvm/Analysis/Dominators.h" 49#include "llvm/Analysis/LoopPass.h" 50#include "llvm/Analysis/ScalarEvolution.h" 51#include "llvm/Transforms/Utils/BasicBlockUtils.h" 52#include "llvm/Transforms/Utils/Local.h" 53#include "llvm/Support/CFG.h" 54#include "llvm/ADT/SetOperations.h" 55#include "llvm/ADT/SetVector.h" 56#include "llvm/ADT/Statistic.h" 57#include "llvm/ADT/DepthFirstIterator.h" 58using namespace llvm; 59 60STATISTIC(NumInserted, "Number of pre-header or exit blocks inserted"); 61STATISTIC(NumNested , "Number of nested loops split out"); 62 63namespace { 64 struct LoopSimplify : public LoopPass { 65 static char ID; // Pass identification, replacement for typeid 66 LoopSimplify() : LoopPass(&ID) {} 67 68 // AA - If we have an alias analysis object to update, this is it, otherwise 69 // this is null. 70 AliasAnalysis *AA; 71 LoopInfo *LI; 72 DominatorTree *DT; 73 Loop *L; 74 virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 75 76 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 77 // We need loop information to identify the loops... 78 AU.addRequiredTransitive<LoopInfo>(); 79 AU.addRequiredTransitive<DominatorTree>(); 80 81 AU.addPreserved<LoopInfo>(); 82 AU.addPreserved<DominatorTree>(); 83 AU.addPreserved<DominanceFrontier>(); 84 AU.addPreserved<AliasAnalysis>(); 85 AU.addPreserved<ScalarEvolution>(); 86 AU.addPreservedID(BreakCriticalEdgesID); // No critical edges added. 87 } 88 89 /// verifyAnalysis() - Verify LoopSimplifyForm's guarantees. 90 void verifyAnalysis() const; 91 92 private: 93 bool ProcessLoop(Loop *L, LPPassManager &LPM); 94 BasicBlock *RewriteLoopExitBlock(Loop *L, BasicBlock *Exit); 95 BasicBlock *InsertPreheaderForLoop(Loop *L); 96 Loop *SeparateNestedLoop(Loop *L, LPPassManager &LPM); 97 BasicBlock *InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader); 98 void PlaceSplitBlockCarefully(BasicBlock *NewBB, 99 SmallVectorImpl<BasicBlock*> &SplitPreds, 100 Loop *L); 101 }; 102} 103 104char LoopSimplify::ID = 0; 105static RegisterPass<LoopSimplify> 106X("loopsimplify", "Canonicalize natural loops", true); 107 108// Publically exposed interface to pass... 109const PassInfo *const llvm::LoopSimplifyID = &X; 110Pass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); } 111 112/// runOnFunction - Run down all loops in the CFG (recursively, but we could do 113/// it in any convenient order) inserting preheaders... 114/// 115bool LoopSimplify::runOnLoop(Loop *l, LPPassManager &LPM) { 116 L = l; 117 bool Changed = false; 118 LI = &getAnalysis<LoopInfo>(); 119 AA = getAnalysisIfAvailable<AliasAnalysis>(); 120 DT = &getAnalysis<DominatorTree>(); 121 122 Changed |= ProcessLoop(L, LPM); 123 124 return Changed; 125} 126 127/// ProcessLoop - Walk the loop structure in depth first order, ensuring that 128/// all loops have preheaders. 129/// 130bool LoopSimplify::ProcessLoop(Loop *L, LPPassManager &LPM) { 131 bool Changed = false; 132ReprocessLoop: 133 134 // Check to see that no blocks (other than the header) in this loop that has 135 // predecessors that are not in the loop. This is not valid for natural 136 // loops, but can occur if the blocks are unreachable. Since they are 137 // unreachable we can just shamelessly delete those CFG edges! 138 for (Loop::block_iterator BB = L->block_begin(), E = L->block_end(); 139 BB != E; ++BB) { 140 if (*BB == L->getHeader()) continue; 141 142 SmallPtrSet<BasicBlock *, 4> BadPreds; 143 for (pred_iterator PI = pred_begin(*BB), PE = pred_end(*BB); PI != PE; ++PI) 144 if (!L->contains(*PI)) 145 BadPreds.insert(*PI); 146 147 // Delete each unique out-of-loop (and thus dead) predecessor. 148 for (SmallPtrSet<BasicBlock *, 4>::iterator I = BadPreds.begin(), 149 E = BadPreds.end(); I != E; ++I) { 150 // Inform each successor of each dead pred. 151 for (succ_iterator SI = succ_begin(*I), SE = succ_end(*I); SI != SE; ++SI) 152 (*SI)->removePredecessor(*I); 153 // Zap the dead pred's terminator and replace it with unreachable. 154 TerminatorInst *TI = (*I)->getTerminator(); 155 TI->replaceAllUsesWith(UndefValue::get(TI->getType())); 156 (*I)->getTerminator()->eraseFromParent(); 157 new UnreachableInst((*I)->getContext(), *I); 158 Changed = true; 159 } 160 } 161 162 // Does the loop already have a preheader? If so, don't insert one. 163 BasicBlock *Preheader = L->getLoopPreheader(); 164 if (!Preheader) { 165 Preheader = InsertPreheaderForLoop(L); 166 if (Preheader) { 167 NumInserted++; 168 Changed = true; 169 } 170 } 171 172 // Next, check to make sure that all exit nodes of the loop only have 173 // predecessors that are inside of the loop. This check guarantees that the 174 // loop preheader/header will dominate the exit blocks. If the exit block has 175 // predecessors from outside of the loop, split the edge now. 176 SmallVector<BasicBlock*, 8> ExitBlocks; 177 L->getExitBlocks(ExitBlocks); 178 179 SetVector<BasicBlock*> ExitBlockSet(ExitBlocks.begin(), ExitBlocks.end()); 180 for (SetVector<BasicBlock*>::iterator I = ExitBlockSet.begin(), 181 E = ExitBlockSet.end(); I != E; ++I) { 182 BasicBlock *ExitBlock = *I; 183 for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock); 184 PI != PE; ++PI) 185 // Must be exactly this loop: no subloops, parent loops, or non-loop preds 186 // allowed. 187 if (!L->contains(*PI)) { 188 if (RewriteLoopExitBlock(L, ExitBlock)) { 189 NumInserted++; 190 Changed = true; 191 } 192 break; 193 } 194 } 195 196 // If the header has more than two predecessors at this point (from the 197 // preheader and from multiple backedges), we must adjust the loop. 198 BasicBlock *LoopLatch = L->getLoopLatch(); 199 if (!LoopLatch) { 200 // If this is really a nested loop, rip it out into a child loop. Don't do 201 // this for loops with a giant number of backedges, just factor them into a 202 // common backedge instead. 203 if (L->getNumBackEdges() < 8) { 204 if (SeparateNestedLoop(L, LPM)) { 205 ++NumNested; 206 // This is a big restructuring change, reprocess the whole loop. 207 Changed = true; 208 // GCC doesn't tail recursion eliminate this. 209 goto ReprocessLoop; 210 } 211 } 212 213 // If we either couldn't, or didn't want to, identify nesting of the loops, 214 // insert a new block that all backedges target, then make it jump to the 215 // loop header. 216 LoopLatch = InsertUniqueBackedgeBlock(L, Preheader); 217 if (LoopLatch) { 218 NumInserted++; 219 Changed = true; 220 } 221 } 222 223 // Scan over the PHI nodes in the loop header. Since they now have only two 224 // incoming values (the loop is canonicalized), we may have simplified the PHI 225 // down to 'X = phi [X, Y]', which should be replaced with 'Y'. 226 PHINode *PN; 227 for (BasicBlock::iterator I = L->getHeader()->begin(); 228 (PN = dyn_cast<PHINode>(I++)); ) 229 if (Value *V = PN->hasConstantValue(DT)) { 230 if (AA) AA->deleteValue(PN); 231 PN->replaceAllUsesWith(V); 232 PN->eraseFromParent(); 233 } 234 235 // If this loop has muliple exits and the exits all go to the same 236 // block, attempt to merge the exits. This helps several passes, such 237 // as LoopRotation, which do not support loops with multiple exits. 238 // SimplifyCFG also does this (and this code uses the same utility 239 // function), however this code is loop-aware, where SimplifyCFG is 240 // not. That gives it the advantage of being able to hoist 241 // loop-invariant instructions out of the way to open up more 242 // opportunities, and the disadvantage of having the responsibility 243 // to preserve dominator information. 244 bool UniqueExit = true; 245 if (!ExitBlocks.empty()) 246 for (unsigned i = 1, e = ExitBlocks.size(); i != e; ++i) 247 if (ExitBlocks[i] != ExitBlocks[0]) { 248 UniqueExit = false; 249 break; 250 } 251 if (UniqueExit) { 252 SmallVector<BasicBlock*, 8> ExitingBlocks; 253 L->getExitingBlocks(ExitingBlocks); 254 for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { 255 BasicBlock *ExitingBlock = ExitingBlocks[i]; 256 if (!ExitingBlock->getSinglePredecessor()) continue; 257 BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()); 258 if (!BI || !BI->isConditional()) continue; 259 CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition()); 260 if (!CI || CI->getParent() != ExitingBlock) continue; 261 262 // Attempt to hoist out all instructions except for the 263 // comparison and the branch. 264 bool AllInvariant = true; 265 for (BasicBlock::iterator I = ExitingBlock->begin(); &*I != BI; ) { 266 Instruction *Inst = I++; 267 if (Inst == CI) 268 continue; 269 if (!L->makeLoopInvariant(Inst, Changed, 270 Preheader ? Preheader->getTerminator() : 0)) { 271 AllInvariant = false; 272 break; 273 } 274 } 275 if (!AllInvariant) continue; 276 277 // The block has now been cleared of all instructions except for 278 // a comparison and a conditional branch. SimplifyCFG may be able 279 // to fold it now. 280 if (!FoldBranchToCommonDest(BI)) continue; 281 282 // Success. The block is now dead, so remove it from the loop, 283 // update the dominator tree and dominance frontier, and delete it. 284 assert(pred_begin(ExitingBlock) == pred_end(ExitingBlock)); 285 Changed = true; 286 LI->removeBlock(ExitingBlock); 287 288 DominanceFrontier *DF = getAnalysisIfAvailable<DominanceFrontier>(); 289 DomTreeNode *Node = DT->getNode(ExitingBlock); 290 const std::vector<DomTreeNodeBase<BasicBlock> *> &Children = 291 Node->getChildren(); 292 while (!Children.empty()) { 293 DomTreeNode *Child = Children.front(); 294 DT->changeImmediateDominator(Child, Node->getIDom()); 295 if (DF) DF->changeImmediateDominator(Child->getBlock(), 296 Node->getIDom()->getBlock(), 297 DT); 298 } 299 DT->eraseNode(ExitingBlock); 300 if (DF) DF->removeBlock(ExitingBlock); 301 302 BI->getSuccessor(0)->removePredecessor(ExitingBlock); 303 BI->getSuccessor(1)->removePredecessor(ExitingBlock); 304 ExitingBlock->eraseFromParent(); 305 } 306 } 307
| 1//===- LoopSimplify.cpp - Loop Canonicalization Pass ----------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This pass performs several transformations to transform natural loops into a 11// simpler form, which makes subsequent analyses and transformations simpler and 12// more effective. 13// 14// Loop pre-header insertion guarantees that there is a single, non-critical 15// entry edge from outside of the loop to the loop header. This simplifies a 16// number of analyses and transformations, such as LICM. 17// 18// Loop exit-block insertion guarantees that all exit blocks from the loop 19// (blocks which are outside of the loop that have predecessors inside of the 20// loop) only have predecessors from inside of the loop (and are thus dominated 21// by the loop header). This simplifies transformations such as store-sinking 22// that are built into LICM. 23// 24// This pass also guarantees that loops will have exactly one backedge. 25// 26// Indirectbr instructions introduce several complications. If the loop 27// contains or is entered by an indirectbr instruction, it may not be possible 28// to transform the loop and make these guarantees. Client code should check 29// that these conditions are true before relying on them. 30// 31// Note that the simplifycfg pass will clean up blocks which are split out but 32// end up being unnecessary, so usage of this pass should not pessimize 33// generated code. 34// 35// This pass obviously modifies the CFG, but updates loop information and 36// dominator information. 37// 38//===----------------------------------------------------------------------===// 39 40#define DEBUG_TYPE "loopsimplify" 41#include "llvm/Transforms/Scalar.h" 42#include "llvm/Constants.h" 43#include "llvm/Instructions.h" 44#include "llvm/Function.h" 45#include "llvm/LLVMContext.h" 46#include "llvm/Type.h" 47#include "llvm/Analysis/AliasAnalysis.h" 48#include "llvm/Analysis/Dominators.h" 49#include "llvm/Analysis/LoopPass.h" 50#include "llvm/Analysis/ScalarEvolution.h" 51#include "llvm/Transforms/Utils/BasicBlockUtils.h" 52#include "llvm/Transforms/Utils/Local.h" 53#include "llvm/Support/CFG.h" 54#include "llvm/ADT/SetOperations.h" 55#include "llvm/ADT/SetVector.h" 56#include "llvm/ADT/Statistic.h" 57#include "llvm/ADT/DepthFirstIterator.h" 58using namespace llvm; 59 60STATISTIC(NumInserted, "Number of pre-header or exit blocks inserted"); 61STATISTIC(NumNested , "Number of nested loops split out"); 62 63namespace { 64 struct LoopSimplify : public LoopPass { 65 static char ID; // Pass identification, replacement for typeid 66 LoopSimplify() : LoopPass(&ID) {} 67 68 // AA - If we have an alias analysis object to update, this is it, otherwise 69 // this is null. 70 AliasAnalysis *AA; 71 LoopInfo *LI; 72 DominatorTree *DT; 73 Loop *L; 74 virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 75 76 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 77 // We need loop information to identify the loops... 78 AU.addRequiredTransitive<LoopInfo>(); 79 AU.addRequiredTransitive<DominatorTree>(); 80 81 AU.addPreserved<LoopInfo>(); 82 AU.addPreserved<DominatorTree>(); 83 AU.addPreserved<DominanceFrontier>(); 84 AU.addPreserved<AliasAnalysis>(); 85 AU.addPreserved<ScalarEvolution>(); 86 AU.addPreservedID(BreakCriticalEdgesID); // No critical edges added. 87 } 88 89 /// verifyAnalysis() - Verify LoopSimplifyForm's guarantees. 90 void verifyAnalysis() const; 91 92 private: 93 bool ProcessLoop(Loop *L, LPPassManager &LPM); 94 BasicBlock *RewriteLoopExitBlock(Loop *L, BasicBlock *Exit); 95 BasicBlock *InsertPreheaderForLoop(Loop *L); 96 Loop *SeparateNestedLoop(Loop *L, LPPassManager &LPM); 97 BasicBlock *InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader); 98 void PlaceSplitBlockCarefully(BasicBlock *NewBB, 99 SmallVectorImpl<BasicBlock*> &SplitPreds, 100 Loop *L); 101 }; 102} 103 104char LoopSimplify::ID = 0; 105static RegisterPass<LoopSimplify> 106X("loopsimplify", "Canonicalize natural loops", true); 107 108// Publically exposed interface to pass... 109const PassInfo *const llvm::LoopSimplifyID = &X; 110Pass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); } 111 112/// runOnFunction - Run down all loops in the CFG (recursively, but we could do 113/// it in any convenient order) inserting preheaders... 114/// 115bool LoopSimplify::runOnLoop(Loop *l, LPPassManager &LPM) { 116 L = l; 117 bool Changed = false; 118 LI = &getAnalysis<LoopInfo>(); 119 AA = getAnalysisIfAvailable<AliasAnalysis>(); 120 DT = &getAnalysis<DominatorTree>(); 121 122 Changed |= ProcessLoop(L, LPM); 123 124 return Changed; 125} 126 127/// ProcessLoop - Walk the loop structure in depth first order, ensuring that 128/// all loops have preheaders. 129/// 130bool LoopSimplify::ProcessLoop(Loop *L, LPPassManager &LPM) { 131 bool Changed = false; 132ReprocessLoop: 133 134 // Check to see that no blocks (other than the header) in this loop that has 135 // predecessors that are not in the loop. This is not valid for natural 136 // loops, but can occur if the blocks are unreachable. Since they are 137 // unreachable we can just shamelessly delete those CFG edges! 138 for (Loop::block_iterator BB = L->block_begin(), E = L->block_end(); 139 BB != E; ++BB) { 140 if (*BB == L->getHeader()) continue; 141 142 SmallPtrSet<BasicBlock *, 4> BadPreds; 143 for (pred_iterator PI = pred_begin(*BB), PE = pred_end(*BB); PI != PE; ++PI) 144 if (!L->contains(*PI)) 145 BadPreds.insert(*PI); 146 147 // Delete each unique out-of-loop (and thus dead) predecessor. 148 for (SmallPtrSet<BasicBlock *, 4>::iterator I = BadPreds.begin(), 149 E = BadPreds.end(); I != E; ++I) { 150 // Inform each successor of each dead pred. 151 for (succ_iterator SI = succ_begin(*I), SE = succ_end(*I); SI != SE; ++SI) 152 (*SI)->removePredecessor(*I); 153 // Zap the dead pred's terminator and replace it with unreachable. 154 TerminatorInst *TI = (*I)->getTerminator(); 155 TI->replaceAllUsesWith(UndefValue::get(TI->getType())); 156 (*I)->getTerminator()->eraseFromParent(); 157 new UnreachableInst((*I)->getContext(), *I); 158 Changed = true; 159 } 160 } 161 162 // Does the loop already have a preheader? If so, don't insert one. 163 BasicBlock *Preheader = L->getLoopPreheader(); 164 if (!Preheader) { 165 Preheader = InsertPreheaderForLoop(L); 166 if (Preheader) { 167 NumInserted++; 168 Changed = true; 169 } 170 } 171 172 // Next, check to make sure that all exit nodes of the loop only have 173 // predecessors that are inside of the loop. This check guarantees that the 174 // loop preheader/header will dominate the exit blocks. If the exit block has 175 // predecessors from outside of the loop, split the edge now. 176 SmallVector<BasicBlock*, 8> ExitBlocks; 177 L->getExitBlocks(ExitBlocks); 178 179 SetVector<BasicBlock*> ExitBlockSet(ExitBlocks.begin(), ExitBlocks.end()); 180 for (SetVector<BasicBlock*>::iterator I = ExitBlockSet.begin(), 181 E = ExitBlockSet.end(); I != E; ++I) { 182 BasicBlock *ExitBlock = *I; 183 for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock); 184 PI != PE; ++PI) 185 // Must be exactly this loop: no subloops, parent loops, or non-loop preds 186 // allowed. 187 if (!L->contains(*PI)) { 188 if (RewriteLoopExitBlock(L, ExitBlock)) { 189 NumInserted++; 190 Changed = true; 191 } 192 break; 193 } 194 } 195 196 // If the header has more than two predecessors at this point (from the 197 // preheader and from multiple backedges), we must adjust the loop. 198 BasicBlock *LoopLatch = L->getLoopLatch(); 199 if (!LoopLatch) { 200 // If this is really a nested loop, rip it out into a child loop. Don't do 201 // this for loops with a giant number of backedges, just factor them into a 202 // common backedge instead. 203 if (L->getNumBackEdges() < 8) { 204 if (SeparateNestedLoop(L, LPM)) { 205 ++NumNested; 206 // This is a big restructuring change, reprocess the whole loop. 207 Changed = true; 208 // GCC doesn't tail recursion eliminate this. 209 goto ReprocessLoop; 210 } 211 } 212 213 // If we either couldn't, or didn't want to, identify nesting of the loops, 214 // insert a new block that all backedges target, then make it jump to the 215 // loop header. 216 LoopLatch = InsertUniqueBackedgeBlock(L, Preheader); 217 if (LoopLatch) { 218 NumInserted++; 219 Changed = true; 220 } 221 } 222 223 // Scan over the PHI nodes in the loop header. Since they now have only two 224 // incoming values (the loop is canonicalized), we may have simplified the PHI 225 // down to 'X = phi [X, Y]', which should be replaced with 'Y'. 226 PHINode *PN; 227 for (BasicBlock::iterator I = L->getHeader()->begin(); 228 (PN = dyn_cast<PHINode>(I++)); ) 229 if (Value *V = PN->hasConstantValue(DT)) { 230 if (AA) AA->deleteValue(PN); 231 PN->replaceAllUsesWith(V); 232 PN->eraseFromParent(); 233 } 234 235 // If this loop has muliple exits and the exits all go to the same 236 // block, attempt to merge the exits. This helps several passes, such 237 // as LoopRotation, which do not support loops with multiple exits. 238 // SimplifyCFG also does this (and this code uses the same utility 239 // function), however this code is loop-aware, where SimplifyCFG is 240 // not. That gives it the advantage of being able to hoist 241 // loop-invariant instructions out of the way to open up more 242 // opportunities, and the disadvantage of having the responsibility 243 // to preserve dominator information. 244 bool UniqueExit = true; 245 if (!ExitBlocks.empty()) 246 for (unsigned i = 1, e = ExitBlocks.size(); i != e; ++i) 247 if (ExitBlocks[i] != ExitBlocks[0]) { 248 UniqueExit = false; 249 break; 250 } 251 if (UniqueExit) { 252 SmallVector<BasicBlock*, 8> ExitingBlocks; 253 L->getExitingBlocks(ExitingBlocks); 254 for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { 255 BasicBlock *ExitingBlock = ExitingBlocks[i]; 256 if (!ExitingBlock->getSinglePredecessor()) continue; 257 BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()); 258 if (!BI || !BI->isConditional()) continue; 259 CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition()); 260 if (!CI || CI->getParent() != ExitingBlock) continue; 261 262 // Attempt to hoist out all instructions except for the 263 // comparison and the branch. 264 bool AllInvariant = true; 265 for (BasicBlock::iterator I = ExitingBlock->begin(); &*I != BI; ) { 266 Instruction *Inst = I++; 267 if (Inst == CI) 268 continue; 269 if (!L->makeLoopInvariant(Inst, Changed, 270 Preheader ? Preheader->getTerminator() : 0)) { 271 AllInvariant = false; 272 break; 273 } 274 } 275 if (!AllInvariant) continue; 276 277 // The block has now been cleared of all instructions except for 278 // a comparison and a conditional branch. SimplifyCFG may be able 279 // to fold it now. 280 if (!FoldBranchToCommonDest(BI)) continue; 281 282 // Success. The block is now dead, so remove it from the loop, 283 // update the dominator tree and dominance frontier, and delete it. 284 assert(pred_begin(ExitingBlock) == pred_end(ExitingBlock)); 285 Changed = true; 286 LI->removeBlock(ExitingBlock); 287 288 DominanceFrontier *DF = getAnalysisIfAvailable<DominanceFrontier>(); 289 DomTreeNode *Node = DT->getNode(ExitingBlock); 290 const std::vector<DomTreeNodeBase<BasicBlock> *> &Children = 291 Node->getChildren(); 292 while (!Children.empty()) { 293 DomTreeNode *Child = Children.front(); 294 DT->changeImmediateDominator(Child, Node->getIDom()); 295 if (DF) DF->changeImmediateDominator(Child->getBlock(), 296 Node->getIDom()->getBlock(), 297 DT); 298 } 299 DT->eraseNode(ExitingBlock); 300 if (DF) DF->removeBlock(ExitingBlock); 301 302 BI->getSuccessor(0)->removePredecessor(ExitingBlock); 303 BI->getSuccessor(1)->removePredecessor(ExitingBlock); 304 ExitingBlock->eraseFromParent(); 305 } 306 } 307
|
308 return Changed; 309} 310 311/// InsertPreheaderForLoop - Once we discover that a loop doesn't have a 312/// preheader, this method is called to insert one. This method has two phases: 313/// preheader insertion and analysis updating. 314/// 315BasicBlock *LoopSimplify::InsertPreheaderForLoop(Loop *L) { 316 BasicBlock *Header = L->getHeader(); 317 318 // Compute the set of predecessors of the loop that are not in the loop. 319 SmallVector<BasicBlock*, 8> OutsideBlocks; 320 for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header); 321 PI != PE; ++PI) 322 if (!L->contains(*PI)) { // Coming in from outside the loop? 323 // If the loop is branched to from an indirect branch, we won't 324 // be able to fully transform the loop, because it prohibits 325 // edge splitting. 326 if (isa<IndirectBrInst>((*PI)->getTerminator())) return 0; 327 328 // Keep track of it. 329 OutsideBlocks.push_back(*PI); 330 } 331 332 // Split out the loop pre-header. 333 BasicBlock *NewBB = 334 SplitBlockPredecessors(Header, &OutsideBlocks[0], OutsideBlocks.size(), 335 ".preheader", this); 336 337 // Make sure that NewBB is put someplace intelligent, which doesn't mess up 338 // code layout too horribly. 339 PlaceSplitBlockCarefully(NewBB, OutsideBlocks, L); 340 341 return NewBB; 342} 343 344/// RewriteLoopExitBlock - Ensure that the loop preheader dominates all exit 345/// blocks. This method is used to split exit blocks that have predecessors 346/// outside of the loop. 347BasicBlock *LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) { 348 SmallVector<BasicBlock*, 8> LoopBlocks; 349 for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) 350 if (L->contains(*I)) { 351 // Don't do this if the loop is exited via an indirect branch. 352 if (isa<IndirectBrInst>((*I)->getTerminator())) return 0; 353 354 LoopBlocks.push_back(*I); 355 } 356 357 assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?"); 358 BasicBlock *NewBB = SplitBlockPredecessors(Exit, &LoopBlocks[0], 359 LoopBlocks.size(), ".loopexit", 360 this); 361 362 return NewBB; 363} 364 365/// AddBlockAndPredsToSet - Add the specified block, and all of its 366/// predecessors, to the specified set, if it's not already in there. Stop 367/// predecessor traversal when we reach StopBlock. 368static void AddBlockAndPredsToSet(BasicBlock *InputBB, BasicBlock *StopBlock, 369 std::set<BasicBlock*> &Blocks) { 370 std::vector<BasicBlock *> WorkList; 371 WorkList.push_back(InputBB); 372 do { 373 BasicBlock *BB = WorkList.back(); WorkList.pop_back(); 374 if (Blocks.insert(BB).second && BB != StopBlock) 375 // If BB is not already processed and it is not a stop block then 376 // insert its predecessor in the work list 377 for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) { 378 BasicBlock *WBB = *I; 379 WorkList.push_back(WBB); 380 } 381 } while(!WorkList.empty()); 382} 383 384/// FindPHIToPartitionLoops - The first part of loop-nestification is to find a 385/// PHI node that tells us how to partition the loops. 386static PHINode *FindPHIToPartitionLoops(Loop *L, DominatorTree *DT, 387 AliasAnalysis *AA) { 388 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) { 389 PHINode *PN = cast<PHINode>(I); 390 ++I; 391 if (Value *V = PN->hasConstantValue(DT)) { 392 // This is a degenerate PHI already, don't modify it! 393 PN->replaceAllUsesWith(V); 394 if (AA) AA->deleteValue(PN); 395 PN->eraseFromParent(); 396 continue; 397 } 398 399 // Scan this PHI node looking for a use of the PHI node by itself. 400 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 401 if (PN->getIncomingValue(i) == PN && 402 L->contains(PN->getIncomingBlock(i))) 403 // We found something tasty to remove. 404 return PN; 405 } 406 return 0; 407} 408 409// PlaceSplitBlockCarefully - If the block isn't already, move the new block to 410// right after some 'outside block' block. This prevents the preheader from 411// being placed inside the loop body, e.g. when the loop hasn't been rotated. 412void LoopSimplify::PlaceSplitBlockCarefully(BasicBlock *NewBB, 413 SmallVectorImpl<BasicBlock*> &SplitPreds, 414 Loop *L) { 415 // Check to see if NewBB is already well placed. 416 Function::iterator BBI = NewBB; --BBI; 417 for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) { 418 if (&*BBI == SplitPreds[i]) 419 return; 420 } 421 422 // If it isn't already after an outside block, move it after one. This is 423 // always good as it makes the uncond branch from the outside block into a 424 // fall-through. 425 426 // Figure out *which* outside block to put this after. Prefer an outside 427 // block that neighbors a BB actually in the loop. 428 BasicBlock *FoundBB = 0; 429 for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) { 430 Function::iterator BBI = SplitPreds[i]; 431 if (++BBI != NewBB->getParent()->end() && 432 L->contains(BBI)) { 433 FoundBB = SplitPreds[i]; 434 break; 435 } 436 } 437 438 // If our heuristic for a *good* bb to place this after doesn't find 439 // anything, just pick something. It's likely better than leaving it within 440 // the loop. 441 if (!FoundBB) 442 FoundBB = SplitPreds[0]; 443 NewBB->moveAfter(FoundBB); 444} 445 446 447/// SeparateNestedLoop - If this loop has multiple backedges, try to pull one of 448/// them out into a nested loop. This is important for code that looks like 449/// this: 450/// 451/// Loop: 452/// ... 453/// br cond, Loop, Next 454/// ... 455/// br cond2, Loop, Out 456/// 457/// To identify this common case, we look at the PHI nodes in the header of the 458/// loop. PHI nodes with unchanging values on one backedge correspond to values 459/// that change in the "outer" loop, but not in the "inner" loop. 460/// 461/// If we are able to separate out a loop, return the new outer loop that was 462/// created. 463/// 464Loop *LoopSimplify::SeparateNestedLoop(Loop *L, LPPassManager &LPM) { 465 PHINode *PN = FindPHIToPartitionLoops(L, DT, AA); 466 if (PN == 0) return 0; // No known way to partition. 467 468 // Pull out all predecessors that have varying values in the loop. This 469 // handles the case when a PHI node has multiple instances of itself as 470 // arguments. 471 SmallVector<BasicBlock*, 8> OuterLoopPreds; 472 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 473 if (PN->getIncomingValue(i) != PN || 474 !L->contains(PN->getIncomingBlock(i))) 475 OuterLoopPreds.push_back(PN->getIncomingBlock(i)); 476 477 BasicBlock *Header = L->getHeader(); 478 BasicBlock *NewBB = SplitBlockPredecessors(Header, &OuterLoopPreds[0], 479 OuterLoopPreds.size(), 480 ".outer", this); 481 482 // Make sure that NewBB is put someplace intelligent, which doesn't mess up 483 // code layout too horribly. 484 PlaceSplitBlockCarefully(NewBB, OuterLoopPreds, L); 485 486 // Create the new outer loop. 487 Loop *NewOuter = new Loop(); 488 489 // Change the parent loop to use the outer loop as its child now. 490 if (Loop *Parent = L->getParentLoop()) 491 Parent->replaceChildLoopWith(L, NewOuter); 492 else 493 LI->changeTopLevelLoop(L, NewOuter); 494 495 // L is now a subloop of our outer loop. 496 NewOuter->addChildLoop(L); 497 498 // Add the new loop to the pass manager queue. 499 LPM.insertLoopIntoQueue(NewOuter); 500 501 for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 502 I != E; ++I) 503 NewOuter->addBlockEntry(*I); 504 505 // Now reset the header in L, which had been moved by 506 // SplitBlockPredecessors for the outer loop. 507 L->moveToHeader(Header); 508 509 // Determine which blocks should stay in L and which should be moved out to 510 // the Outer loop now. 511 std::set<BasicBlock*> BlocksInL; 512 for (pred_iterator PI = pred_begin(Header), E = pred_end(Header); PI!=E; ++PI) 513 if (DT->dominates(Header, *PI)) 514 AddBlockAndPredsToSet(*PI, Header, BlocksInL); 515 516 517 // Scan all of the loop children of L, moving them to OuterLoop if they are 518 // not part of the inner loop. 519 const std::vector<Loop*> &SubLoops = L->getSubLoops(); 520 for (size_t I = 0; I != SubLoops.size(); ) 521 if (BlocksInL.count(SubLoops[I]->getHeader())) 522 ++I; // Loop remains in L 523 else 524 NewOuter->addChildLoop(L->removeChildLoop(SubLoops.begin() + I)); 525 526 // Now that we know which blocks are in L and which need to be moved to 527 // OuterLoop, move any blocks that need it. 528 for (unsigned i = 0; i != L->getBlocks().size(); ++i) { 529 BasicBlock *BB = L->getBlocks()[i]; 530 if (!BlocksInL.count(BB)) { 531 // Move this block to the parent, updating the exit blocks sets 532 L->removeBlockFromLoop(BB); 533 if ((*LI)[BB] == L) 534 LI->changeLoopFor(BB, NewOuter); 535 --i; 536 } 537 } 538 539 return NewOuter; 540} 541 542 543 544/// InsertUniqueBackedgeBlock - This method is called when the specified loop 545/// has more than one backedge in it. If this occurs, revector all of these 546/// backedges to target a new basic block and have that block branch to the loop 547/// header. This ensures that loops have exactly one backedge. 548/// 549BasicBlock * 550LoopSimplify::InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader) { 551 assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!"); 552 553 // Get information about the loop 554 BasicBlock *Header = L->getHeader(); 555 Function *F = Header->getParent(); 556 557 // Unique backedge insertion currently depends on having a preheader. 558 if (!Preheader) 559 return 0; 560 561 // Figure out which basic blocks contain back-edges to the loop header. 562 std::vector<BasicBlock*> BackedgeBlocks; 563 for (pred_iterator I = pred_begin(Header), E = pred_end(Header); I != E; ++I) 564 if (*I != Preheader) BackedgeBlocks.push_back(*I); 565 566 // Create and insert the new backedge block... 567 BasicBlock *BEBlock = BasicBlock::Create(Header->getContext(), 568 Header->getName()+".backedge", F); 569 BranchInst *BETerminator = BranchInst::Create(Header, BEBlock); 570 571 // Move the new backedge block to right after the last backedge block. 572 Function::iterator InsertPos = BackedgeBlocks.back(); ++InsertPos; 573 F->getBasicBlockList().splice(InsertPos, F->getBasicBlockList(), BEBlock); 574 575 // Now that the block has been inserted into the function, create PHI nodes in 576 // the backedge block which correspond to any PHI nodes in the header block. 577 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { 578 PHINode *PN = cast<PHINode>(I); 579 PHINode *NewPN = PHINode::Create(PN->getType(), PN->getName()+".be", 580 BETerminator); 581 NewPN->reserveOperandSpace(BackedgeBlocks.size()); 582 if (AA) AA->copyValue(PN, NewPN); 583 584 // Loop over the PHI node, moving all entries except the one for the 585 // preheader over to the new PHI node. 586 unsigned PreheaderIdx = ~0U; 587 bool HasUniqueIncomingValue = true; 588 Value *UniqueValue = 0; 589 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 590 BasicBlock *IBB = PN->getIncomingBlock(i); 591 Value *IV = PN->getIncomingValue(i); 592 if (IBB == Preheader) { 593 PreheaderIdx = i; 594 } else { 595 NewPN->addIncoming(IV, IBB); 596 if (HasUniqueIncomingValue) { 597 if (UniqueValue == 0) 598 UniqueValue = IV; 599 else if (UniqueValue != IV) 600 HasUniqueIncomingValue = false; 601 } 602 } 603 } 604 605 // Delete all of the incoming values from the old PN except the preheader's 606 assert(PreheaderIdx != ~0U && "PHI has no preheader entry??"); 607 if (PreheaderIdx != 0) { 608 PN->setIncomingValue(0, PN->getIncomingValue(PreheaderIdx)); 609 PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx)); 610 } 611 // Nuke all entries except the zero'th. 612 for (unsigned i = 0, e = PN->getNumIncomingValues()-1; i != e; ++i) 613 PN->removeIncomingValue(e-i, false); 614 615 // Finally, add the newly constructed PHI node as the entry for the BEBlock. 616 PN->addIncoming(NewPN, BEBlock); 617 618 // As an optimization, if all incoming values in the new PhiNode (which is a 619 // subset of the incoming values of the old PHI node) have the same value, 620 // eliminate the PHI Node. 621 if (HasUniqueIncomingValue) { 622 NewPN->replaceAllUsesWith(UniqueValue); 623 if (AA) AA->deleteValue(NewPN); 624 BEBlock->getInstList().erase(NewPN); 625 } 626 } 627 628 // Now that all of the PHI nodes have been inserted and adjusted, modify the 629 // backedge blocks to just to the BEBlock instead of the header. 630 for (unsigned i = 0, e = BackedgeBlocks.size(); i != e; ++i) { 631 TerminatorInst *TI = BackedgeBlocks[i]->getTerminator(); 632 for (unsigned Op = 0, e = TI->getNumSuccessors(); Op != e; ++Op) 633 if (TI->getSuccessor(Op) == Header) 634 TI->setSuccessor(Op, BEBlock); 635 } 636 637 //===--- Update all analyses which we must preserve now -----------------===// 638 639 // Update Loop Information - we know that this block is now in the current 640 // loop and all parent loops. 641 L->addBasicBlockToLoop(BEBlock, LI->getBase()); 642 643 // Update dominator information 644 DT->splitBlock(BEBlock); 645 if (DominanceFrontier *DF = getAnalysisIfAvailable<DominanceFrontier>()) 646 DF->splitBlock(BEBlock); 647 648 return BEBlock; 649} 650 651void LoopSimplify::verifyAnalysis() const { 652 // It used to be possible to just assert L->isLoopSimplifyForm(), however 653 // with the introduction of indirectbr, there are now cases where it's 654 // not possible to transform a loop as necessary. We can at least check 655 // that there is an indirectbr near any time there's trouble. 656 657 // Indirectbr can interfere with preheader and unique backedge insertion. 658 if (!L->getLoopPreheader() || !L->getLoopLatch()) { 659 bool HasIndBrPred = false; 660 for (pred_iterator PI = pred_begin(L->getHeader()), 661 PE = pred_end(L->getHeader()); PI != PE; ++PI) 662 if (isa<IndirectBrInst>((*PI)->getTerminator())) { 663 HasIndBrPred = true; 664 break; 665 } 666 assert(HasIndBrPred && 667 "LoopSimplify has no excuse for missing loop header info!"); 668 } 669 670 // Indirectbr can interfere with exit block canonicalization. 671 if (!L->hasDedicatedExits()) { 672 bool HasIndBrExiting = false; 673 SmallVector<BasicBlock*, 8> ExitingBlocks; 674 L->getExitingBlocks(ExitingBlocks); 675 for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) 676 if (isa<IndirectBrInst>((ExitingBlocks[i])->getTerminator())) { 677 HasIndBrExiting = true; 678 break; 679 } 680 assert(HasIndBrExiting && 681 "LoopSimplify has no excuse for missing exit block info!"); 682 } 683}
| 314 return Changed; 315} 316 317/// InsertPreheaderForLoop - Once we discover that a loop doesn't have a 318/// preheader, this method is called to insert one. This method has two phases: 319/// preheader insertion and analysis updating. 320/// 321BasicBlock *LoopSimplify::InsertPreheaderForLoop(Loop *L) { 322 BasicBlock *Header = L->getHeader(); 323 324 // Compute the set of predecessors of the loop that are not in the loop. 325 SmallVector<BasicBlock*, 8> OutsideBlocks; 326 for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header); 327 PI != PE; ++PI) 328 if (!L->contains(*PI)) { // Coming in from outside the loop? 329 // If the loop is branched to from an indirect branch, we won't 330 // be able to fully transform the loop, because it prohibits 331 // edge splitting. 332 if (isa<IndirectBrInst>((*PI)->getTerminator())) return 0; 333 334 // Keep track of it. 335 OutsideBlocks.push_back(*PI); 336 } 337 338 // Split out the loop pre-header. 339 BasicBlock *NewBB = 340 SplitBlockPredecessors(Header, &OutsideBlocks[0], OutsideBlocks.size(), 341 ".preheader", this); 342 343 // Make sure that NewBB is put someplace intelligent, which doesn't mess up 344 // code layout too horribly. 345 PlaceSplitBlockCarefully(NewBB, OutsideBlocks, L); 346 347 return NewBB; 348} 349 350/// RewriteLoopExitBlock - Ensure that the loop preheader dominates all exit 351/// blocks. This method is used to split exit blocks that have predecessors 352/// outside of the loop. 353BasicBlock *LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) { 354 SmallVector<BasicBlock*, 8> LoopBlocks; 355 for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) 356 if (L->contains(*I)) { 357 // Don't do this if the loop is exited via an indirect branch. 358 if (isa<IndirectBrInst>((*I)->getTerminator())) return 0; 359 360 LoopBlocks.push_back(*I); 361 } 362 363 assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?"); 364 BasicBlock *NewBB = SplitBlockPredecessors(Exit, &LoopBlocks[0], 365 LoopBlocks.size(), ".loopexit", 366 this); 367 368 return NewBB; 369} 370 371/// AddBlockAndPredsToSet - Add the specified block, and all of its 372/// predecessors, to the specified set, if it's not already in there. Stop 373/// predecessor traversal when we reach StopBlock. 374static void AddBlockAndPredsToSet(BasicBlock *InputBB, BasicBlock *StopBlock, 375 std::set<BasicBlock*> &Blocks) { 376 std::vector<BasicBlock *> WorkList; 377 WorkList.push_back(InputBB); 378 do { 379 BasicBlock *BB = WorkList.back(); WorkList.pop_back(); 380 if (Blocks.insert(BB).second && BB != StopBlock) 381 // If BB is not already processed and it is not a stop block then 382 // insert its predecessor in the work list 383 for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) { 384 BasicBlock *WBB = *I; 385 WorkList.push_back(WBB); 386 } 387 } while(!WorkList.empty()); 388} 389 390/// FindPHIToPartitionLoops - The first part of loop-nestification is to find a 391/// PHI node that tells us how to partition the loops. 392static PHINode *FindPHIToPartitionLoops(Loop *L, DominatorTree *DT, 393 AliasAnalysis *AA) { 394 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) { 395 PHINode *PN = cast<PHINode>(I); 396 ++I; 397 if (Value *V = PN->hasConstantValue(DT)) { 398 // This is a degenerate PHI already, don't modify it! 399 PN->replaceAllUsesWith(V); 400 if (AA) AA->deleteValue(PN); 401 PN->eraseFromParent(); 402 continue; 403 } 404 405 // Scan this PHI node looking for a use of the PHI node by itself. 406 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 407 if (PN->getIncomingValue(i) == PN && 408 L->contains(PN->getIncomingBlock(i))) 409 // We found something tasty to remove. 410 return PN; 411 } 412 return 0; 413} 414 415// PlaceSplitBlockCarefully - If the block isn't already, move the new block to 416// right after some 'outside block' block. This prevents the preheader from 417// being placed inside the loop body, e.g. when the loop hasn't been rotated. 418void LoopSimplify::PlaceSplitBlockCarefully(BasicBlock *NewBB, 419 SmallVectorImpl<BasicBlock*> &SplitPreds, 420 Loop *L) { 421 // Check to see if NewBB is already well placed. 422 Function::iterator BBI = NewBB; --BBI; 423 for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) { 424 if (&*BBI == SplitPreds[i]) 425 return; 426 } 427 428 // If it isn't already after an outside block, move it after one. This is 429 // always good as it makes the uncond branch from the outside block into a 430 // fall-through. 431 432 // Figure out *which* outside block to put this after. Prefer an outside 433 // block that neighbors a BB actually in the loop. 434 BasicBlock *FoundBB = 0; 435 for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) { 436 Function::iterator BBI = SplitPreds[i]; 437 if (++BBI != NewBB->getParent()->end() && 438 L->contains(BBI)) { 439 FoundBB = SplitPreds[i]; 440 break; 441 } 442 } 443 444 // If our heuristic for a *good* bb to place this after doesn't find 445 // anything, just pick something. It's likely better than leaving it within 446 // the loop. 447 if (!FoundBB) 448 FoundBB = SplitPreds[0]; 449 NewBB->moveAfter(FoundBB); 450} 451 452 453/// SeparateNestedLoop - If this loop has multiple backedges, try to pull one of 454/// them out into a nested loop. This is important for code that looks like 455/// this: 456/// 457/// Loop: 458/// ... 459/// br cond, Loop, Next 460/// ... 461/// br cond2, Loop, Out 462/// 463/// To identify this common case, we look at the PHI nodes in the header of the 464/// loop. PHI nodes with unchanging values on one backedge correspond to values 465/// that change in the "outer" loop, but not in the "inner" loop. 466/// 467/// If we are able to separate out a loop, return the new outer loop that was 468/// created. 469/// 470Loop *LoopSimplify::SeparateNestedLoop(Loop *L, LPPassManager &LPM) { 471 PHINode *PN = FindPHIToPartitionLoops(L, DT, AA); 472 if (PN == 0) return 0; // No known way to partition. 473 474 // Pull out all predecessors that have varying values in the loop. This 475 // handles the case when a PHI node has multiple instances of itself as 476 // arguments. 477 SmallVector<BasicBlock*, 8> OuterLoopPreds; 478 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 479 if (PN->getIncomingValue(i) != PN || 480 !L->contains(PN->getIncomingBlock(i))) 481 OuterLoopPreds.push_back(PN->getIncomingBlock(i)); 482 483 BasicBlock *Header = L->getHeader(); 484 BasicBlock *NewBB = SplitBlockPredecessors(Header, &OuterLoopPreds[0], 485 OuterLoopPreds.size(), 486 ".outer", this); 487 488 // Make sure that NewBB is put someplace intelligent, which doesn't mess up 489 // code layout too horribly. 490 PlaceSplitBlockCarefully(NewBB, OuterLoopPreds, L); 491 492 // Create the new outer loop. 493 Loop *NewOuter = new Loop(); 494 495 // Change the parent loop to use the outer loop as its child now. 496 if (Loop *Parent = L->getParentLoop()) 497 Parent->replaceChildLoopWith(L, NewOuter); 498 else 499 LI->changeTopLevelLoop(L, NewOuter); 500 501 // L is now a subloop of our outer loop. 502 NewOuter->addChildLoop(L); 503 504 // Add the new loop to the pass manager queue. 505 LPM.insertLoopIntoQueue(NewOuter); 506 507 for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 508 I != E; ++I) 509 NewOuter->addBlockEntry(*I); 510 511 // Now reset the header in L, which had been moved by 512 // SplitBlockPredecessors for the outer loop. 513 L->moveToHeader(Header); 514 515 // Determine which blocks should stay in L and which should be moved out to 516 // the Outer loop now. 517 std::set<BasicBlock*> BlocksInL; 518 for (pred_iterator PI = pred_begin(Header), E = pred_end(Header); PI!=E; ++PI) 519 if (DT->dominates(Header, *PI)) 520 AddBlockAndPredsToSet(*PI, Header, BlocksInL); 521 522 523 // Scan all of the loop children of L, moving them to OuterLoop if they are 524 // not part of the inner loop. 525 const std::vector<Loop*> &SubLoops = L->getSubLoops(); 526 for (size_t I = 0; I != SubLoops.size(); ) 527 if (BlocksInL.count(SubLoops[I]->getHeader())) 528 ++I; // Loop remains in L 529 else 530 NewOuter->addChildLoop(L->removeChildLoop(SubLoops.begin() + I)); 531 532 // Now that we know which blocks are in L and which need to be moved to 533 // OuterLoop, move any blocks that need it. 534 for (unsigned i = 0; i != L->getBlocks().size(); ++i) { 535 BasicBlock *BB = L->getBlocks()[i]; 536 if (!BlocksInL.count(BB)) { 537 // Move this block to the parent, updating the exit blocks sets 538 L->removeBlockFromLoop(BB); 539 if ((*LI)[BB] == L) 540 LI->changeLoopFor(BB, NewOuter); 541 --i; 542 } 543 } 544 545 return NewOuter; 546} 547 548 549 550/// InsertUniqueBackedgeBlock - This method is called when the specified loop 551/// has more than one backedge in it. If this occurs, revector all of these 552/// backedges to target a new basic block and have that block branch to the loop 553/// header. This ensures that loops have exactly one backedge. 554/// 555BasicBlock * 556LoopSimplify::InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader) { 557 assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!"); 558 559 // Get information about the loop 560 BasicBlock *Header = L->getHeader(); 561 Function *F = Header->getParent(); 562 563 // Unique backedge insertion currently depends on having a preheader. 564 if (!Preheader) 565 return 0; 566 567 // Figure out which basic blocks contain back-edges to the loop header. 568 std::vector<BasicBlock*> BackedgeBlocks; 569 for (pred_iterator I = pred_begin(Header), E = pred_end(Header); I != E; ++I) 570 if (*I != Preheader) BackedgeBlocks.push_back(*I); 571 572 // Create and insert the new backedge block... 573 BasicBlock *BEBlock = BasicBlock::Create(Header->getContext(), 574 Header->getName()+".backedge", F); 575 BranchInst *BETerminator = BranchInst::Create(Header, BEBlock); 576 577 // Move the new backedge block to right after the last backedge block. 578 Function::iterator InsertPos = BackedgeBlocks.back(); ++InsertPos; 579 F->getBasicBlockList().splice(InsertPos, F->getBasicBlockList(), BEBlock); 580 581 // Now that the block has been inserted into the function, create PHI nodes in 582 // the backedge block which correspond to any PHI nodes in the header block. 583 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { 584 PHINode *PN = cast<PHINode>(I); 585 PHINode *NewPN = PHINode::Create(PN->getType(), PN->getName()+".be", 586 BETerminator); 587 NewPN->reserveOperandSpace(BackedgeBlocks.size()); 588 if (AA) AA->copyValue(PN, NewPN); 589 590 // Loop over the PHI node, moving all entries except the one for the 591 // preheader over to the new PHI node. 592 unsigned PreheaderIdx = ~0U; 593 bool HasUniqueIncomingValue = true; 594 Value *UniqueValue = 0; 595 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 596 BasicBlock *IBB = PN->getIncomingBlock(i); 597 Value *IV = PN->getIncomingValue(i); 598 if (IBB == Preheader) { 599 PreheaderIdx = i; 600 } else { 601 NewPN->addIncoming(IV, IBB); 602 if (HasUniqueIncomingValue) { 603 if (UniqueValue == 0) 604 UniqueValue = IV; 605 else if (UniqueValue != IV) 606 HasUniqueIncomingValue = false; 607 } 608 } 609 } 610 611 // Delete all of the incoming values from the old PN except the preheader's 612 assert(PreheaderIdx != ~0U && "PHI has no preheader entry??"); 613 if (PreheaderIdx != 0) { 614 PN->setIncomingValue(0, PN->getIncomingValue(PreheaderIdx)); 615 PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx)); 616 } 617 // Nuke all entries except the zero'th. 618 for (unsigned i = 0, e = PN->getNumIncomingValues()-1; i != e; ++i) 619 PN->removeIncomingValue(e-i, false); 620 621 // Finally, add the newly constructed PHI node as the entry for the BEBlock. 622 PN->addIncoming(NewPN, BEBlock); 623 624 // As an optimization, if all incoming values in the new PhiNode (which is a 625 // subset of the incoming values of the old PHI node) have the same value, 626 // eliminate the PHI Node. 627 if (HasUniqueIncomingValue) { 628 NewPN->replaceAllUsesWith(UniqueValue); 629 if (AA) AA->deleteValue(NewPN); 630 BEBlock->getInstList().erase(NewPN); 631 } 632 } 633 634 // Now that all of the PHI nodes have been inserted and adjusted, modify the 635 // backedge blocks to just to the BEBlock instead of the header. 636 for (unsigned i = 0, e = BackedgeBlocks.size(); i != e; ++i) { 637 TerminatorInst *TI = BackedgeBlocks[i]->getTerminator(); 638 for (unsigned Op = 0, e = TI->getNumSuccessors(); Op != e; ++Op) 639 if (TI->getSuccessor(Op) == Header) 640 TI->setSuccessor(Op, BEBlock); 641 } 642 643 //===--- Update all analyses which we must preserve now -----------------===// 644 645 // Update Loop Information - we know that this block is now in the current 646 // loop and all parent loops. 647 L->addBasicBlockToLoop(BEBlock, LI->getBase()); 648 649 // Update dominator information 650 DT->splitBlock(BEBlock); 651 if (DominanceFrontier *DF = getAnalysisIfAvailable<DominanceFrontier>()) 652 DF->splitBlock(BEBlock); 653 654 return BEBlock; 655} 656 657void LoopSimplify::verifyAnalysis() const { 658 // It used to be possible to just assert L->isLoopSimplifyForm(), however 659 // with the introduction of indirectbr, there are now cases where it's 660 // not possible to transform a loop as necessary. We can at least check 661 // that there is an indirectbr near any time there's trouble. 662 663 // Indirectbr can interfere with preheader and unique backedge insertion. 664 if (!L->getLoopPreheader() || !L->getLoopLatch()) { 665 bool HasIndBrPred = false; 666 for (pred_iterator PI = pred_begin(L->getHeader()), 667 PE = pred_end(L->getHeader()); PI != PE; ++PI) 668 if (isa<IndirectBrInst>((*PI)->getTerminator())) { 669 HasIndBrPred = true; 670 break; 671 } 672 assert(HasIndBrPred && 673 "LoopSimplify has no excuse for missing loop header info!"); 674 } 675 676 // Indirectbr can interfere with exit block canonicalization. 677 if (!L->hasDedicatedExits()) { 678 bool HasIndBrExiting = false; 679 SmallVector<BasicBlock*, 8> ExitingBlocks; 680 L->getExitingBlocks(ExitingBlocks); 681 for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) 682 if (isa<IndirectBrInst>((ExitingBlocks[i])->getTerminator())) { 683 HasIndBrExiting = true; 684 break; 685 } 686 assert(HasIndBrExiting && 687 "LoopSimplify has no excuse for missing exit block info!"); 688 } 689}
|