With this, we have complete support for emptiness checks. This also paves the way for future support to check if two FlatAffineConstraints are equal.

# Details

# Diff Detail

- Repository
- rG LLVM Github Monorepo

### Event Timeline

It looks like something went wrong when updating the second revision and the diff now *only* contains the comment change. Note that if you use `arc diff` on a branch of multiple commits, you must specify the commit that the branch is based on rather than `HEAD^`, which is merely the previous-to-head commit.

mlir/include/mlir/Analysis/Presburger/LinearTransform.h | ||
---|---|---|

31 ↗ | (On Diff #315321) | Naming nit: |

mlir/lib/Analysis/AffineStructures.cpp | ||

1079 | Shouldn't this be | |

1103 | Let's not commit commented-out code | |

1106–1107 | Or you can do for (unsigned i = fac.getNumEqualities(); i >0; --i) if (eqInvolvesSuffixDims(fac, i - 1, unboundedDims)) fac.removeEquality(i - 1); that is, replace uses of | |

1183 | You may want to call | |

mlir/lib/Analysis/Presburger/LinearTransform.cpp | ||

14 ↗ | (On Diff #315321) | I suppose you wanted |

16 ↗ | (On Diff #315321) | I don't know how to understand "remainder of division by [0, M(row, sourceCol))". Did you rather mean [0, M(row, sourceCol) be the range of values the remainder can take? |

23 ↗ | (On Diff #315321) | Please only use |

23–24 ↗ | (On Diff #315321) | Note that machine integer division is rounding to zero, as opposed to Euclidean division that rounds to negative infinity. So -4 / 3 gives -1 with machine division and -2 with Euclidean division. Usually, in affine world, I'd expect the latter. If it is used further to compute the remainder, machine division will yield -4 - (-1 * 3) = -1, but one would normally expect the remainder to be non-negative -4 - (-2 * 3) = 2. Please verify that this code does what you expect it to do and, if so, add an appropriate comment (-1 = 2 mod 3 after all). |

75 ↗ | (On Diff #315321) | Except that the code in |

110 ↗ | (On Diff #315321) | Please reserve the space in the vector before pushing back in a loop. |

mlir/unittests/Analysis/AffineStructuresTest.cpp | ||

254 | Please add a test that involves equalities, and a test that exercises Euclidean division when computing the row echelon form. Since these are |

Thanks for the review!

mlir/lib/Analysis/AffineStructures.cpp | ||
---|---|---|

1079 | Sorry, yes. Fixed and added a test case. | |

mlir/lib/Analysis/Presburger/LinearTransform.cpp | ||

16 ↗ | (On Diff #315321) | Yes, fixed. |

23–24 ↗ | (On Diff #315321) | Yeah, my intention was to use Euclidean division. We can't test for this because the Euclidean GCD algorithm is still correct and terminates with machine division (about efficiency, I am not sure). It is still correct with machine division since adding _any_ multiple of one operand to the other preserves their GCD. Termination: Suppose we run the algorithm with integers x and y. If one of x or y is divides the other then the remainder issue doesn't come into play. Otherwise, after one iteration we have -|x| < y < |x|. If |y| > |x|, this means |y| decreases after this iteration. Otherwise, consider the next iteration after x, y are swapped, in which the operand of greater magnitude will be set to the remainder. That operand will decrease in magnitude then. So every two iterations one of the operands decreases in magnitude as long as neither is divisible by the other. Once one operand becomes a multiple of the other, that one gets set to zero and we are done. To test that we use Euclidean division, we would have to directly test this static free function I feel it's easier to reason about the code if both operands are made positive, so I've changed it accordingly. |

mlir/unittests/Analysis/AffineStructuresTest.cpp | ||

254 | Added tests involving equalities. See above regarding the unit test for |

mlir/lib/Analysis/AffineStructures.cpp | ||
---|---|---|

1065 | Might be worth capturing this fact in local variable: unsigned dirsNumCols = getNumCols() - 1; since it is use 3 times below. |

mlir/lib/Analysis/AffineStructures.cpp | ||
---|---|---|

1066 | consider const unsigned dirsNumCols = getNumCols() - 1; to indicate that the value isn't changed throughout the computation. | |

mlir/lib/Analysis/Presburger/Matrix.cpp | ||

88 | nit: eliminate unnecessary return? | |

mlir/lib/Analysis/Presburger/Simplex.cpp | ||

523 | Consider: return computeOptimum(Direction::Up, con[constraintIndex]).hasValue(); instead of: if (Optional<Fraction> opt = computeOptimum(Direction::Up, con[constraintIndex])) return true; return false; |

We can't test for this because the Euclidean GCD algorithm is still correct and terminates with machine division (about efficiency, I am not sure).

You still can write a test computing the column echelon form for a given matrix that requires division by a negative value somewhere. The point of such a test is to (a) demonstrate that the result is correct and (b) provide enough coverage so that potential future changes in the column echelon computation affect a specific test rather than a much larger test (emptiness check) that can also be affected by dozens of other things and makes it ten times harder to find the root cause.

mlir/lib/Analysis/AffineStructures.cpp | ||
---|---|---|

1066 | MLIR does not follow this pattern. If you prefer it had, please bring it up for general discussion rather than diverging locally. |