1 //===- SparsePropagation.h - Sparse Conditional Property Propagation ------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements an abstract sparse conditional propagation algorithm,
11 // modeled after SCCP, but with a customizable lattice function.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_ANALYSIS_SPARSEPROPAGATION_H
16 #define LLVM_ANALYSIS_SPARSEPROPAGATION_H
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/IR/BasicBlock.h"
36 template <typename T> class SmallVectorImpl;
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.
45 class AbstractLatticeFunction {
47 typedef void *LatticeVal;
50 LatticeVal UndefVal, OverdefinedVal, UntrackedVal;
53 AbstractLatticeFunction(LatticeVal undefVal, LatticeVal overdefinedVal,
54 LatticeVal untrackedVal) {
56 OverdefinedVal = overdefinedVal;
57 UntrackedVal = untrackedVal;
59 virtual ~AbstractLatticeFunction();
61 LatticeVal getUndefVal() const { return UndefVal; }
62 LatticeVal getOverdefinedVal() const { return OverdefinedVal; }
63 LatticeVal getUntrackedVal() const { return UntrackedVal; }
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; }
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
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; }
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) {
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
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.
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.
106 /// PrintValue - Render the specified lattice value to the specified stream.
107 virtual void PrintValue(LatticeVal V, raw_ostream &OS);
110 /// SparseSolver - This class is a general purpose solver for Sparse Conditional
111 /// Propagation with a programmable lattice function.
114 typedef AbstractLatticeFunction::LatticeVal LatticeVal;
116 /// LatticeFunc - This is the object that knows the lattice and how to do
117 /// compute transfer functions.
118 AbstractLatticeFunction *LatticeFunc;
120 DenseMap<Value *, LatticeVal> ValueState; // The state each value is in.
121 SmallPtrSet<BasicBlock *, 16> BBExecutable; // The bbs that are executable.
123 std::vector<Instruction *> InstWorkList; // Worklist of insts to process.
125 std::vector<BasicBlock *> BBWorkList; // The BasicBlock work list
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;
132 SparseSolver(const SparseSolver&) = delete;
133 void operator=(const SparseSolver&) = delete;
136 explicit SparseSolver(AbstractLatticeFunction *Lattice)
137 : LatticeFunc(Lattice) {}
138 ~SparseSolver() { delete LatticeFunc; }
140 /// Solve - Solve for constants and executable blocks.
142 void Solve(Function &F);
144 void Print(Function &F, raw_ostream &OS) const;
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();
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.
160 LatticeVal getOrInitValueState(Value *V);
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);
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);
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);
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);
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);
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);
195 void visitInst(Instruction &I);
196 void visitPHINode(PHINode &I);
197 void visitTerminatorInst(TerminatorInst &TI);
200 } // end namespace llvm
202 #endif // LLVM_ANALYSIS_SPARSEPROPAGATION_H