1//===- SparsePropagation.h - Sparse Conditional Property Propagation ------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements an abstract sparse conditional propagation algorithm,
11// modeled after SCCP, but with a customizable lattice function.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_ANALYSIS_SPARSEPROPAGATION_H
16#define LLVM_ANALYSIS_SPARSEPROPAGATION_H
17
18#include "llvm/ADT/DenseMap.h"
19#include "llvm/ADT/SmallPtrSet.h"
20#include <set>
21#include <vector>
22
23namespace llvm {
24  class Value;
25  class Constant;
26  class Argument;
27  class Instruction;
28  class PHINode;
29  class TerminatorInst;
30  class BasicBlock;
31  class Function;
32  class SparseSolver;
33  class raw_ostream;
34
35  template<typename T> class SmallVectorImpl;
36
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.
43///
44class AbstractLatticeFunction {
45public:
46  typedef void *LatticeVal;
47private:
48  LatticeVal UndefVal, OverdefinedVal, UntrackedVal;
49public:
50  AbstractLatticeFunction(LatticeVal undefVal, LatticeVal overdefinedVal,
51                          LatticeVal untrackedVal) {
52    UndefVal = undefVal;
53    OverdefinedVal = overdefinedVal;
54    UntrackedVal = untrackedVal;
55  }
56  virtual ~AbstractLatticeFunction();
57
58  LatticeVal getUndefVal()       const { return UndefVal; }
59  LatticeVal getOverdefinedVal() const { return OverdefinedVal; }
60  LatticeVal getUntrackedVal()   const { return UntrackedVal; }
61
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) {
66    return false;
67  }
68
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
73  }
74
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) {
78    return false;
79  }
80
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) {
85    return nullptr;
86  }
87
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
92  }
93
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.
99  }
100
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.
105  }
106
107  /// PrintValue - Render the specified lattice value to the specified stream.
108  virtual void PrintValue(LatticeVal V, raw_ostream &OS);
109};
110
111
112/// SparseSolver - This class is a general purpose solver for Sparse Conditional
113/// Propagation with a programmable lattice function.
114///
115class SparseSolver {
116  typedef AbstractLatticeFunction::LatticeVal LatticeVal;
117
118  /// LatticeFunc - This is the object that knows the lattice and how to do
119  /// compute transfer functions.
120  AbstractLatticeFunction *LatticeFunc;
121
122  DenseMap<Value*, LatticeVal> ValueState;  // The state each value is in.
123  SmallPtrSet<BasicBlock*, 16> BBExecutable;   // The bbs that are executable.
124
125  std::vector<Instruction*> InstWorkList;   // Worklist of insts to process.
126
127  std::vector<BasicBlock*> BBWorkList;  // The BasicBlock work list
128
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;
133
134  SparseSolver(const SparseSolver&) LLVM_DELETED_FUNCTION;
135  void operator=(const SparseSolver&) LLVM_DELETED_FUNCTION;
136public:
137  explicit SparseSolver(AbstractLatticeFunction *Lattice)
138    : LatticeFunc(Lattice) {}
139  ~SparseSolver() {
140    delete LatticeFunc;
141  }
142
143  /// Solve - Solve for constants and executable blocks.
144  ///
145  void Solve(Function &F);
146
147  void Print(Function &F, raw_ostream &OS) const;
148
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();
155  }
156
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.
162  ///
163  LatticeVal getOrInitValueState(Value *V);
164
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);
172
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);
178  }
179
180private:
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);
184
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);
188
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);
192
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);
197
198  void visitInst(Instruction &I);
199  void visitPHINode(PHINode &I);
200  void visitTerminatorInst(TerminatorInst &TI);
201
202};
203
204} // end namespace llvm
205
206#endif // LLVM_ANALYSIS_SPARSEPROPAGATION_H
207