This is an archive of the discontinued LLVM Phabricator instance.

[MLIR] Add stage to side effect
ClosedPublic

Authored by cxy-1993 on Jul 24 2023, 1:03 AM.

Details

Summary
[MLIR] Add stage and effectOnFullRegion to side effect

This patch add stage and effectOnFullRegion to side effect for optimization pass
to obtain more accurate information.
Stage uses numbering to track the side effects's stage of occurrence.
EffectOnFullRegion indicates if effect act on every single value of resource.

RFC disscussion: https://discourse.llvm.org/t/rfc-add-effect-index-in-memroy-effect/72235
Differential Revision: https://reviews.llvm.org/D156087

Diff Detail

Event Timeline

cxy-1993 created this revision.Jul 24 2023, 1:03 AM
cxy-1993 requested review of this revision.Jul 24 2023, 1:03 AM
cxy-1993 updated this revision to Diff 545360.Jul 29 2023, 4:14 AM

Update patch fixes coding style

There is likely some documentation to update.

Also I'm not sure that "index" is expressive enough to carry the intent here. The closest I can relate here is pipeline stages in VLIW for example, so maybe the word "stage" should appear in the API?

mlir/include/mlir/Dialect/MemRef/IR/MemRefOps.td
284

We're losing the "DefaultResource" here, how does the "*At" compose with various resources?

mlir/include/mlir/Interfaces/SideEffectInterfaceBase.td
181

Why a string and not an int?

mlir/include/mlir/Interfaces/SideEffectInterfaces.h
218

Where is the notion of "index" defined?

cxy-1993 updated this revision to Diff 545389.Jul 29 2023, 5:40 PM

Updated the code according to the review comments

There is likely some documentation to update.

Also I'm not sure that "index" is expressive enough to carry the intent here. The closest I can relate here is pipeline stages in VLIW for example, so maybe the word "stage" should appear in the API?

Thank you for your insightful comments. Indeed, the index is not accurate in this scenario. I have made the necessary changes to the patch based on your feedback. Please review it again.

cxy-1993 updated this revision to Diff 545391.Jul 29 2023, 5:54 PM

Rename SideEffectOrderAttr -> SideEffectStageAttr

Could you please help me review this piece of code again @mehdi_amini . Also, I am unable to trigger the tests for this commit again. I found online that it's currently only allowed for maintainers to trigger the tests. Could you please help me trigger the tests? Thank you very much for your assistance.

cxy-1993 updated this revision to Diff 545881.Jul 31 2023, 5:38 PM

Update test

I still think documentation is missing, I don't see a definition of "Stage" yet?

mlir/include/mlir/Interfaces/SideEffectInterfaces.h
225

It goes with my comment below, but attributes are suboptimal here. If stages is important why not add an Optional<int> stage as member for this class?

mlir/tools/mlir-tblgen/OpDefinitionsGen.cpp
3222

Using attributes does not seem optimal to me: it's far from free and we shouldn't put these creation here.

I still think documentation is missing, I don't see a definition of "Stage" yet?

When I first implemented it, I added a member variable in this class, but during the discussion with Alex Zinenko, he thought using properties would be more appropriate. What do you think about this issue? Looking forward to your reply.

I

Relate disscussion: https://discourse.llvm.org/t/rfc-add-effect-index-in-memroy-effect/72235/4

cxy-1993 updated this revision to Diff 545900.Jul 31 2023, 7:19 PM

Updated the code according to the latest review comments

I agree with your suggestion of making 'stage' as a member variable in the side effect class. I have already updated the code and added the necessary documentation based on your advice. I kindly request you to review it once again. Thank you so much for your valuable comments! @mehdi_amini

Seems better with the int :)

We should still provide more doc, and an example in particular.

Also update the title and the description to reflect the current version, and add a link to the RFC in the description please.

Finally, something that makes all this still not totally complete for safely do the kind of things you described in the RFC is the notion of May/Must associated with the effect, as well as the "partial/full region" aspect of the effect.

mlir/include/mlir/Interfaces/SideEffectInterfaceBase.td
180

Nit: this isn't a sentence?

mlir/include/mlir/Interfaces/SideEffectInterfaces.td
85

Seems like the stage isn't optional here: that is, it is implicitly 0 which I can imagine being different from "undefined".

It may be OK, but it can also be surprising mixing implicit/explicit effects.

cxy-1993 retitled this revision from [MLIR] Add index to side effect to [MLIR] Add stage to side effect.Jul 31 2023, 10:26 PM
cxy-1993 edited the summary of this revision. (Show Details)
cxy-1993 updated this revision to Diff 545950.Aug 1 2023, 1:07 AM

Add effectOnFullRegion to side effect and update docs according to commentsx

cxy-1993 edited the summary of this revision. (Show Details)Aug 1 2023, 1:08 AM
cxy-1993 updated this revision to Diff 545955.Aug 1 2023, 1:15 AM
cxy-1993 edited the summary of this revision. (Show Details)

