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"
18#include "llvm/Analysis/DomTreeUpdater.h"
19#include "llvm/Analysis/TargetLibraryInfo.h"
20#include "llvm/Analysis/ValueLattice.h"
21#include "llvm/Analysis/ValueLatticeUtils.h"
22#include "llvm/IR/InstVisitor.h"
23#include "llvm/Transforms/Utils/PredicateInfo.h"
24#include <cassert>
25#include <utility>
26#include <vector>
27
28namespace llvm {
29
30/// Helper struct for bundling up the analysis results per function for IPSCCP.
31struct AnalysisResultsForFn {
32 std::unique_ptr<PredicateInfo> PredInfo;
33 DominatorTree *DT;
34 PostDominatorTree *PDT;
35};
36
37class SCCPInstVisitor;
38
39//===----------------------------------------------------------------------===//
40//
41/// SCCPSolver - This interface class is a general purpose solver for Sparse
42/// Conditional Constant Propagation (SCCP).
43///
44class SCCPSolver {
45 std::unique_ptr<SCCPInstVisitor> Visitor;
46
47public:
48 SCCPSolver(const DataLayout &DL,
49 std::function<const TargetLibraryInfo &(Function &)> GetTLI,
50 LLVMContext &Ctx);
51
52 ~SCCPSolver();
53
54 void addAnalysis(Function &F, AnalysisResultsForFn A);
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.
59 bool markBlockExecutable(BasicBlock *BB);
60
61 const PredicateBase *getPredicateInfoFor(Instruction *I);
62
63 DomTreeUpdater getDTU(Function &F);
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.
69 void trackValueOfGlobalVariable(GlobalVariable *GV);
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.
74 void addTrackedFunction(Function *F);
75
76 /// Add function to the list of functions whose return cannot be modified.
77 void addToMustPreserveReturnsInFunctions(Function *F);
78
79 /// Returns true if the return of the given function cannot be modified.
80 bool mustPreserveReturn(Function *F);
81
82 void addArgumentTrackedFunction(Function *F);
83
84 /// Returns true if the given function is in the solver's set of
85 /// argument-tracked functions.
86 bool isArgumentTrackedFunction(Function *F);
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.
96 bool resolvedUndefsIn(Function &F);
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
108 const ValueLatticeElement &getLatticeValueFor(Value *V) const;
109
110 /// getTrackedRetVals - Get the inferred return value map.
111 const MapVector<Function *, ValueLatticeElement> &getTrackedRetVals();
112
113 /// getTrackedGlobals - Get and return the set of inferred initializers for
114 /// global variables.
115 const DenseMap<GlobalVariable *, ValueLatticeElement> &getTrackedGlobals();
116
117 /// getMRVFunctionsTracked - Get the set of functions which return multiple
118 /// values tracked by the pass.
119 const SmallPtrSet<Function *, 16> getMRVFunctionsTracked();
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.
128 bool isStructLatticeConstant(Function *F, StructType *STy);
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
138