LLVM 18.0.0git
SCCPSolver.h
Go to the documentation of this file.
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"
19#include "llvm/ADT/Statistic.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
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(hash_value(A.Formal), hash_value(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///
66 std::unique_ptr<SCCPInstVisitor> Visitor;
67
68public:
70 std::function<const TargetLibraryInfo &(Function &)> GetTLI,
71 LLVMContext &Ctx);
72
74
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.
81
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.
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.
94
95 /// Add function to the list of functions whose return cannot be modified.
97
98 /// Returns true if the return of the given function cannot be modified.
100
102
103 /// Returns true if the given function is in the solver's set of
104 /// argument-tracked functions.
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.
116
118
120
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
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
138
139 /// getTrackedRetVals - Get the inferred return value map.
141
142 /// getTrackedGlobals - Get and return the set of inferred initializers for
143 /// global variables.
145
146 /// getMRVFunctionsTracked - Get the set of functions which return multiple
147 /// values tracked by the pass.
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.
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.
165
166 /// Return a reference to the set of argument tracked functions.
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.
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).
180
181 void visit(Instruction *I);
182 void visitCall(CallInst &I);
183
185 SmallPtrSetImpl<Value *> &InsertedValues,
186 Statistic &InstRemovedStat,
187 Statistic &InstReplacedStat);
188
190 BasicBlock *&NewUnreachableBB) const;
191
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
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
BlockVerifier::State From
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This file implements a map that provides insertion order iteration.
This file implements the PredicateInfo analysis, which creates an Extended SSA form for operations us...
This file defines the SmallPtrSet class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1190
This class represents a function call, abstracting a target machine's calling convention.
This is an important base class in LLVM.
Definition: Constant.h:41
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:36
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
SCCPSolver - This interface class is a general purpose solver for Sparse Conditional Constant Propaga...
Definition: SCCPSolver.h:65
void visitCall(CallInst &I)
const DenseMap< GlobalVariable *, ValueLatticeElement > & getTrackedGlobals()
getTrackedGlobals - Get and return the set of inferred initializers for global variables.
void resetLatticeValueFor(CallBase *Call)
Invalidate the Lattice Value of Call and its users after specializing the call.
void trackValueOfGlobalVariable(GlobalVariable *GV)
trackValueOfGlobalVariable - Clients can use this method to inform the SCCPSolver that it should trac...
bool tryToReplaceWithConstant(Value *V)
Definition: SCCPSolver.cpp:76
bool isStructLatticeConstant(Function *F, StructType *STy)
void addPredicateInfo(Function &F, DominatorTree &DT, AssumptionCache &AC)
void solve()
Solve - Solve for constants and executable blocks.
void visit(Instruction *I)
void addTrackedFunction(Function *F)
addTrackedFunction - If the SCCP solver is supposed to track calls into and out of the specified func...
const MapVector< Function *, ValueLatticeElement > & getTrackedRetVals()
getTrackedRetVals - Get the inferred return value map.
void solveWhileResolvedUndefsIn(Module &M)
const PredicateBase * getPredicateInfoFor(Instruction *I)
bool resolvedUndefsIn(Function &F)
resolvedUndefsIn - While solving the dataflow for a function, we assume that branches on undef values...
void addArgumentTrackedFunction(Function *F)
void solveWhileResolvedUndefs()
void removeLatticeValueFor(Value *V)
std::vector< ValueLatticeElement > getStructLatticeValueFor(Value *V) const
const SmallPtrSet< Function *, 16 > getMRVFunctionsTracked()
getMRVFunctionsTracked - Get the set of functions which return multiple values tracked by the pass.
Constant * getConstantOrNull(Value *V) const
Return either a Constant or nullptr for a given Value.
bool simplifyInstsInBlock(BasicBlock &BB, SmallPtrSetImpl< Value * > &InsertedValues, Statistic &InstRemovedStat, Statistic &InstReplacedStat)
Definition: SCCPSolver.cpp:210
Constant * getConstant(const ValueLatticeElement &LV, Type *Ty) const
Helper to return a Constant if LV is either a constant or a constant range with a single element.
const ValueLatticeElement & getLatticeValueFor(Value *V) const
void addToMustPreserveReturnsInFunctions(Function *F)
Add function to the list of functions whose return cannot be modified.
bool removeNonFeasibleEdges(BasicBlock *BB, DomTreeUpdater &DTU, BasicBlock *&NewUnreachableBB) const
Definition: SCCPSolver.cpp:234
bool isBlockExecutable(BasicBlock *BB) const
bool markBlockExecutable(BasicBlock *BB)
markBlockExecutable - This method can be used by clients to mark all of the blocks that are known to ...
void setLatticeValueForSpecializationArguments(Function *F, const SmallVectorImpl< ArgInfo > &Args)
Set the Lattice Value for the arguments of a specialization F.
static bool isConstant(const ValueLatticeElement &LV)
Definition: SCCPSolver.cpp:55
bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const
bool mustPreserveReturn(Function *F)
Returns true if the return of the given function cannot be modified.
static bool isOverdefined(const ValueLatticeElement &LV)
Definition: SCCPSolver.cpp:60
void markFunctionUnreachable(Function *F)
Mark all of the blocks in function F non-executable.
bool isArgumentTrackedFunction(Function *F)
Returns true if the given function is in the solver's set of argument-tracked functions.
SmallPtrSetImpl< Function * > & getArgumentTrackedFunctions()
Return a reference to the set of argument tracked functions.
void markOverdefined(Value *V)
markOverdefined - Mark the specified value overdefined.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:345
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
Class to represent struct types.
Definition: DerivedTypes.h:213
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
This class represents lattice values for constants.
Definition: ValueLattice.h:29
LLVM Value Representation.
Definition: Value.h:74
An opaque object representing a hash code.
Definition: Hashing.h:74
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Other
Any other memory.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:613
Helper struct shared between Function Specialization and SCCP Solver.
Definition: SCCPSolver.h:41
friend hash_code hash_value(const ArgInfo &A)
Definition: SCCPSolver.h:53
Argument * Formal
Definition: SCCPSolver.h:42
Constant * Actual
Definition: SCCPSolver.h:43
ArgInfo(Argument *F, Constant *A)
Definition: SCCPSolver.h:45
bool operator!=(const ArgInfo &Other) const
Definition: SCCPSolver.h:51
bool operator==(const ArgInfo &Other) const
Definition: SCCPSolver.h:47