This is an archive of the discontinued LLVM Phabricator instance.

[MLIR][Presburger] Add applyDomain/Range to IntegerRelation
ClosedPublic

Authored by Groverkss on May 24 2022, 3:48 PM.

Details

Summary

This patch adds support for applying a relation on domain/range of a relation.

Diff Detail

Event Timeline

Groverkss created this revision.May 24 2022, 3:48 PM
Groverkss requested review of this revision.May 24 2022, 3:48 PM
ftynse accepted this revision.May 25 2022, 5:57 AM
This revision is now accepted and ready to land.May 25 2022, 5:57 AM
arjunp requested changes to this revision.May 25 2022, 6:20 AM

I think we should add a compose member function, it being a natural opreation on relations. You can move applyRange's documentation to compose and just mention in applyRange that it's the same as compose, but provided for uniformity with applyDomain.

mlir/include/mlir/Analysis/Presburger/IntegerRelation.h
534–536

It might be simpler to just say that this returns R2.inverse().compose(R1), and then perhaps provide a concrete example.

541–543

You can just write that it returns R1.compose(R2) and mention that this is provided for uniformity with applyDomain.

This revision now requires changes to proceed.May 25 2022, 6:20 AM
Groverkss updated this revision to Diff 432531.May 27 2022, 5:37 AM
Groverkss marked 2 inline comments as done.
  • Rebase
  • Address Arjun's comments
Groverkss added inline comments.May 27 2022, 5:41 AM
mlir/include/mlir/Analysis/Presburger/IntegerRelation.h
534–536

I feel the R2.invese().compose() makes it harder to understand than providing a proper mathematical description.

I think you can remove the backslashes on exists and in, unless doxygen can somehow render them, it seems unnecessary.

mlir/include/mlir/Analysis/Presburger/IntegerRelation.h
534–536

R2.inverse().compose() is in fact a proper mathematical description. For me personally, a concrete example was more useful to understand what the point of this is, and then for a formal specification the inverse compose thing will show what the general version of that example is.

Groverkss updated this revision to Diff 432636.May 27 2022, 2:20 PM
Groverkss marked an inline comment as done.

Address Arjun's comments

arjunp added inline comments.May 28 2022, 4:53 AM
mlir/include/mlir/Analysis/Presburger/IntegerRelation.h
533

What do you mean by R1(R2) here? If R3 is A -> C then R3(x) is R2(R1(x)). It seems the standard notation here is R1;R2 (https://en.wikipedia.org/wiki/Composition_of_relations).

535
536
537
542
543

read the original as (i->j), k at first

545

I would prefer this example, it has less "noise" and also shows a little bit happens when the other variables depend on the projected variable

R1 : i -> j : (0 <= i < 2, j = i)
R2: i -> k : (k = i floordiv 2)

R3: k -> j : (0 <= k < 1, 2k <=  j <= 2k + 1)

R1 = {(0, 0), (1, 1)}. R2 maps both 0 and 1 to 0. So R3 = {(0, 0), (0, 1)}
550–557

Not sure if an example is needed for composition but you can do e.g. R2 : j -> k : k = floordiv 2 and R1 from above

552
557
mlir/lib/Analysis/Presburger/IntegerRelation.cpp
2148–2156

I think the current implementation should be thought of as converting R1 to A -> (B x C), converting R2 to B x C, and intersecting

Groverkss marked 11 inline comments as done.May 28 2022, 11:32 AM
Groverkss added inline comments.
mlir/include/mlir/Analysis/Presburger/IntegerRelation.h
533

I meant it like we represent function composition f(g(x)). But this also works for me.

mlir/lib/Analysis/Presburger/IntegerRelation.cpp
2148–2156

good catch!

Groverkss marked 2 inline comments as done.

Address Arjun's comments

arjunp accepted this revision.May 28 2022, 11:42 AM
arjunp added inline comments.
mlir/include/mlir/Analysis/Presburger/IntegerRelation.h
533

Right, I mean that we are doing R2(R1(x)) then, not R1(R2).

I guess you can also add that it R3)(x) = R2(R1(x)), might be more understandable

546
548
This revision is now accepted and ready to land.May 28 2022, 11:42 AM
Groverkss updated this revision to Diff 432753.May 28 2022, 1:33 PM
Groverkss marked 3 inline comments as done.

Address Arjun's comments and rebase

This revision was landed with ongoing or failed builds.May 28 2022, 1:40 PM
This revision was automatically updated to reflect the committed changes.