LLVM 17.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 LoopInfo;
36class PostDominatorTree;
37class StructType;
38class TargetLibraryInfo;
39class Value;
40class ValueLatticeElement;
41
42/// Helper struct for bundling up the analysis results per function for IPSCCP.
44 std::unique_ptr<PredicateInfo> PredInfo;
48};
49
50/// Helper struct shared between Function Specialization and SCCP Solver.
51struct ArgInfo {
52 Argument *Formal; // The Formal argument being analysed.
53 Constant *Actual; // A corresponding actual constant argument.
54
56
57 bool operator==(const ArgInfo &Other) const {
58 return Formal == Other.Formal && Actual == Other.Actual;
59 }
60
61 bool operator!=(const ArgInfo &Other) const { return !(*this == Other); }
62
63 friend hash_code hash_value(const ArgInfo &A) {
64 return hash_combine(hash_value(A.Formal), hash_value(A.Actual));
65 }
66};
67
68class SCCPInstVisitor;
69
70//===----------------------------------------------------------------------===//
71//
72/// SCCPSolver - This interface class is a general purpose solver for Sparse
73/// Conditional Constant Propagation (SCCP).
74///
76 std::unique_ptr<SCCPInstVisitor> Visitor;
77
78public:
80 std::function<const TargetLibraryInfo &(Function &)> GetTLI,
81 LLVMContext &Ctx);
82
84
86
87 /// markBlockExecutable - This method can be used by clients to mark all of
88 /// the blocks that are known to be intrinsically live in the processed unit.
89 /// This returns true if the block was not considered live before.
91
93
95
97
98 /// trackValueOfGlobalVariable - Clients can use this method to
99 /// inform the SCCPSolver that it should track loads and stores to the
100 /// specified global variable if it can. This is only legal to call if
101 /// performing Interprocedural SCCP.
103
104 /// addTrackedFunction - If the SCCP solver is supposed to track calls into
105 /// and out of the specified function (which cannot have its address taken),
106 /// this method must be called.
108
109 /// Add function to the list of functions whose return cannot be modified.
111
112 /// Returns true if the return of the given function cannot be modified.
114
116
117 /// Returns true if the given function is in the solver's set of
118 /// argument-tracked functions.
120
121 /// Solve - Solve for constants and executable blocks.
122 void solve();
123
124 /// resolvedUndefsIn - While solving the dataflow for a function, we assume
125 /// that branches on undef values cannot reach any of their successors.
126 /// However, this is not a safe assumption. After we solve dataflow, this
127 /// method should be use to handle this. If this returns true, the solver
128 /// should be rerun.
130
132
134
135 bool isBlockExecutable(BasicBlock *BB) const;
136
137 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
138 // block to the 'To' basic block is currently feasible.
139 bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const;
140
141 std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const;
142
144
146
147 /// getTrackedRetVals - Get the inferred return value map.
149
150 /// getTrackedGlobals - Get and return the set of inferred initializers for
151 /// global variables.
153
154 /// getMRVFunctionsTracked - Get the set of functions which return multiple
155 /// values tracked by the pass.
157
158 /// markOverdefined - Mark the specified value overdefined. This
159 /// works with both scalars and structs.
160 void markOverdefined(Value *V);
161
162 // isStructLatticeConstant - Return true if all the lattice values
163 // corresponding to elements of the structure are constants,
164 // false otherwise.
166
167 /// Helper to return a Constant if \p LV is either a constant or a constant
168 /// range with a single element.
169 Constant *getConstant(const ValueLatticeElement &LV) const;
170
171 /// Return a reference to the set of argument tracked functions.
173
174 /// Mark the constant arguments of a new function specialization. \p F points
175 /// to the cloned function and \p Args contains a list of constant arguments
176 /// represented as pairs of {formal,actual} values (the formal argument is
177 /// associated with the original function definition). All other arguments of
178 /// the specialization inherit the lattice state of their corresponding values
179 /// in the original function.
181 const SmallVectorImpl<ArgInfo> &Args);
182
183 /// Mark all of the blocks in function \p F non-executable. Clients can used
184 /// this method to erase a function from the module (e.g., if it has been
185 /// completely specialized and is no longer needed).
187
188 void visit(Instruction *I);
189 void visitCall(CallInst &I);
190
192 SmallPtrSetImpl<Value *> &InsertedValues,
193 Statistic &InstRemovedStat,
194 Statistic &InstReplacedStat);
195
197 BasicBlock *&NewUnreachableBB) const;
198
200
201 // Helper to check if \p LV is either a constant or a constant
202 // range with a single element. This should cover exactly the same cases as
203 // the old ValueLatticeElement::isConstant() and is intended to be used in the
204 // transition to ValueLatticeElement.
205 static bool isConstant(const ValueLatticeElement &LV);
206
207 // Helper to check if \p LV is either overdefined or a constant range with
208 // more than a single element. This should cover exactly the same cases as the
209 // old ValueLatticeElement::isOverdefined() and is intended to be used in the
210 // transition to ValueLatticeElement.
211 static bool isOverdefined(const ValueLatticeElement &LV);
212};
213} // namespace llvm
214
215#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
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
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:37
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
SCCPSolver - This interface class is a general purpose solver for Sparse Conditional Constant Propaga...
Definition: SCCPSolver.h:75
void visitCall(CallInst &I)
const DenseMap< GlobalVariable *, ValueLatticeElement > & getTrackedGlobals()
getTrackedGlobals - Get and return the set of inferred initializers for global variables.
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:75
bool isStructLatticeConstant(Function *F, StructType *STy)
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.
Constant * getConstant(const ValueLatticeElement &LV) const
Helper to return a Constant if LV is either a constant or a constant range with a single element.
void solveWhileResolvedUndefsIn(Module &M)
const PredicateBase * getPredicateInfoFor(Instruction *I)
const LoopInfo & getLoopInfo(Function &F)
bool resolvedUndefsIn(Function &F)
resolvedUndefsIn - While solving the dataflow for a function, we assume that branches on undef values...
DomTreeUpdater getDTU(Function &F)
void addArgumentTrackedFunction(Function *F)
void addAnalysis(Function &F, AnalysisResultsForFn A)
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.
bool simplifyInstsInBlock(BasicBlock &BB, SmallPtrSetImpl< Value * > &InsertedValues, Statistic &InstRemovedStat, Statistic &InstReplacedStat)
Definition: SCCPSolver.cpp:230
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:254
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 ...
static bool isConstant(const ValueLatticeElement &LV)
Definition: SCCPSolver.cpp:54
void markArgInFuncSpecialization(Function *F, const SmallVectorImpl< ArgInfo > &Args)
Mark the constant arguments of a new function specialization.
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:59
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:344
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
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.
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
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:613
Helper struct for bundling up the analysis results per function for IPSCCP.
Definition: SCCPSolver.h:43
DominatorTree * DT
Definition: SCCPSolver.h:45
std::unique_ptr< PredicateInfo > PredInfo
Definition: SCCPSolver.h:44
PostDominatorTree * PDT
Definition: SCCPSolver.h:46
Helper struct shared between Function Specialization and SCCP Solver.
Definition: SCCPSolver.h:51
friend hash_code hash_value(const ArgInfo &A)
Definition: SCCPSolver.h:63
Argument * Formal
Definition: SCCPSolver.h:52
Constant * Actual
Definition: SCCPSolver.h:53
ArgInfo(Argument *F, Constant *A)
Definition: SCCPSolver.h:55
bool operator!=(const ArgInfo &Other) const
Definition: SCCPSolver.h:61
bool operator==(const ArgInfo &Other) const
Definition: SCCPSolver.h:57