1193323Sed//===- SparsePropagation.h - Sparse Conditional Property Propagation ------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements an abstract sparse conditional propagation algorithm, 11193323Sed// modeled after SCCP, but with a customizable lattice function. 12193323Sed// 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15252723Sdim#ifndef LLVM_ANALYSIS_SPARSEPROPAGATION_H 16252723Sdim#define LLVM_ANALYSIS_SPARSEPROPAGATION_H 17193323Sed 18193323Sed#include "llvm/ADT/DenseMap.h" 19193323Sed#include "llvm/ADT/SmallPtrSet.h" 20252723Sdim#include <set> 21193323Sed#include <vector> 22193323Sed 23193323Sednamespace llvm { 24193323Sed class Value; 25193323Sed class Constant; 26193323Sed class Argument; 27193323Sed class Instruction; 28193323Sed class PHINode; 29193323Sed class TerminatorInst; 30193323Sed class BasicBlock; 31193323Sed class Function; 32193323Sed class SparseSolver; 33198090Srdivacky class raw_ostream; 34193323Sed 35193323Sed template<typename T> class SmallVectorImpl; 36193323Sed 37193323Sed/// AbstractLatticeFunction - This class is implemented by the dataflow instance 38193323Sed/// to specify what the lattice values are and how they handle merges etc. 39193323Sed/// This gives the client the power to compute lattice values from instructions, 40193323Sed/// constants, etc. The requirement is that lattice values must all fit into 41193323Sed/// a void*. If a void* is not sufficient, the implementation should use this 42193323Sed/// pointer to be a pointer into a uniquing set or something. 43193323Sed/// 44193323Sedclass AbstractLatticeFunction { 45193323Sedpublic: 46193323Sed typedef void *LatticeVal; 47193323Sedprivate: 48193323Sed LatticeVal UndefVal, OverdefinedVal, UntrackedVal; 49193323Sedpublic: 50193323Sed AbstractLatticeFunction(LatticeVal undefVal, LatticeVal overdefinedVal, 51193323Sed LatticeVal untrackedVal) { 52193323Sed UndefVal = undefVal; 53193323Sed OverdefinedVal = overdefinedVal; 54193323Sed UntrackedVal = untrackedVal; 55193323Sed } 56193323Sed virtual ~AbstractLatticeFunction(); 57193323Sed 58193323Sed LatticeVal getUndefVal() const { return UndefVal; } 59193323Sed LatticeVal getOverdefinedVal() const { return OverdefinedVal; } 60193323Sed LatticeVal getUntrackedVal() const { return UntrackedVal; } 61193323Sed 62193323Sed /// IsUntrackedValue - If the specified Value is something that is obviously 63193323Sed /// uninteresting to the analysis (and would always return UntrackedVal), 64193323Sed /// this function can return true to avoid pointless work. 65193323Sed virtual bool IsUntrackedValue(Value *V) { 66193323Sed return false; 67193323Sed } 68193323Sed 69193323Sed /// ComputeConstant - Given a constant value, compute and return a lattice 70193323Sed /// value corresponding to the specified constant. 71193323Sed virtual LatticeVal ComputeConstant(Constant *C) { 72193323Sed return getOverdefinedVal(); // always safe 73193323Sed } 74198090Srdivacky 75198090Srdivacky /// IsSpecialCasedPHI - Given a PHI node, determine whether this PHI node is 76198090Srdivacky /// one that the we want to handle through ComputeInstructionState. 77198090Srdivacky virtual bool IsSpecialCasedPHI(PHINode *PN) { 78198090Srdivacky return false; 79198090Srdivacky } 80193323Sed 81193323Sed /// GetConstant - If the specified lattice value is representable as an LLVM 82193323Sed /// constant value, return it. Otherwise return null. The returned value 83193323Sed /// must be in the same LLVM type as Val. 84193323Sed virtual Constant *GetConstant(LatticeVal LV, Value *Val, SparseSolver &SS) { 85193323Sed return 0; 86193323Sed } 87193323Sed 88193323Sed /// ComputeArgument - Given a formal argument value, compute and return a 89193323Sed /// lattice value corresponding to the specified argument. 90193323Sed virtual LatticeVal ComputeArgument(Argument *I) { 91193323Sed return getOverdefinedVal(); // always safe 92193323Sed } 93193323Sed 94193323Sed /// MergeValues - Compute and return the merge of the two specified lattice 95193323Sed /// values. Merging should only move one direction down the lattice to 96193323Sed /// guarantee convergence (toward overdefined). 97193323Sed virtual LatticeVal MergeValues(LatticeVal X, LatticeVal Y) { 98193323Sed return getOverdefinedVal(); // always safe, never useful. 99193323Sed } 100193323Sed 101193323Sed /// ComputeInstructionState - Given an instruction and a vector of its operand 102193323Sed /// values, compute the result value of the instruction. 103193323Sed virtual LatticeVal ComputeInstructionState(Instruction &I, SparseSolver &SS) { 104193323Sed return getOverdefinedVal(); // always safe, never useful. 105193323Sed } 106193323Sed 107193323Sed /// PrintValue - Render the specified lattice value to the specified stream. 108198090Srdivacky virtual void PrintValue(LatticeVal V, raw_ostream &OS); 109193323Sed}; 110193323Sed 111193323Sed 112193323Sed/// SparseSolver - This class is a general purpose solver for Sparse Conditional 113193323Sed/// Propagation with a programmable lattice function. 114193323Sed/// 115193323Sedclass SparseSolver { 116193323Sed typedef AbstractLatticeFunction::LatticeVal LatticeVal; 117193323Sed 118193323Sed /// LatticeFunc - This is the object that knows the lattice and how to do 119193323Sed /// compute transfer functions. 120193323Sed AbstractLatticeFunction *LatticeFunc; 121193323Sed 122193323Sed DenseMap<Value*, LatticeVal> ValueState; // The state each value is in. 123193323Sed SmallPtrSet<BasicBlock*, 16> BBExecutable; // The bbs that are executable. 124193323Sed 125193323Sed std::vector<Instruction*> InstWorkList; // Worklist of insts to process. 126193323Sed 127193323Sed std::vector<BasicBlock*> BBWorkList; // The BasicBlock work list 128193323Sed 129193323Sed /// KnownFeasibleEdges - Entries in this set are edges which have already had 130193323Sed /// PHI nodes retriggered. 131193323Sed typedef std::pair<BasicBlock*,BasicBlock*> Edge; 132193323Sed std::set<Edge> KnownFeasibleEdges; 133245431Sdim 134245431Sdim SparseSolver(const SparseSolver&) LLVM_DELETED_FUNCTION; 135245431Sdim void operator=(const SparseSolver&) LLVM_DELETED_FUNCTION; 136193323Sedpublic: 137201360Srdivacky explicit SparseSolver(AbstractLatticeFunction *Lattice) 138201360Srdivacky : LatticeFunc(Lattice) {} 139193323Sed ~SparseSolver() { 140193323Sed delete LatticeFunc; 141193323Sed } 142193323Sed 143193323Sed /// Solve - Solve for constants and executable blocks. 144193323Sed /// 145193323Sed void Solve(Function &F); 146193323Sed 147198090Srdivacky void Print(Function &F, raw_ostream &OS) const; 148193323Sed 149193323Sed /// getLatticeState - Return the LatticeVal object that corresponds to the 150193323Sed /// value. If an value is not in the map, it is returned as untracked, 151193323Sed /// unlike the getOrInitValueState method. 152193323Sed LatticeVal getLatticeState(Value *V) const { 153199481Srdivacky DenseMap<Value*, LatticeVal>::const_iterator I = ValueState.find(V); 154193323Sed return I != ValueState.end() ? I->second : LatticeFunc->getUntrackedVal(); 155193323Sed } 156193323Sed 157193323Sed /// getOrInitValueState - Return the LatticeVal object that corresponds to the 158193323Sed /// value, initializing the value's state if it hasn't been entered into the 159193323Sed /// map yet. This function is necessary because not all values should start 160193323Sed /// out in the underdefined state... Arguments should be overdefined, and 161193323Sed /// constants should be marked as constants. 162193323Sed /// 163193323Sed LatticeVal getOrInitValueState(Value *V); 164193323Sed 165193323Sed /// isEdgeFeasible - Return true if the control flow edge from the 'From' 166193323Sed /// basic block to the 'To' basic block is currently feasible. If 167193323Sed /// AggressiveUndef is true, then this treats values with unknown lattice 168193323Sed /// values as undefined. This is generally only useful when solving the 169193323Sed /// lattice, not when querying it. 170193323Sed bool isEdgeFeasible(BasicBlock *From, BasicBlock *To, 171193323Sed bool AggressiveUndef = false); 172193323Sed 173193323Sed /// isBlockExecutable - Return true if there are any known feasible 174193323Sed /// edges into the basic block. This is generally only useful when 175193323Sed /// querying the lattice. 176193323Sed bool isBlockExecutable(BasicBlock *BB) const { 177193323Sed return BBExecutable.count(BB); 178193323Sed } 179193323Sed 180193323Sedprivate: 181193323Sed /// UpdateState - When the state for some instruction is potentially updated, 182193323Sed /// this function notices and adds I to the worklist if needed. 183193323Sed void UpdateState(Instruction &Inst, LatticeVal V); 184193323Sed 185193323Sed /// MarkBlockExecutable - This method can be used by clients to mark all of 186193323Sed /// the blocks that are known to be intrinsically live in the processed unit. 187193323Sed void MarkBlockExecutable(BasicBlock *BB); 188193323Sed 189193323Sed /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB 190193323Sed /// work list if it is not already executable. 191193323Sed void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest); 192193323Sed 193193323Sed /// getFeasibleSuccessors - Return a vector of booleans to indicate which 194193323Sed /// successors are reachable from a given terminator instruction. 195193323Sed void getFeasibleSuccessors(TerminatorInst &TI, SmallVectorImpl<bool> &Succs, 196193323Sed bool AggressiveUndef); 197193323Sed 198193323Sed void visitInst(Instruction &I); 199193323Sed void visitPHINode(PHINode &I); 200193323Sed void visitTerminatorInst(TerminatorInst &TI); 201193323Sed 202193323Sed}; 203193323Sed 204193323Sed} // end namespace llvm 205193323Sed 206252723Sdim#endif // LLVM_ANALYSIS_SPARSEPROPAGATION_H 207