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