LLVM  15.0.0git
ConstraintSystem.h
Go to the documentation of this file.
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 
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
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:
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(makeArrayRef(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 
56  // If all variable coefficients are 0, the constraint does not provide any
57  // usable information.
58  if (all_of(makeArrayRef(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 
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 
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
i
i
Definition: README.txt:29
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
APInt.h
llvm::ConstraintSystem::addVariableRow
bool addVariableRow(ArrayRef< int64_t > R)
Definition: ConstraintSystem.h:39
llvm::ConstraintSystem::getLastConstraint
ArrayRef< int64_t > getLastConstraint()
Definition: ConstraintSystem.h:82
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:877
llvm::ConstraintSystem::popLastNVariables
void popLastNVariables(unsigned N)
Definition: ConstraintSystem.h:84
llvm::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1617
llvm::ConstraintSystem
Definition: ConstraintSystem.h:20
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::ConstraintSystem::size
unsigned size() const
Returns the number of rows in the constraint system.
Definition: ConstraintSystem.h:92
llvm::ConstraintSystem::negate
static SmallVector< int64_t, 8 > negate(SmallVector< int64_t, 8 > R)
Definition: ConstraintSystem.h:71
llvm::ConstraintSystem::popLastConstraint
void popLastConstraint()
Definition: ConstraintSystem.h:83
ArrayRef.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ConstraintSystem::isConditionImplied
bool isConditionImplied(SmallVector< int64_t, 8 > R) const
Definition: ConstraintSystem.cpp:144
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
uint32_t
llvm::makeArrayRef
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:475
SmallVector.h
llvm::APIntOps::GreatestCommonDivisor
APInt GreatestCommonDivisor(APInt A, APInt B)
Compute GCD of two unsigned APInt values.
Definition: APInt.cpp:759
N
#define N
llvm::ConstraintSystem::addVariableRowFill
bool addVariableRowFill(ArrayRef< int64_t > R)
Definition: ConstraintSystem.h:55
llvm::ConstraintSystem::mayHaveSolution
bool mayHaveSolution()
Returns true if there may be a solution for the constraints in the system.
Definition: ConstraintSystem.cpp:137
llvm::abs
APFloat abs(APFloat X)
Returns the absolute value of the argument.
Definition: APFloat.h:1282
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:927