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