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 {
24public:
25 struct Entry {
26 int64_t Coefficient;
27 uint16_t Id;
28
29 Entry(int64_t Coefficient, uint16_t Id)
30 : Coefficient(Coefficient), Id(Id) {}
31 };
32
33 /// A single constraint of the form 'c >= v1 * c1 + ... + vn * cn'.
34 using RowTy = SmallVector<Entry, 8>;
35
36private:
37 static int64_t getLastCoefficient(ArrayRef<Entry> R, uint16_t Id) {
38 if (R.empty() || R.back().Id != Id)
39 return 0;
40 return R.back().Coefficient;
41 }
42
43 /// Returns true if \p R has an entry for the constant part.
44 static bool hasConstantEntry(ArrayRef<Entry> R) {
45 return !R.empty() && R.front().Id == 0;
46 }
47
48 /// Returns true if \p R does not have an entry for any variable, i.e. it is
49 /// of the form 'c >= 0'.
50 static bool isConstantOnly(ArrayRef<Entry> R) {
51 return R.empty() || (R.size() == 1 && R.front().Id == 0);
52 }
53
54 /// Returns the constant part of \p R, which is 0 if \p R does not have an
55 /// entry for it.
56 static int64_t getConstant(ArrayRef<Entry> R) {
57 return hasConstantEntry(R) ? R.front().Coefficient : 0;
58 }
59
60 /// Number of variables in the system, not counting the constant part. The
61 /// variables use the indices 1 to NumVariables.
62 size_t NumVariables = 0;
63
64 /// Current linear constraints in the system.
65 /// Each entry represents a constraint like
66 /// c0 >= v0 * c1 + .... + v{n-1} * cn
67 SmallVector<RowTy, 4> Constraints;
68
69 /// A map of variables (IR values) to their corresponding index in the
70 /// constraint system.
71 DenseMap<Value *, unsigned> Value2Index;
72
73 // Eliminate constraints from the system using Fourier–Motzkin elimination.
74 bool eliminateUsingFM();
75
76 /// Returns true if there may be a solution for the constraints in the system.
77 bool mayHaveSolutionImpl();
78
79 /// Get list of variable names from the Value2Index map.
80 SmallVector<std::string> getVarNamesList() const;
81
82public:
83 ConstraintSystem() = default;
84 ConstraintSystem(ArrayRef<Value *> FunctionArgs) {
85 NumVariables += FunctionArgs.size();
86 for (auto *Arg : FunctionArgs) {
87 Value2Index.insert(KV: {Arg, Value2Index.size() + 1});
88 }
89 }
90 ConstraintSystem(const DenseMap<Value *, unsigned> &Value2Index)
91 : NumVariables(Value2Index.size()), Value2Index(Value2Index) {}
92
93 bool addRow(ArrayRef<Entry> R, size_t NumVars) {
94 // If all variable coefficients are 0, the constraint does not provide any
95 // usable information.
96 if (isConstantOnly(R))
97 return false;
98
99 assert(NumVars >= R.back().Id && "NumVars must cover all variables in R");
100 NumVariables = std::max(a: NumVars, b: NumVariables);
101 // Only keep non-zero coefficients; in particular drop the entry for the
102 // constant part if it is 0.
103 RowTy &NewRow = Constraints.emplace_back();
104 for (const Entry &E : R)
105 if (E.Coefficient != 0)
106 NewRow.push_back(Elt: E);
107 return true;
108 }
109
110 DenseMap<Value *, unsigned> &getValue2Index() { return Value2Index; }
111 const DenseMap<Value *, unsigned> &getValue2Index() const {
112 return Value2Index;
113 }
114
115 /// Returns true if there may be a solution for the constraints in the system.
116 LLVM_ABI bool mayHaveSolution();
117
118 static RowTy negate(RowTy R) {
119 assert(hasConstantEntry(R) && "row must have a constant entry");
120 // The negated constraint R is obtained by multiplying by -1 and adding 1 to
121 // the constant.
122 if (AddOverflow(X: R[0].Coefficient, Y: int64_t(1), Result&: R[0].Coefficient))
123 return {};
124
125 return negateOrEqual(R: std::move(R));
126 }
127
128 /// Multiplies each coefficient in the given row by -1. Returns an empty row
129 /// on overflow. Does not modify the original row.
130 ///
131 /// \param R The row of coefficients to be negated.
132 static RowTy negateOrEqual(RowTy R) {
133 // The negated constraint R is obtained by multiplying by -1.
134 for (Entry &E : R)
135 if (MulOverflow(X: E.Coefficient, Y: int64_t(-1), Result&: E.Coefficient))
136 return {};
137 return R;
138 }
139
140 /// Converts the given row to form a strict less than inequality. Returns an
141 /// empty row on overflow. Does not modify the original row.
142 ///
143 /// \param R The row of coefficients to be converted.
144 static RowTy toStrictLessThan(RowTy R) {
145 assert(hasConstantEntry(R) && "row must have a constant entry");
146 // The strict less than is obtained by subtracting 1 from the constant.
147 if (SubOverflow(X: R[0].Coefficient, Y: int64_t(1), Result&: R[0].Coefficient))
148 return {};
149 return R;
150 }
151
152 /// Build and return a sub-system of constraints connected (transitively) to
153 /// query \p R, with variables compacted to a dense index range. Also
154 /// translate \p R's entries to the sub-system.
155 LLVM_ABI std::pair<ConstraintSystem, RowTy>
156 getSubSystem(ArrayRef<Entry> R) const;
157
158 LLVM_ABI bool isConditionImplied(RowTy R) const;
159 LLVM_ABI bool isConditionImpliedInSubSystem(ArrayRef<Entry> R) const;
160
161 const RowTy &getLastConstraint() const {
162 assert(!Constraints.empty() && "Constraint system is empty");
163 return Constraints.back();
164 }
165
166 void popLastConstraint() { Constraints.pop_back(); }
167 void popLastNVariables(unsigned N) {
168 assert(NumVariables >= N);
169 NumVariables -= N;
170 }
171
172 /// Returns the number of rows in the constraint system.
173 unsigned size() const { return Constraints.size(); }
174
175 /// Print the constraints in the system.
176 LLVM_ABI void dump() const;
177};
178} // namespace llvm
179
180#endif // LLVM_ANALYSIS_CONSTRAINTSYSTEM_H
181