This patch adds the capability to perform constraint redundancy checks for FlatAffineConstraints using Simplex, via a new member function FlatAffineConstraints::removeRedundantConstraints. The pre-existing redundancy detection algorithm runs a full rational emptiness check for each inequality separately for checking redundancy. Leveraging the existing Simplex infrastructure, in this patch we have an algorithm for redundancy checks that can check each constraint by performing pivots on the tableau, which provides an alternative to running Fourier-Motzkin elimination for each constraint separately.
Details
Diff Detail
- Repository
- rG LLVM Github Monorepo
Event Timeline
Thanks for implementing this functionality. Some superfluous comments on documentation to start with.
mlir/include/mlir/Analysis/AffineStructures.h | ||
---|---|---|
540 | Triple doc comment please. | |
mlir/include/mlir/Analysis/Presburger/Simplex.h | ||
117 | Nit: . i.e., -> , i.e., | |
184 | constraint or inequality? The signature indicates inequality. | |
296 | Missing doc comment. | |
mlir/lib/Analysis/AffineStructures.cpp | ||
1413 | inequalities or inequalities and equalities? | |
mlir/unittests/Analysis/Presburger/SimplexTest.cpp | ||
219 | Comment above on what these tests are testing. | |
299 | Comment here on what you are trying to test. | |
336 | Use i = 0, e = ...; i < e form please. |
mlir/include/mlir/Analysis/AffineStructures.h | ||
---|---|---|
540 | A check using Simplex ... -> Removes redundant constraints using Simplex. It would be good to add a couple of lines to say something about its complexity even if its high level. |
Addressed comments. Also changed the names of some Simplex objects to simplex for uniformity.
clang-format again. Mention redundancy checks in the Simplex.h header comment and first paragraph of the Simplex class documentation.
mlir/include/mlir/Analysis/AffineStructures.h | ||
---|---|---|
541 | Actually, the worst case here is rare and 'n' doesn't keep growing for the use cases as it is tied to loop nest and array dimensionalities - so you may want to just use (rare) in parentheses or to that effect. Otherwise, users may think it's more expensive than it really is. We are looking at a small number of variables and vertices here. Any upper bound in terms of the number of vertices and the number of constraints will also be helpful. |
mlir/include/mlir/Analysis/Presburger/Simplex.h | ||
---|---|---|
301 | Comment here please. | |
mlir/lib/Analysis/AffineStructures.cpp | ||
1437 | is -> if | |
mlir/lib/Analysis/Presburger/Simplex.cpp | ||
507–508 | You can move these comments inline into the body of the function. | |
514 | Comment here. | |
mlir/unittests/Analysis/Presburger/SimplexTest.cpp | ||
357 | Can you rename isMarkedRedundant2? (These are typical constraints from a tiled loop nest.) |
Looks great overall - ideally, I'd like to some more test case patterns - the additional tests can be small. Consider this one:
128x >= -127 x <= 7 y >= 128x y >= 0
The last constraint should be redundant.
Thanks for your review!
In the test you suggested, was the first constraint meant to be 128x >= 127 rather than 128x >= -127? I see that when x is constrained to integers, 128x >= -127 does imply 128x >= 0. Currently, the implementation doesn't use the integrality of the variables at all. This case could be caught by internally running FlatAffineConstraints::GCDTightenInequalities()before constructing the Simplex. Should this be done?
Also, I forgot to mention that in the previous test you suggested, I assumed that the penultimate constraint was meant to be ii <= 32i + 31 rather than ii <= 32ii + 31 (in which ii occurs twice). Was this correct?
Run GCDTightenInequalities() before the redundancy check in order to catch some constraints which are not rational-redundant but are integer-redundant, i.e. the constraint is valid for all integer solutions of the other constraints even though it is not valid for all rational solutions.
I actually meant 128x >= -127 to stress on the integrality part. I now see your comment on the implementation not using integrality in any way.
FlatAffineConstraints::GCDTightenInequalities()before constructing the Simplex. Should this be done?
Well, in this case, GCD tighten inequalities will help tighten it to x >= 0, but that's just a stop gap / best effor thing in that it won't help in other non-trivial / general cases. So I guess one gets the desired simplified result here only by doing this tightening before using the proposed redundancy check?
Also, I forgot to mention that in the previous test you suggested, I assumed that the penultimate constraint was meant to be ii <= 32i + 31 rather than ii <= 32ii + 31 (in which ii occurs twice). Was this correct?
That's right - that was a typo.
mlir/unittests/Analysis/AffineStructuresTest.cpp | ||
---|---|---|
382 | Random comment: for a stronger test, is there a way you can check in addition that a specific inequality doesn't exist in the set? (in this case that y >= 0 doesn't exist). |
I can commit this for you. Do you have anything more to update? Could you look at the last question?
Well, in this case, GCD tighten inequalities will help tighten it to x >= 0, but that's just a stop gap / best effor thing in that it won't help in other non-trivial / general cases. So I guess one gets the desired simplified result here only by doing this tightening before using the proposed redundancy check?
Yes, we have to tighten before running the redundancy check. I don't think it's possible to have a general integer-exact redundancy check without using an integer-exact emptiness check.
Triple doc comment please.