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({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(ArrayRef(R).drop_front(1), [](int64_t C) { return C == 0; }))
82       return false;
83 
84     SmallVector<Entry, 4> NewRow;
85     for (const auto &[Idx, C] : enumerate(R)) {
86       if (C == 0)
87         continue;
88       NewRow.emplace_back(C, Idx);
89     }
90     if (Constraints.empty())
91       NumVariables = R.size();
92     Constraints.push_back(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(ArrayRef(R).drop_front(1), [](int64_t C) { return C == 0; }))
105       return false;
106 
107     NumVariables = std::max(R.size(), 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(C, int64_t(-1), 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(R[0], int64_t(1), 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