This is an archive of the discontinued LLVM Phabricator instance.

[MLIR] Redundancy detection for FlatAffineConstraints using Simplex
ClosedPublic

Authored by arjunp on Jul 30 2020, 5:16 AM.

Details

Summary

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.

Diff Detail

Event Timeline

arjunp created this revision.Jul 30 2020, 5:16 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 30 2020, 5:16 AM
arjunp requested review of this revision.Jul 30 2020, 5:16 AM
arjunp retitled this revision from Redundancy detection for FlatAffineConstraints using Simplex This patch adds the capability to perform constraint redundancy checks for FlatAffineConstraints using Simplex, via a new member function FlatAffineConstraints... to Redundancy detection for FlatAffineConstraints using Simplex.Jul 30 2020, 5:17 AM
arjunp edited the summary of this revision. (Show Details)
arjunp updated this revision to Diff 281905.Jul 30 2020, 5:57 AM

Improved documentation.

arjunp edited the summary of this revision. (Show Details)Jul 30 2020, 6:42 AM
bondhugula requested changes to this revision.Jul 30 2020, 7:05 AM

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–302

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.

This revision now requires changes to proceed.Jul 30 2020, 7:05 AM
bondhugula added inline comments.Jul 30 2020, 7:09 AM
mlir/lib/Analysis/Presburger/Simplex.cpp
501

General comment here on the implementation.

mlir/unittests/Analysis/AffineStructuresTest.cpp
275

Could you add this test case? It's a common pattern.

i >= 0, 32*i <= N - 1, 
ii >= 32i, ii >= 0, ii <= 32ii + 31, ii <= N-1

This fourth constraint is redundant.

bondhugula added inline comments.Jul 30 2020, 7:11 AM
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.

arjunp updated this revision to Diff 282800.Aug 3 2020, 9:57 PM
arjunp marked 11 inline comments as done.

Addressed comments. Also changed the names of some Simplex objects to simplex for uniformity.

arjunp updated this revision to Diff 282855.Aug 4 2020, 3:23 AM

clang-format.

arjunp added inline comments.Aug 4 2020, 3:24 AM
mlir/unittests/Analysis/AffineStructuresTest.cpp
275

Added in SimplexTest.

mlir/unittests/Analysis/Presburger/SimplexTest.cpp
299

Moved to AffineStructuresTest.

arjunp updated this revision to Diff 283307.Aug 5 2020, 11:11 AM

clang-format again. Mention redundancy checks in the Simplex.h header comment and first paragraph of the Simplex class documentation.

bondhugula added inline comments.Aug 6 2020, 12:07 AM
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.

bondhugula added inline comments.Aug 6 2020, 5:33 AM
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.

bondhugula accepted this revision.Aug 6 2020, 5:40 AM
This revision is now accepted and ready to land.Aug 6 2020, 5:40 AM

Please add an [MLIR] tag to the commit title.

arjunp updated this revision to Diff 283619.EditedAug 6 2020, 8:29 AM
arjunp marked 6 inline comments as done.

Address inline review comments.

arjunp retitled this revision from Redundancy detection for FlatAffineConstraints using Simplex to [MLIR] Redundancy detection for FlatAffineConstraints using Simplex.Aug 6 2020, 8:31 AM
arjunp updated this revision to Diff 283624.Aug 6 2020, 8:50 AM

Add suggested test.

Harbormaster completed remote builds in B67324: Diff 283619.
arjunp added a comment.EditedAug 6 2020, 9:31 AM

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?

arjunp updated this revision to Diff 286233.Aug 18 2020, 2:59 AM

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.

Also, I don't have commit access yet, so someone else will need to land this.

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

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.

bondhugula accepted this revision.Aug 18 2020, 4:42 AM
bondhugula added inline comments.
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).

Also, I don't have commit access yet, so someone else will need to land this.

I can commit this for you. Do you have anything more to update? Could you look at the last question?

arjunp updated this revision to Diff 286676.Aug 19 2020, 3:31 PM
arjunp marked an inline comment as done.

Ensure that the removed constraint is the redundant one.

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.