1 //===- LiveValues.cpp - Liveness information for LLVM IR Values. ----------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the implementation for the LLVM IR Value liveness
13 //===----------------------------------------------------------------------===//
15 #include "llvm/Analysis/LiveValues.h"
16 #include "llvm/Instructions.h"
17 #include "llvm/Analysis/Dominators.h"
18 #include "llvm/Analysis/LoopInfo.h"
22 FunctionPass *createLiveValuesPass() { return new LiveValues(); }
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)
33 LiveValues::LiveValues() : FunctionPass(ID) {
34 initializeLiveValuesPass(*PassRegistry::getPassRegistry());
37 void LiveValues::getAnalysisUsage(AnalysisUsage &AU) const {
38 AU.addRequired<DominatorTree>();
39 AU.addRequired<LoopInfo>();
43 bool LiveValues::runOnFunction(Function &F) {
44 DT = &getAnalysis<DominatorTree>();
45 LI = &getAnalysis<LoopInfo>();
47 // This pass' values are computed lazily, so there's nothing to do here.
52 void LiveValues::releaseMemory() {
56 /// isUsedInBlock - Test if the given value is used in the given block.
58 bool LiveValues::isUsedInBlock(const Value *V, const BasicBlock *BB) {
60 return M.Used.count(BB);
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.
69 bool LiveValues::isLiveThroughBlock(const Value *V,
70 const BasicBlock *BB) {
72 return M.LiveThrough.count(BB);
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.
80 bool LiveValues::isKilledInBlock(const Value *V, const BasicBlock *BB) {
82 return M.Killed.count(BB);
85 /// getMemo - Retrieve an existing Memo for the given value if one
86 /// is available, otherwise compute a new one.
88 LiveValues::Memo &LiveValues::getMemo(const Value *V) {
89 DenseMap<const Value *, Memo>::iterator I = Memos.find(V);
95 /// getImmediateDominator - A handy utility for the specific DominatorTree
96 /// query that we need here.
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;
104 /// compute - Compute a new Memo for the given value.
106 LiveValues::Memo &LiveValues::compute(const Value *V) {
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.
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);
130 // Track whether the value is used anywhere outside of the block
131 // in which it is defined.
132 bool LiveOutOfDefBB = false;
134 // Examine each use of the value.
135 for (Value::const_use_iterator I = V->use_begin(), E = V->use_end();
138 const BasicBlock *UseBB = cast<Instruction>(U)->getParent();
140 // Note the block in which this use occurs.
141 M.Used.insert(UseBB);
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);
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))
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);
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;
166 // Otherwise just start the search at the use.
169 // Note if the use is outside the defining block.
170 LiveOutOfDefBB |= UseBB != DefBB;
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))
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.
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);
194 // If the value was never used outside the block in which it was
195 // defined, it's killed in that block.
197 M.Killed.insert(DefBB);