Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 14 | pmbaty | 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(ArrayRef(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(ArrayRef(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 |