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