This is an archive of the discontinued LLVM Phabricator instance.

[MLIR][Presburger] Add support for piece-wise multi-affine functions
ClosedPublic

Authored by arjunp on Feb 2 2022, 4:42 AM.

Details

Summary

Add the class MultiAffineFunction which represents functions whose domain is an
IntegerPolyhedron and which produce an output given by a tuple of affine
expressions in the IntegerPolyhedron's ids.

Also add support for piece-wise MultiAffineFunctions, which are defined on a
union of IntegerPolyhedrons, and may have different output affine expressions
on each IntegerPolyhedron. Thus the function is affine on each individual
IntegerPolyhedron piece in the domain.

This is part of a series of patches leading up to parametric integer programming.

Depends on D118778.

Diff Detail

Event Timeline

arjunp created this revision.Feb 2 2022, 4:42 AM
arjunp requested review of this revision.Feb 2 2022, 4:42 AM
arjunp edited the summary of this revision. (Show Details)Feb 3 2022, 3:17 AM
arjunp updated this revision to Diff 405566.Feb 3 2022, 3:31 AM

Rebase and add forgotten classof

Groverkss added inline comments.Feb 5 2022, 12:11 AM
mlir/include/mlir/Analysis/Presburger/PWMAFunction.h
46

I think there is a better way to do this. The only way identifiers can be moved/removed/inserted in IntegerPolyhedron is through 3 functions:

  1. IntegerPolyhedron::insertId
  2. IntegerPolyhedron::removeIdRange
  3. IntegerPolyhedron::swapId

(I'm very sure that these are the only three functions that do this. In case there are any other, we should make them use these functions as these are the only operations required to modify the identifier space)

You could make these functions virtual in IntegerPolyhedron and just override these functions here to carry over the output information. After this, you can just inherit from public IntegerPolyhedron this and it should carry over the information properly for every method.

173–177

I think you can make these inline.

183–193

I don't think these should be in the header file. The only implementations that should be in the header files are functions that are supposed to be inlined.

mlir/lib/Analysis/Presburger/IntegerPolyhedron.cpp
1073

You can use IntegerPolyhedron::getIdKindOffset here.

mlir/lib/Analysis/Presburger/PWMAFunction.cpp
15–16

Please make this function static. Also a doc comment explaining what it does would be nice.

17

Please add a string to explain what this assert does.

arjunp marked 5 inline comments as done.Feb 5 2022, 7:28 AM

Thanks for the review!

mlir/include/mlir/Analysis/Presburger/PWMAFunction.h
46

The reason I made the inheritance protected is because I don't want this class to inherit the public interface of IntegerPolyhedron, since many of its functions probably don't make sense here.

This class already works basically in the way that you're suggesting. I didn't override removeIdRange earlier though, which I have done now.

173–177

They are already implicitly inline right?

arjunp updated this revision to Diff 406194.Feb 5 2022, 10:27 AM
arjunp marked an inline comment as done.

Address Kunwar's comments

Groverkss added inline comments.Feb 6 2022, 6:03 AM
mlir/include/mlir/Analysis/Presburger/PWMAFunction.h
46

Right. I now understand what you want to do better.

59–71

You can replace all of these except getNumInputs and getNumOutputs by:

using IntegerPolyhedron::getNumIds;
using IntegerPolyhedron::getNumSymbolIds;
.
.
arjunp updated this revision to Diff 406256.EditedFeb 6 2022, 7:35 AM

Incorporate Kunwar's suggestion and fix the build

arjunp marked 3 inline comments as done.Feb 6 2022, 7:36 AM
arjunp added inline comments.
mlir/include/mlir/Analysis/Presburger/PWMAFunction.h
59–71

Good point! Done.

Groverkss added inline comments.Feb 6 2022, 1:22 PM
mlir/lib/Analysis/Presburger/PWMAFunction.cpp
112

The usage of the object this and the word "this" is a bit confusing. Putting backquotes should help. Please fix in other places also in this function implementation.

157–159

Please put a string explaining what these asserts do with the assert.

mlir/unittests/Analysis/Presburger/PWMAFunctionTest.cpp
2–14

I think this header needs to be changed.

63

This comment seems to be unrelated here and seems to be unfinished.

67

This seems incomplete to me.

166

I think this should be at top of file.

arjunp updated this revision to Diff 406291.Feb 6 2022, 2:40 PM
arjunp marked 7 inline comments as done.

Address Kunwar's comments

Groverkss added inline comments.Feb 7 2022, 6:41 AM
mlir/include/mlir/Analysis/Presburger/PWMAFunction.h
157

Is this implemented? Also, a doc comment would be good.

158

Doc comment, please.

160

Same for this. Is this implemented? Also, a doc comment would be good.

162–163

Doc comment please.

mlir/lib/Analysis/Presburger/PWMAFunction.cpp
156–159

Can you add an assert which just checks if the newly added domain intersects (non-empty intersection) with the existing domain? While the check is expensive, it should be fine inside an assert.

mlir/unittests/Analysis/Presburger/PWMAFunctionTest.cpp
9–13

I think this doc comment is for PresburgerSet. Please change it.

arjunp updated this revision to Diff 406455.Feb 7 2022, 7:13 AM
arjunp marked 5 inline comments as done.

Address Kunwar's comments

arjunp marked an inline comment as done.Feb 7 2022, 7:13 AM
arjunp updated this revision to Diff 406460.Feb 7 2022, 7:25 AM

Fix tests

Groverkss accepted this revision.Feb 7 2022, 10:46 AM

LGTM. Thank you for this patch!

mlir/lib/Analysis/Presburger/PWMAFunction.cpp
128–130

I think you should add a comment here that you are adding constraints such that the output of both functions should be equal.

This revision is now accepted and ready to land.Feb 7 2022, 10:46 AM
arjunp updated this revision to Diff 406530.Feb 7 2022, 11:02 AM

Address kunwar's comment

This revision was landed with ongoing or failed builds.Feb 7 2022, 11:14 AM
This revision was automatically updated to reflect the committed changes.

@Groverkss thanks for the review!