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" |
15 | #include "llvm/ADT/SmallVector.h" |
16 | #include "llvm/Support/MathExtras.h" |
17 | |
18 | #include <string> |
19 | |
20 | namespace llvm { |
21 | |
22 | class Value; |
23 | class 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 | |
66 | public: |
67 | ConstraintSystem() {} |
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 | 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 | 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. |
125 | static SmallVector<int64_t, 8> negateOrEqual(SmallVector<int64_t, 8> R) { |
126 | // The negated constraint R is obtained by multiplying by -1. |
127 | for (auto &C : R) |
128 | if (MulOverflow(X: C, Y: int64_t(-1), Result&: 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. |
137 | static SmallVector<int64_t, 8> toStrictLessThan(SmallVector<int64_t, 8> R) { |
138 | // The strict less than is obtained by subtracting 1 from the constant. |
139 | if (SubOverflow(X: R[0], Y: int64_t(1), Result&: R[0])) { |
140 | return {}; |
141 | } |
142 | return R; |
143 | } |
144 | |
145 | bool isConditionImplied(SmallVector<int64_t, 8> R) const; |
146 | |
147 | SmallVector<int64_t> getLastConstraint() const { |
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 |
170 | |