LLVM: include/llvm/Analysis/ConstraintSystem.h Source File (original) (raw)
1
2
3
4
5
6
7
8
9#ifndef LLVM_ANALYSIS_CONSTRAINTSYSTEM_H
10#define LLVM_ANALYSIS_CONSTRAINTSYSTEM_H
11
17
18#include
19
20namespace llvm {
21
24 struct Entry {
25 int64_t Coefficient;
27
28 Entry(int64_t Coefficient, uint16_t Id)
29 : Coefficient(Coefficient), Id(Id) {}
30 };
31
32 static int64_t getConstPart(const Entry &E) {
33 if (E.Id == 0)
34 return E.Coefficient;
35 return 0;
36 }
37
39 if (Row.empty())
40 return 0;
41 if (Row.back().Id == Id)
42 return Row.back().Coefficient;
43 return 0;
44 }
45
46 size_t NumVariables = 0;
47
48
49
50
52
53
54
56
57
58 bool eliminateUsingFM();
59
60
61 bool mayHaveSolutionImpl();
62
63
65
66public:
69 NumVariables += FunctionArgs.size();
70 for (auto *Arg : FunctionArgs) {
71 Value2Index.insert({Arg, Value2Index.size() + 1});
72 }
73 }
75 : NumVariables(Value2Index.size()), Value2Index(Value2Index) {}
76
78 assert(Constraints.empty() || R.size() == NumVariables);
79
80
81 if (all_of(ArrayRef(R).drop_front(1), [](int64_t C) { return C == 0; }))
82 return false;
83
85 for (const auto &[Idx, C] : enumerate(R)) {
86 if (C == 0)
87 continue;
89 }
90 if (Constraints.empty())
91 NumVariables = R.size();
92 Constraints.push_back(std::move(NewRow));
93 return true;
94 }
95
98 return Value2Index;
99 }
100
102
103
104 if (all_of(ArrayRef(R).drop_front(1), [](int64_t C) { return C == 0; }))
105 return false;
106
107 NumVariables = std::max(R.size(), NumVariables);
109 }
110
111
113
115
116
118 return {};
119
121 }
122
123
124
125
126
128
129 for (auto &C : R)
131 return {};
132 return R;
133 }
134
135
136
137
138
140
141 if (SubOverflow(R[0], int64_t(1), R[0])) {
142 return {};
143 }
144 return R;
145 }
146
148
150 assert(!Constraints.empty() && "Constraint system is empty");
152 for (auto &Entry : Constraints.back())
153 Result[Entry.Id] = Entry.Coefficient;
154 return Result;
155 }
156
160 NumVariables -= N;
161 }
162
163
164 unsigned size() const { return Constraints.size(); }
165
166
168};
169}
170
171#endif
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines the DenseMap class.
This file defines the SmallVector class.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
size - Get the array size.
DenseMap< Value *, unsigned > & getValue2Index()
Definition ConstraintSystem.h:96
void popLastConstraint()
Definition ConstraintSystem.h:157
static SmallVector< int64_t, 8 > negate(SmallVector< int64_t, 8 > R)
Definition ConstraintSystem.h:114
LLVM_ABI bool mayHaveSolution()
Returns true if there may be a solution for the constraints in the system.
LLVM_ABI bool isConditionImplied(SmallVector< int64_t, 8 > R) const
unsigned size() const
Returns the number of rows in the constraint system.
Definition ConstraintSystem.h:164
ConstraintSystem(const DenseMap< Value *, unsigned > &Value2Index)
Definition ConstraintSystem.h:74
SmallVector< int64_t > getLastConstraint() const
Definition ConstraintSystem.h:149
static SmallVector< int64_t, 8 > toStrictLessThan(SmallVector< int64_t, 8 > R)
Converts the given vector to form a strict less than inequality.
Definition ConstraintSystem.h:139
bool addVariableRow(ArrayRef< int64_t > R)
Definition ConstraintSystem.h:77
void popLastNVariables(unsigned N)
Definition ConstraintSystem.h:158
static SmallVector< int64_t, 8 > negateOrEqual(SmallVector< int64_t, 8 > R)
Multiplies each coefficient in the given vector by -1.
Definition ConstraintSystem.h:127
ConstraintSystem()=default
const DenseMap< Value *, unsigned > & getValue2Index() const
Definition ConstraintSystem.h:97
bool addVariableRowFill(ArrayRef< int64_t > R)
Definition ConstraintSystem.h:101
LLVM_ABI void dump() const
Print the constraints in the system.
ConstraintSystem(ArrayRef< Value * > FunctionArgs)
Definition ConstraintSystem.h:68
reference emplace_back(ArgTypes &&... Args)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
LLVM Value Representation.
@ C
The default llvm calling convention, compatible with C.
This is an optimization pass for GlobalISel generic memory operations.
std::enable_if_t< std::is_signed_v< T >, T > MulOverflow(T X, T Y, T &Result)
Multiply two signed integers, computing the two's complement truncated result, returning true if an o...
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are tuples (A, B,...
ArrayRef(const T &OneElt) -> ArrayRef< T >
std::enable_if_t< std::is_signed_v< T >, T > AddOverflow(T X, T Y, T &Result)
Add two signed integers, computing the two's complement truncated result, returning true if overflow ...
std::enable_if_t< std::is_signed_v< T >, T > SubOverflow(T X, T Y, T &Result)
Subtract two signed integers, computing the two's complement truncated result, returning true if an o...