LLVM API Documentation

SparsePropagation.h

Go to the documentation of this file.
00001 //===- SparsePropagation.h - Sparse Conditional Property Propagation ------===//
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 implements an abstract sparse conditional propagation algorithm,
00011 // modeled after SCCP, but with a customizable lattice function.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #ifndef LLVM_ANALYSIS_SPARSE_PROPAGATION_H
00016 #define LLVM_ANALYSIS_SPARSE_PROPAGATION_H
00017 
00018 #include "llvm/ADT/DenseMap.h"
00019 #include "llvm/ADT/SmallPtrSet.h"
00020 #include <iosfwd>
00021 #include <vector>
00022 #include <set>
00023 
00024 namespace llvm {
00025   class Value;
00026   class Constant;
00027   class Argument;
00028   class Instruction;
00029   class PHINode;
00030   class TerminatorInst;
00031   class BasicBlock;
00032   class Function;
00033   class SparseSolver;
00034   class LLVMContext;
00035 
00036   template<typename T> class SmallVectorImpl;
00037   
00038 /// AbstractLatticeFunction - This class is implemented by the dataflow instance
00039 /// to specify what the lattice values are and how they handle merges etc.
00040 /// This gives the client the power to compute lattice values from instructions,
00041 /// constants, etc.  The requirement is that lattice values must all fit into
00042 /// a void*.  If a void* is not sufficient, the implementation should use this
00043 /// pointer to be a pointer into a uniquing set or something.
00044 ///
00045 class AbstractLatticeFunction {
00046 public:
00047   typedef void *LatticeVal;
00048 private:
00049   LatticeVal UndefVal, OverdefinedVal, UntrackedVal;
00050 public:
00051   AbstractLatticeFunction(LatticeVal undefVal, LatticeVal overdefinedVal,
00052                           LatticeVal untrackedVal) {
00053     UndefVal = undefVal;
00054     OverdefinedVal = overdefinedVal;
00055     UntrackedVal = untrackedVal;
00056   }
00057   virtual ~AbstractLatticeFunction();
00058   
00059   LatticeVal getUndefVal()       const { return UndefVal; }
00060   LatticeVal getOverdefinedVal() const { return OverdefinedVal; }
00061   LatticeVal getUntrackedVal()   const { return UntrackedVal; }
00062   
00063   /// IsUntrackedValue - If the specified Value is something that is obviously
00064   /// uninteresting to the analysis (and would always return UntrackedVal),
00065   /// this function can return true to avoid pointless work.
00066   virtual bool IsUntrackedValue(Value *V) {
00067     return false;
00068   }
00069   
00070   /// ComputeConstant - Given a constant value, compute and return a lattice
00071   /// value corresponding to the specified constant.
00072   virtual LatticeVal ComputeConstant(Constant *C) {
00073     return getOverdefinedVal(); // always safe
00074   }
00075   
00076   /// GetConstant - If the specified lattice value is representable as an LLVM
00077   /// constant value, return it.  Otherwise return null.  The returned value
00078   /// must be in the same LLVM type as Val.
00079   virtual Constant *GetConstant(LatticeVal LV, Value *Val, SparseSolver &SS) {
00080     return 0;
00081   }
00082 
00083   /// ComputeArgument - Given a formal argument value, compute and return a
00084   /// lattice value corresponding to the specified argument.
00085   virtual LatticeVal ComputeArgument(Argument *I) {
00086     return getOverdefinedVal(); // always safe
00087   }
00088   
00089   /// MergeValues - Compute and return the merge of the two specified lattice
00090   /// values.  Merging should only move one direction down the lattice to
00091   /// guarantee convergence (toward overdefined).
00092   virtual LatticeVal MergeValues(LatticeVal X, LatticeVal Y) {
00093     return getOverdefinedVal(); // always safe, never useful.
00094   }
00095   
00096   /// ComputeInstructionState - Given an instruction and a vector of its operand
00097   /// values, compute the result value of the instruction.
00098   virtual LatticeVal ComputeInstructionState(Instruction &I, SparseSolver &SS) {
00099     return getOverdefinedVal(); // always safe, never useful.
00100   }
00101   
00102   /// PrintValue - Render the specified lattice value to the specified stream.
00103   virtual void PrintValue(LatticeVal V, std::ostream &OS);
00104 };
00105 
00106   
00107 /// SparseSolver - This class is a general purpose solver for Sparse Conditional
00108 /// Propagation with a programmable lattice function.
00109 ///
00110 class SparseSolver {
00111   typedef AbstractLatticeFunction::LatticeVal LatticeVal;
00112   
00113   /// LatticeFunc - This is the object that knows the lattice and how to do
00114   /// compute transfer functions.
00115   AbstractLatticeFunction *LatticeFunc;
00116   
00117   LLVMContext *Context;
00118   
00119   DenseMap<Value*, LatticeVal> ValueState;  // The state each value is in.
00120   SmallPtrSet<BasicBlock*, 16> BBExecutable;   // The bbs that are executable.
00121   
00122   std::vector<Instruction*> InstWorkList;   // Worklist of insts to process.
00123   
00124   std::vector<BasicBlock*> BBWorkList;  // The BasicBlock work list
00125   
00126   /// KnownFeasibleEdges - Entries in this set are edges which have already had
00127   /// PHI nodes retriggered.
00128   typedef std::pair<BasicBlock*,BasicBlock*> Edge;
00129   std::set<Edge> KnownFeasibleEdges;
00130   
00131   SparseSolver(const SparseSolver&);    // DO NOT IMPLEMENT
00132   void operator=(const SparseSolver&);  // DO NOT IMPLEMENT
00133 public:
00134   explicit SparseSolver(AbstractLatticeFunction *Lattice, LLVMContext *C)
00135     : LatticeFunc(Lattice), Context(C) {}
00136   ~SparseSolver() {
00137     delete LatticeFunc;
00138   }
00139   
00140   /// Solve - Solve for constants and executable blocks.
00141   ///
00142   void Solve(Function &F);
00143   
00144   void Print(Function &F, std::ostream &OS) const;
00145 
00146   /// getLatticeState - Return the LatticeVal object that corresponds to the
00147   /// value.  If an value is not in the map, it is returned as untracked,
00148   /// unlike the getOrInitValueState method.
00149   LatticeVal getLatticeState(Value *V) const {
00150     DenseMap<Value*, LatticeVal>::iterator I = ValueState.find(V);
00151     return I != ValueState.end() ? I->second : LatticeFunc->getUntrackedVal();
00152   }
00153   
00154   /// getOrInitValueState - Return the LatticeVal object that corresponds to the
00155   /// value, initializing the value's state if it hasn't been entered into the
00156   /// map yet.   This function is necessary because not all values should start
00157   /// out in the underdefined state... Arguments should be overdefined, and
00158   /// constants should be marked as constants.
00159   ///
00160   LatticeVal getOrInitValueState(Value *V);
00161   
00162   /// isEdgeFeasible - Return true if the control flow edge from the 'From'
00163   /// basic block to the 'To' basic block is currently feasible.  If
00164   /// AggressiveUndef is true, then this treats values with unknown lattice
00165   /// values as undefined.  This is generally only useful when solving the
00166   /// lattice, not when querying it.
00167   bool isEdgeFeasible(BasicBlock *From, BasicBlock *To,
00168                       bool AggressiveUndef = false);
00169 
00170   /// isBlockExecutable - Return true if there are any known feasible
00171   /// edges into the basic block.  This is generally only useful when
00172   /// querying the lattice.
00173   bool isBlockExecutable(BasicBlock *BB) const {
00174     return BBExecutable.count(BB);
00175   }
00176   
00177 private:
00178   /// UpdateState - When the state for some instruction is potentially updated,
00179   /// this function notices and adds I to the worklist if needed.
00180   void UpdateState(Instruction &Inst, LatticeVal V);
00181   
00182   /// MarkBlockExecutable - This method can be used by clients to mark all of
00183   /// the blocks that are known to be intrinsically live in the processed unit.
00184   void MarkBlockExecutable(BasicBlock *BB);
00185   
00186   /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB
00187   /// work list if it is not already executable.
00188   void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest);
00189   
00190   /// getFeasibleSuccessors - Return a vector of booleans to indicate which
00191   /// successors are reachable from a given terminator instruction.
00192   void getFeasibleSuccessors(TerminatorInst &TI, SmallVectorImpl<bool> &Succs,
00193                              bool AggressiveUndef);
00194   
00195   void visitInst(Instruction &I);
00196   void visitPHINode(PHINode &I);
00197   void visitTerminatorInst(TerminatorInst &TI);
00198 
00199 };
00200 
00201 } // end namespace llvm
00202 
00203 #endif // LLVM_ANALYSIS_SPARSE_PROPAGATION_H