Page MenuHomePhabricator

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

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



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

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)


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


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


In general, please avoid using auto.


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

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

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


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


I think you mean "the division variable"


nit: seems a bit odd to use a reference here


Should it be this?

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

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


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!


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


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

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


expr + divisor - 1, not minus?


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

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.


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


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

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.


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


nit: gurantees -> guarantees


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


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?


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

bondhugula added inline comments.Jul 29 2021, 8:12 PM

Use SmallVector to avoid heap allocation.

Moved the bugfix to a separate patch:

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.


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.


indices may be confusing here. Consider rephrasing

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



Please rephrase the last two lines for clarity.


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


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?


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?


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


Assertion message please.


SmallVector here to avoid a heap allocation.


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


This should be marked static?

arjunp added inline comments.Thu, Sep 2, 8:23 AM

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!


It's fine as is then.