20#define DEBUG_TYPE "constraint-system"
22bool ConstraintSystem::eliminateUsingFM() {
29 assert(!Constraints.empty() &&
30 "should only be called for non-empty constraint systems");
32 unsigned LastIdx = NumVariables - 1;
37 for (
unsigned R1 = 0; R1 < Constraints.size();) {
39 if (getLastCoefficient(Row1, LastIdx) == 0) {
40 if (Row1.
size() > 0 && Row1.
back().Id == LastIdx)
44 std::swap(Constraints[R1], Constraints.back());
45 RemainingRows.
push_back(std::move(Constraints.back()));
46 Constraints.pop_back();
51 unsigned NumRemainingConstraints = RemainingRows.
size();
52 for (
unsigned R1 = 0; R1 < NumRemainingConstraints; R1++) {
54 for (
unsigned R2 = R1 + 1;
R2 < NumRemainingConstraints;
R2++) {
55 int64_t UpperLast = getLastCoefficient(RemainingRows[
R2], LastIdx);
56 int64_t LowerLast = getLastCoefficient(RemainingRows[R1], LastIdx);
58 UpperLast != 0 && LowerLast != 0 &&
59 "RemainingRows should only contain rows where the variable is != 0");
61 if ((LowerLast < 0 && UpperLast < 0) || (LowerLast > 0 && UpperLast > 0))
72 unsigned IdxUpper = 0;
73 unsigned IdxLower = 0;
74 auto &LowerRow = RemainingRows[LowerR];
75 auto &UpperRow = RemainingRows[UpperR];
77 if (IdxUpper >= UpperRow.size() || IdxLower >= LowerRow.size())
82 uint16_t CurrentId = std::numeric_limits<uint16_t>::max();
83 if (IdxUpper < UpperRow.size()) {
84 CurrentId = std::min(UpperRow[IdxUpper].Id, CurrentId);
86 if (IdxLower < LowerRow.size()) {
87 CurrentId = std::min(LowerRow[IdxLower].Id, CurrentId);
90 if (IdxUpper < UpperRow.size() && UpperRow[IdxUpper].Id == CurrentId) {
91 UpperV = UpperRow[IdxUpper].Coefficient;
97 if (IdxLower < LowerRow.size() && LowerRow[IdxLower].Id == CurrentId) {
98 LowerV = LowerRow[IdxLower].Coefficient;
112 Constraints.push_back(std::move(NR));
114 if (Constraints.size() > 500)
123bool ConstraintSystem::mayHaveSolutionImpl() {
124 while (!Constraints.empty() && NumVariables > 1) {
125 if (!eliminateUsingFM())
129 if (Constraints.empty() || NumVariables > 1)
132 return all_of(Constraints, [](
auto &R) {
136 return R[0].Coefficient >= 0;
144 for (
auto &[V, Index] : Value2Index) {
145 std::string OperandName;
146 if (
V->getName().empty())
147 OperandName =
V->getNameOrAsOperand();
149 OperandName = std::string(
"%") +
V->getName().str();
150 Names[
Index - 1] = OperandName;
158 if (Constraints.empty())
161 for (
const auto &Row : Constraints) {
163 for (
const Entry &E : Row) {
164 if (E.Id >= NumVariables)
168 std::string Coefficient;
169 if (E.Coefficient != 1)
170 Coefficient = std::to_string(E.Coefficient) +
" * ";
171 Parts.
push_back(Coefficient + Names[E.Id - 1]);
174 int64_t ConstPart = 0;
176 ConstPart = Row[0].Coefficient;
178 <<
" <= " << std::to_string(ConstPart) <<
"\n");
186 bool HasSolution = mayHaveSolutionImpl();
203 auto NewSystem = *
this;
204 NewSystem.addVariableRow(R);
205 return !NewSystem.mayHaveSolution();
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),...
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
void dump() const
Print the constraints in the system.
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
@ C
The default llvm calling convention, compatible with C.
This is an optimization pass for GlobalISel generic memory operations.
std::enable_if_t< std::is_signed_v< T >, T > MulOverflow(T X, T Y, T &Result)
Multiply two signed integers, computing the two's complement truncated result, returning true if an o...
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
unsigned M1(unsigned Val)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
std::enable_if_t< std::is_signed_v< T >, T > AddOverflow(T X, T Y, T &Result)
Add two signed integers, computing the two's complement truncated result, returning true if overflow ...
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.