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