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   /// Current greatest common divisor for all coefficients in the system.
58   uint32_t GCD = 1;
59 
60   // Eliminate constraints from the system using Fourier–Motzkin elimination.
61   bool eliminateUsingFM();
62 
63   /// Returns true if there may be a solution for the constraints in the system.
64   bool mayHaveSolutionImpl();
65 
66   /// Get list of variable names from the Value2Index map.
67   SmallVector<std::string> getVarNamesList() const;
68 
69 public:
70   ConstraintSystem() {}
71   ConstraintSystem(ArrayRef<Value *> FunctionArgs) {
72     NumVariables += FunctionArgs.size();
73     for (auto *Arg : FunctionArgs) {
74       Value2Index.insert({Arg, Value2Index.size() + 1});
75     }
76   }
77   ConstraintSystem(const DenseMap<Value *, unsigned> &Value2Index)
78       : NumVariables(Value2Index.size()), Value2Index(Value2Index) {}
79 
80   bool addVariableRow(ArrayRef<int64_t> R) {
81     assert(Constraints.empty() || R.size() == NumVariables);
82     // If all variable coefficients are 0, the constraint does not provide any
83     // usable information.
84     if (all_of(ArrayRef(R).drop_front(1), [](int64_t C) { return C == 0; }))
85       return false;
86 
87     SmallVector<Entry, 4> NewRow;
88     for (const auto &[Idx, C] : enumerate(R)) {
89       if (C == 0)
90         continue;
91       auto A = std::abs(C);
92       GCD = APIntOps::GreatestCommonDivisor({32, (uint32_t)A}, {32, GCD})
93                 .getZExtValue();
94 
95       NewRow.emplace_back(C, Idx);
96     }
97     if (Constraints.empty())
98       NumVariables = R.size();
99     Constraints.push_back(std::move(NewRow));
100     return true;
101   }
102 
103   DenseMap<Value *, unsigned> &getValue2Index() { return Value2Index; }
104   const DenseMap<Value *, unsigned> &getValue2Index() const {
105     return Value2Index;
106   }
107 
108   bool addVariableRowFill(ArrayRef<int64_t> R) {
109     // If all variable coefficients are 0, the constraint does not provide any
110     // usable information.
111     if (all_of(ArrayRef(R).drop_front(1), [](int64_t C) { return C == 0; }))
112       return false;
113 
114     NumVariables = std::max(R.size(), NumVariables);
115     return addVariableRow(R);
116   }
117 
118   /// Returns true if there may be a solution for the constraints in the system.
119   bool mayHaveSolution();
120 
121   static SmallVector<int64_t, 8> negate(SmallVector<int64_t, 8> R) {
122     // The negated constraint R is obtained by multiplying by -1 and adding 1 to
123     // the constant.
124     R[0] += 1;
125     return negateOrEqual(R);
126   }
127 
128   /// Multiplies each coefficient in the given vector by -1. Does not modify the
129   /// original vector.
130   ///
131   /// \param R The vector of coefficients to be negated.
132   static SmallVector<int64_t, 8> negateOrEqual(SmallVector<int64_t, 8> R) {
133     // The negated constraint R is obtained by multiplying by -1.
134     for (auto &C : R)
135       if (MulOverflow(C, int64_t(-1), C))
136         return {};
137     return R;
138   }
139 
140   /// Converts the given vector to form a strict less than inequality. Does not
141   /// modify the original vector.
142   ///
143   /// \param R The vector of coefficients to be converted.
144   static SmallVector<int64_t, 8> toStrictLessThan(SmallVector<int64_t, 8> R) {
145     // The strict less than is obtained by subtracting 1 from the constant.
146     if (SubOverflow(R[0], int64_t(1), R[0])) {
147       return {};
148     }
149     return R;
150   }
151 
152   bool isConditionImplied(SmallVector<int64_t, 8> R) const;
153 
154   SmallVector<int64_t> getLastConstraint() const {
155     assert(!Constraints.empty() && "Constraint system is empty");
156     SmallVector<int64_t> Result(NumVariables, 0);
157     for (auto &Entry : Constraints.back())
158       Result[Entry.Id] = Entry.Coefficient;
159     return Result;
160   }
161 
162   void popLastConstraint() { Constraints.pop_back(); }
163   void popLastNVariables(unsigned N) {
164     assert(NumVariables > N);
165     NumVariables -= N;
166   }
167 
168   /// Returns the number of rows in the constraint system.
169   unsigned size() const { return Constraints.size(); }
170 
171   /// Print the constraints in the system.
172   void dump() const;
173 };
174 } // namespace llvm
175 
176 #endif // LLVM_ANALYSIS_CONSTRAINTSYSTEM_H
177