1 | //===- SCCPSolver.h - SCCP Utility ----------------------------- *- C++ -*-===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // |
9 | // \file |
10 | // This file implements Sparse Conditional Constant Propagation (SCCP) utility. |
11 | // |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | #ifndef LLVM_TRANSFORMS_UTILS_SCCPSOLVER_H |
15 | #define LLVM_TRANSFORMS_UTILS_SCCPSOLVER_H |
16 | |
17 | #include "llvm/ADT/MapVector.h" |
18 | #include "llvm/ADT/SmallPtrSet.h" |
19 | #include "llvm/ADT/Statistic.h" |
20 | #include "llvm/Analysis/DomTreeUpdater.h" |
21 | #include "llvm/Transforms/Utils/PredicateInfo.h" |
22 | #include <vector> |
23 | |
24 | namespace llvm { |
25 | class Argument; |
26 | class BasicBlock; |
27 | class CallInst; |
28 | class Constant; |
29 | class DataLayout; |
30 | class DominatorTree; |
31 | class Function; |
32 | class GlobalVariable; |
33 | class Instruction; |
34 | class LLVMContext; |
35 | class StructType; |
36 | class TargetLibraryInfo; |
37 | class Value; |
38 | class ValueLatticeElement; |
39 | |
40 | /// Helper struct shared between Function Specialization and SCCP Solver. |
41 | struct ArgInfo { |
42 | Argument *Formal; // The Formal argument being analysed. |
43 | Constant *Actual; // A corresponding actual constant argument. |
44 | |
45 | ArgInfo(Argument *F, Constant *A) : Formal(F), Actual(A) {} |
46 | |
47 | bool operator==(const ArgInfo &Other) const { |
48 | return Formal == Other.Formal && Actual == Other.Actual; |
49 | } |
50 | |
51 | bool operator!=(const ArgInfo &Other) const { return !(*this == Other); } |
52 | |
53 | friend hash_code hash_value(const ArgInfo &A) { |
54 | return hash_combine(args: hash_value(ptr: A.Formal), args: hash_value(ptr: A.Actual)); |
55 | } |
56 | }; |
57 | |
58 | class SCCPInstVisitor; |
59 | |
60 | //===----------------------------------------------------------------------===// |
61 | // |
62 | /// SCCPSolver - This interface class is a general purpose solver for Sparse |
63 | /// Conditional Constant Propagation (SCCP). |
64 | /// |
65 | class SCCPSolver { |
66 | std::unique_ptr<SCCPInstVisitor> Visitor; |
67 | |
68 | public: |
69 | SCCPSolver(const DataLayout &DL, |
70 | std::function<const TargetLibraryInfo &(Function &)> GetTLI, |
71 | LLVMContext &Ctx); |
72 | |
73 | ~SCCPSolver(); |
74 | |
75 | void addPredicateInfo(Function &F, DominatorTree &DT, AssumptionCache &AC); |
76 | |
77 | /// markBlockExecutable - This method can be used by clients to mark all of |
78 | /// the blocks that are known to be intrinsically live in the processed unit. |
79 | /// This returns true if the block was not considered live before. |
80 | bool markBlockExecutable(BasicBlock *BB); |
81 | |
82 | const PredicateBase *getPredicateInfoFor(Instruction *I); |
83 | |
84 | /// trackValueOfGlobalVariable - Clients can use this method to |
85 | /// inform the SCCPSolver that it should track loads and stores to the |
86 | /// specified global variable if it can. This is only legal to call if |
87 | /// performing Interprocedural SCCP. |
88 | void trackValueOfGlobalVariable(GlobalVariable *GV); |
89 | |
90 | /// addTrackedFunction - If the SCCP solver is supposed to track calls into |
91 | /// and out of the specified function (which cannot have its address taken), |
92 | /// this method must be called. |
93 | void addTrackedFunction(Function *F); |
94 | |
95 | /// Add function to the list of functions whose return cannot be modified. |
96 | void addToMustPreserveReturnsInFunctions(Function *F); |
97 | |
98 | /// Returns true if the return of the given function cannot be modified. |
99 | bool mustPreserveReturn(Function *F); |
100 | |
101 | void addArgumentTrackedFunction(Function *F); |
102 | |
103 | /// Returns true if the given function is in the solver's set of |
104 | /// argument-tracked functions. |
105 | bool isArgumentTrackedFunction(Function *F); |
106 | |
107 | /// Solve - Solve for constants and executable blocks. |
108 | void solve(); |
109 | |
110 | /// resolvedUndefsIn - While solving the dataflow for a function, we assume |
111 | /// that branches on undef values cannot reach any of their successors. |
112 | /// However, this is not a safe assumption. After we solve dataflow, this |
113 | /// method should be use to handle this. If this returns true, the solver |
114 | /// should be rerun. |
115 | bool resolvedUndefsIn(Function &F); |
116 | |
117 | void solveWhileResolvedUndefsIn(Module &M); |
118 | |
119 | void solveWhileResolvedUndefsIn(SmallVectorImpl<Function *> &WorkList); |
120 | |
121 | void solveWhileResolvedUndefs(); |
122 | |
123 | bool isBlockExecutable(BasicBlock *BB) const; |
124 | |
125 | // isEdgeFeasible - Return true if the control flow edge from the 'From' basic |
126 | // block to the 'To' basic block is currently feasible. |
127 | bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const; |
128 | |
129 | std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const; |
130 | |
131 | void removeLatticeValueFor(Value *V); |
132 | |
133 | /// Invalidate the Lattice Value of \p Call and its users after specializing |
134 | /// the call. Then recompute it. |
135 | void resetLatticeValueFor(CallBase *Call); |
136 | |
137 | const ValueLatticeElement &getLatticeValueFor(Value *V) const; |
138 | |
139 | /// getTrackedRetVals - Get the inferred return value map. |
140 | const MapVector<Function *, ValueLatticeElement> &getTrackedRetVals(); |
141 | |
142 | /// getTrackedGlobals - Get and return the set of inferred initializers for |
143 | /// global variables. |
144 | const DenseMap<GlobalVariable *, ValueLatticeElement> &getTrackedGlobals(); |
145 | |
146 | /// getMRVFunctionsTracked - Get the set of functions which return multiple |
147 | /// values tracked by the pass. |
148 | const SmallPtrSet<Function *, 16> getMRVFunctionsTracked(); |
149 | |
150 | /// markOverdefined - Mark the specified value overdefined. This |
151 | /// works with both scalars and structs. |
152 | void markOverdefined(Value *V); |
153 | |
154 | // isStructLatticeConstant - Return true if all the lattice values |
155 | // corresponding to elements of the structure are constants, |
156 | // false otherwise. |
157 | bool isStructLatticeConstant(Function *F, StructType *STy); |
158 | |
159 | /// Helper to return a Constant if \p LV is either a constant or a constant |
160 | /// range with a single element. |
161 | Constant *getConstant(const ValueLatticeElement &LV, Type *Ty) const; |
162 | |
163 | /// Return either a Constant or nullptr for a given Value. |
164 | Constant *getConstantOrNull(Value *V) const; |
165 | |
166 | /// Return a reference to the set of argument tracked functions. |
167 | SmallPtrSetImpl<Function *> &getArgumentTrackedFunctions(); |
168 | |
169 | /// Set the Lattice Value for the arguments of a specialization \p F. |
170 | /// If an argument is Constant then its lattice value is marked with the |
171 | /// corresponding actual argument in \p Args. Otherwise, its lattice value |
172 | /// is inherited (copied) from the corresponding formal argument in \p Args. |
173 | void setLatticeValueForSpecializationArguments(Function *F, |
174 | const SmallVectorImpl<ArgInfo> &Args); |
175 | |
176 | /// Mark all of the blocks in function \p F non-executable. Clients can used |
177 | /// this method to erase a function from the module (e.g., if it has been |
178 | /// completely specialized and is no longer needed). |
179 | void markFunctionUnreachable(Function *F); |
180 | |
181 | void visit(Instruction *I); |
182 | void visitCall(CallInst &I); |
183 | |
184 | bool simplifyInstsInBlock(BasicBlock &BB, |
185 | SmallPtrSetImpl<Value *> &InsertedValues, |
186 | Statistic &InstRemovedStat, |
187 | Statistic &InstReplacedStat); |
188 | |
189 | bool removeNonFeasibleEdges(BasicBlock *BB, DomTreeUpdater &DTU, |
190 | BasicBlock *&NewUnreachableBB) const; |
191 | |
192 | bool tryToReplaceWithConstant(Value *V); |
193 | |
194 | // Helper to check if \p LV is either a constant or a constant |
195 | // range with a single element. This should cover exactly the same cases as |
196 | // the old ValueLatticeElement::isConstant() and is intended to be used in the |
197 | // transition to ValueLatticeElement. |
198 | static bool isConstant(const ValueLatticeElement &LV); |
199 | |
200 | // Helper to check if \p LV is either overdefined or a constant range with |
201 | // more than a single element. This should cover exactly the same cases as the |
202 | // old ValueLatticeElement::isOverdefined() and is intended to be used in the |
203 | // transition to ValueLatticeElement. |
204 | static bool isOverdefined(const ValueLatticeElement &LV); |
205 | }; |
206 | } // namespace llvm |
207 | |
208 | #endif // LLVM_TRANSFORMS_UTILS_SCCPSOLVER_H |
209 | |