LLVM  14.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"
22 #include "llvm/IR/InstVisitor.h"
24 #include <cassert>
25 #include <utility>
26 #include <vector>
27 
28 namespace llvm {
29 
30 /// Helper struct for bundling up the analysis results per function for IPSCCP.
32  std::unique_ptr<PredicateInfo> PredInfo;
35 };
36 
37 class SCCPInstVisitor;
38 
39 //===----------------------------------------------------------------------===//
40 //
41 /// SCCPSolver - This interface class is a general purpose solver for Sparse
42 /// Conditional Constant Propagation (SCCP).
43 ///
44 class SCCPSolver {
45  std::unique_ptr<SCCPInstVisitor> Visitor;
46 
47 public:
48  SCCPSolver(const DataLayout &DL,
49  std::function<const TargetLibraryInfo &(Function &)> GetTLI,
50  LLVMContext &Ctx);
51 
52  ~SCCPSolver();
53 
55 
56  /// markBlockExecutable - This method can be used by clients to mark all of
57  /// the blocks that are known to be intrinsically live in the processed unit.
58  /// This returns true if the block was not considered live before.
60 
62 
64 
65  /// trackValueOfGlobalVariable - Clients can use this method to
66  /// inform the SCCPSolver that it should track loads and stores to the
67  /// specified global variable if it can. This is only legal to call if
68  /// performing Interprocedural SCCP.
70 
71  /// addTrackedFunction - If the SCCP solver is supposed to track calls into
72  /// and out of the specified function (which cannot have its address taken),
73  /// this method must be called.
75 
76  /// Add function to the list of functions whose return cannot be modified.
78 
79  /// Returns true if the return of the given function cannot be modified.
81 
83 
84  /// Returns true if the given function is in the solver's set of
85  /// argument-tracked functions.
87 
88  /// Solve - Solve for constants and executable blocks.
89  void solve();
90 
91  /// resolvedUndefsIn - While solving the dataflow for a function, we assume
92  /// that branches on undef values cannot reach any of their successors.
93  /// However, this is not a safe assumption. After we solve dataflow, this
94  /// method should be use to handle this. If this returns true, the solver
95  /// should be rerun.
97 
98  bool isBlockExecutable(BasicBlock *BB) const;
99 
100  // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
101  // block to the 'To' basic block is currently feasible.
102  bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const;
103 
104  std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const;
105 
106  void removeLatticeValueFor(Value *V);
107 
109 
110  /// getTrackedRetVals - Get the inferred return value map.
112 
113  /// getTrackedGlobals - Get and return the set of inferred initializers for
114  /// global variables.
116 
117  /// getMRVFunctionsTracked - Get the set of functions which return multiple
118  /// values tracked by the pass.
120 
121  /// markOverdefined - Mark the specified value overdefined. This
122  /// works with both scalars and structs.
123  void markOverdefined(Value *V);
124 
125  // isStructLatticeConstant - Return true if all the lattice values
126  // corresponding to elements of the structure are constants,
127  // false otherwise.
129 
130  /// Helper to return a Constant if \p LV is either a constant or a constant
131  /// range with a single element.
132  Constant *getConstant(const ValueLatticeElement &LV) const;
133 
134  /// Return a reference to the set of argument tracked functions.
136 
137  /// Mark argument \p A constant with value \p C in a new function
138  /// specialization. The argument's parent function is a specialization of the
139  /// original function \p F. All other arguments of the specialization inherit
140  /// the lattice state of their corresponding values in the original function.
142 
143  /// Mark all of the blocks in function \p F non-executable. Clients can used
144  /// this method to erase a function from the module (e.g., if it has been
145  /// completely specialized and is no longer needed).
147 
148  void visit(Instruction *I);
149  void visitCall(CallInst &I);
150 };
151 
152 } // namespace llvm
153 
154 #endif // LLVM_TRANSFORMS_UTILS_SCCPSOLVER_H
llvm::AnalysisResultsForFn::PDT
PostDominatorTree * PDT
Definition: SCCPSolver.h:34
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
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:31
llvm::Function
Definition: Function.h:62
llvm::SCCPSolver::getStructLatticeValueFor
std::vector< ValueLatticeElement > getStructLatticeValueFor(Value *V) const
Definition: SCCPSolver.cpp:1668
MapVector.h
DomTreeUpdater.h
llvm::GlobalVariable
Definition: GlobalVariable.h:40
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
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:1700
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:449
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:1619
llvm::SCCPSolver::visit
void visit(Instruction *I)
Definition: SCCPSolver.cpp:1717
llvm::SCCPSolver::addArgumentTrackedFunction
void addArgumentTrackedFunction(Function *F)
Definition: SCCPSolver.cpp:1645
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::SCCPSolver::markFunctionUnreachable
void markFunctionUnreachable(Function *F)
Mark all of the blocks in function F non-executable.
Definition: SCCPSolver.cpp:1713
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::SCCPSolver::markOverdefined
void markOverdefined(Value *V)
markOverdefined - Mark the specified value overdefined.
Definition: SCCPSolver.cpp:1694
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
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:1649
TargetLibraryInfo.h
llvm::SCCPSolver::addAnalysis
void addAnalysis(Function &F, AnalysisResultsForFn A)
Definition: SCCPSolver.cpp:1615
llvm::Instruction
Definition: Instruction.h:45
llvm::AnalysisResultsForFn::PredInfo
std::unique_ptr< PredicateInfo > PredInfo
Definition: SCCPSolver.h:32
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
llvm::SCCPSolver::isStructLatticeConstant
bool isStructLatticeConstant(Function *F, StructType *STy)
Definition: SCCPSolver.cpp:1696
llvm::SCCPSolver::getTrackedRetVals
const MapVector< Function *, ValueLatticeElement > & getTrackedRetVals()
getTrackedRetVals - Get the inferred return value map.
Definition: SCCPSolver.cpp:1681
llvm::PredicateBase
Definition: PredicateInfo.h:82
llvm::SCCPSolver::visitCall
void visitCall(CallInst &I)
Definition: SCCPSolver.cpp:1719
llvm::SCCPSolver::getLatticeValueFor
const ValueLatticeElement & getLatticeValueFor(Value *V) const
Definition: SCCPSolver.cpp:1676
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::SCCPInstVisitor
Helper class for SCCPSolver.
Definition: SCCPSolver.cpp:69
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:1623
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::SCCPSolver
SCCPSolver - This interface class is a general purpose solver for Sparse Conditional Constant Propaga...
Definition: SCCPSolver.h:44
llvm::SCCPSolver::getTrackedGlobals
const DenseMap< GlobalVariable *, ValueLatticeElement > & getTrackedGlobals()
getTrackedGlobals - Get and return the set of inferred initializers for global variables.
Definition: SCCPSolver.cpp:1686
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:83
llvm::SCCPSolver::~SCCPSolver
~SCCPSolver()
Definition: SCCPSolver.cpp:1613
llvm::SCCPSolver::getDTU
DomTreeUpdater getDTU(Function &F)
Definition: SCCPSolver.cpp:1627
llvm::SCCPSolver::SCCPSolver
SCCPSolver(const DataLayout &DL, std::function< const TargetLibraryInfo &(Function &)> GetTLI, LLVMContext &Ctx)
Definition: SCCPSolver.cpp:1607
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:213
InstVisitor.h
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:1672
llvm::ValueLatticeElement
This class represents lattice values for constants.
Definition: ValueLattice.h:27
llvm::SCCPSolver::mustPreserveReturn
bool mustPreserveReturn(Function *F)
Returns true if the return of the given function cannot be modified.
Definition: SCCPSolver.cpp:1641
ValueLatticeUtils.h
llvm::SCCPSolver::isBlockExecutable
bool isBlockExecutable(BasicBlock *BB) const
Definition: SCCPSolver.cpp:1659
llvm::SCCPSolver::isEdgeFeasible
bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const
Definition: SCCPSolver.cpp:1663
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:221
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:1655
llvm::SCCPSolver::addToMustPreserveReturnsInFunctions
void addToMustPreserveReturnsInFunctions(Function *F)
Add function to the list of functions whose return cannot be modified.
Definition: SCCPSolver.cpp:1637
llvm::SCCPSolver::markArgInFuncSpecialization
void markArgInFuncSpecialization(Function *F, Argument *A, Constant *C)
Mark argument A constant with value C in a new function specialization.
Definition: SCCPSolver.cpp:1708
llvm::AnalysisResultsForFn::DT
DominatorTree * DT
Definition: SCCPSolver.h:33
llvm::SCCPSolver::trackValueOfGlobalVariable
void trackValueOfGlobalVariable(GlobalVariable *GV)
trackValueOfGlobalVariable - Clients can use this method to inform the SCCPSolver that it should trac...
Definition: SCCPSolver.cpp:1629
llvm::SmallPtrSetImpl< Function * >
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1475
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:1653
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
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:1633
ValueLattice.h
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:1690
llvm::SCCPSolver::getArgumentTrackedFunctions
SmallPtrSetImpl< Function * > & getArgumentTrackedFunctions()
Return a reference to the set of argument tracked functions.
Definition: SCCPSolver.cpp:1704