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