Go to the documentation of this file.
19 #define DEBUG_TYPE "constraint-system"
21 bool ConstraintSystem::eliminateUsingFM() {
28 assert(!Constraints.empty() &&
29 "should only be called for non-empty constraint systems");
30 unsigned NumVariables = Constraints[0].size();
33 unsigned NumConstraints = Constraints.size();
36 for (
unsigned R1 = 0; R1 < NumConstraints; R1++) {
37 if (Constraints[R1][1] == 0) {
39 NR.push_back(Constraints[R1][0]);
40 for (
unsigned i = 2;
i < NumVariables;
i++) {
41 NR.push_back(Constraints[R1][
i]);
48 for (
unsigned R2 = R1 + 1;
R2 < NumConstraints;
R2++) {
53 if (Constraints[
R2][1] == 0)
56 if ((Constraints[R1][1] < 0 && Constraints[
R2][1] < 0) ||
57 (Constraints[R1][1] > 0 && Constraints[
R2][1] > 0))
62 if (Constraints[UpperR][1] < 0)
66 for (
unsigned I = 0;
I < NumVariables;
I++) {
72 ((-1) * Constraints[LowerR][1] / GCD),
M1))
75 (Constraints[UpperR][1] / GCD), M2))
87 if (NewSystem.size() > 500)
97 bool ConstraintSystem::mayHaveSolutionImpl() {
98 while (!Constraints.empty() && Constraints[0].size() > 1) {
99 if (!eliminateUsingFM())
103 if (Constraints.empty() || Constraints[0].size() > 1)
106 return all_of(Constraints, [](
auto &R) {
return R[0] >= 0; });
110 if (Constraints.empty())
113 for (
auto &Row : Constraints) {
115 for (
unsigned I = 1,
S = Row.size();
I <
S; ++
I) {
118 std::string Coefficient;
121 Parts.push_back(Coefficient + Names[
I - 1]);
123 assert(!Parts.empty() &&
"need to have at least some parts");
129 void ConstraintSystem::dump()
const {
131 for (
unsigned i = 1;
i < Constraints.back().
size(); ++
i)
139 bool HasSolution = mayHaveSolutionImpl();
154 auto NewSystem = *
this;
155 NewSystem.addVariableRow(R);
156 return !NewSystem.mayHaveSolution();
This is an optimization pass for GlobalISel generic memory operations.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
(vector float) vec_cmpeq(*A, *B) C
std::enable_if_t< std::is_signed< T >::value, T > AddOverflow(T X, T Y, T &Result)
Add two signed integers, computing the two's complement truncated result, returning true if overflow ...
unsigned size() const
Returns the number of rows in the constraint system.
static SmallVector< int64_t, 8 > negate(SmallVector< int64_t, 8 > R)
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
bool isConditionImplied(SmallVector< int64_t, 8 > R) const
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
std::enable_if_t< std::is_signed< T >::value, T > MulOverflow(T X, T Y, T &Result)
Multiply two signed integers, computing the two's complement truncated result, returning true if an o...
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
APInt GreatestCommonDivisor(APInt A, APInt B)
Compute GCD of two unsigned APInt values.
std::string to_string(const T &Value)
bool mayHaveSolution()
Returns true if there may be a solution for the constraints in the system.
unsigned M1(unsigned Val)