LLVM  15.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"
20 #include <vector>
21 
22 namespace llvm {
23 class Argument;
24 class BasicBlock;
25 class CallInst;
26 class Constant;
27 class DataLayout;
28 class DominatorTree;
29 class Function;
30 class GlobalVariable;
31 class Instruction;
32 class LLVMContext;
33 class PostDominatorTree;
34 class StructType;
35 class TargetLibraryInfo;
36 class Value;
37 class ValueLatticeElement;
38 
39 /// Helper struct for bundling up the analysis results per function for IPSCCP.
41  std::unique_ptr<PredicateInfo> PredInfo;
44 };
45 
46 /// Helper struct shared between Function Specialization and SCCP Solver.
47 struct ArgInfo {
48  Argument *Formal; // The Formal argument being analysed.
49  Constant *Actual; // A corresponding actual constant argument.
50 
52 };
53 
54 class SCCPInstVisitor;
55 
56 //===----------------------------------------------------------------------===//
57 //
58 /// SCCPSolver - This interface class is a general purpose solver for Sparse
59 /// Conditional Constant Propagation (SCCP).
60 ///
61 class SCCPSolver {
62  std::unique_ptr<SCCPInstVisitor> Visitor;
63 
64 public:
65  SCCPSolver(const DataLayout &DL,
66  std::function<const TargetLibraryInfo &(Function &)> GetTLI,
67  LLVMContext &Ctx);
68 
69  ~SCCPSolver();
70 
72 
73  /// markBlockExecutable - This method can be used by clients to mark all of
74  /// the blocks that are known to be intrinsically live in the processed unit.
75  /// This returns true if the block was not considered live before.
77 
79 
81 
82  /// trackValueOfGlobalVariable - Clients can use this method to
83  /// inform the SCCPSolver that it should track loads and stores to the
84  /// specified global variable if it can. This is only legal to call if
85  /// performing Interprocedural SCCP.
87 
88  /// addTrackedFunction - If the SCCP solver is supposed to track calls into
89  /// and out of the specified function (which cannot have its address taken),
90  /// this method must be called.
92 
93  /// Add function to the list of functions whose return cannot be modified.
95 
96  /// Returns true if the return of the given function cannot be modified.
98 
100 
101  /// Returns true if the given function is in the solver's set of
102  /// argument-tracked functions.
104 
105  /// Solve - Solve for constants and executable blocks.
106  void solve();
107 
108  /// resolvedUndefsIn - While solving the dataflow for a function, we assume
109  /// that branches on undef values cannot reach any of their successors.
110  /// However, this is not a safe assumption. After we solve dataflow, this
111  /// method should be use to handle this. If this returns true, the solver
112  /// should be rerun.
113  bool resolvedUndefsIn(Function &F);
114 
115  bool isBlockExecutable(BasicBlock *BB) const;
116 
117  // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
118  // block to the 'To' basic block is currently feasible.
119  bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const;
120 
121  std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const;
122 
123  void removeLatticeValueFor(Value *V);
124 
126 
127  /// getTrackedRetVals - Get the inferred return value map.
129 
130  /// getTrackedGlobals - Get and return the set of inferred initializers for
131  /// global variables.
133 
134  /// getMRVFunctionsTracked - Get the set of functions which return multiple
135  /// values tracked by the pass.
137 
138  /// markOverdefined - Mark the specified value overdefined. This
139  /// works with both scalars and structs.
140  void markOverdefined(Value *V);
141 
142  // isStructLatticeConstant - Return true if all the lattice values
143  // corresponding to elements of the structure are constants,
144  // false otherwise.
146 
147  /// Helper to return a Constant if \p LV is either a constant or a constant
148  /// range with a single element.
149  Constant *getConstant(const ValueLatticeElement &LV) const;
150 
151  /// Return a reference to the set of argument tracked functions.
153 
154  /// Mark the constant arguments of a new function specialization. \p F points
155  /// to the cloned function and \p Args contains a list of constant arguments
156  /// represented as pairs of {formal,actual} values (the formal argument is
157  /// associated with the original function definition). All other arguments of
158  /// the specialization inherit the lattice state of their corresponding values
159  /// in the original function.
162 
163  /// Mark all of the blocks in function \p F non-executable. Clients can used
164  /// this method to erase a function from the module (e.g., if it has been
165  /// completely specialized and is no longer needed).
167 
168  void visit(Instruction *I);
169  void visitCall(CallInst &I);
170 };
171 
172 } // namespace llvm
173 
174 #endif // LLVM_TRANSFORMS_UTILS_SCCPSOLVER_H
llvm::AnalysisResultsForFn::PDT
PostDominatorTree * PDT
Definition: SCCPSolver.h:43
llvm::ArgInfo::Formal
Argument * Formal
Definition: SCCPSolver.h:48
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
PredicateInfo.h
llvm::AnalysisResultsForFn
Helper struct for bundling up the analysis results per function for IPSCCP.
Definition: SCCPSolver.h:40
llvm::Function
Definition: Function.h:60
llvm::SCCPSolver::getStructLatticeValueFor
std::vector< ValueLatticeElement > getStructLatticeValueFor(Value *V) const
Definition: SCCPSolver.cpp:1684
MapVector.h
DomTreeUpdater.h
llvm::GlobalVariable
Definition: GlobalVariable.h:39
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::SCCPSolver::getConstant
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.
Definition: SCCPSolver.cpp:1716
llvm::MapVector
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:37
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::SCCPSolver::markBlockExecutable
bool markBlockExecutable(BasicBlock *BB)
markBlockExecutable - This method can be used by clients to mark all of the blocks that are known to ...
Definition: SCCPSolver.cpp:1635
llvm::SCCPSolver::visit
void visit(Instruction *I)
Definition: SCCPSolver.cpp:1733
llvm::SCCPSolver::addArgumentTrackedFunction
void addArgumentTrackedFunction(Function *F)
Definition: SCCPSolver.cpp:1661
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::SCCPSolver::markFunctionUnreachable
void markFunctionUnreachable(Function *F)
Mark all of the blocks in function F non-executable.
Definition: SCCPSolver.cpp:1729
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::ISD::Constant
@ Constant
Definition: ISDOpcodes.h:76
llvm::SCCPSolver::markOverdefined
void markOverdefined(Value *V)
markOverdefined - Mark the specified value overdefined.
Definition: SCCPSolver.cpp:1710
llvm::SCCPSolver::isArgumentTrackedFunction
bool isArgumentTrackedFunction(Function *F)
Returns true if the given function is in the solver's set of argument-tracked functions.
Definition: SCCPSolver.cpp:1665
llvm::SCCPSolver::addAnalysis
void addAnalysis(Function &F, AnalysisResultsForFn A)
Definition: SCCPSolver.cpp:1631
llvm::Instruction
Definition: Instruction.h:42
llvm::AnalysisResultsForFn::PredInfo
std::unique_ptr< PredicateInfo > PredInfo
Definition: SCCPSolver.h:41
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
llvm::SCCPSolver::isStructLatticeConstant
bool isStructLatticeConstant(Function *F, StructType *STy)
Definition: SCCPSolver.cpp:1712
llvm::SCCPSolver::getTrackedRetVals
const MapVector< Function *, ValueLatticeElement > & getTrackedRetVals()
getTrackedRetVals - Get the inferred return value map.
Definition: SCCPSolver.cpp:1697
llvm::PredicateBase
Definition: PredicateInfo.h:82
llvm::SCCPSolver::visitCall
void visitCall(CallInst &I)
Definition: SCCPSolver.cpp:1735
llvm::SCCPSolver::getLatticeValueFor
const ValueLatticeElement & getLatticeValueFor(Value *V) const
Definition: SCCPSolver.cpp:1692
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::ArgInfo::ArgInfo
ArgInfo(Argument *F, Constant *A)
Definition: SCCPSolver.h:51
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::SCCPSolver::getPredicateInfoFor
const PredicateBase * getPredicateInfoFor(Instruction *I)
Definition: SCCPSolver.cpp:1639
llvm::DenseMap
Definition: DenseMap.h:716
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::SCCPSolver
SCCPSolver - This interface class is a general purpose solver for Sparse Conditional Constant Propaga...
Definition: SCCPSolver.h:61
llvm::SCCPSolver::getTrackedGlobals
const DenseMap< GlobalVariable *, ValueLatticeElement > & getTrackedGlobals()
getTrackedGlobals - Get and return the set of inferred initializers for global variables.
Definition: SCCPSolver.cpp:1702
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:82
llvm::SCCPSolver::~SCCPSolver
~SCCPSolver()
llvm::SCCPSolver::getDTU
DomTreeUpdater getDTU(Function &F)
Definition: SCCPSolver.cpp:1643
llvm::SCCPSolver::markArgInFuncSpecialization
void markArgInFuncSpecialization(Function *F, const SmallVectorImpl< ArgInfo > &Args)
Mark the constant arguments of a new function specialization.
Definition: SCCPSolver.cpp:1724
llvm::SCCPSolver::SCCPSolver
SCCPSolver(const DataLayout &DL, std::function< const TargetLibraryInfo &(Function &)> GetTLI, LLVMContext &Ctx)
Definition: SCCPSolver.cpp:1623
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:213
llvm::PostDominatorTree
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Definition: PostDominators.h:28
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::SCCPSolver::removeLatticeValueFor
void removeLatticeValueFor(Value *V)
Definition: SCCPSolver.cpp:1688
llvm::ValueLatticeElement
This class represents lattice values for constants.
Definition: ValueLattice.h:29
llvm::SCCPSolver::mustPreserveReturn
bool mustPreserveReturn(Function *F)
Returns true if the return of the given function cannot be modified.
Definition: SCCPSolver.cpp:1657
llvm::ArgInfo
Helper struct shared between Function Specialization and SCCP Solver.
Definition: SCCPSolver.h:47
llvm::SCCPSolver::isBlockExecutable
bool isBlockExecutable(BasicBlock *BB) const
Definition: SCCPSolver.cpp:1675
llvm::SCCPSolver::isEdgeFeasible
bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const
Definition: SCCPSolver.cpp:1679
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:222
llvm::SCCPSolver::resolvedUndefsIn
bool resolvedUndefsIn(Function &F)
resolvedUndefsIn - While solving the dataflow for a function, we assume that branches on undef values...
Definition: SCCPSolver.cpp:1671
llvm::ArgInfo::Actual
Constant * Actual
Definition: SCCPSolver.h:49
llvm::SCCPSolver::addToMustPreserveReturnsInFunctions
void addToMustPreserveReturnsInFunctions(Function *F)
Add function to the list of functions whose return cannot be modified.
Definition: SCCPSolver.cpp:1653
llvm::AnalysisResultsForFn::DT
DominatorTree * DT
Definition: SCCPSolver.h:42
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::SCCPSolver::trackValueOfGlobalVariable
void trackValueOfGlobalVariable(GlobalVariable *GV)
trackValueOfGlobalVariable - Clients can use this method to inform the SCCPSolver that it should trac...
Definition: SCCPSolver.cpp:1645
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1474
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::SCCPSolver::solve
void solve()
Solve - Solve for constants and executable blocks.
Definition: SCCPSolver.cpp:1669
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::AMDGPU::HSAMD::Kernel::Key::Args
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
Definition: AMDGPUMetadata.h:394
llvm::SCCPSolver::addTrackedFunction
void addTrackedFunction(Function *F)
addTrackedFunction - If the SCCP solver is supposed to track calls into and out of the specified func...
Definition: SCCPSolver.cpp:1649
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::SCCPSolver::getMRVFunctionsTracked
const SmallPtrSet< Function *, 16 > getMRVFunctionsTracked()
getMRVFunctionsTracked - Get the set of functions which return multiple values tracked by the pass.
Definition: SCCPSolver.cpp:1706
llvm::codeview::PublicSymFlags::Function
@ Function
llvm::SCCPSolver::getArgumentTrackedFunctions
SmallPtrSetImpl< Function * > & getArgumentTrackedFunctions()
Return a reference to the set of argument tracked functions.
Definition: SCCPSolver.cpp:1720