1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
|
//===- SCCPSolver.h - SCCP Utility ----------------------------- *- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// \file
// This file implements Sparse Conditional Constant Propagation (SCCP) utility.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_TRANSFORMS_UTILS_SCCPSOLVER_H
#define LLVM_TRANSFORMS_UTILS_SCCPSOLVER_H
#include "llvm/ADT/MapVector.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueLattice.h"
#include "llvm/Analysis/ValueLatticeUtils.h"
#include "llvm/IR/InstVisitor.h"
#include "llvm/Transforms/Utils/PredicateInfo.h"
#include <cassert>
#include <utility>
#include <vector>
namespace llvm {
/// Helper struct for bundling up the analysis results per function for IPSCCP.
struct AnalysisResultsForFn {
std::unique_ptr<PredicateInfo> PredInfo;
DominatorTree *DT;
PostDominatorTree *PDT;
};
class SCCPInstVisitor;
//===----------------------------------------------------------------------===//
//
/// SCCPSolver - This interface class is a general purpose solver for Sparse
/// Conditional Constant Propagation (SCCP).
///
class SCCPSolver {
std::unique_ptr<SCCPInstVisitor> Visitor;
public:
SCCPSolver(const DataLayout &DL,
std::function<const TargetLibraryInfo &(Function &)> GetTLI,
LLVMContext &Ctx);
~SCCPSolver();
void addAnalysis(Function &F, AnalysisResultsForFn A);
/// markBlockExecutable - This method can be used by clients to mark all of
/// the blocks that are known to be intrinsically live in the processed unit.
/// This returns true if the block was not considered live before.
bool markBlockExecutable(BasicBlock *BB);
const PredicateBase *getPredicateInfoFor(Instruction *I);
DomTreeUpdater getDTU(Function &F);
/// trackValueOfGlobalVariable - Clients can use this method to
/// inform the SCCPSolver that it should track loads and stores to the
/// specified global variable if it can. This is only legal to call if
/// performing Interprocedural SCCP.
void trackValueOfGlobalVariable(GlobalVariable *GV);
/// addTrackedFunction - If the SCCP solver is supposed to track calls into
/// and out of the specified function (which cannot have its address taken),
/// this method must be called.
void addTrackedFunction(Function *F);
/// Add function to the list of functions whose return cannot be modified.
void addToMustPreserveReturnsInFunctions(Function *F);
/// Returns true if the return of the given function cannot be modified.
bool mustPreserveReturn(Function *F);
void addArgumentTrackedFunction(Function *F);
/// Returns true if the given function is in the solver's set of
/// argument-tracked functions.
bool isArgumentTrackedFunction(Function *F);
/// Solve - Solve for constants and executable blocks.
void solve();
/// resolvedUndefsIn - While solving the dataflow for a function, we assume
/// that branches on undef values cannot reach any of their successors.
/// However, this is not a safe assumption. After we solve dataflow, this
/// method should be use to handle this. If this returns true, the solver
/// should be rerun.
bool resolvedUndefsIn(Function &F);
bool isBlockExecutable(BasicBlock *BB) const;
// isEdgeFeasible - Return true if the control flow edge from the 'From' basic
// block to the 'To' basic block is currently feasible.
bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const;
std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const;
void removeLatticeValueFor(Value *V);
const ValueLatticeElement &getLatticeValueFor(Value *V) const;
/// getTrackedRetVals - Get the inferred return value map.
const MapVector<Function *, ValueLatticeElement> &getTrackedRetVals();
/// getTrackedGlobals - Get and return the set of inferred initializers for
/// global variables.
const DenseMap<GlobalVariable *, ValueLatticeElement> &getTrackedGlobals();
/// getMRVFunctionsTracked - Get the set of functions which return multiple
/// values tracked by the pass.
const SmallPtrSet<Function *, 16> getMRVFunctionsTracked();
/// markOverdefined - Mark the specified value overdefined. This
/// works with both scalars and structs.
void markOverdefined(Value *V);
// isStructLatticeConstant - Return true if all the lattice values
// corresponding to elements of the structure are constants,
// false otherwise.
bool isStructLatticeConstant(Function *F, StructType *STy);
/// Helper to return a Constant if \p LV is either a constant or a constant
/// range with a single element.
Constant *getConstant(const ValueLatticeElement &LV) const;
/// Return a reference to the set of argument tracked functions.
SmallPtrSetImpl<Function *> &getArgumentTrackedFunctions();
/// Mark argument \p A constant with value \p C in a new function
/// specialization. The argument's parent function is a specialization of the
/// original function \p F. All other arguments of the specialization inherit
/// the lattice state of their corresponding values in the original function.
void markArgInFuncSpecialization(Function *F, Argument *A, Constant *C);
/// Mark all of the blocks in function \p F non-executable. Clients can used
/// this method to erase a function from the module (e.g., if it has been
/// completely specialized and is no longer needed).
void markFunctionUnreachable(Function *F);
void visit(Instruction *I);
void visitCall(CallInst &I);
};
} // namespace llvm
#endif // LLVM_TRANSFORMS_UTILS_SCCPSOLVER_H
|
