LLVM API Documentation
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 }