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