LLVM API Documentation
00001 //===- LiveValues.h - 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 interface for the LLVM IR Value liveness 00011 // analysis pass. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #ifndef LLVM_ANALYSIS_LIVEVALUES_H 00016 #define LLVM_ANALYSIS_LIVEVALUES_H 00017 00018 #include "llvm/Pass.h" 00019 #include "llvm/ADT/DenseMap.h" 00020 #include "llvm/ADT/SmallPtrSet.h" 00021 00022 namespace llvm { 00023 00024 class DominatorTree; 00025 class LoopInfo; 00026 class Value; 00027 00028 /// LiveValues - Analysis that provides liveness information for 00029 /// LLVM IR Values. 00030 /// 00031 class LiveValues : public FunctionPass { 00032 DominatorTree *DT; 00033 LoopInfo *LI; 00034 00035 /// Memo - A bunch of state to be associated with a value. 00036 /// 00037 struct Memo { 00038 /// Used - The set of blocks which contain a use of the value. 00039 /// 00040 SmallPtrSet<const BasicBlock *, 4> Used; 00041 00042 /// LiveThrough - A conservative approximation of the set of blocks in 00043 /// which the value is live-through, meaning blocks properly dominated 00044 /// by the definition, and from which blocks containing uses of the 00045 /// value are reachable. 00046 /// 00047 SmallPtrSet<const BasicBlock *, 4> LiveThrough; 00048 00049 /// Killed - A conservative approximation of the set of blocks in which 00050 /// the value is used and not live-out. 00051 /// 00052 SmallPtrSet<const BasicBlock *, 4> Killed; 00053 }; 00054 00055 /// Memos - Remembers the Memo for each Value. This is populated on 00056 /// demand. 00057 /// 00058 DenseMap<const Value *, Memo> Memos; 00059 00060 /// getMemo - Retrieve an existing Memo for the given value if one 00061 /// is available, otherwise compute a new one. 00062 /// 00063 Memo &getMemo(const Value *V); 00064 00065 /// compute - Compute a new Memo for the given value. 00066 /// 00067 Memo &compute(const Value *V); 00068 00069 public: 00070 static char ID; 00071 LiveValues(); 00072 00073 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 00074 virtual bool runOnFunction(Function &F); 00075 virtual void releaseMemory(); 00076 00077 /// isUsedInBlock - Test if the given value is used in the given block. 00078 /// 00079 bool isUsedInBlock(const Value *V, const BasicBlock *BB); 00080 00081 /// isLiveThroughBlock - Test if the given value is known to be 00082 /// live-through the given block, meaning that the block is properly 00083 /// dominated by the value's definition, and there exists a block 00084 /// reachable from it that contains a use. This uses a conservative 00085 /// approximation that errs on the side of returning false. 00086 /// 00087 bool isLiveThroughBlock(const Value *V, const BasicBlock *BB); 00088 00089 /// isKilledInBlock - Test if the given value is known to be killed in 00090 /// the given block, meaning that the block contains a use of the value, 00091 /// and no blocks reachable from the block contain a use. This uses a 00092 /// conservative approximation that errs on the side of returning false. 00093 /// 00094 bool isKilledInBlock(const Value *V, const BasicBlock *BB); 00095 }; 00096 00097 /// createLiveValuesPass - This creates an instance of the LiveValues pass. 00098 /// 00099 FunctionPass *createLiveValuesPass(); 00100 00101 } 00102 00103 #endif