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