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_SPARSE_PROPAGATION_H
16 #define LLVM_ANALYSIS_SPARSE_PROPAGATION_H
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/ADT/SmallVector.h"
34 /// AbstractLatticeFunction - This class is implemented by the dataflow instance
35 /// to specify what the lattice values are and what how they handle merges etc.
36 /// This gives the client the power to compute lattice values from instructions,
37 /// constants, etc. The requirement is that lattice values must all fit into
38 /// a void*. If a void* is not sufficient, the implementation should use this
39 /// pointer to be a pointer into a uniquing set or something.
41 class AbstractLatticeFunction {
43 typedef void *LatticeVal;
45 LatticeVal UndefVal, OverdefinedVal, UntrackedVal;
47 AbstractLatticeFunction(LatticeVal undefVal, LatticeVal overdefinedVal,
48 LatticeVal untrackedVal) {
50 OverdefinedVal = overdefinedVal;
51 UntrackedVal = untrackedVal;
53 virtual ~AbstractLatticeFunction();
55 LatticeVal getUndefVal() const { return UndefVal; }
56 LatticeVal getOverdefinedVal() const { return OverdefinedVal; }
57 LatticeVal getUntrackedVal() const { return UntrackedVal; }
59 /// IsUntrackedValue - If the specified Value is something that is obviously
60 /// uninteresting to the analysis (and would always return UntrackedVal),
61 /// this function can return true to avoid pointless work.
62 virtual bool IsUntrackedValue(Value *V) {
66 /// ComputeConstant - Given a constant value, compute and return a lattice
67 /// value corresponding to the specified constant.
68 virtual LatticeVal ComputeConstant(Constant *C) {
69 return getOverdefinedVal(); // always safe
72 /// GetConstant - If the specified lattice value is representable as an LLVM
73 /// constant value, return it. Otherwise return null. The returned value
74 /// must be in the same LLVM type as Val.
75 virtual Constant *GetConstant(LatticeVal LV, Value *Val, SparseSolver &SS) {
79 /// MergeValues - Compute and return the merge of the two specified lattice
80 /// values. Merging should only move one direction down the lattice to
81 /// guarantee convergence (toward overdefined).
82 virtual LatticeVal MergeValues(LatticeVal X, LatticeVal Y) {
83 return getOverdefinedVal(); // always safe, never useful.
86 /// ComputeInstructionState - Given an instruction and a vector of its operand
87 /// values, compute the result value of the instruction.
88 virtual LatticeVal ComputeInstructionState(Instruction &I, SparseSolver &SS) {
89 return getOverdefinedVal(); // always safe, never useful.
92 /// PrintValue - Render the specified lattice value to the specified stream.
93 virtual void PrintValue(LatticeVal V, std::ostream &OS);
97 /// SparseSolver - This class is a general purpose solver for Sparse Conditional
98 /// Propagation with a programmable lattice function.
101 typedef AbstractLatticeFunction::LatticeVal LatticeVal;
103 /// LatticeFunc - This is the object that knows the lattice and how to do
104 /// compute transfer functions.
105 AbstractLatticeFunction *LatticeFunc;
107 DenseMap<Value*, LatticeVal> ValueState; // The state each value is in.
108 SmallPtrSet<BasicBlock*, 16> BBExecutable; // The bbs that are executable.
110 std::vector<Instruction*> InstWorkList; // Worklist of insts to process.
112 std::vector<BasicBlock*> BBWorkList; // The BasicBlock work list
114 /// KnownFeasibleEdges - Entries in this set are edges which have already had
115 /// PHI nodes retriggered.
116 typedef std::pair<BasicBlock*,BasicBlock*> Edge;
117 std::set<Edge> KnownFeasibleEdges;
119 SparseSolver(const SparseSolver&); // DO NOT IMPLEMENT
120 void operator=(const SparseSolver&); // DO NOT IMPLEMENT
122 SparseSolver(AbstractLatticeFunction *Lattice) : LatticeFunc(Lattice) {}
127 /// Solve - Solve for constants and executable blocks.
129 void Solve(Function &F);
131 void Print(Function &F, std::ostream &OS);
133 /// getLatticeState - Return the LatticeVal object that corresponds to the
134 /// value. If an value is not in the map, it is returned as untracked,
135 /// unlike the getOrInitValueState method.
136 LatticeVal getLatticeState(Value *V) const {
137 DenseMap<Value*, LatticeVal>::iterator I = ValueState.find(V);
138 return I != ValueState.end() ? I->second : LatticeFunc->getUntrackedVal();
141 /// getOrInitValueState - Return the LatticeVal object that corresponds to the
142 /// value, initializing the value's state if it hasn't been entered into the
143 /// map yet. This function is necessary because not all values should start
144 /// out in the underdefined state... Arguments should be overdefined, and
145 /// constants should be marked as constants.
147 LatticeVal getOrInitValueState(Value *V);
150 /// UpdateState - When the state for some instruction is potentially updated,
151 /// this function notices and adds I to the worklist if needed.
152 void UpdateState(Instruction &Inst, LatticeVal V);
154 /// MarkBlockExecutable - This method can be used by clients to mark all of
155 /// the blocks that are known to be intrinsically live in the processed unit.
156 void MarkBlockExecutable(BasicBlock *BB);
158 /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB
159 /// work list if it is not already executable.
160 void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest);
162 /// getFeasibleSuccessors - Return a vector of booleans to indicate which
163 /// successors are reachable from a given terminator instruction.
164 void getFeasibleSuccessors(TerminatorInst &TI, SmallVectorImpl<bool> &Succs);
166 /// isEdgeFeasible - Return true if the control flow edge from the 'From'
167 /// basic block to the 'To' basic block is currently feasible...
168 bool isEdgeFeasible(BasicBlock *From, BasicBlock *To);
170 void visitInst(Instruction &I);
171 void visitPHINode(PHINode &I);
172 void visitTerminatorInst(TerminatorInst &TI);
176 } // end namespace llvm
178 #endif // LLVM_ANALYSIS_SPARSE_PROPAGATION_H