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