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