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