This is an archive of the discontinued LLVM Phabricator instance.

[mlir][affine] Support affine.parallel in the index set analysis
ClosedPublic

Authored by Lewuathe on Oct 16 2022, 11:29 PM.

Details

Summary

Support affine.parallel in the index set analysis. It allows us to do dependence analysis containing affine.parallel in addition to affine.for and affine.if. This change only supports the constant lower/upper bound in affine.parallel. Other complicated affine map bounds will be supported in further commits.

See https://github.com/llvm/llvm-project/issues/57327

Diff Detail

Event Timeline

Lewuathe created this revision.Oct 16 2022, 11:29 PM
Lewuathe requested review of this revision.Oct 16 2022, 11:29 PM
Lewuathe edited the summary of this revision. (Show Details)Oct 16 2022, 11:30 PM
Lewuathe edited the summary of this revision. (Show Details)Oct 16 2022, 11:33 PM

Some general code-style comments to start the review.

mlir/lib/Dialect/Affine/Analysis/AffineAnalysis.cpp
246–248

Please update this message.

254–255

Any reason for not using else if?

271–273

nit: remove braces here.

mlir/lib/Dialect/Affine/Analysis/AffineStructures.cpp
654

Is there a reason for using auto here and not the actual type? I think generally the actual type is prefered.

655–660

nit: remove braces here.

mlir/lib/Dialect/Affine/IR/AffineOps.cpp
2330–2331

nit: there is no need for a newline before the if.

2332–2334

nit: remove braces.

Groverkss added inline comments.Oct 17 2022, 3:33 AM
mlir/lib/Dialect/Affine/Analysis/AffineAnalysis.cpp
650–652

I don't think this ordering is valid for affine.parallel since it does not define any lexicographic order. For example:

affine.parallel (%i) = (0) to (10) {
  %1 = affine.load %m[9 - %i]
  affine.store %1, [%i]
}

There can be a dependence from %i = 9 to %i = 0, since no lexicographic order is defined.

Lewuathe updated this revision to Diff 468412.Oct 17 2022, 9:48 PM

Apply format

Lewuathe added inline comments.Oct 17 2022, 9:51 PM
mlir/lib/Dialect/Affine/Analysis/AffineAnalysis.cpp
650–652

I see. We may need to skip this constraint in the case of affine.parallel in the middle.

Lewuathe updated this revision to Diff 468781.Oct 18 2022, 9:57 PM

Fix format issues

Lewuathe updated this revision to Diff 471416.Oct 28 2022, 12:04 AM

Add test for checking lexicographical order

Lewuathe added inline comments.Oct 28 2022, 12:07 AM
mlir/lib/Dialect/Affine/Analysis/AffineAnalysis.cpp
650–652