Update style

mehdi_amini added inline comments.Aug 1 2023, 1:29 AM
mlir/docs/Rationale/SideEffectsAndSpeculation.md
174

Thanks for providing a good doc for the "effectOnFullRegion", what about stage? Seems like stages aren't really needed in any of these examples?

mlir/include/mlir/Dialect/GPU/IR/GPUOps.td
1303

I'm not sure how to interpret the stages here: do we guarantee that all of the read happen before the write?
What about a loop that copy one element at a time?

mlir/include/mlir/Interfaces/SideEffectInterfaces.td
38

Do we have enums in TableGen? (I don't remember).

I rather read "Full" and "Partial" than true/false if possible.

Thanks for your advice.
The "partial/full region" aspect of the effect is also an important feature in side effect, i have already added them to the member variable of EffectInstance and they can be specified via the 'td' parameter.
Regarding May/Must associated with the effect, I believe you are referring to the relationship between memrefs. If that's the case, we will leave this issue to the pass to invoke alias analysis. If it's not, please let me know.

Regarding May/Must associated with the effect, I believe you are referring to the relationship between memrefs. If that's the case, we will leave this issue to the pass to invoke alias analysis. If it's not, please let me know.

No I wasn't referring to alias analysis (where "May alias"/"Must alias" is important) but to the read/write effects: how do we model an op that may write the full resource, or may not?
We can say that conservatively we say "write full" when it may do so, but then you can't use this information for kill the liveness of the entire resource.

Regarding May/Must associated with the effect, I believe you are referring to the relationship between memrefs. If that's the case, we will leave this issue to the pass to invoke alias analysis. If it's not, please let me know.

No I wasn't referring to alias analysis (where "May alias"/"Must alias" is important) but to the read/write effects: how do we model an op that may write the full resource, or may not?
We can say that conservatively we say "write full" when it may do so, but then you can't use this information for kill the liveness of the entire resource.

I believe that when we say “write full” to a particular resource, this write is certain to occur. Therefore, any writes to this resource before that point can be killed by this operation. If the write is only possible, and we shouldn't explicitly mark it as writing all resources, do you think this approach is feasible?

Sorry, I don't know how to reply inline comment...
The copy like example read source on stage 0 and write target on stage 1. By using stages, we indicate the sequence in which these two side effects occur. Is it enough for "stage" or we need to provide more exmaple?.

cxy-1993 updated this revision to Diff 545982.Aug 1 2023, 2:45 AM

Do not set side effects stage for operations where we cannot determine the order of side effects on all values.

Thank you for your guidance. I have update the patch according to your comment. @mehdi_amini

mlir/docs/Rationale/SideEffectsAndSpeculation.md
174

I rewrote the first example and used a virtual SIMD operation to illustrate the effect of stages.

mlir/include/mlir/Dialect/GPU/IR/GPUOps.td
1303

NICE CATCH! Stage modeling indeed not be suitable for operations that can lower to loops, as its primary application lies in SIMD-like operations where hardware guarantees the order of reads and writes. I have updated existing dialect's side effects and the descriptions in the documentation.

mlir/include/mlir/Dialect/MemRef/IR/MemRefOps.td
284

DONE

mlir/include/mlir/Interfaces/SideEffectInterfaceBase.td
180

I refactored this comment for better clarity.

181

I have changed it to int.

mlir/include/mlir/Interfaces/SideEffectInterfaces.h
218

Changed to "stage" now.

225

DONE

mlir/include/mlir/Interfaces/SideEffectInterfaces.td
38

I can not found any enum in TableGen except EnumAttr...

85

I have replace optional<int> member variable with default value null with int member variable with default value 0.

mlir/tools/mlir-tblgen/OpDefinitionsGen.cpp
3222

DONE

I believe that when we say “write full” to a particular resource, this write is certain to occur. Therefore, any writes to this resource before that point can be killed by this operation. If the write is only possible, and we shouldn't explicitly mark it as writing all resources, do you think this approach is feasible?

It might be ok, I am not sure it is conservative in every situation? Assuming it is, it should likely be the default, right now your MemAlloc default to full.

mlir/include/mlir/Interfaces/SideEffectInterfaces.td
38

I think it should look like this in TableGen:

class EffectRange <bits<1> val> {
  bits<1> Value = val;
}

def FullEffect : EffectStage<1>;
def PartialEffect : EffectStage<0>;

class SideEffect<EffectOpInterfaceBase interface, string effectName,
                 Resource resourceReference, int effectStage, EffectRange range> {
   ...

  // Does this side effect act on every single value of resource.
  EffectRange effectOnFullRegion = range;
}

But it may be possible to write also here:

// Does this side effect act on every single value of resource.
bit effectOnFullRegion = range.Value;
cxy-1993 added a comment.EditedAug 1 2023, 3:28 PM

I believe that when we say “write full” to a particular resource, this write is certain to occur. Therefore, any writes to this resource before that point can be killed by this operation. If the write is only possible, and we shouldn't explicitly mark it as writing all resources, do you think this approach is feasible?

It might be ok, I am not sure it is conservative in every situation? Assuming it is, it should likely be the default, right now your MemAlloc default to full.

I agree that treating side effects as default on partially memrefs is a cautious approach. Currently, almost all visible ops have side effects on the entire memref, so can we consider this common but less safe behavior as the default and require the definers of specific ops to understand the scope of side effects and make modifications accordingly?Otherwise, I would have to modify almost all existing side effects to become FullEffect.

I see where you're coming from, but I'm much more on the side of avoiding footgun in our APIs: especially this kind, where it won't be caught until there is a subtle miscompute which requires long hours of debug.

cxy-1993 updated this revision to Diff 546267.Aug 1 2023, 4:48 PM

Update patch according to review comments

I see where you're coming from, but I'm much more on the side of avoiding footgun in our APIs: especially this kind, where it won't be caught until there is a subtle miscompute which requires long hours of debug.

I have already changed the default range of side effects to "partial" and made corresponding modifications to all feasible ops. Thank you for your valuable comments, please review it again.

mlir/include/mlir/Interfaces/SideEffectInterfaces.td
38

DONE

I have already modified the default range of side effects to "partial" and made necessary adjustments to various ops based on your feedback. I am reaching out to kindly request another code review for the changes I have made. @mehdi_amini

Mogball accepted this revision.Aug 2 2023, 12:03 PM

+1. This patch makes sense to me. Having this level of granularity is useful.

Do any of the upstream transformations need to be taught about this?

This revision is now accepted and ready to land.Aug 2 2023, 12:03 PM

Please wait for @mehdi_amini and others to chime in first

+1. This patch makes sense to me. Having this level of granularity is useful.

Do any of the upstream transformations need to be taught about this?

Thank you for the recognition. I believe that currently, the existing passes in MLIR don't have an immediate use for this feature. The motivation behind this feature is to improve the modeling of operation read and write order, as well as their ranges, for certain SIMD backends. With the introduction of this feature, I am confident that more analysis and optimizations will gradually be contributed to the MLIR community.

cxy-1993 updated this revision to Diff 546657.Aug 2 2023, 5:36 PM

Update docs

Ping @rriddle Could you please help me review this piece of code? Thank you! :)

