LLVM  14.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/STLExtras.h"
15 #include "llvm/ADT/SmallVector.h"
16 
17 #include <string>
18 
19 namespace llvm {
20 
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
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 Fourier–Motzkin 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:
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 
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 
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 
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
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::ConstraintSystem::addVariableRowFill
bool addVariableRowFill(const SmallVector< int64_t, 8 > &R)
Definition: ConstraintSystem.h:56
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::ConstraintSystem::isConditionImplied
bool isConditionImplied(SmallVector< int64_t, 8 > R)
Definition: ConstraintSystem.cpp:145
APInt.h
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:876
STLExtras.h
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:1551
llvm::ConstraintSystem
Definition: ConstraintSystem.h:21
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:81
llvm::ConstraintSystem::negate
static SmallVector< int64_t, 8 > negate(SmallVector< int64_t, 8 > R)
Definition: ConstraintSystem.h:67
llvm::ConstraintSystem::popLastConstraint
void popLastConstraint()
Definition: ConstraintSystem.h:78
ArrayRef.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ConstraintSystem::addVariableRow
bool addVariableRow(const SmallVector< int64_t, 8 > &R)
Definition: ConstraintSystem.h:40
llvm::ArrayRef< std::string >
uint32_t
llvm::makeArrayRef
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:476
SmallVector.h
llvm::APIntOps::GreatestCommonDivisor
APInt GreatestCommonDivisor(APInt A, APInt B)
Compute GCD of two unsigned APInt values.
Definition: APInt.cpp:744
llvm::ConstraintSystem::mayHaveSolution
bool mayHaveSolution()
Returns true if there may be a solution for the constraints in the system.
Definition: ConstraintSystem.cpp:138
llvm::abs
APFloat abs(APFloat X)
Returns the absolute value of the argument.
Definition: APFloat.h:1282