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"
14#include "llvm/ADT/SmallVector.h"
15#include "llvm/Support/Compiler.h"
16#include "llvm/Support/MathExtras.h"
17
18#include <string>
19
20namespace llvm {
21
22class Value;
23class ConstraintSystem {
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
51 SmallVector<SmallVector<Entry, 8>, 4> Constraints;
52
53 /// A map of variables (IR values) to their corresponding index in the
54 /// constraint system.
55 DenseMap<Value *, unsigned> Value2Index;
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:
67 ConstraintSystem() = default;
68 ConstraintSystem(ArrayRef<Value *> FunctionArgs) {
69 NumVariables += FunctionArgs.size();
70 for (auto *Arg : FunctionArgs) {
71 Value2Index.insert(KV: {Arg, Value2Index.size() + 1});
72 }
73 }
74 ConstraintSystem(const DenseMap<Value *, unsigned> &Value2Index)
75 : NumVariables(Value2Index.size()), Value2Index(Value2Index) {}
76
77 bool addVariableRow(ArrayRef<int64_t> R) {
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(Range: ArrayRef(R).drop_front(N: 1), P: [](int64_t C) { return C == 0; }))
82 return false;
83
84 SmallVector<Entry, 4> NewRow;
85 for (const auto &[Idx, C] : enumerate(First&: R)) {
86 if (C == 0)
87 continue;
88 NewRow.emplace_back(Args: C, Args&: Idx);
89 }
90 if (Constraints.empty())
91 NumVariables = R.size();
92 Constraints.push_back(Elt: std::move(NewRow));
93 return true;
94 }
95
96 DenseMap<Value *, unsigned> &getValue2Index() { return Value2Index; }
97 const DenseMap<Value *, unsigned> &getValue2Index() const {
98 return Value2Index;
99 }
100
101 bool addVariableRowFill(ArrayRef<int64_t> R) {
102 // If all variable coefficients are 0, the constraint does not provide any
103 // usable information.
104 if (all_of(Range: ArrayRef(R).drop_front(N: 1), P: [](int64_t C) { return C == 0; }))
105 return false;
106
107 NumVariables = std::max(a: R.size(), b: NumVariables);
108 return addVariableRow(R);
109 }
110
111 /// Returns true if there may be a solution for the constraints in the system.
112 LLVM_ABI bool mayHaveSolution();
113
114 static SmallVector<int64_t, 8> negate(SmallVector<int64_t, 8> R) {
115 // The negated constraint R is obtained by multiplying by -1 and adding 1 to
116 // the constant.
117 if (AddOverflow(X: R[0], Y: int64_t(1), Result&: R[0]))
118 return {};
119
120 return negateOrEqual(R);
121 }
122
123 /// Multiplies each coefficient in the given vector by -1. Does not modify the
124 /// original vector.
125 ///
126 /// \param R The vector of coefficients to be negated.
127 static SmallVector<int64_t, 8> negateOrEqual(SmallVector<int64_t, 8> R) {
128 // The negated constraint R is obtained by multiplying by -1.
129 for (auto &C : R)
130 if (MulOverflow(X: C, Y: int64_t(-1), Result&: C))
131 return {};
132 return R;
133 }
134
135 /// Converts the given vector to form a strict less than inequality. Does not
136 /// modify the original vector.
137 ///
138 /// \param R The vector of coefficients to be converted.
139 static SmallVector<int64_t, 8> toStrictLessThan(SmallVector<int64_t, 8> R) {
140 // The strict less than is obtained by subtracting 1 from the constant.
141 if (SubOverflow(X: R[0], Y: int64_t(1), Result&: R[0])) {
142 return {};
143 }
144 return R;
145 }
146
147 LLVM_ABI bool isConditionImplied(SmallVector<int64_t, 8> R) const;
148
149 SmallVector<int64_t> getLastConstraint() const {
150 assert(!Constraints.empty() && "Constraint system is empty");
151 SmallVector<int64_t> Result(NumVariables, 0);
152 for (auto &Entry : Constraints.back())
153 Result[Entry.Id] = Entry.Coefficient;
154 return Result;
155 }
156
157 void popLastConstraint() { Constraints.pop_back(); }
158 void popLastNVariables(unsigned N) {
159 assert(NumVariables > N);
160 NumVariables -= N;
161 }
162
163 /// Returns the number of rows in the constraint system.
164 unsigned size() const { return Constraints.size(); }
165
166 /// Print the constraints in the system.
167 LLVM_ABI void dump() const;
168};
169} // namespace llvm
170
171#endif // LLVM_ANALYSIS_CONSTRAINTSYSTEM_H
172