ping @mehdi_amini @rriddle Could you please take some time to help me with the review and merging of this patch? Thank you. :)

@rriddle @mehdi_amini Could you kindly spare a moment to review the updated code at your convenience? Thank you for your time and consideration.

Mogball accepted this revision.Aug 10 2023, 1:17 AM

That seems fine to me, but I wanted to hear if @rriddle does not have any opposition here!

@rriddle Please help me review this piece of code. Thank you for your time. :)

@rriddle ping :) Could you please spare some time to review this patch, thank you!

@cxy-1993 please just go ahead and land this. River is indisposed wrt MLIR reviews at the moment

DIdn't the forum RFC conclude on using the parameters attribute for this instead of adding new fields?

cxy-1993 added a comment.EditedSep 19 2023, 5:06 AM

DIdn't the forum RFC conclude on using the parameters attribute for this instead of adding new fields?

Sorry for not inform you and updating the RFC in a timely manner. During our discussions with amini, we concluded that it would be more appropriate to use a new field to represent the stages at which side effects occur, rather than directly using the attribute. As a result, I have replaced the usage of the parameter with two new fields: "stage" and "effectOnFullRegion." You can refer to the comments above for the discussion details.

Personally, I believe that adding a new field instead of using parameters would make this more straightforward and easier to comprehend.

ftynse requested changes to this revision.Sep 19 2023, 5:37 AM

Then I'll block this until I had time to go through the discussion that should have happened on the RFC.

This revision now requires changes to proceed.Sep 19 2023, 5:37 AM
ftynse resigned from this revision.Sep 21 2023, 1:11 AM
This revision is now accepted and ready to land.Sep 21 2023, 1:11 AM
cxy-1993 updated this revision to Diff 557175.Sep 21 2023, 6:17 AM

rebase main

This patch has already been rebased onto the main branch and passed precheckin. I don't have write access to the LLVM repo. Could you please help me to push this code into the master, Thanks. @Mogball

cxy-1993 updated this revision to Diff 557501.Sep 29 2023, 4:47 PM

rebase main

mehdi_amini accepted this revision.Sep 29 2023, 5:09 PM

ftynse acknowledged my rationale with a "like" on Discourse, so I suspect this is good to go?

ftynse acknowledged my rationale with a "like" on Discourse, so I suspect this is good to go?

Thank you for your recognition.I have already retested this code locally and i don't have write access to the LLVM repository. Could you please help me push this patch to the repository? @mehdi_amini

This revision was automatically updated to reflect the committed changes.