LLVM API Documentation

LiveValues.h

Go to the documentation of this file.
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