This is an archive of the discontinued LLVM Phabricator instance.

[MLIR] Generalize Affine dependence analysis using Affine Relations
ClosedPublic

Authored by Groverkss on Sep 27 2021, 9:20 AM.

Details

Summary

This patch removes code very specific to affine dependence analysis and
refactors it as a FlatAfffineRelation.

A FlatAffineRelation represents a set of ordered pairs (domain -> range) where
"domain" and "range" are tuples of identifiers. These relations are used to
represent an "access relation" for memory access on a memref. An access
relation maps elements of an iteration domain to the element(s) of an array
domain accessed by that iteration of the associated statement through some
array reference. The dependence relation representing the dependence
constraints between two memory accesses can be built by composing the access
relation of the destination access by the inverse of the access relation of
source access.

This patch does not change the functionality of the existing dependence
analysis in checkMemrefAccessDependence, but refactors it to use
FlatAffineRelations to deduplicate code and enable code reuse for future
development of features like scheduling, value-based dependence analysis, etc.

Diff Detail

Event Timeline

Groverkss created this revision.Sep 27 2021, 9:20 AM
Groverkss requested review of this revision.Sep 27 2021, 9:20 AM
Groverkss retitled this revision from Generalize Affine dependence analysis using Affine Relations to [MLIR] Generalize Affine dependence analysis using Affine Relations.Sep 27 2021, 9:22 AM

This looks great to me in general. Some initial comments below.

in checkMemrefAccessDependence, but refactors it to be reusable.

You may want to say here as to in which context we'd want this to be reusable. It's fine (and in fact better here) if the thing that reuses it comes later but it'd be good to mention that.

mlir/include/mlir/Analysis/AffineAnalysis.h
30

Sorted order.

109

You may want to add a phrase here on when it could fail.

mlir/include/mlir/Analysis/AffineStructures.h
907

Spell fix: separation

942–943

Doc comments although looks obvious now.

mlir/lib/Analysis/AffineStructures.cpp
1856

dimStart will always be non-negative here (it's unsigned).

bondhugula requested changes to this revision.Sep 27 2021, 10:25 AM
bondhugula added inline comments.
mlir/lib/Analysis/AffineStructures.cpp
3664–3665

Broken sentence here.

mlir/test/Transforms/loop-fusion-2.mlir
252–254 ↗(On Diff #375298)

What's happening here? This isn't the same slice.

This revision now requires changes to proceed.Sep 27 2021, 10:25 AM
Groverkss marked 6 inline comments as done.
  • Addressed comments

Addressed @bondhugula's comments.

mlir/test/Transforms/loop-fusion-2.mlir
252–254 ↗(On Diff #375298)

It looks like the refactoring changes the order of inequalities which leads to a change in the loop order. I will try to find out more about why this is happening and try to fix it.

bondhugula added inline comments.Sep 28 2021, 5:09 AM
mlir/test/Transforms/loop-fusion-2.mlir
252–254 ↗(On Diff #375298)

It's not just the loop order: note the trip count of the innermost loop - the slice is larger and sub-optimal (has redundant iterations). This revision is changing functionality contrary to the commit summary.

Groverkss updated this revision to Diff 375596.Sep 28 2021, 8:58 AM
  • Keep inequality order same as before
Groverkss marked 2 inline comments as done.Sep 28 2021, 12:44 PM

Fixed tests.

Groverkss edited the summary of this revision. (Show Details)Sep 30 2021, 6:10 AM
bondhugula accepted this revision.Oct 5 2021, 10:33 AM

This is looking good to me. Mostly minor comments. Also, the last line of the commit summary is a big vague. Can you spell it out clearly?

mlir/include/mlir/Analysis/AffineStructures.h
970

Separate lines and doc comments for these.

1050–1051

No const on AffineMap - it's immutable by design.

mlir/lib/Analysis/AffineAnalysis.cpp
413

Nit: ret or rel?

425

/*arg_name=*/... syntax wherever you are sending constant values.

432–433

LLVM/MLIR style - use braces for then when using for else.

596

locations?

597–600

Nice.

mlir/lib/Analysis/AffineStructures.cpp
2094

Remove debug code.

This revision is now accepted and ready to land.Oct 5 2021, 10:33 AM
Groverkss updated this revision to Diff 379622.Oct 14 2021, 1:17 AM
Groverkss marked 8 inline comments as done.

Address comments and fix a minor bug.

Groverkss updated this revision to Diff 379624.Oct 14 2021, 1:25 AM
Groverkss edited the summary of this revision. (Show Details)

No change. Just update using arcanist.

Groverkss edited the summary of this revision. (Show Details)Oct 14 2021, 2:25 AM
Groverkss edited the summary of this revision. (Show Details)
Groverkss edited the summary of this revision. (Show Details)Oct 14 2021, 4:34 AM