lib/Analysis/LiveValues.cpp

   1 //===- LiveValues.cpp - Liveness information for LLVM IR Values. ----------===//
   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 file defines the implementation for the LLVM IR Value liveness
  11 // analysis pass.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Analysis/LiveValues.h"
  16 #include "llvm/Instructions.h"
  17 #include "llvm/Analysis/Dominators.h"
  18 #include "llvm/Analysis/LoopInfo.h"
  19 using namespace llvm;
  20
  21 namespace llvm {
  22   FunctionPass *createLiveValuesPass() { return new LiveValues(); }
  23 }
  24
  25 char LiveValues::ID = 0;
  26 INITIALIZE_PASS_BEGIN(LiveValues, "live-values",
  27                 "Value Liveness Analysis", false, true)
  28 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
  29 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
  30 INITIALIZE_PASS_END(LiveValues, "live-values",
  31                 "Value Liveness Analysis", false, true)
  32
  33 LiveValues::LiveValues() : FunctionPass(ID) {
  34   initializeLiveValuesPass(*PassRegistry::getPassRegistry());
  35 }
  36
  37 void LiveValues::getAnalysisUsage(AnalysisUsage &AU) const {
  38   AU.addRequired<DominatorTree>();
  39   AU.addRequired<LoopInfo>();
  40   AU.setPreservesAll();
  41 }
  42
  43 bool LiveValues::runOnFunction(Function &F) {
  44   DT = &getAnalysis<DominatorTree>();
  45   LI = &getAnalysis<LoopInfo>();
  46
  47   // This pass' values are computed lazily, so there's nothing to do here.
  48
  49   return false;
  50 }
  51
  52 void LiveValues::releaseMemory() {
  53   Memos.clear();
  54 }
  55
  56 /// isUsedInBlock - Test if the given value is used in the given block.
  57 ///
  58 bool LiveValues::isUsedInBlock(const Value *V, const BasicBlock *BB) {
  59   Memo &M = getMemo(V);
  60   return M.Used.count(BB);
  61 }
  62
  63 /// isLiveThroughBlock - Test if the given value is known to be
  64 /// live-through the given block, meaning that the block is properly
  65 /// dominated by the value's definition, and there exists a block
  66 /// reachable from it that contains a use. This uses a conservative
  67 /// approximation that errs on the side of returning false.
  68 ///
  69 bool LiveValues::isLiveThroughBlock(const Value *V,
  70                                     const BasicBlock *BB) {
  71   Memo &M = getMemo(V);
  72   return M.LiveThrough.count(BB);
  73 }
  74
  75 /// isKilledInBlock - Test if the given value is known to be killed in
  76 /// the given block, meaning that the block contains a use of the value,
  77 /// and no blocks reachable from the block contain a use. This uses a
  78 /// conservative approximation that errs on the side of returning false.
  79 ///
  80 bool LiveValues::isKilledInBlock(const Value *V, const BasicBlock *BB) {
  81   Memo &M = getMemo(V);
  82   return M.Killed.count(BB);
  83 }
  84
  85 /// getMemo - Retrieve an existing Memo for the given value if one
  86 /// is available, otherwise compute a new one.
  87 ///
  88 LiveValues::Memo &LiveValues::getMemo(const Value *V) {
  89   DenseMap<const Value *, Memo>::iterator I = Memos.find(V);
  90   if (I != Memos.end())
  91     return I->second;
  92   return compute(V);
  93 }
  94
  95 /// getImmediateDominator - A handy utility for the specific DominatorTree
  96 /// query that we need here.
  97 ///
  98 static const BasicBlock *getImmediateDominator(const BasicBlock *BB,
  99                                                const DominatorTree *DT) {
 100   DomTreeNode *Node = DT->getNode(const_cast<BasicBlock *>(BB))->getIDom();
 101   return Node ? Node->getBlock() : 0;
 102 }
 103
 104 /// compute - Compute a new Memo for the given value.
 105 ///
 106 LiveValues::Memo &LiveValues::compute(const Value *V) {
 107   Memo &M = Memos[V];
 108
 109   // Determine the block containing the definition.
 110   const BasicBlock *DefBB;
 111   // Instructions define values with meaningful live ranges.
 112   if (const Instruction *I = dyn_cast<Instruction>(V))
 113     DefBB = I->getParent();
 114   // Arguments can be analyzed as values defined in the entry block.
 115   else if (const Argument *A = dyn_cast<Argument>(V))
 116     DefBB = &A->getParent()->getEntryBlock();
 117   // Constants and other things aren't meaningful here, so just
 118   // return having computed an empty Memo so that we don't come
 119   // here again. The assumption here is that client code won't
 120   // be asking about such values very often.
 121   else
 122     return M;
 123
 124   // Determine if the value is defined inside a loop. This is used
 125   // to track whether the value is ever used outside the loop, so
 126   // it'll be set to null if the value is either not defined in a
 127   // loop or used outside the loop in which it is defined.
 128   const Loop *L = LI->getLoopFor(DefBB);
 129
 130   // Track whether the value is used anywhere outside of the block
 131   // in which it is defined.
 132   bool LiveOutOfDefBB = false;
 133
 134   // Examine each use of the value.
 135   for (Value::const_use_iterator I = V->use_begin(), E = V->use_end();
 136        I != E; ++I) {
 137     const User *U = *I;
 138     const BasicBlock *UseBB = cast<Instruction>(U)->getParent();
 139
 140     // Note the block in which this use occurs.
 141     M.Used.insert(UseBB);
 142
 143     // If the use block doesn't have successors, the value can be
 144     // considered killed.
 145     if (succ_begin(UseBB) == succ_end(UseBB))
 146       M.Killed.insert(UseBB);
 147
 148     // Observe whether the value is used outside of the loop in which
 149     // it is defined. Switch to an enclosing loop if necessary.
 150     for (; L; L = L->getParentLoop())
 151       if (L->contains(UseBB))
 152         break;
 153
 154     // Search for live-through blocks.
 155     const BasicBlock *BB;
 156     if (const PHINode *PHI = dyn_cast<PHINode>(U)) {
 157       // For PHI nodes, start the search at the incoming block paired with the
 158       // incoming value, which must be dominated by the definition.
 159       unsigned Num = PHI->getIncomingValueNumForOperand(I.getOperandNo());
 160       BB = PHI->getIncomingBlock(Num);
 161
 162       // A PHI-node use means the value is live-out of it's defining block
 163       // even if that block also contains the only use.
 164       LiveOutOfDefBB = true;
 165     } else {
 166       // Otherwise just start the search at the use.
 167       BB = UseBB;
 168
 169       // Note if the use is outside the defining block.
 170       LiveOutOfDefBB |= UseBB != DefBB;
 171     }
 172
 173     // Climb the immediate dominator tree from the use to the definition
 174     // and mark all intermediate blocks as live-through.
 175     for (; BB != DefBB; BB = getImmediateDominator(BB, DT)) {
 176       if (BB != UseBB && !M.LiveThrough.insert(BB))
 177         break;
 178     }
 179   }
 180
 181   // If the value is defined inside a loop and is not live outside
 182   // the loop, then each exit block of the loop in which the value
 183   // is used is a kill block.
 184   if (L) {
 185     SmallVector<BasicBlock *, 4> ExitingBlocks;
 186     L->getExitingBlocks(ExitingBlocks);
 187     for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
 188       const BasicBlock *ExitingBlock = ExitingBlocks[i];
 189       if (M.Used.count(ExitingBlock))
 190         M.Killed.insert(ExitingBlock);
 191     }
 192   }
 193
 194   // If the value was never used outside the block in which it was
 195   // defined, it's killed in that block.
 196   if (!LiveOutOfDefBB)
 197     M.Killed.insert(DefBB);
 198
 199   return M;
 200 }