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/STLExtras.h"
15 #include "llvm/ADT/SmallVector.h"
16 
17 #include <string>
18 
19 namespace llvm {
20 
21 class ConstraintSystem {
22   /// Current linear constraints in the system.
23   /// An entry of the form c0, c1, ... cn represents the following constraint:
24   ///   c0 >= v0 * c1 + .... + v{n-1} * cn
25   SmallVector<SmallVector<int64_t, 8>, 4> Constraints;
26 
27   /// Current greatest common divisor for all coefficients in the system.
28   uint32_t GCD = 1;
29 
30   // Eliminate constraints from the system using Fourier–Motzkin elimination.
31   bool eliminateUsingFM();
32 
33   /// Print the constraints in the system, using \p Names as variable names.
34   void dump(ArrayRef<std::string> Names) const;
35 
36   /// Print the constraints in the system, using x0...xn as variable names.
37   void dump() const;
38 
39   /// Returns true if there may be a solution for the constraints in the system.
40   bool mayHaveSolutionImpl();
41 
42 public:
43   bool addVariableRow(const SmallVector<int64_t, 8> &R) {
44     assert(Constraints.empty() || R.size() == Constraints.back().size());
45     // If all variable coefficients are 0, the constraint does not provide any
46     // usable information.
47     if (all_of(makeArrayRef(R).drop_front(1), [](int64_t C) { return C == 0; }))
48       return false;
49 
50     for (const auto &C : R) {
51       auto A = std::abs(C);
52       GCD = APIntOps::GreatestCommonDivisor({32, (uint32_t)A}, {32, GCD})
53                 .getZExtValue();
54     }
55     Constraints.push_back(R);
56     return true;
57   }
58 
59   bool addVariableRowFill(const SmallVector<int64_t, 8> &R) {
60     for (auto &CR : Constraints) {
61       while (CR.size() != R.size())
62         CR.push_back(0);
63     }
64     return addVariableRow(R);
65   }
66 
67   /// Returns true if there may be a solution for the constraints in the system.
68   bool mayHaveSolution();
69 
70   static SmallVector<int64_t, 8> negate(SmallVector<int64_t, 8> R) {
71     // The negated constraint R is obtained by multiplying by -1 and adding 1 to
72     // the constant.
73     R[0] += 1;
74     for (auto &C : R)
75       C *= -1;
76     return R;
77   }
78 
79   bool isConditionImplied(SmallVector<int64_t, 8> R);
80 
81   void popLastConstraint() { Constraints.pop_back(); }
82 
83   /// Returns the number of rows in the constraint system.
84   unsigned size() const { return Constraints.size(); }
85 };
86 } // namespace llvm
87 
88 #endif // LLVM_ANALYSIS_CONSTRAINTSYSTEM_H
89