LLVM API Documentation
00001 //===-- LCSSA.cpp - Convert loops into loop-closed SSA form ---------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This pass transforms loops by placing phi nodes at the end of the loops for 00011 // all values that are live across the loop boundary. For example, it turns 00012 // the left into the right code: 00013 // 00014 // for (...) for (...) 00015 // if (c) if (c) 00016 // X1 = ... X1 = ... 00017 // else else 00018 // X2 = ... X2 = ... 00019 // X3 = phi(X1, X2) X3 = phi(X1, X2) 00020 // ... = X3 + 4 X4 = phi(X3) 00021 // ... = X4 + 4 00022 // 00023 // This is still valid LLVM; the extra phi nodes are purely redundant, and will 00024 // be trivially eliminated by InstCombine. The major benefit of this 00025 // transformation is that it makes many other loop optimizations, such as 00026 // LoopUnswitching, simpler. 00027 // 00028 //===----------------------------------------------------------------------===// 00029 00030 #define DEBUG_TYPE "lcssa" 00031 #include "llvm/Transforms/Scalar.h" 00032 #include "llvm/Constants.h" 00033 #include "llvm/Pass.h" 00034 #include "llvm/Function.h" 00035 #include "llvm/Instructions.h" 00036 #include "llvm/LLVMContext.h" 00037 #include "llvm/ADT/SetVector.h" 00038 #include "llvm/ADT/Statistic.h" 00039 #include "llvm/Analysis/Dominators.h" 00040 #include "llvm/Analysis/LoopPass.h" 00041 #include "llvm/Analysis/ScalarEvolution.h" 00042 #include "llvm/Support/CFG.h" 00043 #include "llvm/Support/Compiler.h" 00044 #include "llvm/Support/PredIteratorCache.h" 00045 #include <algorithm> 00046 #include <map> 00047 using namespace llvm; 00048 00049 STATISTIC(NumLCSSA, "Number of live out of a loop variables"); 00050 00051 namespace { 00052 struct VISIBILITY_HIDDEN LCSSA : public LoopPass { 00053 static char ID; // Pass identification, replacement for typeid 00054 LCSSA() : LoopPass(&ID) {} 00055 00056 // Cached analysis information for the current function. 00057 LoopInfo *LI; 00058 DominatorTree *DT; 00059 std::vector<BasicBlock*> LoopBlocks; 00060 PredIteratorCache PredCache; 00061 00062 virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 00063 00064 void ProcessInstruction(Instruction* Instr, 00065 const SmallVector<BasicBlock*, 8>& exitBlocks); 00066 00067 /// This transformation requires natural loop information & requires that 00068 /// loop preheaders be inserted into the CFG. It maintains both of these, 00069 /// as well as the CFG. It also requires dominator information. 00070 /// 00071 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00072 AU.setPreservesCFG(); 00073 AU.addRequiredID(LoopSimplifyID); 00074 AU.addPreservedID(LoopSimplifyID); 00075 AU.addRequired<LoopInfo>(); 00076 AU.addPreserved<LoopInfo>(); 00077 AU.addRequired<DominatorTree>(); 00078 AU.addPreserved<ScalarEvolution>(); 00079 AU.addPreserved<DominatorTree>(); 00080 00081 // Request DominanceFrontier now, even though LCSSA does 00082 // not use it. This allows Pass Manager to schedule Dominance 00083 // Frontier early enough such that one LPPassManager can handle 00084 // multiple loop transformation passes. 00085 AU.addRequired<DominanceFrontier>(); 00086 AU.addPreserved<DominanceFrontier>(); 00087 } 00088 private: 00089 void getLoopValuesUsedOutsideLoop(Loop *L, 00090 SetVector<Instruction*> &AffectedValues, 00091 const SmallVector<BasicBlock*, 8>& exitBlocks); 00092 00093 Value *GetValueForBlock(DomTreeNode *BB, Instruction *OrigInst, 00094 DenseMap<DomTreeNode*, Value*> &Phis); 00095 00096 /// inLoop - returns true if the given block is within the current loop 00097 bool inLoop(BasicBlock* B) { 00098 return std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), B); 00099 } 00100 }; 00101 } 00102 00103 char LCSSA::ID = 0; 00104 static RegisterPass<LCSSA> X("lcssa", "Loop-Closed SSA Form Pass"); 00105 00106 Pass *llvm::createLCSSAPass() { return new LCSSA(); } 00107 const PassInfo *const llvm::LCSSAID = &X; 00108 00109 /// runOnFunction - Process all loops in the function, inner-most out. 00110 bool LCSSA::runOnLoop(Loop *L, LPPassManager &LPM) { 00111 PredCache.clear(); 00112 00113 LI = &LPM.getAnalysis<LoopInfo>(); 00114 DT = &getAnalysis<DominatorTree>(); 00115 00116 // Speed up queries by creating a sorted list of blocks 00117 LoopBlocks.clear(); 00118 LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end()); 00119 std::sort(LoopBlocks.begin(), LoopBlocks.end()); 00120 00121 SmallVector<BasicBlock*, 8> exitBlocks; 00122 L->getExitBlocks(exitBlocks); 00123 00124 SetVector<Instruction*> AffectedValues; 00125 getLoopValuesUsedOutsideLoop(L, AffectedValues, exitBlocks); 00126 00127 // If no values are affected, we can save a lot of work, since we know that 00128 // nothing will be changed. 00129 if (AffectedValues.empty()) 00130 return false; 00131 00132 // Iterate over all affected values for this loop and insert Phi nodes 00133 // for them in the appropriate exit blocks 00134 00135 for (SetVector<Instruction*>::iterator I = AffectedValues.begin(), 00136 E = AffectedValues.end(); I != E; ++I) 00137 ProcessInstruction(*I, exitBlocks); 00138 00139 assert(L->isLCSSAForm()); 00140 00141 return true; 00142 } 00143 00144 /// processInstruction - Given a live-out instruction, insert LCSSA Phi nodes, 00145 /// eliminate all out-of-loop uses. 00146 void LCSSA::ProcessInstruction(Instruction *Instr, 00147 const SmallVector<BasicBlock*, 8>& exitBlocks) { 00148 ++NumLCSSA; // We are applying the transformation 00149 00150 // Keep track of the blocks that have the value available already. 00151 DenseMap<DomTreeNode*, Value*> Phis; 00152 00153 BasicBlock *DomBB = Instr->getParent(); 00154 00155 // Invoke instructions are special in that their result value is not available 00156 // along their unwind edge. The code below tests to see whether DomBB dominates 00157 // the value, so adjust DomBB to the normal destination block, which is 00158 // effectively where the value is first usable. 00159 if (InvokeInst *Inv = dyn_cast<InvokeInst>(Instr)) 00160 DomBB = Inv->getNormalDest(); 00161 00162 DomTreeNode *DomNode = DT->getNode(DomBB); 00163 00164 // Insert the LCSSA phi's into the exit blocks (dominated by the value), and 00165 // add them to the Phi's map. 00166 for (SmallVector<BasicBlock*, 8>::const_iterator BBI = exitBlocks.begin(), 00167 BBE = exitBlocks.end(); BBI != BBE; ++BBI) { 00168 BasicBlock *BB = *BBI; 00169 DomTreeNode *ExitBBNode = DT->getNode(BB); 00170 Value *&Phi = Phis[ExitBBNode]; 00171 if (!Phi && DT->dominates(DomNode, ExitBBNode)) { 00172 PHINode *PN = PHINode::Create(Instr->getType(), Instr->getName()+".lcssa", 00173 BB->begin()); 00174 PN->reserveOperandSpace(PredCache.GetNumPreds(BB)); 00175 00176 // Remember that this phi makes the value alive in this block. 00177 Phi = PN; 00178 00179 // Add inputs from inside the loop for this PHI. 00180 for (BasicBlock** PI = PredCache.GetPreds(BB); *PI; ++PI) 00181 PN->addIncoming(Instr, *PI); 00182 } 00183 } 00184 00185 00186 // Record all uses of Instr outside the loop. We need to rewrite these. The 00187 // LCSSA phis won't be included because they use the value in the loop. 00188 for (Value::use_iterator UI = Instr->use_begin(), E = Instr->use_end(); 00189 UI != E;) { 00190 BasicBlock *UserBB = cast<Instruction>(*UI)->getParent(); 00191 if (PHINode *P = dyn_cast<PHINode>(*UI)) { 00192 UserBB = P->getIncomingBlock(UI); 00193 } 00194 00195 // If the user is in the loop, don't rewrite it! 00196 if (UserBB == Instr->getParent() || inLoop(UserBB)) { 00197 ++UI; 00198 continue; 00199 } 00200 00201 // Otherwise, patch up uses of the value with the appropriate LCSSA Phi, 00202 // inserting PHI nodes into join points where needed. 00203 Value *Val = GetValueForBlock(DT->getNode(UserBB), Instr, Phis); 00204 00205 // Preincrement the iterator to avoid invalidating it when we change the 00206 // value. 00207 Use &U = UI.getUse(); 00208 ++UI; 00209 U.set(Val); 00210 } 00211 } 00212 00213 /// getLoopValuesUsedOutsideLoop - Return any values defined in the loop that 00214 /// are used by instructions outside of it. 00215 void LCSSA::getLoopValuesUsedOutsideLoop(Loop *L, 00216 SetVector<Instruction*> &AffectedValues, 00217 const SmallVector<BasicBlock*, 8>& exitBlocks) { 00218 // FIXME: For large loops, we may be able to avoid a lot of use-scanning 00219 // by using dominance information. In particular, if a block does not 00220 // dominate any of the loop exits, then none of the values defined in the 00221 // block could be used outside the loop. 00222 for (Loop::block_iterator BB = L->block_begin(), BE = L->block_end(); 00223 BB != BE; ++BB) { 00224 for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; ++I) 00225 for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); UI != UE; 00226 ++UI) { 00227 BasicBlock *UserBB = cast<Instruction>(*UI)->getParent(); 00228 if (PHINode* p = dyn_cast<PHINode>(*UI)) { 00229 UserBB = p->getIncomingBlock(UI); 00230 } 00231 00232 if (*BB != UserBB && !inLoop(UserBB)) { 00233 AffectedValues.insert(I); 00234 break; 00235 } 00236 } 00237 } 00238 } 00239 00240 /// GetValueForBlock - Get the value to use within the specified basic block. 00241 /// available values are in Phis. 00242 Value *LCSSA::GetValueForBlock(DomTreeNode *BB, Instruction *OrigInst, 00243 DenseMap<DomTreeNode*, Value*> &Phis) { 00244 // If there is no dominator info for this BB, it is unreachable. 00245 if (BB == 0) 00246 return UndefValue::get(OrigInst->getType()); 00247 00248 // If we have already computed this value, return the previously computed val. 00249 if (Phis.count(BB)) return Phis[BB]; 00250 00251 DomTreeNode *IDom = BB->getIDom(); 00252 00253 // Otherwise, there are two cases: we either have to insert a PHI node or we 00254 // don't. We need to insert a PHI node if this block is not dominated by one 00255 // of the exit nodes from the loop (the loop could have multiple exits, and 00256 // though the value defined *inside* the loop dominated all its uses, each 00257 // exit by itself may not dominate all the uses). 00258 // 00259 // The simplest way to check for this condition is by checking to see if the 00260 // idom is in the loop. If so, we *know* that none of the exit blocks 00261 // dominate this block. Note that we *know* that the block defining the 00262 // original instruction is in the idom chain, because if it weren't, then the 00263 // original value didn't dominate this use. 00264 if (!inLoop(IDom->getBlock())) { 00265 // Idom is not in the loop, we must still be "below" the exit block and must 00266 // be fully dominated by the value live in the idom. 00267 Value* val = GetValueForBlock(IDom, OrigInst, Phis); 00268 Phis.insert(std::make_pair(BB, val)); 00269 return val; 00270 } 00271 00272 BasicBlock *BBN = BB->getBlock(); 00273 00274 // Otherwise, the idom is the loop, so we need to insert a PHI node. Do so 00275 // now, then get values to fill in the incoming values for the PHI. 00276 PHINode *PN = PHINode::Create(OrigInst->getType(), 00277 OrigInst->getName() + ".lcssa", BBN->begin()); 00278 PN->reserveOperandSpace(PredCache.GetNumPreds(BBN)); 00279 Phis.insert(std::make_pair(BB, PN)); 00280 00281 // Fill in the incoming values for the block. 00282 for (BasicBlock** PI = PredCache.GetPreds(BBN); *PI; ++PI) 00283 PN->addIncoming(GetValueForBlock(DT->getNode(*PI), OrigInst, Phis), *PI); 00284 return PN; 00285 } 00286