Page MenuHomePhabricator

[MLIR] FlatAffineConstraints : Store explicit division representation for local identifiers
AbandonedPublic

Authored by Groverkss on Jul 16 2021, 5:45 AM.

Details

Summary

This patch improves support for local identifiers by explicitly storing representations of their values as divisions of an affine expression by a constant denominator, when such a representation is known.

Exact re-computation of division representations from inequalities is expensive. Many operations on PresburgerSets when local identifiers are involved require these representations. Storing these representations allows for faster computation in PresburgerSet operations where local identifiers are involved.

Diff Detail

Event Timeline

Groverkss created this revision.Jul 16 2021, 5:45 AM
Groverkss requested review of this revision.Jul 16 2021, 5:45 AM
Groverkss edited the summary of this revision. (Show Details)

Thanks for the patch!

I did not point it out in each instance, but in general, please use full sentences and punctuation for all comments.

mlir/include/mlir/Analysis/AffineStructures.h
83

You can initialize this directly in the member initializer list above right?

213–217

Can we add a getDivNumerator?

308

Division representation? Also, please put the full stop, here and everywhere.

322

nit: unnecessary extra line?

323

nit: the floordiv

327

Maybe say that the FAC is considered to be in an inconsistent state?

679

nit: corresponding to

mlir/lib/Analysis/AffineStructures.cpp
158

Initialize divDenom?

227

Please use pre-increment.

233

Please use pre-increment.

234

If you add getDivNumerator, you can replace this loop with getDivNumerator(r) == other.getDivNumerator(r).

2199

This is not needed right? This is not set anywhere and should already be zero? (You can probably still add a comment saying that it's zero)

2202

Maybe mention, with a zero inserted for the new local

2248

nit: swap division representationS OF both?

2249

nit: unsigned?

2261

If one is a local and the other isn't, you should clear the representation for the local right?

2635

I think it might be more consistent to skip the + and just put a space

mlir/unittests/Analysis/AffineStructuresTest.cpp
601

Here and below, expect that the optional actually has a value as well?

604

Also check (0, 2)?

604

You can also check the inequalities that were added.

606

Can you add at position 0 instead? Will the other one get moved appropriately?

612

Shouldn't it be -1?

617

Can you add a division with non-zero constant term and check it?

639

Try removing the first division and check if the other one moves?

640

You can also use 1u

640

Also check for consistency?

arjunp added inline comments.Jul 16 2021, 7:54 AM
mlir/unittests/Analysis/AffineStructuresTest.cpp
612

It should be fac2 I think

Groverkss marked 24 inline comments as done.Jul 16 2021, 12:04 PM
Groverkss added inline comments.
mlir/lib/Analysis/AffineStructures.cpp
158

Initializing divDenom does not make sense according to me. IntegerSet has no concept of local variables so divDenom is always of size 0. divisions need to be initialized due to column size.

234

I'm not sure about this. getDivNumerator would return an ArrayRef<int64_t>. Does using == work on ArrayRefs?

mlir/unittests/Analysis/AffineStructuresTest.cpp
640

The consistency check is a private method IIUC. Not sure how to use it here.

  • Addressed arjunp's comments
  • Fixed punctuation in comments
Groverkss updated this revision to Diff 359447.Jul 16 2021, 2:16 PM

Restored accidently deleted previous commits

  • Fixed failing tests
Groverkss updated this revision to Diff 359542.Jul 17 2021, 1:04 AM
  • Fixed formatting issues
bondhugula requested changes to this revision.Jul 17 2021, 4:13 AM

Exact re-computation of division representations from inequalities is expensive. Many operations on PresburgerSets when local identifiers are involved require these representations.
Storing these representations allows for faster computation in PresburgerSet operations where local identifiers are involved.

This approach is storing redundant information in the system for faster detection/computation later. One can't be sure of updating any inequality without invalidating such information. There are some non-trivial tradeoffs to discuss here. This is a major change and non-trivial enough to discuss thoroughly on discourse first? Could you please post a description of this - sort of an expanded commit summary with additional detail on tradeoffs?

mlir/include/mlir/Analysis/AffineStructures.h
178

This doc comment doesn't parse well - rephrase?

185

Missing assertion on valid pos range.

187

Likewise.

214

Doc comment here along the same lines as as getDivDenonm....

This revision now requires changes to proceed.Jul 17 2021, 4:13 AM
Groverkss abandoned this revision.Aug 5 2021, 12:29 AM