LLVM  13.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 
135 } // namespace llvm
136 
137 #endif // LLVM_TRANSFORMS_UTILS_SCCPSOLVER_H
llvm::AnalysisResultsForFn::PDT
PostDominatorTree * PDT
Definition: SCCPSolver.h:34
llvm
Definition: AllocatorList.h:23
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
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:61
llvm::SCCPSolver::getStructLatticeValueFor
std::vector< ValueLatticeElement > getStructLatticeValueFor(Value *V) const
Definition: SCCPSolver.cpp:1632
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:1664
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:1583
llvm::SCCPSolver::addArgumentTrackedFunction
void addArgumentTrackedFunction(Function *F)
Definition: SCCPSolver.cpp:1609
F
#define F(x, y, z)
Definition: MD5.cpp:56
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:1658
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:1613
TargetLibraryInfo.h
llvm::SCCPSolver::addAnalysis
void addAnalysis(Function &F, AnalysisResultsForFn A)
Definition: SCCPSolver.cpp:1579
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:1660
llvm::SCCPSolver::getTrackedRetVals
const MapVector< Function *, ValueLatticeElement > & getTrackedRetVals()
getTrackedRetVals - Get the inferred return value map.
Definition: SCCPSolver.cpp:1645
llvm::PredicateBase
Definition: PredicateInfo.h:80
llvm::SCCPSolver::getLatticeValueFor
const ValueLatticeElement & getLatticeValueFor(Value *V) const
Definition: SCCPSolver.cpp:1640
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:1587
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:1650
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:83
llvm::SCCPSolver::~SCCPSolver
~SCCPSolver()
Definition: SCCPSolver.cpp:1577
llvm::SCCPSolver::getDTU
DomTreeUpdater getDTU(Function &F)
Definition: SCCPSolver.cpp:1591
llvm::SCCPSolver::SCCPSolver
SCCPSolver(const DataLayout &DL, std::function< const TargetLibraryInfo &(Function &)> GetTLI, LLVMContext &Ctx)
Definition: SCCPSolver.cpp:1571
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:212
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:1636
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:1605
ValueLatticeUtils.h
llvm::SCCPSolver::isBlockExecutable
bool isBlockExecutable(BasicBlock *BB) const
Definition: SCCPSolver.cpp:1623
llvm::SCCPSolver::isEdgeFeasible
bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const
Definition: SCCPSolver.cpp:1627
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:208
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:1619
llvm::SCCPSolver::addToMustPreserveReturnsInFunctions
void addToMustPreserveReturnsInFunctions(Function *F)
Add function to the list of functions whose return cannot be modified.
Definition: SCCPSolver.cpp:1601
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:1593
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:1617
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:1597
ValueLattice.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
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:1654