I think there should be a dependency from the store to write (e.g. store %m[0] (%i=0) to load %m[0] (%i = 9). But this case is not properly checked.

func.func @no_lexicographic_order() {
  %m = memref.alloc() : memref<10xf32>
  %c7 = arith.constant 7.0 : f32
  affine.parallel (%i) = (0) to (10) {
    %1 = affine.load %m[9 - %i] : memref<10xf32>
    // expected-remark@above {{dependence from 0 to 0 at depth 1 = false}}
    // expected-remark@above {{dependence from 0 to 1 at depth 1 = true}}
    affine.store %1, %m[%i] : memref<10xf32>
    // expected-remark@above {{dependence from 1 to 0 at depth 1 = false}}
    // expected-remark@above {{dependence from 1 to 1 at depth 1 = false}}
  }
  return
}

Thanks for contributing this support. This was long overdue. While this is fine, I feel just directly supporting the general (arbitrary bound case) is better -- since the affine.for support already supports that, and we may have to again throw away most of this code when handling the general bound case. Just supporting the constant bound case to start with isn't an incremental step.

mlir/lib/Dialect/Affine/Analysis/AffineAnalysis.cpp
253

Use comments on top (LLVM/MLIR style), not trailing.

259–260

May be good to fix the comment while on this:
associated -> associating

mlir/lib/Dialect/Affine/Analysis/AffineStructures.cpp
650

Improve the assertion message here: variable expected for the IV value?

655–658

Negate condition and unguard addBound.

661–664

Likewise.

@bondhugula Thank you for the comments. Sorry for taking the time to work on this. I was struggling with how to treat the ordering constraint in the affine.parallel. (Just removing the ordering constraint does not work as expected).

So for now, should we discard this patch completely and restart working on supporting general case?

@bondhugula Thank you for the comments. Sorry for taking the time to work on this. I was struggling with how to treat the ordering constraint in the affine.parallel. (Just removing the ordering constraint does not work as expected).

So for now, should we discard this patch completely and restart working on supporting general case?

It would be good to support the generic case. Parts of this patch are still useful towards that. I didn't understand the issue related to "ordering constraint". You would order the dimensions in the order in which they appear in the affine.parallel.

@bondhugula Thank you for the comments. Sorry for taking the time to work on this. I was struggling with how to treat the ordering constraint in the affine.parallel. (Just removing the ordering constraint does not work as expected).

So for now, should we discard this patch completely and restart working on supporting general case?

It would be good to support the generic case. Parts of this patch are still useful towards that. I didn't understand the issue related to "ordering constraint". You would order the dimensions in the order in which they appear in the affine.parallel.

I think the "ordering constraint" refers to the dependence analysis, since affine.parallel does not define a schedule for iterations, we cannot impose ordering constraints based on lexicographic order as it currently does for every induction variable.

I think the patch is good other than the dependence analysis part since that needs more discussion. For example, checkMemRefDependence takes a loop depth. Currently, loop depth implies the induction variable at that position. What would that mean after introducing affine.paralllel to the dependence analysis? Would it mean after affine.parallel is allowed? Would it mean the loop or the induction variable? I think some things need to be discussed more before we support it.

I would be happy to review the patch if you send the generic case without dependence analysis.

@bondhugula @Groverkss Thanks again. I'd like to work on the general cases for supporting affine.parallel in the getIndexSet.

But I have one question about the test for that case. Where should we write the test if we do not support the dependence analysis for affine.parallel for the time being? Is there any existing test checking the getIndexSet functionality?

@bondhugula @Groverkss Thanks again. I'd like to work on the general cases for supporting affine.parallel in the getIndexSet.

But I have one question about the test for that case. Where should we write the test if we do not support the dependence analysis for affine.parallel for the time being? Is there any existing test checking the getIndexSet functionality?

If we don't support it temporarily, you can always return failure() from getIndexSet which will cleanly fail the dependence analysis check. There is a status for "dependence analysis failed" that gets returned already.

@bondhugula Okay, I'll return failure() to unsupport the dependence analysis with affine.parallel for the time being. Thanks!

Lewuathe updated this revision to Diff 475343.Nov 14 2022, 10:36 PM

Support non-constant constraints.

Lewuathe updated this revision to Diff 475346.Nov 14 2022, 10:48 PM

Post review follow-up.

Lewuathe updated this revision to Diff 475650.Nov 15 2022, 5:54 PM

Apply format.

Groverkss added inline comments.Nov 16 2022, 2:56 AM
mlir/include/mlir/Dialect/Affine/Analysis/AffineStructures.h
148

Is this stil lvalid?

149

Is it required that the variable exists in the constraint system? The documentation does not make this clear.

mlir/lib/Dialect/Affine/Analysis/AffineAnalysis.cpp
616

This statement is misleading. Dependence analysis isn't implemented for affine.parallel. This statement claims it's not possible. Please add a TODO instead explaining why we did not implement it right now, which is affine.parallel does not specify an ordering.

mlir/lib/Dialect/Affine/Analysis/AffineStructures.cpp
654

Is there any reason we specialize for the constant case? If there is, could you write a comment explaining why we specialize? It is not obvious to me.

Lewuathe added inline comments.Nov 16 2022, 9:09 PM
mlir/lib/Dialect/Affine/Analysis/AffineStructures.cpp
654

The addBound method depends on whether the bound is constant. In the case of non-constant, we need to give operands explicitly. We use this pattern for affine.for and it's also the case for affine.parallel too.

Lewuathe updated this revision to Diff 476000.Nov 16 2022, 9:14 PM

Refine TODO comments.

The added code isn't exercised by any test case, right? Is this ready for review?

mlir/include/mlir/Dialect/Affine/IR/AffineOps.h
459

What can operations contain? operations -> affineOps?

mlir/lib/Dialect/Affine/Analysis/AffineAnalysis.cpp
270

Can use auto here since the type is on the RHS.

mlir/lib/Dialect/Affine/Analysis/AffineStructures.cpp
646

The debug message isn't helpful here. Suggest adding more text to it.

mlir/lib/Dialect/Affine/IR/AffineOps.cpp
259–264

This is nothing but checking getParentOpOfType<AffineParallelOp>() is null. We don't need to add a public method!

2325

Pass output argument by reference (MLIR convention).

2329

Use auto here.

2331

Use braces here per new LLVM/MLIR style.

Thank you for taking a look again.

I'll try to add a test case covering getIndexSet somehow. But there seems to be no dedicated test case for getIndexSet. Test cases for dependent analysis only check the logic of getIndexSet. Do you know whether there is already any test code covering getIndexSet usage?

@bondhugula @Groverkss Thanks again. I'd like to work on the general cases for supporting affine.parallel in the getIndexSet.

But I have one question about the test for that case. Where should we write the test if we do not support the dependence analysis for affine.parallel for the time being? Is there any existing test checking the getIndexSet functionality?

If we don't support it temporarily, you can always return failure() from getIndexSet which will cleanly fail the dependence analysis check. There is a status for "dependence analysis failed" that gets returned already.

Thank you for taking a look again.

I'll try to add a test case covering getIndexSet somehow. But there seems to be no dedicated test case for getIndexSet. Test cases for dependent analysis only check the logic of getIndexSet. Do you know whether there is already any test code covering getIndexSet usage?

I didn't understand - you don't need to add test cases for the utility. Just test dependence analysis in the presence of affine.parallel. This can be done via the affine-scalrep pass or test-memref-dependence-check.

Lewuathe updated this revision to Diff 477855.Nov 24 2022, 9:27 PM

Add test cases and reflect the latest reviews.

Lewuathe added a comment.EditedNov 24 2022, 9:33 PM

@bondhugula

Sorry for the confusion. I just wanted to know how/where to add test cases for the utility functions like this. But I've found a way to test the case including affine.parallel somehow for dependence check and scalrep. I'm so sorry for bothering you many times but could you review this change again when you get a chance?

Can you please resolve the other remaining comments and mark them done before a round of review? For eg. all comments in AffineStructures.cpp many of which are trivial are still pending.

mlir/lib/Dialect/Affine/IR/AffineOps.cpp
2332–2334

Drop trivial braces.

mlir/test/Transforms/memref-dependence-check.mlir
1078–1080 ↗(On Diff #477855)

There seems to be something incorrect here. Both these "expected" checks are pointing to the same line (@above from below is the same as +1 here).

mlir/test/lib/Analysis/TestMemRefDependenceCheck.cpp
90 ↗(On Diff #477855)

Thank you for improving/fixing this.

Lewuathe updated this revision to Diff 478805.Nov 29 2022, 10:26 PM

Validate affine.parallel existence strictly in memref dependence check.

Lewuathe marked 27 inline comments as done.Nov 29 2022, 10:29 PM
Lewuathe added inline comments.
mlir/test/Transforms/memref-dependence-check.mlir
1078–1080 ↗(On Diff #477855)

We should have checked the affine.parallel existence before returning no dependence when there is no AffineWriteOpInterface.

Lewuathe marked an inline comment as done.Nov 29 2022, 10:30 PM
bondhugula accepted this revision.Dec 3 2022, 6:46 AM

This looks great to me - thanks! A comment on some missing test cases below.

mlir/test/Dialect/Affine/scalrep.mlir
796 ↗(On Diff #478805)

Missing test case for non-constant loop bound case and mixed affine.parallel + affine.for case. (For eg., affine.for surrounded by affine.parallel or vice versa) -- either here or in the dependence check test case file.

This revision is now accepted and ready to land.Dec 3 2022, 6:46 AM
Lewuathe updated this revision to Diff 479910.Dec 4 2022, 3:35 AM

Post review follow-up

Lewuathe marked an inline comment as done.Dec 4 2022, 3:36 AM
This revision was landed with ongoing or failed builds.Dec 4 2022, 3:51 AM
This revision was automatically updated to reflect the committed changes.