LLVM 19.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/APInt.h"
13#include "llvm/ADT/ArrayRef.h"
14#include "llvm/ADT/DenseMap.h"
17
18#include <string>
19
20namespace llvm {
21
22class Value;
24 struct Entry {
25 int64_t Coefficient;
26 uint16_t Id;
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
38 static int64_t getLastCoefficient(ArrayRef<Entry> Row, uint16_t Id) {
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 /// Current linear constraints in the system.
49 /// An entry of the form c0, c1, ... cn represents the following constraint:
50 /// c0 >= v0 * c1 + .... + v{n-1} * cn
52
53 /// A map of variables (IR values) to their corresponding index in the
54 /// constraint system.
56
57 // Eliminate constraints from the system using Fourier–Motzkin elimination.
58 bool eliminateUsingFM();
59
60 /// Returns true if there may be a solution for the constraints in the system.
61 bool mayHaveSolutionImpl();
62
63 /// Get list of variable names from the Value2Index map.
64 SmallVector<std::string> getVarNamesList() const;
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 // If all variable coefficients are 0, the constraint does not provide any
80 // usable information.
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;
88 NewRow.emplace_back(C, Idx);
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 // If all variable coefficients are 0, the constraint does not provide any
103 // usable information.
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);
108 return addVariableRow(R);
109 }
110
111 /// Returns true if there may be a solution for the constraints in the system.
112 bool mayHaveSolution();
113
115 // The negated constraint R is obtained by multiplying by -1 and adding 1 to
116 // the constant.
117 R[0] += 1;
118 return negateOrEqual(R);
119 }
120
121 /// Multiplies each coefficient in the given vector by -1. Does not modify the
122 /// original vector.
123 ///
124 /// \param R The vector of coefficients to be negated.
126 // The negated constraint R is obtained by multiplying by -1.
127 for (auto &C : R)
128 if (MulOverflow(C, int64_t(-1), C))
129 return {};
130 return R;
131 }
132
133 /// Converts the given vector to form a strict less than inequality. Does not
134 /// modify the original vector.
135 ///
136 /// \param R The vector of coefficients to be converted.
138 // The strict less than is obtained by subtracting 1 from the constant.
139 if (SubOverflow(R[0], int64_t(1), R[0])) {
140 return {};
141 }
142 return R;
143 }
144
146
148 assert(!Constraints.empty() && "Constraint system is empty");
149 SmallVector<int64_t> Result(NumVariables, 0);
150 for (auto &Entry : Constraints.back())
151 Result[Entry.Id] = Entry.Coefficient;
152 return Result;
153 }
154
155 void popLastConstraint() { Constraints.pop_back(); }
156 void popLastNVariables(unsigned N) {
157 assert(NumVariables > N);
158 NumVariables -= N;
159 }
160
161 /// Returns the number of rows in the constraint system.
162 unsigned size() const { return Constraints.size(); }
163
164 /// Print the constraints in the system.
165 void dump() const;
166};
167} // namespace llvm
168
169#endif // LLVM_ANALYSIS_CONSTRAINTSYSTEM_H
This file implements a class to represent arbitrary precision integral constant values and operations...
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:220
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:623
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:1731
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are are tuples (A,...
Definition: STLExtras.h:2386
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:597
#define N