LLVM  16.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 LoopInfo;
34 class PostDominatorTree;
35 class StructType;
36 class TargetLibraryInfo;
37 class Value;
38 class ValueLatticeElement;
39 
40 /// Helper struct for bundling up the analysis results per function for IPSCCP.
42  std::unique_ptr<PredicateInfo> PredInfo;
46 };
47 
48 /// Helper struct shared between Function Specialization and SCCP Solver.
49 struct ArgInfo {
50  Argument *Formal; // The Formal argument being analysed.
51  Constant *Actual; // A corresponding actual constant argument.
52 
54 };
55 
56 class SCCPInstVisitor;
57 
58 //===----------------------------------------------------------------------===//
59 //
60 /// SCCPSolver - This interface class is a general purpose solver for Sparse
61 /// Conditional Constant Propagation (SCCP).
62 ///
63 class SCCPSolver {
64  std::unique_ptr<SCCPInstVisitor> Visitor;
65 
66 public:
67  SCCPSolver(const DataLayout &DL,
68  std::function<const TargetLibraryInfo &(Function &)> GetTLI,
69  LLVMContext &Ctx);
70 
71  ~SCCPSolver();
72 
74 
75  /// markBlockExecutable - This method can be used by clients to mark all of
76  /// the blocks that are known to be intrinsically live in the processed unit.
77  /// This returns true if the block was not considered live before.
79 
81 
82  const LoopInfo &getLoopInfo(Function &F);
83 
85 
86  /// trackValueOfGlobalVariable - Clients can use this method to
87  /// inform the SCCPSolver that it should track loads and stores to the
88  /// specified global variable if it can. This is only legal to call if
89  /// performing Interprocedural SCCP.
91 
92  /// addTrackedFunction - If the SCCP solver is supposed to track calls into
93  /// and out of the specified function (which cannot have its address taken),
94  /// this method must be called.
96 
97  /// Add function to the list of functions whose return cannot be modified.
99 
100  /// Returns true if the return of the given function cannot be modified.
102 
104 
105  /// Returns true if the given function is in the solver's set of
106  /// argument-tracked functions.
108 
109  /// Solve - Solve for constants and executable blocks.
110  void solve();
111 
112  /// resolvedUndefsIn - While solving the dataflow for a function, we assume
113  /// that branches on undef values cannot reach any of their successors.
114  /// However, this is not a safe assumption. After we solve dataflow, this
115  /// method should be use to handle this. If this returns true, the solver
116  /// should be rerun.
117  bool resolvedUndefsIn(Function &F);
118 
119  bool isBlockExecutable(BasicBlock *BB) const;
120 
121  // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
122  // block to the 'To' basic block is currently feasible.
123  bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const;
124 
125  std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const;
126 
127  void removeLatticeValueFor(Value *V);
128 
130 
131  /// getTrackedRetVals - Get the inferred return value map.
133 
134  /// getTrackedGlobals - Get and return the set of inferred initializers for
135  /// global variables.
137 
138  /// getMRVFunctionsTracked - Get the set of functions which return multiple
139  /// values tracked by the pass.
141 
142  /// markOverdefined - Mark the specified value overdefined. This
143  /// works with both scalars and structs.
144  void markOverdefined(Value *V);
145 
146  // isStructLatticeConstant - Return true if all the lattice values
147  // corresponding to elements of the structure are constants,
148  // false otherwise.
150 
151  /// Helper to return a Constant if \p LV is either a constant or a constant
152  /// range with a single element.
153  Constant *getConstant(const ValueLatticeElement &LV) const;
154 
155  /// Return a reference to the set of argument tracked functions.
157 
158  /// Mark the constant arguments of a new function specialization. \p F points
159  /// to the cloned function and \p Args contains a list of constant arguments
160  /// represented as pairs of {formal,actual} values (the formal argument is
161  /// associated with the original function definition). All other arguments of
162  /// the specialization inherit the lattice state of their corresponding values
163  /// in the original function.
166 
167  /// Mark all of the blocks in function \p F non-executable. Clients can used
168  /// this method to erase a function from the module (e.g., if it has been
169  /// completely specialized and is no longer needed).
171 
172  void visit(Instruction *I);
173  void visitCall(CallInst &I);
174 };
175 
176 } // namespace llvm
177 
178 #endif // LLVM_TRANSFORMS_UTILS_SCCPSOLVER_H
llvm::AnalysisResultsForFn::PDT
PostDominatorTree * PDT
Definition: SCCPSolver.h:44
llvm::ArgInfo::Formal
Argument * Formal
Definition: SCCPSolver.h:50
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:18
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:41
llvm::Function
Definition: Function.h:60
llvm::SCCPSolver::getStructLatticeValueFor
std::vector< ValueLatticeElement > getStructLatticeValueFor(Value *V) const
Definition: SCCPSolver.cpp:1574
MapVector.h
DomTreeUpdater.h
llvm::GlobalVariable
Definition: GlobalVariable.h:39
llvm::SCCPSolver::getLoopInfo
const LoopInfo & getLoopInfo(Function &F)
Definition: SCCPSolver.cpp:1529
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:1606
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:1521
llvm::SCCPSolver::visit
void visit(Instruction *I)
Definition: SCCPSolver.cpp:1623
llvm::logicalview::LVAttributeKind::Argument
@ Argument
llvm::SCCPSolver::addArgumentTrackedFunction
void addArgumentTrackedFunction(Function *F)
Definition: SCCPSolver.cpp:1551
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:1619
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:1600
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:1555
llvm::SCCPSolver::addAnalysis
void addAnalysis(Function &F, AnalysisResultsForFn A)
Definition: SCCPSolver.cpp:1517
llvm::Instruction
Definition: Instruction.h:42
llvm::AnalysisResultsForFn::PredInfo
std::unique_ptr< PredicateInfo > PredInfo
Definition: SCCPSolver.h:42
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
llvm::SCCPSolver::isStructLatticeConstant
bool isStructLatticeConstant(Function *F, StructType *STy)
Definition: SCCPSolver.cpp:1602
llvm::SCCPSolver::getTrackedRetVals
const MapVector< Function *, ValueLatticeElement > & getTrackedRetVals()
getTrackedRetVals - Get the inferred return value map.
Definition: SCCPSolver.cpp:1587
llvm::PredicateBase
Definition: PredicateInfo.h:82
llvm::SCCPSolver::visitCall
void visitCall(CallInst &I)
Definition: SCCPSolver.cpp:1625
llvm::SCCPSolver::getLatticeValueFor
const ValueLatticeElement & getLatticeValueFor(Value *V) const
Definition: SCCPSolver.cpp:1582
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:53
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
llvm::SCCPSolver::getPredicateInfoFor
const PredicateBase * getPredicateInfoFor(Instruction *I)
Definition: SCCPSolver.cpp:1525
llvm::DenseMap
Definition: DenseMap.h:714
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:63
llvm::AnalysisResultsForFn::LI
LoopInfo * LI
Definition: SCCPSolver.h:45
llvm::SCCPSolver::getTrackedGlobals
const DenseMap< GlobalVariable *, ValueLatticeElement > & getTrackedGlobals()
getTrackedGlobals - Get and return the set of inferred initializers for global variables.
Definition: SCCPSolver.cpp:1592
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:1533
llvm::SCCPSolver::markArgInFuncSpecialization
void markArgInFuncSpecialization(Function *F, const SmallVectorImpl< ArgInfo > &Args)
Mark the constant arguments of a new function specialization.
Definition: SCCPSolver.cpp:1614
llvm::LoopInfo
Definition: LoopInfo.h:1108
llvm::SCCPSolver::SCCPSolver
SCCPSolver(const DataLayout &DL, std::function< const TargetLibraryInfo &(Function &)> GetTLI, LLVMContext &Ctx)
Definition: SCCPSolver.cpp:1509
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:1578
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:1547
llvm::ArgInfo
Helper struct shared between Function Specialization and SCCP Solver.
Definition: SCCPSolver.h:49
llvm::SCCPSolver::isBlockExecutable
bool isBlockExecutable(BasicBlock *BB) const
Definition: SCCPSolver.cpp:1565
llvm::SCCPSolver::isEdgeFeasible
bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const
Definition: SCCPSolver.cpp:1569
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:226
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:1561
llvm::ArgInfo::Actual
Constant * Actual
Definition: SCCPSolver.h:51
llvm::SCCPSolver::addToMustPreserveReturnsInFunctions
void addToMustPreserveReturnsInFunctions(Function *F)
Add function to the list of functions whose return cannot be modified.
Definition: SCCPSolver.cpp:1543
llvm::AnalysisResultsForFn::DT
DominatorTree * DT
Definition: SCCPSolver.h:43
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:1535
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:1559
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:1539
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:1596
llvm::codeview::PublicSymFlags::Function
@ Function
llvm::SCCPSolver::getArgumentTrackedFunctions
SmallPtrSetImpl< Function * > & getArgumentTrackedFunctions()
Return a reference to the set of argument tracked functions.
Definition: SCCPSolver.cpp:1610