This is an archive of the discontinued LLVM Phabricator instance.

[MLIR] Introduce coalesce for PresburgerSet
ClosedPublic

Authored by webmiche on Sep 28 2021, 2:43 AM.

Details

Summary

This patch provides functionality for simplifying PresburgerSets by checking if any FlatAffineConstraints in the set is contained in another, and removing such redundant FACs.

This is part of a series of patches to provide functionality for integer set coalescing in MLIR.

Diff Detail

Event Timeline

webmiche created this revision.Sep 28 2021, 2:43 AM
webmiche requested review of this revision.Sep 28 2021, 2:43 AM
webmiche updated this revision to Diff 375509.Sep 28 2021, 2:58 AM
webmiche added a comment.EditedSep 28 2021, 2:58 AM
  • update FACUtils license
Herald added a project: Restricted Project. · View Herald Transcript
webmiche updated this revision to Diff 375511.Sep 28 2021, 3:00 AM

update the revision to the proper HEAD state

webmiche removed a project: Restricted Project.
webmiche removed subscribers: hiraditya, pengfei, llvm-commits.
webmiche updated this revision to Diff 375517.Sep 28 2021, 3:40 AM
  • add header guard to FACUtils.h

Hi, thanks for the patch!

mlir/include/mlir/Analysis/Presburger/Simplex.h
241

Maybe clarify the name as isRedundantInequality.

Maybe even add a function isRedundantEquality for equalities as well as some tests for it.

mlir/include/mlir/Analysis/PresburgerSet.h
99

Nit: inparticular -> in particular

subset-> subsets

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

nit: maybe remove this blank line

1253

Don't you have to check both inequalities that make up the equality?

1259

A bit of documentation might be useful here.

mlir/lib/Analysis/PresburgerSet.cpp
386

nit: I think you can drop the this-> everywhere. We're only operating on one PresburgerSet.

387

You can use SmallBitVector.

410

I think you can drop these braces.

