LLVM 20.0.0git
ConstraintSystem.h
Go to the documentation of this file.
1//===- ConstraintSystem.h - A system of linear constraints. --------------===//
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#ifndef LLVM_ANALYSIS_CONSTRAINTSYSTEM_H
10#define LLVM_ANALYSIS_CONSTRAINTSYSTEM_H
11
12#include "llvm/ADT/ArrayRef.h"
13#include "llvm/ADT/DenseMap.h"
16
17#include <string>
18
19namespace llvm {
20
21class Value;
23 struct Entry {
24 int64_t Coefficient;
25 uint16_t Id;
26
27 Entry(int64_t Coefficient, uint16_t Id)
28 : Coefficient(Coefficient), Id(Id) {}
29 };
30
31 static int64_t getConstPart(const Entry &E) {
32 if (E.Id == 0)
33 return E.Coefficient;
34 return 0;
35 }
36
37 static int64_t getLastCoefficient(ArrayRef<Entry> Row, uint16_t Id) {
38 if (Row.empty())
39 return 0;
40 if (Row.back().Id == Id)
41 return Row.back().Coefficient;
42 return 0;
43 }
44
45 size_t NumVariables = 0;
46
47 /// Current linear constraints in the system.
48 /// An entry of the form c0, c1, ... cn represents the following constraint:
49 /// c0 >= v0 * c1 + .... + v{n-1} * cn
51
52 /// A map of variables (IR values) to their corresponding index in the
53 /// constraint system.
55
56 // Eliminate constraints from the system using Fourier–Motzkin elimination.
57 bool eliminateUsingFM();
58
59 /// Returns true if there may be a solution for the constraints in the system.
60 bool mayHaveSolutionImpl();
61
62 /// Get list of variable names from the Value2Index map.
63 SmallVector<std::string> getVarNamesList() const;
64
65public:
68 NumVariables += FunctionArgs.size();
69 for (auto *Arg : FunctionArgs) {
70 Value2Index.insert({Arg, Value2Index.size() + 1});
71 }
72 }
74 : NumVariables(Value2Index.size()), Value2Index(Value2Index) {}
75
77 assert(Constraints.empty() || R.size() == NumVariables);
78 // If all variable coefficients are 0, the constraint does not provide any
79 // usable information.
80 if (all_of(ArrayRef(R).drop_front(1), [](int64_t C) { return C == 0; }))
81 return false;
82
84 for (const auto &[Idx, C] : enumerate(R)) {
85 if (C == 0)
86 continue;
87 NewRow.emplace_back(C, Idx);
88 }
89 if (Constraints.empty())
90 NumVariables = R.size();
91 Constraints.push_back(std::move(NewRow));
92 return true;
93 }
94
97 return Value2Index;
98 }
99
101 // If all variable coefficients are 0, the constraint does not provide any
102 // usable information.
103 if (all_of(ArrayRef(R).drop_front(1), [](int64_t C) { return C == 0; }))
104 return false;
105
106 NumVariables = std::max(R.size(), NumVariables);
107 return addVariableRow(R);
108 }
109
110 /// Returns true if there may be a solution for the constraints in the system.
111 bool mayHaveSolution();
112
114 // The negated constraint R is obtained by multiplying by -1 and adding 1 to
115 // the constant.
116 R[0] += 1;
117 return negateOrEqual(R);
118 }
119
120 /// Multiplies each coefficient in the given vector by -1. Does not modify the
121 /// original vector.
122 ///
123 /// \param R The vector of coefficients to be negated.
125 // The negated constraint R is obtained by multiplying by -1.
126 for (auto &C : R)
127 if (MulOverflow(C, int64_t(-1), C))
128 return {};
129 return R;
130 }
131
132 /// Converts the given vector to form a strict less than inequality. Does not
133 /// modify the original vector.
134 ///
135 /// \param R The vector of coefficients to be converted.
137 // The strict less than is obtained by subtracting 1 from the constant.
138 if (SubOverflow(R[0], int64_t(1), R[0])) {
139 return {};
140 }
141 return R;
142 }
143
145
147 assert(!Constraints.empty() && "Constraint system is empty");
148 SmallVector<int64_t> Result(NumVariables, 0);
149 for (auto &Entry : Constraints.back())
150 Result[Entry.Id] = Entry.Coefficient;
151 return Result;
152 }
153
154 void popLastConstraint() { Constraints.pop_back(); }
155 void popLastNVariables(unsigned N) {
156 assert(NumVariables > N);
157 NumVariables -= N;
158 }
159
160 /// Returns the number of rows in the constraint system.
161 unsigned size() const { return Constraints.size(); }
162
163 /// Print the constraints in the system.
164 void dump() const;
165};
166} // namespace llvm
167
168#endif // LLVM_ANALYSIS_CONSTRAINTSYSTEM_H
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:165
DenseMap< Value *, unsigned > & getValue2Index()
static SmallVector< int64_t, 8 > negate(SmallVector< int64_t, 8 > R)
bool mayHaveSolution()
Returns true if there may be a solution for the constraints in the system.
bool isConditionImplied(SmallVector< int64_t, 8 > R) const
unsigned size() const
Returns the number of rows in the constraint system.
ConstraintSystem(const DenseMap< Value *, unsigned > &Value2Index)
SmallVector< int64_t > getLastConstraint() const
static SmallVector< int64_t, 8 > toStrictLessThan(SmallVector< int64_t, 8 > R)
Converts the given vector to form a strict less than inequality.
bool addVariableRow(ArrayRef< int64_t > R)
void popLastNVariables(unsigned N)
static SmallVector< int64_t, 8 > negateOrEqual(SmallVector< int64_t, 8 > R)
Multiplies each coefficient in the given vector by -1.
const DenseMap< Value *, unsigned > & getValue2Index() const
bool addVariableRowFill(ArrayRef< int64_t > R)
void dump() const
Print the constraints in the system.
ConstraintSystem(ArrayRef< Value * > FunctionArgs)
unsigned size() const
Definition: DenseMap.h:99
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:211
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:950
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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...
Definition: MathExtras.h:753
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1722
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are tuples (A, B,...
Definition: STLExtras.h:2431
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...
Definition: MathExtras.h:727
#define N