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"
35
template<typename T> class SmallVectorImpl;
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.
44
class AbstractLatticeFunction {
46
typedef void *LatticeVal;
48
LatticeVal UndefVal, OverdefinedVal, UntrackedVal;
50
AbstractLatticeFunction(LatticeVal undefVal, LatticeVal overdefinedVal,
51
LatticeVal untrackedVal) {
53
OverdefinedVal = overdefinedVal;
54
UntrackedVal = untrackedVal;
56
virtual ~AbstractLatticeFunction();
58
LatticeVal getUndefVal() const { return UndefVal; }
59
LatticeVal getOverdefinedVal() const { return OverdefinedVal; }
60
LatticeVal getUntrackedVal() const { return UntrackedVal; }
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) {
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
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) {
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) {
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
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.
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.
107
/// PrintValue - Render the specified lattice value to the specified stream.
108
virtual void PrintValue(LatticeVal V, raw_ostream &OS);
112
/// SparseSolver - This class is a general purpose solver for Sparse Conditional
113
/// Propagation with a programmable lattice function.
116
typedef AbstractLatticeFunction::LatticeVal LatticeVal;
118
/// LatticeFunc - This is the object that knows the lattice and how to do
119
/// compute transfer functions.
120
AbstractLatticeFunction *LatticeFunc;
122
DenseMap<Value*, LatticeVal> ValueState; // The state each value is in.
123
SmallPtrSet<BasicBlock*, 16> BBExecutable; // The bbs that are executable.
125
std::vector<Instruction*> InstWorkList; // Worklist of insts to process.
127
std::vector<BasicBlock*> BBWorkList; // The BasicBlock work list
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;
134
SparseSolver(const SparseSolver&); // DO NOT IMPLEMENT
135
void operator=(const SparseSolver&); // DO NOT IMPLEMENT
137
explicit SparseSolver(AbstractLatticeFunction *Lattice)
138
: LatticeFunc(Lattice) {}
143
/// Solve - Solve for constants and executable blocks.
145
void Solve(Function &F);
147
void Print(Function &F, raw_ostream &OS) const;
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();
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.
163
LatticeVal getOrInitValueState(Value *V);
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);
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);
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);
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);
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);
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);
198
void visitInst(Instruction &I);
199
void visitPHINode(PHINode &I);
200
void visitTerminatorInst(TerminatorInst &TI);
204
} // end namespace llvm
206
#endif // LLVM_ANALYSIS_SPARSE_PROPAGATION_H