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 normalizeByGCD(R: NewRow);
108 return true;
109 }
110
111 DenseMap<Value *, unsigned> &getValue2Index() { return Value2Index; }
112 const DenseMap<Value *, unsigned> &getValue2Index() const {
113 return Value2Index;
114 }
115
116 /// Returns true if there may be a solution for the constraints in the system.
117 LLVM_ABI bool mayHaveSolution();
118
119 /// Divide the variable coefficients of \p R by their greatest common divisor
120 /// G and round the constant down to a multiple of G.
121 LLVM_ABI static void normalizeByGCD(MutableArrayRef<Entry> R);
122
123 static RowTy negate(RowTy R) {
124 assert(hasConstantEntry(R) && "row must have a constant entry");
125 // The negated constraint R is obtained by multiplying by -1 and adding 1 to
126 // the constant.
127 if (AddOverflow(X: R[0].Coefficient, Y: int64_t(1), Result&: R[0].Coefficient))
128 return {};
129
130 return negateOrEqual(R: std::move(R));
131 }
132
133 /// Multiplies each coefficient in the given row by -1. Returns an empty row
134 /// on overflow. Does not modify the original row.
135 ///
136 /// \param R The row of coefficients to be negated.
137 static RowTy negateOrEqual(RowTy R) {
138 // The negated constraint R is obtained by multiplying by -1.
139 for (Entry &E : R)
140 if (MulOverflow(X: E.Coefficient, Y: int64_t(-1), Result&: E.Coefficient))
141 return {};
142 return R;
143 }
144
145 /// Converts the given row to form a strict less than inequality. Returns an
146 /// empty row on overflow. Does not modify the original row.
147 ///
148 /// \param R The row of coefficients to be converted.
149 static RowTy toStrictLessThan(RowTy R) {
150 assert(hasConstantEntry(R) && "row must have a constant entry");
151 // The strict less than is obtained by subtracting 1 from the constant.
152 if (SubOverflow(X: R[0].Coefficient, Y: int64_t(1), Result&: R[0].Coefficient))
153 return {};
154 return R;
155 }
156
157 /// Build and return a sub-system of constraints connected (transitively) to
158 /// query \p R, with variables compacted to a dense index range. Also
159 /// translate \p R's entries to the sub-system.
160 LLVM_ABI std::pair<ConstraintSystem, RowTy>
161 getSubSystem(ArrayRef<Entry> R) const;
162
163 /// Returns true if a single row of the system implies \p R.
164 LLVM_ABI bool isImpliedBySingleRow(ArrayRef<Entry> R) const;
165
166 LLVM_ABI bool isConditionImplied(RowTy R) const;
167 LLVM_ABI bool isConditionImpliedInSubSystem(ArrayRef<Entry> R) const;
168
169 const RowTy &getLastConstraint() const {
170 assert(!Constraints.empty() && "Constraint system is empty");
171 return Constraints.back();
172 }
173
174 void popLastConstraint() { Constraints.pop_back(); }
175 void popLastNVariables(unsigned N) {
176 assert(NumVariables >= N);
177 NumVariables -= N;
178 }
179
180 /// Returns the number of rows in the constraint system.
181 unsigned size() const { return Constraints.size(); }
182
183 /// Print the constraints in the system.
184 LLVM_ABI void dump() const;
185};
186} // namespace llvm
187
188#endif // LLVM_ANALYSIS_CONSTRAINTSYSTEM_H
189