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
24namespace llvm {
25class Argument;
26class BasicBlock;
27class CallInst;
28class Constant;
29class DataLayout;
30class DominatorTree;
31class Function;
32class GlobalVariable;
33class Instruction;
34class LLVMContext;
35class StructType;
36class TargetLibraryInfo;
37class Value;
38class ValueLatticeElement;
39
40/// Helper struct shared between Function Specialization and SCCP Solver.
41struct 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
58class SCCPInstVisitor;
59
60//===----------------------------------------------------------------------===//
61//
62/// SCCPSolver - This interface class is a general purpose solver for Sparse
63/// Conditional Constant Propagation (SCCP).
64///
65class SCCPSolver {
66 std::unique_ptr<SCCPInstVisitor> Visitor;
67
68public:
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

source code of llvm/include/llvm/Transforms/Utils/SCCPSolver.h