1 //===- LiveValues.h - 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 interface for the LLVM IR Value liveness
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_ANALYSIS_LIVEVALUES_H
16 #define LLVM_ANALYSIS_LIVEVALUES_H
18 #include "llvm/Pass.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/SmallPtrSet.h"
28 /// LiveValues - Analysis that provides liveness information for
31 class LiveValues : public FunctionPass {
35 /// Memo - A bunch of state to be associated with a value.
38 /// Used - The set of blocks which contain a use of the value.
40 SmallPtrSet<const BasicBlock *, 4> Used;
42 /// LiveThrough - A conservative approximation of the set of blocks in
43 /// which the value is live-through, meaning blocks properly dominated
44 /// by the definition, and from which blocks containing uses of the
45 /// value are reachable.
47 SmallPtrSet<const BasicBlock *, 4> LiveThrough;
49 /// Killed - A conservative approximation of the set of blocks in which
50 /// the value is used and not live-out.
52 SmallPtrSet<const BasicBlock *, 4> Killed;
55 /// Memos - Remembers the Memo for each Value. This is populated on
58 DenseMap<const Value *, Memo> Memos;
60 /// getMemo - Retrieve an existing Memo for the given value if one
61 /// is available, otherwise compute a new one.
63 Memo &getMemo(const Value *V);
65 /// compute - Compute a new Memo for the given value.
67 Memo &compute(const Value *V);
73 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
74 virtual bool runOnFunction(Function &F);
75 virtual void releaseMemory();
77 /// isUsedInBlock - Test if the given value is used in the given block.
79 bool isUsedInBlock(const Value *V, const BasicBlock *BB);
81 /// isLiveThroughBlock - Test if the given value is known to be
82 /// live-through the given block, meaning that the block is properly
83 /// dominated by the value's definition, and there exists a block
84 /// reachable from it that contains a use. This uses a conservative
85 /// approximation that errs on the side of returning false.
87 bool isLiveThroughBlock(const Value *V, const BasicBlock *BB);
89 /// isKilledInBlock - Test if the given value is known to be killed in
90 /// the given block, meaning that the block contains a use of the value,
91 /// and no blocks reachable from the block contain a use. This uses a
92 /// conservative approximation that errs on the side of returning false.
94 bool isKilledInBlock(const Value *V, const BasicBlock *BB);
97 /// createLiveValuesPass - This creates an instance of the LiveValues pass.
99 FunctionPass *createLiveValuesPass();