LLVM 17.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"
15
16#include <string>
17
18namespace 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
38public:
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
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
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
This file implements a class to represent arbitrary precision integral constant values and operations...
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
ArrayRef< int64_t > getLastConstraint()
static SmallVector< int64_t, 8 > negate(SmallVector< int64_t, 8 > R)
bool mayHaveSolution()
Returns true if there may be a solution for the constraints in the system.
bool isConditionImplied(SmallVector< int64_t, 8 > R) const
unsigned size() const
Returns the number of rows in the constraint system.
bool addVariableRow(ArrayRef< int64_t > R)
void popLastNVariables(unsigned N)
bool addVariableRowFill(ArrayRef< int64_t > R)
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:941
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
APInt GreatestCommonDivisor(APInt A, APInt B)
Compute GCD of two unsigned APInt values.
Definition: APInt.cpp:759
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
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:1735
#define N