LLVM API Documentation
00001 //===-- LoopUnswitch.cpp - Hoist loop-invariant conditionals in loop ------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This pass transforms loops that contain branches on loop-invariant conditions 00011 // to have multiple loops. For example, it turns the left into the right code: 00012 // 00013 // for (...) if (lic) 00014 // A for (...) 00015 // if (lic) A; B; C 00016 // B else 00017 // C for (...) 00018 // A; C 00019 // 00020 // This can increase the size of the code exponentially (doubling it every time 00021 // a loop is unswitched) so we only unswitch if the resultant code will be 00022 // smaller than a threshold. 00023 // 00024 // This pass expects LICM to be run before it to hoist invariant conditions out 00025 // of the loop, to make the unswitching opportunity obvious. 00026 // 00027 //===----------------------------------------------------------------------===// 00028 00029 #define DEBUG_TYPE "loop-unswitch" 00030 #include "llvm/Transforms/Scalar.h" 00031 #include "llvm/Constants.h" 00032 #include "llvm/Function.h" 00033 #include "llvm/Instructions.h" 00034 #include "llvm/Analysis/Dominators.h" 00035 #include "llvm/Analysis/LoopInfo.h" 00036 #include "llvm/Transforms/Utils/Cloning.h" 00037 #include "llvm/Transforms/Utils/Local.h" 00038 #include "llvm/Support/Debug.h" 00039 #include "llvm/ADT/Statistic.h" 00040 #include <algorithm> 00041 using namespace llvm; 00042 00043 namespace { 00044 Statistic<> NumUnswitched("loop-unswitch", "Number of loops unswitched"); 00045 00046 class LoopUnswitch : public FunctionPass { 00047 LoopInfo *LI; // Loop information 00048 DominatorSet *DS; 00049 public: 00050 virtual bool runOnFunction(Function &F); 00051 bool visitLoop(Loop *L); 00052 00053 /// This transformation requires natural loop information & requires that 00054 /// loop preheaders be inserted into the CFG... 00055 /// 00056 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00057 AU.addRequiredID(LoopSimplifyID); 00058 //AU.addRequired<DominatorSet>(); 00059 AU.addRequired<LoopInfo>(); 00060 AU.addPreserved<LoopInfo>(); 00061 } 00062 00063 private: 00064 void VersionLoop(Value *LIC, Loop *L); 00065 BasicBlock *SplitBlock(BasicBlock *BB, bool SplitAtTop); 00066 void RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, bool Val); 00067 }; 00068 RegisterOpt<LoopUnswitch> X("loop-unswitch", "Unswitch loops"); 00069 } 00070 00071 FunctionPass *createLoopUnswitchPass() { return new LoopUnswitch(); } 00072 00073 bool LoopUnswitch::runOnFunction(Function &F) { 00074 bool Changed = false; 00075 LI = &getAnalysis<LoopInfo>(); 00076 DS = 0; //&getAnalysis<DominatorSet>(); 00077 00078 // Transform all the top-level loops. Copy the loop list so that the child 00079 // can update the loop tree if it needs to delete the loop. 00080 std::vector<Loop*> SubLoops(LI->begin(), LI->end()); 00081 for (unsigned i = 0, e = SubLoops.size(); i != e; ++i) 00082 Changed |= visitLoop(SubLoops[i]); 00083 00084 return Changed; 00085 } 00086 00087 bool LoopUnswitch::visitLoop(Loop *L) { 00088 bool Changed = false; 00089 00090 // Recurse through all subloops before we process this loop. Copy the loop 00091 // list so that the child can update the loop tree if it needs to delete the 00092 // loop. 00093 std::vector<Loop*> SubLoops(L->begin(), L->end()); 00094 for (unsigned i = 0, e = SubLoops.size(); i != e; ++i) 00095 Changed |= visitLoop(SubLoops[i]); 00096 00097 // Loop over all of the basic blocks in the loop. If we find an interior 00098 // block that is branching on a loop-invariant condition, we can unswitch this 00099 // loop. 00100 for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 00101 I != E; ++I) { 00102 TerminatorInst *TI = (*I)->getTerminator(); 00103 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 00104 if (!isa<Constant>(SI) && L->isLoopInvariant(SI->getCondition())) 00105 DEBUG(std::cerr << "Can't unswitching 'switch' loop %" 00106 << L->getHeader()->getName() << ", cost = " 00107 << L->getBlocks().size() << "\n" << **I); 00108 } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) 00109 if (BI->isConditional() && !isa<Constant>(BI->getCondition()) && 00110 L->isLoopInvariant(BI->getCondition())) { 00111 // Check to see if it would be profitable to unswitch this loop. 00112 if (L->getBlocks().size() > 10) { 00113 DEBUG(std::cerr << "NOT unswitching loop %" 00114 << L->getHeader()->getName() << ", cost too high: " 00115 << L->getBlocks().size() << "\n"); 00116 } else { 00117 // FIXME: check for profitability. 00118 //std::cerr << "BEFORE:\n"; LI->dump(); 00119 00120 VersionLoop(BI->getCondition(), L); 00121 00122 //std::cerr << "AFTER:\n"; LI->dump(); 00123 return true; 00124 } 00125 } 00126 } 00127 00128 return Changed; 00129 } 00130 00131 /// SplitBlock - Split the specified basic block into two pieces. If SplitAtTop 00132 /// is false, this splits the block so the second half only has an unconditional 00133 /// branch. If SplitAtTop is true, it makes it so the first half of the block 00134 /// only has an unconditional branch in it. 00135 /// 00136 /// This method updates the LoopInfo for this function to correctly reflect the 00137 /// CFG changes made. 00138 BasicBlock *LoopUnswitch::SplitBlock(BasicBlock *BB, bool SplitAtTop) { 00139 BasicBlock::iterator SplitPoint; 00140 if (!SplitAtTop) 00141 SplitPoint = BB->getTerminator(); 00142 else { 00143 SplitPoint = BB->begin(); 00144 while (isa<PHINode>(SplitPoint)) ++SplitPoint; 00145 } 00146 00147 BasicBlock *New = BB->splitBasicBlock(SplitPoint, BB->getName()+".tail"); 00148 // New now lives in whichever loop that BB used to. 00149 if (Loop *L = LI->getLoopFor(BB)) 00150 L->addBasicBlockToLoop(New, *LI); 00151 return SplitAtTop ? BB : New; 00152 } 00153 00154 00155 // RemapInstruction - Convert the instruction operands from referencing the 00156 // current values into those specified by ValueMap. 00157 // 00158 static inline void RemapInstruction(Instruction *I, 00159 std::map<const Value *, Value*> &ValueMap) { 00160 for (unsigned op = 0, E = I->getNumOperands(); op != E; ++op) { 00161 Value *Op = I->getOperand(op); 00162 std::map<const Value *, Value*>::iterator It = ValueMap.find(Op); 00163 if (It != ValueMap.end()) Op = It->second; 00164 I->setOperand(op, Op); 00165 } 00166 } 00167 00168 /// CloneLoop - Recursively clone the specified loop and all of its children, 00169 /// mapping the blocks with the specified map. 00170 static Loop *CloneLoop(Loop *L, Loop *PL, std::map<const Value*, Value*> &VM, 00171 LoopInfo *LI) { 00172 Loop *New = new Loop(); 00173 00174 if (PL) 00175 PL->addChildLoop(New); 00176 else 00177 LI->addTopLevelLoop(New); 00178 00179 // Add all of the blocks in L to the new loop. 00180 for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 00181 I != E; ++I) 00182 if (LI->getLoopFor(*I) == L) 00183 New->addBasicBlockToLoop(cast<BasicBlock>(VM[*I]), *LI); 00184 00185 // Add all of the subloops to the new loop. 00186 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) 00187 CloneLoop(*I, New, VM, LI); 00188 00189 return New; 00190 } 00191 00192 00193 /// InsertPHINodesForUsesOutsideLoop - If this instruction is used outside of 00194 /// the specified loop, insert a PHI node in the appropriate exit block to merge 00195 /// the values in the two different loop versions. 00196 /// 00197 /// Most values are not used outside of the loop they are defined in, so be 00198 /// efficient for this case. 00199 /// 00200 static AllocaInst * 00201 InsertPHINodesForUsesOutsideLoop(Instruction *OI, Instruction *NI, 00202 DominatorSet &DS, Loop *OL, Loop *NL, 00203 std::vector<BasicBlock*> &OldExitBlocks, 00204 std::map<const Value*, Value*> &ValueMap) { 00205 assert(OI->getType() == NI->getType() && OI->getOpcode() == NI->getOpcode() && 00206 "Hrm, should be mapping between identical instructions!"); 00207 for (Value::use_iterator UI = OI->use_begin(), E = OI->use_end(); UI != E; 00208 ++UI) 00209 if (!OL->contains(cast<Instruction>(*UI)->getParent()) && 00210 !NL->contains(cast<Instruction>(*UI)->getParent())) 00211 goto UsedOutsideOfLoop; 00212 return 0; 00213 00214 UsedOutsideOfLoop: 00215 // Okay, this instruction is used outside of the current loop. Insert a PHI 00216 // nodes for the instruction merging the values together. 00217 00218 // FIXME: For now we just spill the object to the stack, assuming that a 00219 // subsequent mem2reg pass will clean up after us. This should be improved in 00220 // two ways: 00221 // 1. If there is only one exit block, trivially insert the PHI nodes 00222 // 2. Once we update domfrontier, we should do the promotion after everything 00223 // is stable again. 00224 AllocaInst *Result = DemoteRegToStack(*OI); 00225 00226 // Store to the stack location right after the new instruction. 00227 BasicBlock::iterator InsertPoint = NI; 00228 if (InvokeInst *II = dyn_cast<InvokeInst>(NI)) 00229 InsertPoint = II->getNormalDest()->begin(); 00230 else 00231 ++InsertPoint; 00232 while (isa<PHINode>(InsertPoint)) ++InsertPoint; 00233 new StoreInst(NI, Result, InsertPoint); 00234 return Result; 00235 } 00236 00237 00238 00239 /// VersionLoop - We determined that the loop is profitable to unswitch and 00240 /// contains a branch on a loop invariant condition. Split it into loop 00241 /// versions and test the condition outside of either loop. 00242 void LoopUnswitch::VersionLoop(Value *LIC, Loop *L) { 00243 Function *F = L->getHeader()->getParent(); 00244 00245 DEBUG(std::cerr << "loop-unswitch: Unswitching loop %" 00246 << L->getHeader()->getName() << " [" << L->getBlocks().size() 00247 << " blocks] in Function " << F->getName() 00248 << " on cond:" << *LIC << "\n"); 00249 00250 std::vector<BasicBlock*> LoopBlocks; 00251 00252 // First step, split the preheader and exit blocks, and add these blocks to 00253 // the LoopBlocks list. 00254 BasicBlock *OrigPreheader = L->getLoopPreheader(); 00255 LoopBlocks.push_back(SplitBlock(OrigPreheader, false)); 00256 00257 // We want the loop to come after the preheader, but before the exit blocks. 00258 LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end()); 00259 00260 std::vector<BasicBlock*> ExitBlocks; 00261 L->getExitBlocks(ExitBlocks); 00262 std::sort(ExitBlocks.begin(), ExitBlocks.end()); 00263 ExitBlocks.erase(std::unique(ExitBlocks.begin(), ExitBlocks.end()), 00264 ExitBlocks.end()); 00265 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 00266 LoopBlocks.push_back(ExitBlocks[i] = SplitBlock(ExitBlocks[i], true)); 00267 00268 // Next step, clone all of the basic blocks that make up the loop (including 00269 // the loop preheader and exit blocks), keeping track of the mapping between 00270 // the instructions and blocks. 00271 std::vector<BasicBlock*> NewBlocks; 00272 NewBlocks.reserve(LoopBlocks.size()); 00273 std::map<const Value*, Value*> ValueMap; 00274 for (unsigned i = 0, e = LoopBlocks.size(); i != e; ++i) { 00275 NewBlocks.push_back(CloneBasicBlock(LoopBlocks[i], ValueMap, ".us", F)); 00276 ValueMap[LoopBlocks[i]] = NewBlocks.back(); // Keep the BB mapping. 00277 } 00278 00279 // Splice the newly inserted blocks into the function right before the 00280 // original preheader. 00281 F->getBasicBlockList().splice(LoopBlocks[0], F->getBasicBlockList(), 00282 NewBlocks[0], F->end()); 00283 00284 // Now we create the new Loop object for the versioned loop. 00285 Loop *NewLoop = CloneLoop(L, L->getParentLoop(), ValueMap, LI); 00286 if (Loop *Parent = L->getParentLoop()) { 00287 // Make sure to add the cloned preheader and exit blocks to the parent loop 00288 // as well. 00289 Parent->addBasicBlockToLoop(NewBlocks[0], *LI); 00290 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 00291 Parent->addBasicBlockToLoop(cast<BasicBlock>(ValueMap[ExitBlocks[i]]), 00292 *LI); 00293 } 00294 00295 // Rewrite the code to refer to itself. 00296 for (unsigned i = 0, e = NewBlocks.size(); i != e; ++i) 00297 for (BasicBlock::iterator I = NewBlocks[i]->begin(), 00298 E = NewBlocks[i]->end(); I != E; ++I) 00299 RemapInstruction(I, ValueMap); 00300 00301 // If the instructions are used outside of the loop, insert a PHI node in any 00302 // exit blocks dominated by the instruction. 00303 for (unsigned i = 0, e = NewBlocks.size(); i != e; ++i) 00304 for (BasicBlock::iterator OI = LoopBlocks[i]->begin(), 00305 E = LoopBlocks[i]->end(); OI != E; ++OI) 00306 if (!OI->use_empty()) { 00307 std::map<const Value*,Value*>::iterator OII = ValueMap.find(OI); 00308 // The PHINode rewriting stuff can insert stores that are not in the 00309 // mapping. Don't mess around with them. 00310 if (OII != ValueMap.end()) { 00311 Instruction *NI = cast<Instruction>(OII->second); 00312 InsertPHINodesForUsesOutsideLoop(OI, NI, *DS, L, NewLoop, 00313 ExitBlocks, ValueMap); 00314 } 00315 } 00316 00317 // Rewrite the original preheader to select between versions of the loop. 00318 assert(isa<BranchInst>(OrigPreheader->getTerminator()) && 00319 cast<BranchInst>(OrigPreheader->getTerminator())->isUnconditional() && 00320 OrigPreheader->getTerminator()->getSuccessor(0) == LoopBlocks[0] && 00321 "Preheader splitting did not work correctly!"); 00322 // Remove the unconditional branch to LoopBlocks[0]. 00323 OrigPreheader->getInstList().pop_back(); 00324 00325 // Insert a conditional branch on LIC to the two preheaders. The original 00326 // code is the true version and the new code is the false version. 00327 new BranchInst(LoopBlocks[0], NewBlocks[0], LIC, OrigPreheader); 00328 00329 // Now we rewrite the original code to know that the condition is true and the 00330 // new code to know that the condition is false. 00331 RewriteLoopBodyWithConditionConstant(L, LIC, true); 00332 RewriteLoopBodyWithConditionConstant(NewLoop, LIC, false); 00333 ++NumUnswitched; 00334 00335 // Try to unswitch each of our new loops now! 00336 visitLoop(L); 00337 visitLoop(NewLoop); 00338 } 00339 00340 // RewriteLoopBodyWithConditionConstant - We know that the boolean value LIC has 00341 // the value specified by Val in the specified loop. Rewrite any uses of LIC or 00342 // of properties correlated to it. 00343 void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, 00344 bool Val) { 00345 // FIXME: Support correlated properties, like: 00346 // for (...) 00347 // if (li1 < li2) 00348 // ... 00349 // if (li1 > li2) 00350 // ... 00351 ConstantBool *BoolVal = ConstantBool::get(Val); 00352 00353 std::vector<User*> Users(LIC->use_begin(), LIC->use_end()); 00354 for (unsigned i = 0, e = Users.size(); i != e; ++i) 00355 if (Instruction *U = dyn_cast<Instruction>(Users[i])) 00356 if (L->contains(U->getParent())) 00357 U->replaceUsesOfWith(LIC, BoolVal); 00358 }