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/DenseMap.h" 15 #include "llvm/ADT/SmallVector.h" 16 #include "llvm/Support/MathExtras.h" 17 18 #include <string> 19 20 namespace llvm { 21 22 class Value; 23 class ConstraintSystem { 24 struct Entry { 25 int64_t Coefficient; 26 uint16_t Id; 27 28 Entry(int64_t Coefficient, uint16_t Id) 29 : Coefficient(Coefficient), Id(Id) {} 30 }; 31 32 static int64_t getConstPart(const Entry &E) { 33 if (E.Id == 0) 34 return E.Coefficient; 35 return 0; 36 } 37 38 static int64_t getLastCoefficient(ArrayRef<Entry> Row, uint16_t Id) { 39 if (Row.empty()) 40 return 0; 41 if (Row.back().Id == Id) 42 return Row.back().Coefficient; 43 return 0; 44 } 45 46 size_t NumVariables = 0; 47 48 /// Current linear constraints in the system. 49 /// An entry of the form c0, c1, ... cn represents the following constraint: 50 /// c0 >= v0 * c1 + .... + v{n-1} * cn 51 SmallVector<SmallVector<Entry, 8>, 4> Constraints; 52 53 /// A map of variables (IR values) to their corresponding index in the 54 /// constraint system. 55 DenseMap<Value *, unsigned> Value2Index; 56 57 /// Current greatest common divisor for all coefficients in the system. 58 uint32_t GCD = 1; 59 60 // Eliminate constraints from the system using Fourier–Motzkin elimination. 61 bool eliminateUsingFM(); 62 63 /// Returns true if there may be a solution for the constraints in the system. 64 bool mayHaveSolutionImpl(); 65 66 /// Get list of variable names from the Value2Index map. 67 SmallVector<std::string> getVarNamesList() const; 68 69 public: 70 ConstraintSystem() {} 71 ConstraintSystem(ArrayRef<Value *> FunctionArgs) { 72 NumVariables += FunctionArgs.size(); 73 for (auto *Arg : FunctionArgs) { 74 Value2Index.insert({Arg, Value2Index.size() + 1}); 75 } 76 } 77 ConstraintSystem(const DenseMap<Value *, unsigned> &Value2Index) 78 : NumVariables(Value2Index.size()), Value2Index(Value2Index) {} 79 80 bool addVariableRow(ArrayRef<int64_t> R) { 81 assert(Constraints.empty() || R.size() == NumVariables); 82 // If all variable coefficients are 0, the constraint does not provide any 83 // usable information. 84 if (all_of(ArrayRef(R).drop_front(1), [](int64_t C) { return C == 0; })) 85 return false; 86 87 SmallVector<Entry, 4> NewRow; 88 for (const auto &[Idx, C] : enumerate(R)) { 89 if (C == 0) 90 continue; 91 auto A = std::abs(C); 92 GCD = APIntOps::GreatestCommonDivisor({32, (uint32_t)A}, {32, GCD}) 93 .getZExtValue(); 94 95 NewRow.emplace_back(C, Idx); 96 } 97 if (Constraints.empty()) 98 NumVariables = R.size(); 99 Constraints.push_back(std::move(NewRow)); 100 return true; 101 } 102 103 DenseMap<Value *, unsigned> &getValue2Index() { return Value2Index; } 104 const DenseMap<Value *, unsigned> &getValue2Index() const { 105 return Value2Index; 106 } 107 108 bool addVariableRowFill(ArrayRef<int64_t> R) { 109 // If all variable coefficients are 0, the constraint does not provide any 110 // usable information. 111 if (all_of(ArrayRef(R).drop_front(1), [](int64_t C) { return C == 0; })) 112 return false; 113 114 NumVariables = std::max(R.size(), NumVariables); 115 return addVariableRow(R); 116 } 117 118 /// Returns true if there may be a solution for the constraints in the system. 119 bool mayHaveSolution(); 120 121 static SmallVector<int64_t, 8> negate(SmallVector<int64_t, 8> R) { 122 // The negated constraint R is obtained by multiplying by -1 and adding 1 to 123 // the constant. 124 R[0] += 1; 125 return negateOrEqual(R); 126 } 127 128 /// Multiplies each coefficient in the given vector by -1. Does not modify the 129 /// original vector. 130 /// 131 /// \param R The vector of coefficients to be negated. 132 static SmallVector<int64_t, 8> negateOrEqual(SmallVector<int64_t, 8> R) { 133 // The negated constraint R is obtained by multiplying by -1. 134 for (auto &C : R) 135 if (MulOverflow(C, int64_t(-1), C)) 136 return {}; 137 return R; 138 } 139 140 /// Converts the given vector to form a strict less than inequality. Does not 141 /// modify the original vector. 142 /// 143 /// \param R The vector of coefficients to be converted. 144 static SmallVector<int64_t, 8> toStrictLessThan(SmallVector<int64_t, 8> R) { 145 // The strict less than is obtained by subtracting 1 from the constant. 146 if (SubOverflow(R[0], int64_t(1), R[0])) { 147 return {}; 148 } 149 return R; 150 } 151 152 bool isConditionImplied(SmallVector<int64_t, 8> R) const; 153 154 SmallVector<int64_t> getLastConstraint() const { 155 assert(!Constraints.empty() && "Constraint system is empty"); 156 SmallVector<int64_t> Result(NumVariables, 0); 157 for (auto &Entry : Constraints.back()) 158 Result[Entry.Id] = Entry.Coefficient; 159 return Result; 160 } 161 162 void popLastConstraint() { Constraints.pop_back(); } 163 void popLastNVariables(unsigned N) { 164 assert(NumVariables > N); 165 NumVariables -= N; 166 } 167 168 /// Returns the number of rows in the constraint system. 169 unsigned size() const { return Constraints.size(); } 170 171 /// Print the constraints in the system. 172 void dump() const; 173 }; 174 } // namespace llvm 175 176 #endif // LLVM_ANALYSIS_CONSTRAINTSYSTEM_H 177