LLVM API Documentation
00001 //===-- LCSSA.cpp - Convert loops into loop-closed SSA form ---------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by Owen Anderson and is distributed under the 00006 // University of Illinois Open Source 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 #include "llvm/Transforms/Scalar.h" 00031 #include "llvm/Constants.h" 00032 #include "llvm/Pass.h" 00033 #include "llvm/Function.h" 00034 #include "llvm/Instructions.h" 00035 #include "llvm/ADT/SetVector.h" 00036 #include "llvm/ADT/Statistic.h" 00037 #include "llvm/Analysis/Dominators.h" 00038 #include "llvm/Analysis/LoopInfo.h" 00039 #include "llvm/Support/CFG.h" 00040 #include <algorithm> 00041 #include <map> 00042 00043 using namespace llvm; 00044 00045 namespace { 00046 static Statistic<> NumLCSSA("lcssa", 00047 "Number of live out of a loop variables"); 00048 00049 class LCSSA : public FunctionPass { 00050 public: 00051 00052 00053 LoopInfo *LI; // Loop information 00054 DominatorTree *DT; // Dominator Tree for the current Function... 00055 DominanceFrontier *DF; // Current Dominance Frontier 00056 std::vector<BasicBlock*> LoopBlocks; 00057 00058 virtual bool runOnFunction(Function &F); 00059 bool visitSubloop(Loop* L); 00060 void processInstruction(Instruction* Instr, 00061 const std::vector<BasicBlock*>& exitBlocks); 00062 00063 /// This transformation requires natural loop information & requires that 00064 /// loop preheaders be inserted into the CFG. It maintains both of these, 00065 /// as well as the CFG. It also requires dominator information. 00066 /// 00067 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00068 AU.setPreservesCFG(); 00069 AU.addRequiredID(LoopSimplifyID); 00070 AU.addPreservedID(LoopSimplifyID); 00071 AU.addRequired<LoopInfo>(); 00072 AU.addRequired<DominatorTree>(); 00073 AU.addRequired<DominanceFrontier>(); 00074 } 00075 private: 00076 SetVector<Instruction*> getLoopValuesUsedOutsideLoop(Loop *L); 00077 Value *getValueDominatingBlock(BasicBlock *BB, 00078 std::map<BasicBlock*, Value*>& PotDoms) { 00079 return getValueDominatingDTNode(DT->getNode(BB), PotDoms); 00080 } 00081 Value *getValueDominatingDTNode(DominatorTree::Node *Node, 00082 std::map<BasicBlock*, Value*>& PotDoms); 00083 00084 /// inLoop - returns true if the given block is within the current loop 00085 const bool inLoop(BasicBlock* B) { 00086 return std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), B); 00087 } 00088 }; 00089 00090 RegisterOpt<LCSSA> X("lcssa", "Loop-Closed SSA Form Pass"); 00091 } 00092 00093 FunctionPass *llvm::createLCSSAPass() { return new LCSSA(); } 00094 const PassInfo *llvm::LCSSAID = X.getPassInfo(); 00095 00096 /// runOnFunction - Process all loops in the function, inner-most out. 00097 bool LCSSA::runOnFunction(Function &F) { 00098 bool changed = false; 00099 00100 LI = &getAnalysis<LoopInfo>(); 00101 DF = &getAnalysis<DominanceFrontier>(); 00102 DT = &getAnalysis<DominatorTree>(); 00103 00104 for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) { 00105 changed |= visitSubloop(*I); 00106 } 00107 00108 return changed; 00109 } 00110 00111 /// visitSubloop - Recursively process all subloops, and then process the given 00112 /// loop if it has live-out values. 00113 bool LCSSA::visitSubloop(Loop* L) { 00114 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) 00115 visitSubloop(*I); 00116 00117 // Speed up queries by creating a sorted list of blocks 00118 LoopBlocks.clear(); 00119 LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end()); 00120 std::sort(LoopBlocks.begin(), LoopBlocks.end()); 00121 00122 SetVector<Instruction*> AffectedValues = getLoopValuesUsedOutsideLoop(L); 00123 00124 // If no values are affected, we can save a lot of work, since we know that 00125 // nothing will be changed. 00126 if (AffectedValues.empty()) 00127 return false; 00128 00129 std::vector<BasicBlock*> exitBlocks; 00130 L->getExitBlocks(exitBlocks); 00131 00132 00133 // Iterate over all affected values for this loop and insert Phi nodes 00134 // for them in the appropriate exit blocks 00135 00136 for (SetVector<Instruction*>::iterator I = AffectedValues.begin(), 00137 E = AffectedValues.end(); I != E; ++I) { 00138 processInstruction(*I, exitBlocks); 00139 } 00140 00141 assert(L->isLCSSAForm()); 00142 00143 return true; 00144 } 00145 00146 /// processInstruction - Given a live-out instruction, insert LCSSA Phi nodes, 00147 /// eliminate all out-of-loop uses. 00148 void LCSSA::processInstruction(Instruction* Instr, 00149 const std::vector<BasicBlock*>& exitBlocks) 00150 { 00151 ++NumLCSSA; // We are applying the transformation 00152 00153 std::map<BasicBlock*, Value*> Phis; 00154 00155 // Add the base instruction to the Phis list. This makes tracking down 00156 // the dominating values easier when we're filling in Phi nodes. This will 00157 // be removed later, before we perform use replacement. 00158 Phis[Instr->getParent()] = Instr; 00159 00160 // Phi nodes that need to be IDF-processed 00161 std::vector<PHINode*> workList; 00162 00163 for (std::vector<BasicBlock*>::const_iterator BBI = exitBlocks.begin(), 00164 BBE = exitBlocks.end(); BBI != BBE; ++BBI) { 00165 Value*& phi = Phis[*BBI]; 00166 if (phi == 0 && 00167 DT->getNode(Instr->getParent())->dominates(DT->getNode(*BBI))) { 00168 phi = new PHINode(Instr->getType(), Instr->getName()+".lcssa", 00169 (*BBI)->begin()); 00170 workList.push_back(cast<PHINode>(phi)); 00171 } 00172 } 00173 00174 // Phi nodes that need to have their incoming values filled. 00175 std::vector<PHINode*> needIncomingValues; 00176 00177 // Calculate the IDF of these LCSSA Phi nodes, inserting new Phi's where 00178 // necessary. Keep track of these new Phi's in the "Phis" map. 00179 while (!workList.empty()) { 00180 PHINode *CurPHI = workList.back(); 00181 workList.pop_back(); 00182 00183 // Even though we've removed this Phi from the work list, we still need 00184 // to fill in its incoming values. 00185 needIncomingValues.push_back(CurPHI); 00186 00187 // Get the current Phi's DF, and insert Phi nodes. Add these new 00188 // nodes to our worklist. 00189 DominanceFrontier::const_iterator it = DF->find(CurPHI->getParent()); 00190 if (it != DF->end()) { 00191 const DominanceFrontier::DomSetType &S = it->second; 00192 for (DominanceFrontier::DomSetType::const_iterator P = S.begin(), 00193 PE = S.end(); P != PE; ++P) { 00194 if (DT->getNode(Instr->getParent())->dominates(DT->getNode(*P))) { 00195 Value *&Phi = Phis[*P]; 00196 if (Phi == 0) { 00197 // Still doesn't have operands... 00198 Phi = new PHINode(Instr->getType(), Instr->getName()+".lcssa", 00199 (*P)->begin()); 00200 00201 workList.push_back(cast<PHINode>(Phi)); 00202 } 00203 } 00204 } 00205 } 00206 } 00207 00208 // Fill in all Phis we've inserted that need their incoming values filled in. 00209 for (std::vector<PHINode*>::iterator IVI = needIncomingValues.begin(), 00210 IVE = needIncomingValues.end(); IVI != IVE; ++IVI) 00211 for (pred_iterator PI = pred_begin((*IVI)->getParent()), 00212 E = pred_end((*IVI)->getParent()); PI != E; ++PI) 00213 (*IVI)->addIncoming(getValueDominatingBlock(*PI, Phis), 00214 *PI); 00215 00216 // Find all uses of the affected value, and replace them with the 00217 // appropriate Phi. 00218 std::vector<Instruction*> Uses; 00219 for (Instruction::use_iterator UI = Instr->use_begin(), UE = Instr->use_end(); 00220 UI != UE; ++UI) { 00221 Instruction* use = cast<Instruction>(*UI); 00222 BasicBlock* UserBB = use->getParent(); 00223 if (PHINode* p = dyn_cast<PHINode>(use)) { 00224 unsigned OperandNo = UI.getOperandNo(); 00225 UserBB = p->getIncomingBlock(OperandNo/2); 00226 } 00227 00228 // Don't need to update uses within the loop body. 00229 if (!inLoop(use->getParent())) 00230 Uses.push_back(use); 00231 } 00232 00233 for (std::vector<Instruction*>::iterator II = Uses.begin(), IE = Uses.end(); 00234 II != IE; ++II) { 00235 if (PHINode* phi = dyn_cast<PHINode>(*II)) { 00236 for (unsigned int i = 0; i < phi->getNumIncomingValues(); ++i) { 00237 if (phi->getIncomingValue(i) == Instr) { 00238 Value* dominator = 00239 getValueDominatingBlock(phi->getIncomingBlock(i), Phis); 00240 phi->setIncomingValue(i, dominator); 00241 } 00242 } 00243 } else { 00244 Value *NewVal = getValueDominatingBlock((*II)->getParent(), Phis); 00245 (*II)->replaceUsesOfWith(Instr, NewVal); 00246 } 00247 } 00248 } 00249 00250 /// getLoopValuesUsedOutsideLoop - Return any values defined in the loop that 00251 /// are used by instructions outside of it. 00252 SetVector<Instruction*> LCSSA::getLoopValuesUsedOutsideLoop(Loop *L) { 00253 00254 // FIXME: For large loops, we may be able to avoid a lot of use-scanning 00255 // by using dominance information. In particular, if a block does not 00256 // dominate any of the loop exits, then none of the values defined in the 00257 // block could be used outside the loop. 00258 00259 SetVector<Instruction*> AffectedValues; 00260 for (Loop::block_iterator BB = L->block_begin(), E = L->block_end(); 00261 BB != E; ++BB) { 00262 for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; ++I) 00263 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; 00264 ++UI) { 00265 BasicBlock *UserBB = cast<Instruction>(*UI)->getParent(); 00266 if (PHINode* p = dyn_cast<PHINode>(*UI)) { 00267 unsigned OperandNo = UI.getOperandNo(); 00268 UserBB = p->getIncomingBlock(OperandNo/2); 00269 } 00270 00271 if (!inLoop(UserBB)) { 00272 AffectedValues.insert(I); 00273 break; 00274 } 00275 } 00276 } 00277 return AffectedValues; 00278 } 00279 00280 /// getValueDominatingBlock - Return the value within the potential dominators 00281 /// map that dominates the given block. 00282 Value *LCSSA::getValueDominatingDTNode(DominatorTree::Node *Node, 00283 std::map<BasicBlock*, Value*>& PotDoms) { 00284 // FIXME: The following assertion should be in place rather than the if 00285 // statement. Currently, this is due to the fact that LCSSA isn't smart 00286 // enough to avoid inserting IDF Phis that don't dominate any uses. In some 00287 // of those cases, it could ask us to provide a dominating value for a block 00288 // that has none, so we need to return undef. 00289 //assert(Node != 0 && "Didn't find dom value?"); 00290 if (Node == 0) return UndefValue::get(PotDoms.begin()->second->getType()); 00291 00292 Value *&CacheSlot = PotDoms[Node->getBlock()]; 00293 if (CacheSlot) return CacheSlot; 00294 00295 // Otherwise, return the value of the idom and remember this for next time. 00296 return CacheSlot = getValueDominatingDTNode(Node->getIDom(), PotDoms); 00297 }