Page MenuHomePhabricator

[MLIR] FlatAffineConstraints: Refactored computation of explicit representation for identifiers
ClosedPublic

Authored by Groverkss on Jul 23 2021, 7:04 AM.

Details

Summary

This patch refactors the existing implementation of computing an explicit
representation of an identifier as a floordiv in terms of other identifiers and
exposes this computation as a public function.

The computation of this representation is required to support local identifiers
in PresburgerSet subtract, complement and isEqual.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
arjunp added inline comments.Jul 23 2021, 8:16 AM
mlir/lib/Analysis/AffineStructures.cpp
1268

Technically, even if the divisor is one it would work right? (I guess it would just be an equality then. But it still yields a representation for that variable)

1281–1282

nit: if you factor out checking an upper-lower bound pair into a separate function, then all this would look cleaner I feel.

1301

I don't like setting this inside. I would take foundRepr as a const reference and set it in the caller.

1331

In general, please avoid using auto.

1331–1335

The if (auto opt = ... idiom might be more readable:

if (auto res = computeSingleVarRepr(*this, foundRepr, divOffset + i)) {
  repr[i] = res;
  changed = false;
}
1620

I believe it is preferred to drop these braces in LLVM style

1630

The lower bound is just divisor * id >= expr right?

1636–1652

I think you mean "the division variable"

mlir/unittests/Analysis/AffineStructuresTest.cpp
598

nit: seems a bit odd to use a reference here

608–609

Should it be this?

// divisor * id >=  expr     <-- Lower bound for 'id'
// divisor * id <=  expr + divisor - 1                  <-- Upper bound for 'id'
623

Can you pass the numerators and denominators for the floordivs and check that the inequalities returned are actually correct for each floordiv?

626–658

Please add some comments saying what the tests are checking.

arjunp requested changes to this revision.Jul 23 2021, 8:17 AM
This revision now requires changes to proceed.Jul 23 2021, 8:17 AM
Groverkss marked 17 inline comments as done.Jul 25 2021, 3:56 PM

Thank you for the review!

mlir/lib/Analysis/AffineStructures.cpp
1302

I'm not sure why but it does not work. Gives a no-matching constructor error for me.

mlir/unittests/Analysis/AffineStructuresTest.cpp
623

I'm not sure if that is required. If two inequalities are found which satisfy the checks given before this, the variable can be represented as a floordiv. It may not give the same floordiv that was added.

Groverkss updated this revision to Diff 361556.Jul 25 2021, 3:57 PM

Addressed review comments

arjunp added inline comments.Jul 26 2021, 5:52 AM
mlir/lib/Analysis/AffineStructures.cpp
1302

Does llvm::Optional({ubPos, lbPos}) also not work?

mlir/unittests/Analysis/AffineStructuresTest.cpp
608–609

expr + divisor - 1, not minus?

623

It seems a bit funny to copy paste the algorithm's logic again to check if the algorithm is correct.

The tests should trivially verify the answer IMO. I would just use tests where there is only one possible answer and check directly.

arjunp added inline comments.Jul 26 2021, 5:58 AM
mlir/lib/Analysis/AffineStructures.cpp
1623–1624

Shouldn't the constant term just be the constant term of expr?

Groverkss updated this revision to Diff 361635.Jul 26 2021, 6:11 AM

Fixed accidently removed commits

Groverkss updated this revision to Diff 362747.Jul 29 2021, 6:16 AM
Groverkss marked 6 inline comments as done.
  • Improved testing for computing divisions and fixed some bugs

Addressed more review comments.

mlir/lib/Analysis/AffineStructures.cpp
1302

This does not work since llvm::Optional requires template arguments. std::make_pair does work so I have used that instead.

1331

Due to the return type being too big, I have used auto here to improve readability. Let me know if it would still be better to replace it.

Groverkss updated this revision to Diff 362753.Jul 29 2021, 6:22 AM
  • Added punctuation in comments
arjunp added inline comments.Jul 29 2021, 8:29 AM
mlir/lib/Analysis/AffineStructures.cpp
1255

Can you use the 0 <= expr - divisor*id <= divisor - 1 form of the inequalities everywhere? I feel this is much more intuitive since you can immediately see that expr - divisor * id is the remainder and this should be between 0 and divisor - 1.

1623–1624

If you change the representation to divisor - 1 >= expr - divisor*id >= 0 then this will become the lower bound.

1651

nit: gurantees -> guarantees

mlir/unittests/Analysis/AffineStructuresTest.cpp
614–616

nit: I think EXPECT_FALSE(res[i].hasValue()) is more intuitive

624–625

If you're changing the representation you'll have to change it here as well

Can you please separate out the bugfix from the refactoring?

mlir/include/mlir/Analysis/AffineStructures.h
164

These can lead to expensive copies. Could you take an output argument instead?

bondhugula added inline comments.Jul 29 2021, 8:12 PM
mlir/unittests/Analysis/AffineStructuresTest.cpp
704

Use SmallVector to avoid heap allocation.

Moved the bugfix to a separate patch: https://reviews.llvm.org/D107214

Groverkss updated this revision to Diff 363904.Aug 3 2021, 4:20 PM

Rebased to latest main branch

Groverkss updated this revision to Diff 363917.Aug 3 2021, 5:38 PM
Groverkss marked 8 inline comments as done.
  • Addressed comments

Addressed Comments.

mlir/lib/Analysis/AffineStructures.cpp
1623–1624

If I understand correctly, the upper bound is defined based on the value of the division variable and not on the value of the remainder of the division. So it will still be the upper bound. I don't think this needs to be changed.

arjunp added a comment.Aug 4 2021, 7:49 AM

Looks good to me, please resolve the clang-format issues though.

Regarding the use of auto, I'm not sure where the line is drawn generally. It seems okay to me. Let's see what the others think.

Groverkss updated this revision to Diff 364191.Aug 4 2021, 11:09 AM
  • Fixed clang-format issues

@Groverkss, the commit message still references the bugfix that was factored out.

Groverkss edited the summary of this revision. (Show Details)Aug 4 2021, 1:55 PM

Hi @bondhugula, @vinayaka-polymage, I think I've addressed all the comments. Can you please check if there are any more changes to be made?

Hi @bondhugula , @vinayaka-polymage , gentle reminder 🙂 Are there any other changes to be made?

arjunp accepted this revision.Aug 24 2021, 2:08 AM

Seems good to me. Let's also wait to see if @bondhugula or @vinayaka-polymage have any additional comments.

This revision is now accepted and ready to land.Aug 24 2021, 2:08 AM

Hi @arjunp @Groverkss , sorry - I am currently unavailable until the end of the week, and will not be able to review this. I will check this during the weekend if it is still open.

This overall is looking good to me. Some questions and comments for minor improvements I feel.

mlir/include/mlir/Analysis/AffineStructures.h
159

indices may be confusing here. Consider rephrasing

... pairs of inequalities identified by their position indices, ...

?

162

Please rephrase the last two lines for clarity.

163

It's perhaps better to be explicit here: computeLocalRepresentation?

163

Is this name appropriate? It's not computing the local representation but only finding the pairs to use to construct the local representation. Better name?

getLocalReprLbUbPairs?

On this note, do we need to expose this publicly? Shouldn't detectAsFloorDiv be the one to expose and the former is just a local helper?

mlir/lib/Analysis/AffineStructures.cpp
1242

Put foundRepr in backticks. Similarly, at any places in doc comments.

1248

Assertion message please.

1328

SmallVector here to avoid a heap allocation.

1619

Can you use a SmallVector here to prevent a heap allocation?

mlir/unittests/Analysis/AffineStructuresTest.cpp
598

This should be marked static?

arjunp added inline comments.Thu, Sep 2, 8:23 AM
mlir/include/mlir/Analysis/AffineStructures.h
163

PresburgerSet will require access to this function to support divisions in subtract, intersect, and equality checks. We could make this private if we are find with making PresburgerSet a friend class.

Groverkss updated this revision to Diff 370362.EditedThu, Sep 2, 12:27 PM
Groverkss marked 8 inline comments as done.
bondhugula accepted this revision.Mon, Sep 6, 5:52 PM

Looks good - thanks!

mlir/include/mlir/Analysis/AffineStructures.h
163

It's fine as is then.