LLVM API Documentation

LiveValues.cpp

Go to the documentation of this file.
00001 //===- LiveValues.cpp - Liveness information for LLVM IR Values. ----------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines the implementation for the LLVM IR Value liveness
00011 // analysis pass.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #include "llvm/Analysis/LiveValues.h"
00016 #include "llvm/Analysis/Dominators.h"
00017 #include "llvm/Analysis/LoopInfo.h"
00018 using namespace llvm;
00019 
00020 FunctionPass *llvm::createLiveValuesPass() { return new LiveValues(); }
00021 
00022 char LiveValues::ID = 0;
00023 static RegisterPass<LiveValues>
00024 X("live-values", "Value Liveness Analysis", false, true);
00025 
00026 LiveValues::LiveValues() : FunctionPass(&ID) {}
00027 
00028 void LiveValues::getAnalysisUsage(AnalysisUsage &AU) const {
00029   AU.addRequired<DominatorTree>();
00030   AU.addRequired<LoopInfo>();
00031   AU.setPreservesAll();
00032 }
00033 
00034 bool LiveValues::runOnFunction(Function &F) {
00035   DT = &getAnalysis<DominatorTree>();
00036   LI = &getAnalysis<LoopInfo>();
00037 
00038   // This pass' values are computed lazily, so there's nothing to do here.
00039 
00040   return false;
00041 }
00042 
00043 void LiveValues::releaseMemory() {
00044   Memos.clear();
00045 }
00046 
00047 /// isUsedInBlock - Test if the given value is used in the given block.
00048 ///
00049 bool LiveValues::isUsedInBlock(const Value *V, const BasicBlock *BB) {
00050   Memo &M = getMemo(V);
00051   return M.Used.count(BB);
00052 }
00053 
00054 /// isLiveThroughBlock - Test if the given value is known to be
00055 /// live-through the given block, meaning that the block is properly
00056 /// dominated by the value's definition, and there exists a block
00057 /// reachable from it that contains a use. This uses a conservative
00058 /// approximation that errs on the side of returning false.
00059 ///
00060 bool LiveValues::isLiveThroughBlock(const Value *V,
00061                                     const BasicBlock *BB) {
00062   Memo &M = getMemo(V);
00063   return M.LiveThrough.count(BB);
00064 }
00065 
00066 /// isKilledInBlock - Test if the given value is known to be killed in
00067 /// the given block, meaning that the block contains a use of the value,
00068 /// and no blocks reachable from the block contain a use. This uses a
00069 /// conservative approximation that errs on the side of returning false.
00070 ///
00071 bool LiveValues::isKilledInBlock(const Value *V, const BasicBlock *BB) {
00072   Memo &M = getMemo(V);
00073   return M.Killed.count(BB);
00074 }
00075 
00076 /// getMemo - Retrieve an existing Memo for the given value if one
00077 /// is available, otherwise compute a new one.
00078 ///
00079 LiveValues::Memo &LiveValues::getMemo(const Value *V) {
00080   DenseMap<const Value *, Memo>::iterator I = Memos.find(V);
00081   if (I != Memos.end())
00082     return I->second;
00083   return compute(V);
00084 }
00085 
00086 /// getImmediateDominator - A handy utility for the specific DominatorTree
00087 /// query that we need here.
00088 ///
00089 static const BasicBlock *getImmediateDominator(const BasicBlock *BB,
00090                                                const DominatorTree *DT) {
00091   DomTreeNode *Node = DT->getNode(const_cast<BasicBlock *>(BB))->getIDom();
00092   return Node ? Node->getBlock() : 0;
00093 }
00094 
00095 /// compute - Compute a new Memo for the given value.
00096 ///
00097 LiveValues::Memo &LiveValues::compute(const Value *V) {
00098   Memo &M = Memos[V];
00099 
00100   // Determine the block containing the definition.
00101   const BasicBlock *DefBB;
00102   // Instructions define values with meaningful live ranges.
00103   if (const Instruction *I = dyn_cast<Instruction>(V))
00104     DefBB = I->getParent();
00105   // Arguments can be analyzed as values defined in the entry block.
00106   else if (const Argument *A = dyn_cast<Argument>(V))
00107     DefBB = &A->getParent()->getEntryBlock();
00108   // Constants and other things aren't meaningful here, so just
00109   // return having computed an empty Memo so that we don't come
00110   // here again. The assumption here is that client code won't
00111   // be asking about such values very often.
00112   else
00113     return M;
00114 
00115   // Determine if the value is defined inside a loop. This is used
00116   // to track whether the value is ever used outside the loop, so
00117   // it'll be set to null if the value is either not defined in a
00118   // loop or used outside the loop in which it is defined.
00119   const Loop *L = LI->getLoopFor(DefBB);
00120 
00121   // Track whether the value is used anywhere outside of the block
00122   // in which it is defined.
00123   bool LiveOutOfDefBB = false;
00124 
00125   // Examine each use of the value.
00126   for (Value::use_const_iterator I = V->use_begin(), E = V->use_end();
00127        I != E; ++I) {
00128     const User *U = *I;
00129     const BasicBlock *UseBB = cast<Instruction>(U)->getParent();
00130 
00131     // Note the block in which this use occurs.
00132     M.Used.insert(UseBB);
00133 
00134     // If the use block doesn't have successors, the value can be
00135     // considered killed.
00136     if (succ_begin(UseBB) == succ_end(UseBB))
00137       M.Killed.insert(UseBB);
00138 
00139     // Observe whether the value is used outside of the loop in which
00140     // it is defined. Switch to an enclosing loop if necessary.
00141     for (; L; L = L->getParentLoop())
00142       if (L->contains(UseBB))
00143         break;
00144 
00145     // Search for live-through blocks.
00146     const BasicBlock *BB;
00147     if (const PHINode *PHI = dyn_cast<PHINode>(U)) {
00148       // For PHI nodes, start the search at the incoming block paired with the
00149       // incoming value, which must be dominated by the definition.
00150       unsigned Num = PHI->getIncomingValueNumForOperand(I.getOperandNo());
00151       BB = PHI->getIncomingBlock(Num);
00152 
00153       // A PHI-node use means the value is live-out of it's defining block
00154       // even if that block also contains the only use.
00155       LiveOutOfDefBB = true;
00156     } else {
00157       // Otherwise just start the search at the use.
00158       BB = UseBB;
00159 
00160       // Note if the use is outside the defining block.
00161       LiveOutOfDefBB |= UseBB != DefBB;
00162     }
00163 
00164     // Climb the immediate dominator tree from the use to the definition
00165     // and mark all intermediate blocks as live-through.
00166     for (; BB != DefBB; BB = getImmediateDominator(BB, DT)) {
00167       if (BB != UseBB && !M.LiveThrough.insert(BB))
00168         break;
00169     }
00170   }
00171 
00172   // If the value is defined inside a loop and is not live outside
00173   // the loop, then each exit block of the loop in which the value
00174   // is used is a kill block.
00175   if (L) {
00176     SmallVector<BasicBlock *, 4> ExitingBlocks;
00177     L->getExitingBlocks(ExitingBlocks);
00178     for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
00179       const BasicBlock *ExitingBlock = ExitingBlocks[i];
00180       if (M.Used.count(ExitingBlock))
00181         M.Killed.insert(ExitingBlock);
00182     }
00183   }
00184 
00185   // If the value was never used outside the the block in which it was
00186   // defined, it's killed in that block.
00187   if (!LiveOutOfDefBB)
00188     M.Killed.insert(DefBB);
00189 
00190   return M;
00191 }