This is an archive of the discontinued LLVM Phabricator instance.

[MLIR][Presburger] Support lexicographic max/min union of two PWMAFunction
ClosedPublic

Authored by Groverkss on Jun 29 2022, 8:08 AM.

Details

Summary

This patch implements a lexicographic max/min union of two PWMAFunctions.

The lexmax/lexmin union of two functions is defined as a function defined on
the union of the input domains of both functions, such that when only one of the
functions are defined, it outputs the same as that function, and if both are
defined, it outputs the lexmax/lexmin of the two outputs. On points where
neither function is defined, the union is not defined either.

Diff Detail

Event Timeline

Groverkss created this revision.Jun 29 2022, 8:08 AM
Groverkss requested review of this revision.Jun 29 2022, 8:08 AM
arjunp added inline comments.Jun 29 2022, 10:27 AM
mlir/include/mlir/Analysis/Presburger/PWMAFunction.h
58–59

I would call these getOutputMatrix and getOutputExpr

174–177

I prefer to explain it as:

Return a function defined on the union of the domains of this and func,
such that when only one of the functions is defined, it outputs the same as that function,
and if both are defined, it outputs the lexmax/lexmin of the two outputs.
On points where neither function is defined, the returned function is not defined either.

190–202

I prefer explaining it like this:

Return a function defined on the union of the domains of this and func,
such that when only one of the functions is defined, it outputs the same as that function,
and if neither is defined, the returned function is not defined either.

The provided `tiebreak` function determines which of the two functions' output should be used
on inputs where both the functions are defined. More precisely, given two `MultiAffineFunction`s
`mafA` and `mafB`, `tiebreak` returns the subset of the intersection of the two functions' domains
where the output of `mafA` should be used.

Also, what about just calling the function argument tiebreak?

205–206

Please use mafA and mafB

mlir/lib/Analysis/Presburger/PWMAFunction.cpp
237

Nits: Please use funcA and funcB below.

238–239
240

Please write a high-level description of the algorithm used here, and explain why all the output domains will be disjoint

241

nit: I prefer = here

243–248

These comments seem redundant, as they just repeat the same thing that's written in the code?

256–259
265–267

Doc?

272–273

Why is this a reference?

276
278–283

Why are you recomputing this every time in the loop? Just maintain the set incrementally, add and remove the last inequality every time

285

Please describe what inequality is being added in the doc.

286–288

I'm confused. For lexmin this should be maf1 < maf2 right? You seem to have written maf1 > maf2? Please write doc to clarify.

Groverkss marked 15 inline comments as done.Jul 1 2022, 6:30 AM
Groverkss added inline comments.
mlir/lib/Analysis/Presburger/PWMAFunction.cpp
241

This will not work since the copy constructor is explcit.

Groverkss updated this revision to Diff 441678.Jul 1 2022, 6:30 AM

Address Arjun's comments

arjunp added inline comments.Jul 2 2022, 1:13 PM
mlir/include/mlir/Analysis/Presburger/IntegerRelation.h
587–590

Locals need not be divs anymroe

mlir/lib/Analysis/Presburger/PWMAFunction.cpp
238–242
252
259–260

It has to be disjoint from the other pieces already added. I don't understand what you've written here?

AFAIU, you need to write that all pieces that have been added so far are either

a) subsets of the domains of other MAFs in this, which are guaranteed to be disjoint from dom, or
b) they are one of the pieces added for funcA, and we have been subtracting all such pieces from dom so dom is disjoint from those pieces as well.

273
274
282

assert that the spaces are compatible, have same number of outputs

294
303

same as above

314

This still seems incorrect. the complement of outA > outB is outA <= outB. We want outA < outB. Please also add regression tests for these bug fixes

323
Groverkss updated this revision to Diff 441961.Jul 3 2022, 9:42 AM
Groverkss marked 11 inline comments as done.

Address Arjun's comments

arjunp added inline comments.Jul 3 2022, 10:24 AM
mlir/lib/Analysis/Presburger/PWMAFunction.cpp
314

Again, this doesn't look correct.

ineq is outA - outB - 1 >= 0.
We want outB - outA - 1 >= 0.
You seem to be adding outB - outA + 1 >= 0.

Also, can you please add some regression tests?

Groverkss updated this revision to Diff 442090.Jul 4 2022, 6:57 AM
Groverkss marked an inline comment as done.

Fix bug and add regression tests for tiebreakLex

arjunp added inline comments.Jul 4 2022, 10:12 AM
mlir/unittests/Analysis/Presburger/PWMAFunctionTest.cpp
208

func3 is redundant?

314

func3 is redundant

377

Please write short explanations of what's going on in the more complex test cases

Given a piecewise multi affine function func, the lexicographic
maximum/minimum union of func and this is defined as the maximum/minimum
output at the points where both functions are defined and the output of the
defined function where one of the functions is defined but the
other is not.

This is really convoluted. Can you please rewrite clearly referring to the right functions?

mlir/include/mlir/Analysis/Presburger/IntegerRelation.h
802

Missing doc comment.

mlir/include/mlir/Analysis/Presburger/PWMAFunction.h
58–59

These are missing doc comments as well -- the non-trivial ones above as well.

Groverkss edited the summary of this revision. (Show Details)Jul 5 2022, 6:24 AM
Groverkss edited the summary of this revision. (Show Details)
Groverkss updated this revision to Diff 442280.Jul 5 2022, 6:28 AM
Groverkss marked 5 inline comments as done.
  • Address Arjun's comments
  • Address Uday's comments
arjunp added a comment.Jul 6 2022, 7:02 AM

Can you write a little bit more detailed explanations for the complex test cases?

mlir/unittests/Analysis/Presburger/PWMAFunctionTest.cpp
464

Can you call all the func3's result?

arjunp added inline comments.Jul 6 2022, 7:38 AM
mlir/unittests/Analysis/Presburger/PWMAFunctionTest.cpp
372

explain the other two pieces in the output?

Groverkss updated this revision to Diff 442579.Jul 6 2022, 7:57 AM
Groverkss marked an inline comment as done.
  • Add more docs for tests
Groverkss marked an inline comment as done.Jul 6 2022, 7:58 AM
Groverkss added inline comments.
mlir/unittests/Analysis/Presburger/PWMAFunctionTest.cpp
372

I think they are already explained, right?

arjunp added inline comments.Jul 6 2022, 8:03 AM
mlir/unittests/Analysis/Presburger/PWMAFunctionTest.cpp
495

should be y - 1 < y ?

Groverkss updated this revision to Diff 442584.Jul 6 2022, 8:05 AM
Groverkss marked 2 inline comments as done.
  • Fix doc in tests
arjunp accepted this revision.Jul 6 2022, 8:06 AM
arjunp added inline comments.
mlir/unittests/Analysis/Presburger/PWMAFunctionTest.cpp
495

I think this is always true, not just when x == 0

This revision is now accepted and ready to land.Jul 6 2022, 8:06 AM
Groverkss updated this revision to Diff 442586.Jul 6 2022, 8:07 AM
  • Fix doc
Groverkss marked an inline comment as done.Jul 6 2022, 8:07 AM
This revision was landed with ongoing or failed builds.Jul 6 2022, 8:09 AM
This revision was automatically updated to reflect the committed changes.