llvm/Analysis/ConstraintSystem.h

0001 //===- ConstraintSystem.h -  A system of linear constraints. --------------===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef LLVM_ANALYSIS_CONSTRAINTSYSTEM_H
0010 #define LLVM_ANALYSIS_CONSTRAINTSYSTEM_H
0011
0012 #include "llvm/ADT/ArrayRef.h"
0013 #include "llvm/ADT/DenseMap.h"
0014 #include "llvm/ADT/SmallVector.h"
0015 #include "llvm/Support/MathExtras.h"
0016
0017 #include <string>
0018
0019 namespace llvm {
0020
0021 class Value;
0022 class ConstraintSystem {
0023   struct Entry {
0024     int64_t Coefficient;
0025     uint16_t Id;
0026
0027     Entry(int64_t Coefficient, uint16_t Id)
0028         : Coefficient(Coefficient), Id(Id) {}
0029   };
0030
0031   static int64_t getConstPart(const Entry &E) {
0032     if (E.Id == 0)
0033       return E.Coefficient;
0034     return 0;
0035   }
0036
0037   static int64_t getLastCoefficient(ArrayRef<Entry> Row, uint16_t Id) {
0038     if (Row.empty())
0039       return 0;
0040     if (Row.back().Id == Id)
0041       return Row.back().Coefficient;
0042     return 0;
0043   }
0044
0045   size_t NumVariables = 0;
0046
0047   /// Current linear constraints in the system.
0048   /// An entry of the form c0, c1, ... cn represents the following constraint:
0049   ///   c0 >= v0 * c1 + .... + v{n-1} * cn
0050   SmallVector<SmallVector<Entry, 8>, 4> Constraints;
0051
0052   /// A map of variables (IR values) to their corresponding index in the
0053   /// constraint system.
0054   DenseMap<Value *, unsigned> Value2Index;
0055
0056   // Eliminate constraints from the system using Fourier–Motzkin elimination.
0057   bool eliminateUsingFM();
0058
0059   /// Returns true if there may be a solution for the constraints in the system.
0060   bool mayHaveSolutionImpl();
0061
0062   /// Get list of variable names from the Value2Index map.
0063   SmallVector<std::string> getVarNamesList() const;
0064
0065 public:
0066   ConstraintSystem() {}
0067   ConstraintSystem(ArrayRef<Value *> FunctionArgs) {
0068     NumVariables += FunctionArgs.size();
0069     for (auto *Arg : FunctionArgs) {
0070       Value2Index.insert({Arg, Value2Index.size() + 1});
0071     }
0072   }
0073   ConstraintSystem(const DenseMap<Value *, unsigned> &Value2Index)
0074       : NumVariables(Value2Index.size()), Value2Index(Value2Index) {}
0075
0076   bool addVariableRow(ArrayRef<int64_t> R) {
0077     assert(Constraints.empty() || R.size() == NumVariables);
0078     // If all variable coefficients are 0, the constraint does not provide any
0079     // usable information.
0080     if (all_of(ArrayRef(R).drop_front(1), [](int64_t C) { return C == 0; }))
0081       return false;
0082
0083     SmallVector<Entry, 4> NewRow;
0084     for (const auto &[Idx, C] : enumerate(R)) {
0085       if (C == 0)
0086         continue;
0087       NewRow.emplace_back(C, Idx);
0088     }
0089     if (Constraints.empty())
0090       NumVariables = R.size();
0091     Constraints.push_back(std::move(NewRow));
0092     return true;
0093   }
0094
0095   DenseMap<Value *, unsigned> &getValue2Index() { return Value2Index; }
0096   const DenseMap<Value *, unsigned> &getValue2Index() const {
0097     return Value2Index;
0098   }
0099
0100   bool addVariableRowFill(ArrayRef<int64_t> R) {
0101     // If all variable coefficients are 0, the constraint does not provide any
0102     // usable information.
0103     if (all_of(ArrayRef(R).drop_front(1), [](int64_t C) { return C == 0; }))
0104       return false;
0105
0106     NumVariables = std::max(R.size(), NumVariables);
0107     return addVariableRow(R);
0108   }
0109
0110   /// Returns true if there may be a solution for the constraints in the system.
0111   bool mayHaveSolution();
0112
0113   static SmallVector<int64_t, 8> negate(SmallVector<int64_t, 8> R) {
0114     // The negated constraint R is obtained by multiplying by -1 and adding 1 to
0115     // the constant.
0116     if (AddOverflow(R[0], int64_t(1), R[0]))
0117       return {};
0118
0119     return negateOrEqual(R);
0120   }
0121
0122   /// Multiplies each coefficient in the given vector by -1. Does not modify the
0123   /// original vector.
0124   ///
0125   /// \param R The vector of coefficients to be negated.
0126   static SmallVector<int64_t, 8> negateOrEqual(SmallVector<int64_t, 8> R) {
0127     // The negated constraint R is obtained by multiplying by -1.
0128     for (auto &C : R)
0129       if (MulOverflow(C, int64_t(-1), C))
0130         return {};
0131     return R;
0132   }
0133
0134   /// Converts the given vector to form a strict less than inequality. Does not
0135   /// modify the original vector.
0136   ///
0137   /// \param R The vector of coefficients to be converted.
0138   static SmallVector<int64_t, 8> toStrictLessThan(SmallVector<int64_t, 8> R) {
0139     // The strict less than is obtained by subtracting 1 from the constant.
0140     if (SubOverflow(R[0], int64_t(1), R[0])) {
0141       return {};
0142     }
0143     return R;
0144   }
0145
0146   bool isConditionImplied(SmallVector<int64_t, 8> R) const;
0147
0148   SmallVector<int64_t> getLastConstraint() const {
0149     assert(!Constraints.empty() && "Constraint system is empty");
0150     SmallVector<int64_t> Result(NumVariables, 0);
0151     for (auto &Entry : Constraints.back())
0152       Result[Entry.Id] = Entry.Coefficient;
0153     return Result;
0154   }
0155
0156   void popLastConstraint() { Constraints.pop_back(); }
0157   void popLastNVariables(unsigned N) {
0158     assert(NumVariables > N);
0159     NumVariables -= N;
0160   }
0161
0162   /// Returns the number of rows in the constraint system.
0163   unsigned size() const { return Constraints.size(); }
0164
0165   /// Print the constraints in the system.
0166   void dump() const;
0167 };
0168 } // namespace llvm
0169
0170 #endif // LLVM_ANALYSIS_CONSTRAINTSYSTEM_H