1 //===-- LCSSA.cpp - Convert loops into loop-closed SSA form ---------------===// 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 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 #define DEBUG_TYPE "lcssa" 31 #include "llvm/Transforms/Scalar.h" 32 #include "llvm/Constants.h" 33 #include "llvm/Pass.h" 34 #include "llvm/Function.h" 35 #include "llvm/Instructions.h" 36 #include "llvm/LLVMContext.h" 37 #include "llvm/ADT/SetVector.h" 38 #include "llvm/ADT/Statistic.h" 39 #include "llvm/Analysis/Dominators.h" 40 #include "llvm/Analysis/LoopPass.h" 41 #include "llvm/Analysis/ScalarEvolution.h" 42 #include "llvm/Support/CFG.h" 43 #include "llvm/Support/Compiler.h" 44 #include "llvm/Support/PredIteratorCache.h" 45 #include <algorithm> 46 #include <map> 47 using namespace llvm; 48 49 STATISTIC(NumLCSSA, "Number of live out of a loop variables"); 50 51 namespace { 52 struct VISIBILITY_HIDDEN LCSSA : public LoopPass { 53 static char ID; // Pass identification, replacement for typeid 54 LCSSA() : LoopPass(&ID) {} 55 56 // Cached analysis information for the current function. 57 LoopInfo *LI; 58 DominatorTree *DT; 59 std::vector<BasicBlock*> LoopBlocks; 60 PredIteratorCache PredCache; 61 Loop *L; 62 63 virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 64 65 void ProcessInstruction(Instruction* Instr, 66 const SmallVector<BasicBlock*, 8>& exitBlocks); 67 68 /// This transformation requires natural loop information & requires that 69 /// loop preheaders be inserted into the CFG. It maintains both of these, 70 /// as well as the CFG. It also requires dominator information. 71 /// 72 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 73 AU.setPreservesCFG(); 74 AU.addRequiredID(LoopSimplifyID); 75 AU.addPreservedID(LoopSimplifyID); 76 AU.addRequiredTransitive<LoopInfo>(); 77 AU.addPreserved<LoopInfo>(); 78 AU.addRequiredTransitive<DominatorTree>(); 79 AU.addPreserved<ScalarEvolution>(); 80 AU.addPreserved<DominatorTree>(); 81 82 // Request DominanceFrontier now, even though LCSSA does 83 // not use it. This allows Pass Manager to schedule Dominance 84 // Frontier early enough such that one LPPassManager can handle 85 // multiple loop transformation passes. 86 AU.addRequired<DominanceFrontier>(); 87 AU.addPreserved<DominanceFrontier>(); 88 } 89 private: 90 91 /// verifyAnalysis() - Verify loop nest. 92 virtual void verifyAnalysis() const { 93 // Check the special guarantees that LCSSA makes. 94 assert(L->isLCSSAForm() && "LCSSA form not preserved!"); 95 } 96 97 void getLoopValuesUsedOutsideLoop(Loop *L, 98 SetVector<Instruction*> &AffectedValues, 99 const SmallVector<BasicBlock*, 8>& exitBlocks); 100 101 Value *GetValueForBlock(DomTreeNode *BB, Instruction *OrigInst, 102 DenseMap<DomTreeNode*, Value*> &Phis); 103 104 /// inLoop - returns true if the given block is within the current loop 105 bool inLoop(BasicBlock* B) { 106 return std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), B); 107 } 108 }; 109 } 110 111 char LCSSA::ID = 0; 112 static RegisterPass<LCSSA> X("lcssa", "Loop-Closed SSA Form Pass"); 113 114 Pass *llvm::createLCSSAPass() { return new LCSSA(); } 115 const PassInfo *const llvm::LCSSAID = &X; 116 117 /// runOnFunction - Process all loops in the function, inner-most out. 118 bool LCSSA::runOnLoop(Loop *l, LPPassManager &LPM) { 119 L = l; 120 PredCache.clear(); 121 122 LI = &LPM.getAnalysis<LoopInfo>(); 123 DT = &getAnalysis<DominatorTree>(); 124 125 // Speed up queries by creating a sorted list of blocks 126 LoopBlocks.clear(); 127 LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end()); 128 std::sort(LoopBlocks.begin(), LoopBlocks.end()); 129 130 SmallVector<BasicBlock*, 8> exitBlocks; 131 L->getExitBlocks(exitBlocks); 132 133 SetVector<Instruction*> AffectedValues; 134 getLoopValuesUsedOutsideLoop(L, AffectedValues, exitBlocks); 135 136 // If no values are affected, we can save a lot of work, since we know that 137 // nothing will be changed. 138 if (AffectedValues.empty()) 139 return false; 140 141 // Iterate over all affected values for this loop and insert Phi nodes 142 // for them in the appropriate exit blocks 143 144 for (SetVector<Instruction*>::iterator I = AffectedValues.begin(), 145 E = AffectedValues.end(); I != E; ++I) 146 ProcessInstruction(*I, exitBlocks); 147 148 assert(L->isLCSSAForm()); 149 150 return true; 151 } 152 153 /// processInstruction - Given a live-out instruction, insert LCSSA Phi nodes, 154 /// eliminate all out-of-loop uses. 155 void LCSSA::ProcessInstruction(Instruction *Instr, 156 const SmallVector<BasicBlock*, 8>& exitBlocks) { 157 ++NumLCSSA; // We are applying the transformation 158 159 // Keep track of the blocks that have the value available already. 160 DenseMap<DomTreeNode*, Value*> Phis; 161 162 BasicBlock *DomBB = Instr->getParent(); 163 164 // Invoke instructions are special in that their result value is not available 165 // along their unwind edge. The code below tests to see whether DomBB dominates 166 // the value, so adjust DomBB to the normal destination block, which is 167 // effectively where the value is first usable. 168 if (InvokeInst *Inv = dyn_cast<InvokeInst>(Instr)) 169 DomBB = Inv->getNormalDest(); 170 171 DomTreeNode *DomNode = DT->getNode(DomBB); 172 173 // Insert the LCSSA phi's into the exit blocks (dominated by the value), and 174 // add them to the Phi's map. 175 for (SmallVector<BasicBlock*, 8>::const_iterator BBI = exitBlocks.begin(), 176 BBE = exitBlocks.end(); BBI != BBE; ++BBI) { 177 BasicBlock *BB = *BBI; 178 DomTreeNode *ExitBBNode = DT->getNode(BB); 179 Value *&Phi = Phis[ExitBBNode]; 180 if (!Phi && DT->dominates(DomNode, ExitBBNode)) { 181 PHINode *PN = PHINode::Create(Instr->getType(), Instr->getName()+".lcssa", 182 BB->begin()); 183 PN->reserveOperandSpace(PredCache.GetNumPreds(BB)); 184 185 // Remember that this phi makes the value alive in this block. 186 Phi = PN; 187 188 // Add inputs from inside the loop for this PHI. 189 for (BasicBlock** PI = PredCache.GetPreds(BB); *PI; ++PI) 190 PN->addIncoming(Instr, *PI); 191 } 192 } 193 194 195 // Record all uses of Instr outside the loop. We need to rewrite these. The 196 // LCSSA phis won't be included because they use the value in the loop. 197 for (Value::use_iterator UI = Instr->use_begin(), E = Instr->use_end(); 198 UI != E;) { 199 BasicBlock *UserBB = cast<Instruction>(*UI)->getParent(); 200 if (PHINode *P = dyn_cast<PHINode>(*UI)) 201 UserBB = P->getIncomingBlock(UI); 202 203 // If the user is in the loop, don't rewrite it! 204 if (UserBB == Instr->getParent() || inLoop(UserBB)) { 205 ++UI; 206 continue; 207 } 208 209 // Otherwise, patch up uses of the value with the appropriate LCSSA Phi, 210 // inserting PHI nodes into join points where needed. 211 Value *Val = GetValueForBlock(DT->getNode(UserBB), Instr, Phis); 212 213 // Preincrement the iterator to avoid invalidating it when we change the 214 // value. 215 Use &U = UI.getUse(); 216 ++UI; 217 U.set(Val); 218 } 219 } 220 221 /// getLoopValuesUsedOutsideLoop - Return any values defined in the loop that 222 /// are used by instructions outside of it. 223 void LCSSA::getLoopValuesUsedOutsideLoop(Loop *L, 224 SetVector<Instruction*> &AffectedValues, 225 const SmallVector<BasicBlock*, 8>& exitBlocks) { 226 // FIXME: For large loops, we may be able to avoid a lot of use-scanning 227 // by using dominance information. In particular, if a block does not 228 // dominate any of the loop exits, then none of the values defined in the 229 // block could be used outside the loop. 230 for (Loop::block_iterator BB = L->block_begin(), BE = L->block_end(); 231 BB != BE; ++BB) { 232 for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; ++I) 233 for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); 234 UI != UE; ++UI) { 235 BasicBlock *UserBB = cast<Instruction>(*UI)->getParent(); 236 if (PHINode *p = dyn_cast<PHINode>(*UI)) 237 UserBB = p->getIncomingBlock(UI); 238 239 if (*BB != UserBB && !inLoop(UserBB)) { 240 AffectedValues.insert(I); 241 break; 242 } 243 } 244 } 245 } 246 247 /// GetValueForBlock - Get the value to use within the specified basic block. 248 /// available values are in Phis. 249 Value *LCSSA::GetValueForBlock(DomTreeNode *BB, Instruction *OrigInst, 250 DenseMap<DomTreeNode*, Value*> &Phis) { 251 // If there is no dominator info for this BB, it is unreachable. 252 if (BB == 0) 253 return UndefValue::get(OrigInst->getType()); 254 255 // If we have already computed this value, return the previously computed val. 256 if (Phis.count(BB)) return Phis[BB]; 257 258 DomTreeNode *IDom = BB->getIDom(); 259 260 // Otherwise, there are two cases: we either have to insert a PHI node or we 261 // don't. We need to insert a PHI node if this block is not dominated by one 262 // of the exit nodes from the loop (the loop could have multiple exits, and 263 // though the value defined *inside* the loop dominated all its uses, each 264 // exit by itself may not dominate all the uses). 265 // 266 // The simplest way to check for this condition is by checking to see if the 267 // idom is in the loop. If so, we *know* that none of the exit blocks 268 // dominate this block. Note that we *know* that the block defining the 269 // original instruction is in the idom chain, because if it weren't, then the 270 // original value didn't dominate this use. 271 if (!inLoop(IDom->getBlock())) { 272 // Idom is not in the loop, we must still be "below" the exit block and must 273 // be fully dominated by the value live in the idom. 274 Value* val = GetValueForBlock(IDom, OrigInst, Phis); 275 Phis.insert(std::make_pair(BB, val)); 276 return val; 277 } 278 279 BasicBlock *BBN = BB->getBlock(); 280 281 // Otherwise, the idom is the loop, so we need to insert a PHI node. Do so 282 // now, then get values to fill in the incoming values for the PHI. 283 PHINode *PN = PHINode::Create(OrigInst->getType(), 284 OrigInst->getName() + ".lcssa", BBN->begin()); 285 PN->reserveOperandSpace(PredCache.GetNumPreds(BBN)); 286 Phis.insert(std::make_pair(BB, PN)); 287 288 // Fill in the incoming values for the block. 289 for (BasicBlock **PI = PredCache.GetPreds(BBN); *PI; ++PI) 290 PN->addIncoming(GetValueForBlock(DT->getNode(*PI), OrigInst, Phis), *PI); 291 return PN; 292 } 293 294