Home | History | Annotate | Line # | Download | only in Analysis 
      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 FourierMotzkin elimination.
     31   bool eliminateUsingFM();
     32 
     33   /// Print the constraints in the system, using x0...xn as variable names.
     34   void dump() const;
     35 
     36   /// Returns true if there may be a solution for the constraints in the system.
     37   bool mayHaveSolutionImpl();
     38 
     39 public:
     40   bool addVariableRow(const SmallVector<int64_t, 8> &R) {
     41     assert(Constraints.empty() || R.size() == Constraints.back().size());
     42     // If all variable coefficients are 0, the constraint does not provide any
     43     // usable information.
     44     if (all_of(makeArrayRef(R).drop_front(1), [](int64_t C) { return C == 0; }))
     45       return false;
     46 
     47     for (const auto &C : R) {
     48       auto A = std::abs(C);
     49       GCD = APIntOps::GreatestCommonDivisor({32, (uint32_t)A}, {32, GCD})
     50                 .getZExtValue();
     51     }
     52     Constraints.push_back(R);
     53     return true;
     54   }
     55 
     56   bool addVariableRowFill(const SmallVector<int64_t, 8> &R) {
     57     for (auto &CR : Constraints) {
     58       while (CR.size() != R.size())
     59         CR.push_back(0);
     60     }
     61     return addVariableRow(R);
     62   }
     63 
     64   /// Returns true if there may be a solution for the constraints in the system.
     65   bool mayHaveSolution();
     66 
     67   static SmallVector<int64_t, 8> negate(SmallVector<int64_t, 8> R) {
     68     // The negated constraint R is obtained by multiplying by -1 and adding 1 to
     69     // the constant.
     70     R[0] += 1;
     71     for (auto &C : R)
     72       C *= -1;
     73     return R;
     74   }
     75 
     76   bool isConditionImplied(SmallVector<int64_t, 8> R);
     77 
     78   void popLastConstraint() { Constraints.pop_back(); }
     79 
     80   /// Returns the number of rows in the constraint system.
     81   unsigned size() const { return Constraints.size(); }
     82 
     83   /// Print the constraints in the system, using \p Names as variable names.
     84   void dump(ArrayRef<std::string> Names) const;
     85 };
     86 } // namespace llvm
     87 
     88 #endif // LLVM_ANALYSIS_CONSTRAINTSYSTEM_H
     89