mlir/unittests/Analysis/FACUtils.h
1 ↗(On Diff #375517)

IMO you can just name it Utils.h.

9 ↗(On Diff #375517)

I believe it wants you to remove the trailing underscore.

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

Not sure about this. Let's see what the others think.

416–418

nit: The numbering [0] [1] [2] doesn't seem to be used, so you can probably remove it.

429–439

nit: I feel these blank lines aren't needed.

mlir/unittests/Analysis/PresburgerSetTest.cpp
614

Please add some tests involving equalities.

614

Please add a set with zero FACs in the set.

arjunp added inline comments.Sep 28 2021, 4:56 AM
mlir/include/mlir/Analysis/Presburger/Simplex.h
244

all inequalities -> all constraints

mlir/lib/Analysis/PresburgerSet.cpp
398

Please write a complete sentence; capitalize the first letter and put a full stop at the end. Also, you can use backticks to refer to variables like bs1.

Groverkss added inline comments.Sep 28 2021, 5:48 AM
mlir/include/mlir/Analysis/Presburger/Simplex.h
243–245

Could you mention what happens in the case either of the sets is empty?

mlir/lib/Analysis/PresburgerSet.cpp
389

Use preincrement: ++i instead of i++.

mlir/unittests/Analysis/FACUtils.h
19–22 ↗(On Diff #375517)

The same function is used in AffineStructuresTest. If you decide to use this utils file, you can also use it there.

webmiche updated this revision to Diff 376680.Oct 2 2021, 2:18 AM
  • address review comments
webmiche marked 16 inline comments as done.Oct 2 2021, 3:21 AM
webmiche added inline comments.
mlir/lib/Analysis/Presburger/Simplex.cpp
1268

the both -> both the

arjunp added inline comments.Oct 2 2021, 3:20 PM
mlir/lib/Analysis/Presburger/Simplex.cpp
1259–1268

What are subplanes? do you mean hyperplanes?

mlir/lib/Analysis/PresburgerSet.cpp
387

Maybe we can call it something more descriptive, e.g., isRedundant or something.

401

I think there is nothing called bs1 in the code now.

webmiche updated this revision to Diff 376970.Oct 4 2021, 11:50 AM
  • update codumentation
mlir/lib/Analysis/Presburger/Simplex.cpp
1259–1268

I was thinking in 2D 😅 . I think in 3D, one would describe the thing I am thinking of as a half-space.

webmiche marked 3 inline comments as done.Oct 4 2021, 11:51 AM
bondhugula added a comment.EditedOct 5 2021, 10:37 PM

Great to see this. Separately, I think it'll be good to create in the future some high-level documentation of PresburgerSet and the underlying machinery being used (GBR, simplex, etc.) as part of a larger document perhaps on Affine Analysis. This can go into the doc tree and appear at mlir.llvm.org.

bondhugula added inline comments.Oct 6 2021, 7:14 PM
mlir/unittests/Analysis/Utils.h
16–17

FACUTILS_H -> UTILS_H

26–47

We shouldn't be having these definitions in the header file but in the .cpp file. Is this some sort of an exception for unit tests includes?

bondhugula added inline comments.Oct 6 2021, 7:16 PM
mlir/unittests/Analysis/PresburgerSetTest.cpp
614

Doc comment here.

614

const ref for set?

webmiche updated this revision to Diff 378910.Oct 12 2021, 1:07 AM
split Utils.h, add possible const refs

Utils.h was split into Utils.h and Utils.cpp. Furthermore, addressed the remaining comments, in particular the PresburgerSet in coalesce is const now.
rriddle added inline comments.Oct 12 2021, 1:08 AM
mlir/unittests/Analysis/Utils.h
15

Can you rename this to something that highlights that this is for affine analyses? Utils is fairly generic of a name.

webmiche marked 3 inline comments as done.Oct 12 2021, 1:09 AM
webmiche added inline comments.Oct 12 2021, 1:11 AM
mlir/unittests/Analysis/Utils.h
15

I agree. What do you suggest? FACUtils? FACGenerationUtils?

rriddle added inline comments.Oct 12 2021, 1:14 AM
mlir/unittests/Analysis/Utils.h
15

Either of those is fine, I don't have a strong preference.

webmiche updated this revision to Diff 378916.Oct 12 2021, 1:24 AM
rename Utils -> FACGenerationUtils
arjunp added inline comments.Oct 13 2021, 9:54 AM
mlir/include/mlir/Analysis/Presburger/Simplex.h
248
248–249

Personally I feel that these lines make this sound more complex than it really is. Maybe just call the function isSubsetOf and say that it returns true if this Simplex's polytope is a subset of the given FAC; then hopefully everyone knows that empty set is subset of empty set, etc.

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

It is not clear which two half spaces "both half-spaces defined by coeffs" is referring to.

bondhugula added inline comments.Oct 15 2021, 9:14 PM
mlir/unittests/Analysis/FACGenerationUtils.cpp
24 ↗(On Diff #378916)

Use ArrayRef instead of const SmallVector ref.

26 ↗(On Diff #378916)

Likewise.

mlir/unittests/Analysis/Presburger/CMakeLists.txt
8–9

Please place the libraries each on a separate line.

webmiche added inline comments.Dec 5 2021, 11:39 PM
mlir/include/mlir/Analysis/Presburger/Simplex.h
248–249

As discussed, I will rename this function to isRationalSubsetOf. Notice that there can be cases where an FAC is a subset in terms of integer points, but has some additional rational points. In this case, this function returns false.

A full subset check at this point would be too slow to justify for a heuristic mainly targeted at runtime optimization.

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

I am thinking here about the one for which coeffs is >= 0 and the one where coeffs is <= 0. If both hold, then we know that coeffs== 0, so it holds as an equality.

I am unsure how to write this better, while still justifying why we need both the minimum and the maximum.

/// Computes the minimum and maximum value `coeffs` can take. If the
/// minimum is greater than 0 and the maximum is less than 0, `coeffs`>= 0
/// and `coeffs` <= 0 respectively hold, hence `coeffs`== 0 and
/// the equality defined by `coeffs` holds in the entire polytope.
arjunp added inline comments.Dec 6 2021, 3:52 AM
mlir/lib/Analysis/Presburger/Simplex.cpp
1268

since 0 <= minimum <= maximum <= 0, the checks be changed to just minimum && maximum && *minimum == 0 && *maximum == 0 instead right? Then you can write the doc:

Check whether the equality given by `coeffs == 0` is redundant given the existing constraints. This is redundant when `coeffs` is already always zero under the existing constraints. `coeffs` is always zero when the minimum and maximum value that `coeffs` can take are both zero.
webmiche updated this revision to Diff 392050.EditedDec 6 2021, 6:53 AM
  • address review comments, update unittests to use AffineParser

I was able to delete all the FACGenerationUtils.{h,cpp}, as I am now using the AffineStructuresParser. Feedback on that is very welcome! :)

webmiche marked 4 inline comments as done.Dec 6 2021, 6:56 AM
arjunp added inline comments.Dec 7 2021, 5:04 AM
mlir/include/mlir/Analysis/Presburger/Simplex.h
246–249

You can simplify the documentation now as I mentioned -- you can just say it returns true if this Simplex's polytope is a subset of the given FAC

webmiche updated this revision to Diff 392712.Dec 8 2021, 4:43 AM
  • update isRationalSubsetOf comment
webmiche updated this revision to Diff 392713.Dec 8 2021, 4:44 AM
webmiche marked an inline comment as done.
  • fix typo

This revision appears to be pending for quite some time. Is there a plan of action here? Is this waiting on reviewers? @arjunp @Groverkss

arjunp accepted this revision.Dec 9 2021, 1:55 AM

LGTM. Please fix the nits below though.

mlir/lib/Analysis/Presburger/Simplex.cpp
1258
1260
This revision is now accepted and ready to land.Dec 9 2021, 1:55 AM
webmiche updated this revision to Diff 393074.Dec 9 2021, 2:12 AM

updated isRedundantInequality comment

webmiche marked 2 inline comments as done.Dec 9 2021, 2:12 AM
This revision was landed with ongoing or failed builds.Dec 9 2021, 2:20 AM
This revision was automatically updated to reflect the committed changes.