include/llvm/Analysis/SparsePropagation.h

   1 //===- SparsePropagation.h - Sparse Conditional Property Propagation ------===//
   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 implements an abstract sparse conditional propagation algorithm,
  11 // modeled after SCCP, but with a customizable lattice function.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_ANALYSIS_SPARSE_PROPAGATION_H
  16 #define LLVM_ANALYSIS_SPARSE_PROPAGATION_H
  17
  18 #include "llvm/ADT/DenseMap.h"
  19 #include "llvm/ADT/SmallPtrSet.h"
  20 #include "llvm/ADT/SmallVector.h"
  21 #include <vector>
  22 #include <set>
  23
  24 namespace llvm {
  25   class Value;
  26   class Constant;
  27   class Instruction;
  28   class PHINode;
  29   class TerminatorInst;
  30   class BasicBlock;
  31   class Function;
  32   class SparseSolver;
  33
  34 /// AbstractLatticeFunction - This class is implemented by the dataflow instance
  35 /// to specify what the lattice values are and what how they handle merges etc.
  36 /// This gives the client the power to compute lattice values from instructions,
  37 /// constants, etc.  The requirement is that lattice values must all fit into
  38 /// a void*.  If a void* is not sufficient, the implementation should use this
  39 /// pointer to be a pointer into a uniquing set or something.
  40 ///
  41 class AbstractLatticeFunction {
  42 public:
  43   typedef void *LatticeVal;
  44 private:
  45   LatticeVal UndefVal, OverdefinedVal, UntrackedVal;
  46 public:
  47   AbstractLatticeFunction(LatticeVal undefVal, LatticeVal overdefinedVal,
  48                           LatticeVal untrackedVal) {
  49     UndefVal = undefVal;
  50     OverdefinedVal = overdefinedVal;
  51     UntrackedVal = untrackedVal;
  52   }
  53   virtual ~AbstractLatticeFunction();
  54
  55   LatticeVal getUndefVal()       const { return UndefVal; }
  56   LatticeVal getOverdefinedVal() const { return OverdefinedVal; }
  57   LatticeVal getUntrackedVal()   const { return UntrackedVal; }
  58
  59   /// IsUntrackedValue - If the specified Value is something that is obviously
  60   /// uninteresting to the analysis (and would always return UntrackedVal),
  61   /// this function can return true to avoid pointless work.
  62   virtual bool IsUntrackedValue(Value *V) {
  63     return false;
  64   }
  65
  66   /// ComputeConstant - Given a constant value, compute and return a lattice
  67   /// value corresponding to the specified constant.
  68   virtual LatticeVal ComputeConstant(Constant *C) {
  69     return getOverdefinedVal(); // always safe
  70   }
  71
  72   /// GetConstant - If the specified lattice value is representable as an LLVM
  73   /// constant value, return it.  Otherwise return null.  The returned value
  74   /// must be in the same LLVM type as Val.
  75   virtual Constant *GetConstant(LatticeVal LV, Value *Val, SparseSolver &SS) {
  76     return 0;
  77   }
  78
  79   /// MergeValues - Compute and return the merge of the two specified lattice
  80   /// values.  Merging should only move one direction down the lattice to
  81   /// guarantee convergence (toward overdefined).
  82   virtual LatticeVal MergeValues(LatticeVal X, LatticeVal Y) {
  83     return getOverdefinedVal(); // always safe, never useful.
  84   }
  85
  86   /// ComputeInstructionState - Given an instruction and a vector of its operand
  87   /// values, compute the result value of the instruction.
  88   virtual LatticeVal ComputeInstructionState(Instruction &I, SparseSolver &SS) {
  89     return getOverdefinedVal(); // always safe, never useful.
  90   }
  91
  92   /// PrintValue - Render the specified lattice value to the specified stream.
  93   virtual void PrintValue(LatticeVal V, std::ostream &OS);
  94 };
  95
  96
  97 /// SparseSolver - This class is a general purpose solver for Sparse Conditional
  98 /// Propagation with a programmable lattice function.
  99 ///
 100 class SparseSolver {
 101   typedef AbstractLatticeFunction::LatticeVal LatticeVal;
 102
 103   /// LatticeFunc - This is the object that knows the lattice and how to do
 104   /// compute transfer functions.
 105   AbstractLatticeFunction *LatticeFunc;
 106
 107   DenseMap<Value*, LatticeVal> ValueState;  // The state each value is in.
 108   SmallPtrSet<BasicBlock*, 16> BBExecutable;   // The bbs that are executable.
 109
 110   std::vector<Instruction*> InstWorkList;   // Worklist of insts to process.
 111
 112   std::vector<BasicBlock*> BBWorkList;  // The BasicBlock work list
 113
 114   /// KnownFeasibleEdges - Entries in this set are edges which have already had
 115   /// PHI nodes retriggered.
 116   typedef std::pair<BasicBlock*,BasicBlock*> Edge;
 117   std::set<Edge> KnownFeasibleEdges;
 118
 119   SparseSolver(const SparseSolver&);    // DO NOT IMPLEMENT
 120   void operator=(const SparseSolver&);  // DO NOT IMPLEMENT
 121 public:
 122   SparseSolver(AbstractLatticeFunction *Lattice) : LatticeFunc(Lattice) {}
 123   ~SparseSolver() {
 124     delete LatticeFunc;
 125   }
 126
 127   /// Solve - Solve for constants and executable blocks.
 128   ///
 129   void Solve(Function &F);
 130
 131   void Print(Function &F, std::ostream &OS);
 132
 133   /// getLatticeState - Return the LatticeVal object that corresponds to the
 134   /// value.  If an value is not in the map, it is returned as untracked,
 135   /// unlike the getOrInitValueState method.
 136   LatticeVal getLatticeState(Value *V) const {
 137     DenseMap<Value*, LatticeVal>::iterator I = ValueState.find(V);
 138     return I != ValueState.end() ? I->second : LatticeFunc->getUntrackedVal();
 139   }
 140
 141   /// getOrInitValueState - Return the LatticeVal object that corresponds to the
 142   /// value, initializing the value's state if it hasn't been entered into the
 143   /// map yet.   This function is necessary because not all values should start
 144   /// out in the underdefined state... Arguments should be overdefined, and
 145   /// constants should be marked as constants.
 146   ///
 147   LatticeVal getOrInitValueState(Value *V);
 148
 149 private:
 150   /// UpdateState - When the state for some instruction is potentially updated,
 151   /// this function notices and adds I to the worklist if needed.
 152   void UpdateState(Instruction &Inst, LatticeVal V);
 153
 154   /// MarkBlockExecutable - This method can be used by clients to mark all of
 155   /// the blocks that are known to be intrinsically live in the processed unit.
 156   void MarkBlockExecutable(BasicBlock *BB);
 157
 158   /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB
 159   /// work list if it is not already executable.
 160   void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest);
 161
 162   /// getFeasibleSuccessors - Return a vector of booleans to indicate which
 163   /// successors are reachable from a given terminator instruction.
 164   void getFeasibleSuccessors(TerminatorInst &TI, SmallVectorImpl<bool> &Succs);
 165
 166   /// isEdgeFeasible - Return true if the control flow edge from the 'From'
 167   /// basic block to the 'To' basic block is currently feasible...
 168   bool isEdgeFeasible(BasicBlock *From, BasicBlock *To);
 169
 170   void visitInst(Instruction &I);
 171   void visitPHINode(PHINode &I);
 172   void visitTerminatorInst(TerminatorInst &TI);
 173
 174 };
 175
 176 } // end namespace llvm
 177
 178 #endif // LLVM_ANALYSIS_SPARSE_PROPAGATION_H