include/llvm/Analysis/LiveValues.h

   1 //===- LiveValues.h - Liveness information for LLVM IR Values. ------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the interface for the LLVM IR Value liveness
  11 // analysis pass.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_ANALYSIS_LIVEVALUES_H
  16 #define LLVM_ANALYSIS_LIVEVALUES_H
  17
  18 #include "llvm/Pass.h"
  19 #include "llvm/ADT/DenseMap.h"
  20 #include "llvm/ADT/SmallPtrSet.h"
  21
  22 namespace llvm {
  23
  24 class DominatorTree;
  25 class LoopInfo;
  26 class Value;
  27
  28 /// LiveValues - Analysis that provides liveness information for
  29 /// LLVM IR Values.
  30 ///
  31 class LiveValues : public FunctionPass {
  32   DominatorTree *DT;
  33   LoopInfo *LI;
  34
  35   /// Memo - A bunch of state to be associated with a value.
  36   ///
  37   struct Memo {
  38     /// Used - The set of blocks which contain a use of the value.
  39     ///
  40     SmallPtrSet<const BasicBlock *, 4> Used;
  41
  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.
  46     ///
  47     SmallPtrSet<const BasicBlock *, 4> LiveThrough;
  48
  49     /// Killed - A conservative approximation of the set of blocks in which
  50     /// the value is used and not live-out.
  51     ///
  52     SmallPtrSet<const BasicBlock *, 4> Killed;
  53   };
  54
  55   /// Memos - Remembers the Memo for each Value. This is populated on
  56   /// demand.
  57   ///
  58   DenseMap<const Value *, Memo> Memos;
  59
  60   /// getMemo - Retrieve an existing Memo for the given value if one
  61   /// is available, otherwise compute a new one.
  62   ///
  63   Memo &getMemo(const Value *V);
  64
  65   /// compute - Compute a new Memo for the given value.
  66   ///
  67   Memo &compute(const Value *V);
  68
  69 public:
  70   static char ID;
  71   LiveValues();
  72
  73   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
  74   virtual bool runOnFunction(Function &F);
  75   virtual void releaseMemory();
  76
  77   /// isUsedInBlock - Test if the given value is used in the given block.
  78   ///
  79   bool isUsedInBlock(const Value *V, const BasicBlock *BB);
  80
  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.
  86   ///
  87   bool isLiveThroughBlock(const Value *V, const BasicBlock *BB);
  88
  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.
  93   ///
  94   bool isKilledInBlock(const Value *V, const BasicBlock *BB);
  95 };
  96
  97 }  // end namespace llvm
  98
  99 #endif