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