1 //===-- LCSSA.cpp - Convert loops into loop-closed SSA form ---------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file was developed by Owen Anderson and is distributed under the 6 // University of Illinois Open Source License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This pass transforms loops by placing phi nodes at the end of the loops for 11 // all values that are live across the loop boundary. For example, it turns 12 // the left into the right code: 13 // 14 // for (...) for (...) 15 // if (c) if(c) 16 // X1 = ... X1 = ... 17 // else else 18 // X2 = ... X2 = ... 19 // X3 = phi(X1, X2) X3 = phi(X1, X2) 20 // ... = X3 + 4 X4 = phi(X3) 21 // ... = X4 + 4 22 // 23 // This is still valid LLVM; the extra phi nodes are purely redundant, and will 24 // be trivially eliminated by InstCombine. The major benefit of this 25 // transformation is that it makes many other loop optimizations, such as 26 // LoopUnswitching, simpler. 27 // 28 //===----------------------------------------------------------------------===// 29 30 #include "llvm/Transforms/Scalar.h" 31 #include "llvm/Pass.h" 32 #include "llvm/Function.h" 33 #include "llvm/Instructions.h" 34 #include "llvm/ADT/Statistic.h" 35 #include "llvm/Analysis/Dominators.h" 36 #include "llvm/Analysis/LoopInfo.h" 37 #include "llvm/Support/CFG.h" 38 #include <algorithm> 39 #include <map> 40 #include <vector> 41 42 using namespace llvm; 43 44 namespace { 45 static Statistic<> NumLCSSA("lcssa", 46 "Number of live out of a loop variables"); 47 48 class LCSSA : public FunctionPass { 49 public: 50 51 52 LoopInfo *LI; // Loop information 53 DominatorTree *DT; // Dominator Tree for the current Loop... 54 DominanceFrontier *DF; // Current Dominance Frontier 55 56 virtual bool runOnFunction(Function &F); 57 bool visitSubloop(Loop* L); 58 59 /// This transformation requires natural loop information & requires that 60 /// loop preheaders be inserted into the CFG. It maintains both of these, 61 /// as well as the CFG. It also requires dominator information. 62 /// 63 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 64 AU.setPreservesCFG(); 65 AU.addRequiredID(LoopSimplifyID); 66 AU.addPreservedID(LoopSimplifyID); 67 AU.addRequired<LoopInfo>(); 68 AU.addPreserved<LoopInfo>(); 69 AU.addRequired<DominatorTree>(); 70 AU.addRequired<DominanceFrontier>(); 71 } 72 private: 73 std::set<Instruction*> getLoopValuesUsedOutsideLoop(Loop *L, 74 std::vector<BasicBlock*> LoopBlocks); 75 }; 76 77 RegisterOpt<LCSSA> X("lcssa", "Loop-Closed SSA Form Pass"); 78 } 79 80 FunctionPass *llvm::createLCSSAPass() { return new LCSSA(); } 81 82 bool LCSSA::runOnFunction(Function &F) { 83 bool changed = false; 84 LI = &getAnalysis<LoopInfo>(); 85 DF = &getAnalysis<DominanceFrontier>(); 86 DT = &getAnalysis<DominatorTree>(); 87 88 for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) { 89 changed |= visitSubloop(*I); 90 } 91 92 return changed; 93 } 94 95 bool LCSSA::visitSubloop(Loop* L) { 96 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) 97 visitSubloop(*I); 98 99 // Speed up queries by creating a sorted list of blocks 100 std::vector<BasicBlock*> LoopBlocks(L->block_begin(), L->block_end()); 101 std::sort(LoopBlocks.begin(), LoopBlocks.end()); 102 103 std::set<Instruction*> AffectedValues = getLoopValuesUsedOutsideLoop(L, 104 LoopBlocks); 105 106 std::vector<BasicBlock*> exitBlocks; 107 L->getExitBlocks(exitBlocks); 108 109 // Phi nodes that need to be IDF-processed 110 std::vector<PHINode*> workList; 111 112 // Iterate over all affected values for this loop and insert Phi nodes 113 // for them in the appropriate exit blocks 114 std::map<BasicBlock*, PHINode*> ExitPhis; 115 for (std::set<Instruction*>::iterator I = AffectedValues.begin(), 116 E = AffectedValues.end(); I != E; ++I) { 117 ++NumLCSSA; // We are applying the transformation 118 for (std::vector<BasicBlock*>::iterator BBI = exitBlocks.begin(), 119 BBE = exitBlocks.end(); BBI != BBE; ++BBI) { 120 PHINode *phi = new PHINode((*I)->getType(), "lcssa"); 121 (*BBI)->getInstList().insert((*BBI)->front(), phi); 122 workList.push_back(phi); 123 ExitPhis[*BBI] = phi; 124 125 // Since LoopSimplify has been run, we know that all of these predecessors 126 // are in the loop, so just hook them up in the obvious manner. 127 for (pred_iterator PI = pred_begin(*BBI), PE = pred_end(*BBI); PI != PE; 128 ++PI) 129 phi->addIncoming(*I, *PI); 130 } 131 132 // Calculate the IDF of these LCSSA Phi nodes, inserting new Phi's where 133 // necessary. Keep track of these new Phi's in DFPhis. 134 std::map<BasicBlock*, PHINode*> DFPhis; 135 for (std::vector<PHINode*>::iterator DFI = workList.begin(), 136 E = workList.end(); DFI != E; ++DFI) { 137 138 // Get the current Phi's DF, and insert Phi nodes. Add these new 139 // nodes to our worklist. 140 DominanceFrontier::const_iterator it = DF->find((*DFI)->getParent()); 141 if (it != DF->end()) { 142 const DominanceFrontier::DomSetType &S = it->second; 143 for (DominanceFrontier::DomSetType::const_iterator P = S.begin(), 144 PE = S.end(); P != PE; ++P) { 145 if (DFPhis[*P] == 0) { 146 // Still doesn't have operands... 147 PHINode *phi = new PHINode((*DFI)->getType(), "lcssa"); 148 (*P)->getInstList().insert((*P)->front(), phi); 149 DFPhis[*P] = phi; 150 151 workList.push_back(phi); 152 } 153 } 154 } 155 156 // Get the predecessor blocks of the current Phi, and use them to hook up 157 // the operands of the current Phi to any members of DFPhis that dominate 158 // it. This is a nop for the Phis inserted directly in the exit blocks, 159 // since they are not dominated by any members of DFPhis. 160 for (pred_iterator PI = pred_begin((*DFI)->getParent()), 161 E = pred_end((*DFI)->getParent()); PI != E; ++PI) 162 for (std::map<BasicBlock*, PHINode*>::iterator MI = DFPhis.begin(), 163 ME = DFPhis.end(); MI != ME; ++MI) 164 if (DT->getNode((*MI).first)->dominates(DT->getNode(*PI))) { 165 (*DFI)->addIncoming((*MI).second, *PI); 166 167 // Since dominate() is not cheap, don't do it more than we have to. 168 break; 169 } 170 } 171 172 173 174 // Find all uses of the affected value, and replace them with the 175 // appropriate Phi. 176 for (Instruction::use_iterator UI = (*I)->use_begin(), UE=(*I)->use_end(); 177 UI != UE; ++UI) { 178 Instruction* use = cast<Instruction>(*UI); 179 180 // Don't need to update uses within the loop body 181 if (!std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), 182 use->getParent())) { 183 184 for (std::map<BasicBlock*, PHINode*>::iterator DI = ExitPhis.begin(), 185 DE = ExitPhis.end(); DI != DE; ++DI) { 186 if (DT->getNode((*DI).first)->dominates( \ 187 DT->getNode(use->getParent())) && use != (*DI).second) { 188 use->replaceUsesOfWith(*I, (*DI).second); 189 break; 190 } 191 } 192 193 for (std::map<BasicBlock*, PHINode*>::iterator DI = DFPhis.begin(), 194 DE = DFPhis.end(); DI != DE; ++DI) { 195 if (DT->getNode((*DI).first)->dominates( \ 196 DT->getNode(use->getParent()))) { 197 use->replaceUsesOfWith(*I, (*DI).second); 198 break; 199 } 200 } 201 } 202 } 203 } 204 205 return true; // FIXME: Should be more intelligent in our return value. 206 } 207 208 /// getLoopValuesUsedOutsideLoop - Return any values defined in the loop that 209 /// are used by instructions outside of it. 210 std::set<Instruction*> LCSSA::getLoopValuesUsedOutsideLoop(Loop *L, 211 std::vector<BasicBlock*> LoopBlocks) { 212 213 std::set<Instruction*> AffectedValues; 214 for (Loop::block_iterator BB = L->block_begin(), E = L->block_end(); 215 BB != E; ++BB) { 216 for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; ++I) 217 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; 218 ++UI) { 219 BasicBlock *UserBB = cast<Instruction>(*UI)->getParent(); 220 if (!std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), UserBB)) 221 AffectedValues.insert(I); 222 } 223 } 224 return AffectedValues; 225 } 226