Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

  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/SmallVector.h"
  15.  
  16. #include <string>
  17.  
  18. namespace llvm {
  19.  
  20. class ConstraintSystem {
  21.   /// Current linear constraints in the system.
  22.   /// An entry of the form c0, c1, ... cn represents the following constraint:
  23.   ///   c0 >= v0 * c1 + .... + v{n-1} * cn
  24.   SmallVector<SmallVector<int64_t, 8>, 4> Constraints;
  25.  
  26.   /// Current greatest common divisor for all coefficients in the system.
  27.   uint32_t GCD = 1;
  28.  
  29.   // Eliminate constraints from the system using Fourier–Motzkin elimination.
  30.   bool eliminateUsingFM();
  31.  
  32.   /// Print the constraints in the system, using x0...xn as variable names.
  33.   void dump() const;
  34.  
  35.   /// Returns true if there may be a solution for the constraints in the system.
  36.   bool mayHaveSolutionImpl();
  37.  
  38. public:
  39.   bool addVariableRow(ArrayRef<int64_t> R) {
  40.     assert(Constraints.empty() || R.size() == Constraints.back().size());
  41.     // If all variable coefficients are 0, the constraint does not provide any
  42.     // usable information.
  43.     if (all_of(ArrayRef(R).drop_front(1), [](int64_t C) { return C == 0; }))
  44.       return false;
  45.  
  46.     for (const auto &C : R) {
  47.       auto A = std::abs(C);
  48.       GCD = APIntOps::GreatestCommonDivisor({32, (uint32_t)A}, {32, GCD})
  49.                 .getZExtValue();
  50.     }
  51.     Constraints.emplace_back(R.begin(), R.end());
  52.     return true;
  53.   }
  54.  
  55.   bool addVariableRowFill(ArrayRef<int64_t> R) {
  56.     // If all variable coefficients are 0, the constraint does not provide any
  57.     // usable information.
  58.     if (all_of(ArrayRef(R).drop_front(1), [](int64_t C) { return C == 0; }))
  59.       return false;
  60.  
  61.     for (auto &CR : Constraints) {
  62.       while (CR.size() != R.size())
  63.         CR.push_back(0);
  64.     }
  65.     return addVariableRow(R);
  66.   }
  67.  
  68.   /// Returns true if there may be a solution for the constraints in the system.
  69.   bool mayHaveSolution();
  70.  
  71.   static SmallVector<int64_t, 8> negate(SmallVector<int64_t, 8> R) {
  72.     // The negated constraint R is obtained by multiplying by -1 and adding 1 to
  73.     // the constant.
  74.     R[0] += 1;
  75.     for (auto &C : R)
  76.       C *= -1;
  77.     return R;
  78.   }
  79.  
  80.   bool isConditionImplied(SmallVector<int64_t, 8> R) const;
  81.  
  82.   ArrayRef<int64_t> getLastConstraint() { return Constraints[0]; }
  83.   void popLastConstraint() { Constraints.pop_back(); }
  84.   void popLastNVariables(unsigned N) {
  85.     for (auto &C : Constraints) {
  86.       for (unsigned i = 0; i < N; i++)
  87.         C.pop_back();
  88.     }
  89.   }
  90.  
  91.   /// Returns the number of rows in the constraint system.
  92.   unsigned size() const { return Constraints.size(); }
  93.  
  94.   /// Print the constraints in the system, using \p Names as variable names.
  95.   void dump(ArrayRef<std::string> Names) const;
  96. };
  97. } // namespace llvm
  98.  
  99. #endif // LLVM_ANALYSIS_CONSTRAINTSYSTEM_H
  100.