lib/Transforms/Utils/LCSSA.cpp

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