This is an archive of the discontinued LLVM Phabricator instance.

Introduce a ConditionallySpeculatable op interface
ClosedPublic

Authored by sanjoy on Oct 7 2022, 6:57 PM.

Details

Summary

This patch takes the first step towards a more principled modeling of undefined behavior in MLIR as discussed in the following discourse threads:

  1. https://discourse.llvm.org/t/semantics-modeling-undefined-behavior-and-side-effects/4812
  2. https://discourse.llvm.org/t/rfc-mark-tensor-dim-and-memref-dim-as-side-effecting/65729

This patch in particular does the following:

  1. Introduces a ConditionallySpeculatable OpInterface that dynamically determines whether an Operation can be speculated.
  2. Re-defines NoSideEffect to allow undefined behavior, making it necessary but not sufficient for speculation. Also renames it to NoMemoryEffect.
  3. Makes LICM respect the above semantics.
  4. Changes all ops tagged with NoSideEffect today to additionally implement ConditionallySpeculatable and mark themselves as always speculatable. This combined trait is named Pure. This makes this change NFC.

For out of tree dialects:

  1. Replace NoSideEffect with Pure if the operation does not have any memory effects, undefined behavior or infinite loops.
  2. Replace NoSideEffect with NoSideEffect otherwise.

The next steps in this process are (I'm proposing to do these in upcoming patches):

  1. Update operations like tensor.dim, memref.dim, scf.for, affine.for to implement a correct hook for ConditionallySpeculatable. I'm also happy to update ops in other dialects if the respective dialect owners would like to and can give me some pointers.
  2. Update other passes that speculate operations to consult ConditionallySpeculatable in addition to NoMemoryEffect. I could not find any other than LICM on a quick skim, but I could have missed some.
  3. Add some documentation / FAQs detailing the differences between side effects, undefined behavior, speculatabilty.

Diff Detail

Event Timeline

sanjoy created this revision.Oct 7 2022, 6:57 PM
Herald added a reviewer: rriddle. · View Herald Transcript
Herald added a reviewer: aartbik. · View Herald Transcript
Herald added a reviewer: jpienaar. · View Herald Transcript
Herald added a reviewer: ftynse. · View Herald Transcript
Herald added a reviewer: aartbik. · View Herald Transcript
Herald added a reviewer: aartbik. · View Herald Transcript
Herald added a project: Restricted Project. · View Herald Transcript
sanjoy requested review of this revision.Oct 7 2022, 6:57 PM
sanjoy edited the summary of this revision. (Show Details)Oct 7 2022, 7:03 PM
sanjoy edited the summary of this revision. (Show Details)Oct 7 2022, 7:05 PM
sanjoy updated this revision to Diff 466239.Oct 7 2022, 7:45 PM
  • No need for extraClassDeclaration in always_speculatable_op

Thanks, Sanjoy. Just did a quick pass for now.

mlir/include/mlir/Interfaces/SideEffectInterfaces.h
199

nit: use ` ` for code references?

232

typo: remove injects? Not sure I can parse this properly. Same below.

mlir/include/mlir/Interfaces/SideEffectInterfaces.td
161

nit: indent?

mlir/test/Transforms/loop-invariant-code-motion.mlir
442

nit: add // ----- markers or split-input-file

I am a bit concerned by this patch conflating the concepts of specutability and the notion of side effects. In particular the fact that AlwaysSpeculatable and RecursiveSpeculatable have essentially now been made supersets of NoSideEffect. I believe these two things to be orthogonal concepts. That means that an operation that has side effects, may still want to implement the specutable interface, if it is possibly free of undefined behaviour. I think this is actually rather common with MemAlloc ops. Callers of the interface (aka the passes like LICM), should be the ones to do analysis and to choose whether it can handle a specutable op with side effects and I don't see a reason the interface can't support this.

I would personally, if possible, also split the patch. First one maybe implementing the interface and its API, followed by LICM changes, followed by changes to upstream dialects. I'd wait for other reviewers to suggest this as well however and not just take my word for it.

mlir/include/mlir/Interfaces/SideEffectInterfaces.h
249

There is a little trick/hack you can do here, but I am not sure how others feel about it. Instead of inheriting from TraitBase you could inherit from ConditionallySpeculatable::Trait. This would lead to an Op using this trait to both, automatically become an instance of ConditionallySpeculatable as well as inject an implementation via the trait.

mlir/lib/Transforms/Utils/LoopInvariantCodeMotionUtils.cpp
103–105

This should check for both isSideEffectFree, and isSpecutable. The former, as it'd require analysis to prove there is not interferring writes otherwise, the later to not introduce any UB.

mlir/lib/Transforms/Utils/SideEffectUtils.cpp
67

The MemoryEffectsOpInterface is capable of conditionally returning side effects based on an operations property, so this already exists.

I also think this assert should be removed due to the reasons in my comment.

sanjoy added a comment.Oct 9 2022, 9:20 AM

@zero9178

Just making sure I understand -- are you saying that MemAlloc is speculatable but still needs a non-trivial MemoryEffect because it allocates memory? Now that I think of it, another such example is a load from a global variable. Since the global variable is deferenceable for the lifetime of the program, the load itself is speculatable, but we still need to model the read memory effect to make sure we don't reorder it with aliasing writes.

So I agree that splitting Speculatable from MemoryEffect is a good idea. However, IMO it is confusing to say "this op has side effects but can be speculated", so I propose s/NoSideEffect/NoMemoryEffect and s/isSideEffectFree/isMemoryEffectFree in the patch and then make the other changes you suggest below.

And I'll create a def Pure : TraitList[AlwaysSpeculatable, NoMemoryEffects]; (name bikeshedding welcome) to reduce boilerplate for the large number of ops that need both.

What do you think? CC @rriddle

Regarding

I would personally, if possible, also split the patch.

I wanted a non-trivial test case for the op interface with its patch, so I had to combine LICM with adding it, and this meant I need to change all the upstream ops to avoid regression.

sanjoy updated this revision to Diff 466423.Oct 9 2022, 10:33 PM
sanjoy marked 5 inline comments as done.

Addressed review comments:

  • Cleanly split out memory effects from speculatibility
  • Fixed nits
sanjoy added inline comments.Oct 9 2022, 10:34 PM
mlir/test/Transforms/loop-invariant-code-motion.mlir
442

My understanding was that for tests that are not checking for errors, the benefit of // ----- is that it avoids name clashes, e.g. I didn't need to check if test_never_speculatable_op existed earlier in this file. If that's true, then this scope looks fine to me; it demarcates a "block" of related tests.

Please let me know if I'm missing something here.

sanjoy updated this revision to Diff 466424.Oct 9 2022, 10:34 PM
  • fix comment

@zero9178: incorporated your suggestion, PTAL.

mlir/include/mlir/Interfaces/SideEffectInterfaces.h
249

Does this trick exist elsewhere in the codebase?

silvas added a subscriber: silvas.Oct 10 2022, 2:07 AM
  1. Add some documentation / FAQs detailing the differences between side effects, undefined behavior, speculatabilty.

Where is this? I would have perhaps expected it in Rationale.md

mlir/lib/Transforms/Utils/SideEffectUtils.cpp
16

Is this a TODO?

sanjoy updated this revision to Diff 466515.Oct 10 2022, 8:38 AM

Remove stray comment

sanjoy edited the summary of this revision. (Show Details)Oct 10 2022, 8:38 AM

Where is this? I would have perhaps expected it in Rationale.md

Thanks, Rationale.md sounds good!

mlir/lib/Transforms/Utils/SideEffectUtils.cpp
16

That's a stray comment, removed.

sanjoy updated this revision to Diff 466545.Oct 10 2022, 10:36 AM
  • remove stray whitespace

@zero9178

Just making sure I understand -- are you saying that MemAlloc is speculatable but still needs a non-trivial MemoryEffect because it allocates memory? Now that I think of it, another such example is a load from a global variable. Since the global variable is deferenceable for the lifetime of the program, the load itself is speculatable, but we still need to model the read memory effect to make sure we don't reorder it with aliasing writes.

Yes, and your load operation example is even better (and something LLVM does IIRC).

So I agree that splitting Speculatable from MemoryEffect is a good idea. However, IMO it is confusing to say "this op has side effects but can be speculated", so I propose s/NoSideEffect/NoMemoryEffect and s/isSideEffectFree/isMemoryEffectFree in the patch and then make the other changes you suggest below.

I am indifferent about that, but do wonder whether it is somewhat out of scope for this patch and requires more discussion. It is renaming one of the (if not the) most used trait after all, and its not obvious for downstream users looking through the commit title that such a rename is required.

mlir/include/mlir/Interfaces/SideEffectInterfaces.h
249

I don't think so. On further thought your ODS logic is probably better.

mlir/include/mlir/Interfaces/SideEffectInterfaces.td
114–116

Why is the method body here required? I believe this is equal to what TableGen generates by default.

sanjoy updated this revision to Diff 466552.Oct 10 2022, 10:55 AM
sanjoy marked an inline comment as done.
  • Remove code that TableGen generates anyway

I am indifferent about that, but do wonder whether it is somewhat out of scope for this patch and requires more discussion. It is renaming one of the (if not the) most used trait after all, and its not obvious for downstream users looking through the commit title that such a rename is required.

I'm happy to change the commit message or announce in a wider forum, but I don't think keeping both Speculatable and NoSideEffect (in its current form) in the MLIR vocabulary is a reasonable end state. Operations with side effects (in the traditional sense) are by definition not speculatable so having an operation that both has "side effects" and is also speculatable is pretty confusiong IMO.

I also don't think the migration cost for out of tree dialects is high -- they just need to s/NoSideEffect/Pure/ to get the older behavior.

mehdi_amini accepted this revision.Oct 10 2022, 3:56 PM

I also don't think the migration cost for out of tree dialects is high -- they just need to s/NoSideEffect/Pure/ to get the older behavior.

Technically the "safe" update is s/NoSideEffect /NoMemoryEffect/ right?
(I agree that most of the time they want Pure instead)

Current patch LGTM overall, but of course it is central enough to MLIR that we should make sure we have a larger consensus, waiting to hear from @rriddle and @jpienaar in particular.

Technically the "safe" update is s/NoSideEffect /NoMemoryEffect/

(I agree that most of the time they want Pure instead)

Yes to both.

rriddle accepted this revision.Oct 11 2022, 2:47 PM

Sorry for the delay, I've been out. This LGTM. I had the same concerns as others about the original patch, which had speculatability becoming a superset of no memory effects. Pure seems like a good name to describe the behavior.

Where is this? I would have perhaps expected it in Rationale.md

Thanks, Rationale.md sounds good!

I'd love to instead have a proper SideEffects.md (or something) document that details our modeling of side effect behaviors, when to use which trait/interface, etc.

mlir/include/mlir/Dialect/SCF/IR/SCFOps.td
333–334

Is this really useful to add here? I'd rather just remove this and actually add it in the future if necessary.

mlir/include/mlir/Interfaces/SideEffectInterfaces.h
202–203
233

Is the ::mlir:: here necessary? Same below.

mlir/include/mlir/Interfaces/SideEffectInterfaces.td
96–116

I would move the speculation stuff under a new:

//===----------------------------------------------------------------------===//
// Speculation
//===----------------------------------------------------------------------===//
114

Can you rename this? Having an is method return something other than bool is a little confusing. It'd be nicer to name this something like: getSpeculatability

LGTM for the sparse dialect ops changes (all marked as PURE)

sanjoy updated this revision to Diff 467012.Oct 11 2022, 9:54 PM
sanjoy marked 5 inline comments as done.

Address review

sanjoy retitled this revision from Make NoSideEffect allow undefined behavior; step 1/N to Introduce a ConditionallySpeculatable op interface.Oct 12 2022, 10:32 AM
sanjoy edited the summary of this revision. (Show Details)
This revision was not accepted when it landed; it landed in state Needs Review.Oct 12 2022, 10:56 AM
This revision was landed with ongoing or failed builds.
This revision was automatically updated to reflect the committed changes.

Why this patch landed with obvious failures in the pre merge checks? https://buildkite.com/llvm-project/premerge-checks/builds/116406#0183ca8c-bc14-4314-9b1d-c764cf47e0aa

The premiere checks aren't "visible enough": I never notice them myself (I use to when they were posting the results in a comment initially).

Please revert if a fix forward isn't straightforward (should be a sed in flang I think?)

I didn't notice the failure either. A comment would be more visible.

I'll fix forward or revert within the next hour.

Why this patch landed with obvious failures in the pre merge checks? https://buildkite.com/llvm-project/premerge-checks/builds/116406#0183ca8c-bc14-4314-9b1d-c764cf47e0aa

The premiere checks aren't "visible enough": I never notice them myself (I use to when they were posting the results in a comment initially).

Please revert if a fix forward isn't straightforward (should be a sed in flang I think?)

Fixed in e4ccba1598c07bc1fb6f3b73942dbc0a03fa51ed

Why this patch landed with obvious failures in the pre merge checks? https://buildkite.com/llvm-project/premerge-checks/builds/116406#0183ca8c-bc14-4314-9b1d-c764cf47e0aa

The premiere checks aren't "visible enough": I never notice them myself (I use to when they were posting the results in a comment initially).

Please revert if a fix forward isn't straightforward (should be a sed in flang I think?)

Fixed in e4ccba1598c07bc1fb6f3b73942dbc0a03fa51ed

Thanks @clementval !

There is also a failure in the MLIR Windows bot. https://lab.llvm.org/buildbot/#/builders/13/builds/27028

C:\buildbot\mlir-x64-windows-ninja\llvm-project\mlir\lib\Transforms\Utils\SideEffectUtils.cpp(58) : error C2220: the following warning is treated as an error
C:\buildbot\mlir-x64-windows-ninja\llvm-project\mlir\lib\Transforms\Utils\SideEffectUtils.cpp(58) : warning C4715: 'mlir::isSpeculatable': not all control paths return a value

There is also a failure in the MLIR Windows bot. https://lab.llvm.org/buildbot/#/builders/13/builds/27028

C:\buildbot\mlir-x64-windows-ninja\llvm-project\mlir\lib\Transforms\Utils\SideEffectUtils.cpp(58) : error C2220: the following warning is treated as an error
C:\buildbot\mlir-x64-windows-ninja\llvm-project\mlir\lib\Transforms\Utils\SideEffectUtils.cpp(58) : warning C4715: 'mlir::isSpeculatable': not all control paths return a value

How do we usually address these? I believe that switch covers all enums so this looks like a false positive to me.

How do we usually address these? I believe that switch covers all enums so this looks like a false positive to me.

I believe the easiest way to make all the compilers happy is to put an llvm_unreachable or equivalent at the end of the function after the case.

There is also a failure in the MLIR Windows bot. https://lab.llvm.org/buildbot/#/builders/13/builds/27028

C:\buildbot\mlir-x64-windows-ninja\llvm-project\mlir\lib\Transforms\Utils\SideEffectUtils.cpp(58) : error C2220: the following warning is treated as an error
C:\buildbot\mlir-x64-windows-ninja\llvm-project\mlir\lib\Transforms\Utils\SideEffectUtils.cpp(58) : warning C4715: 'mlir::isSpeculatable': not all control paths return a value

How do we usually address these? I believe that switch covers all enums so this looks like a false positive to me.

gcc is also raising a wanring for this. I think you need need a default case to get rid of it.

Sent https://reviews.llvm.org/D135899 adding the llvm_unreachable.

I'd prefer to not add a default: since that would silence the warning we'd otherwise get if someone adds a new enum value and forgets to update this method.

I just noticed this patch when it got merged into our tree.

@sanjoy question for you:

Replace NoSideEffect with Pure if the operation does not have any memory effects, undefined behavior or infinite loops.

Did you consider alternate names for this than "Pure"? Pure has historically been super confusing for people because it means different things in different contexts. For example, the GCC/Clang "pure" attribute, actually means "readonly" and not "readnone".

Did you consider something more explicit and less loaded with terminology baggage?

More information on the GCC/Clang attribute semantics:
https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html

The confusion here is why llvm calls the corresponding concepts "readonly" and "readnone". These are perhaps not general enough to model the MLIR concept, but you can hopefully understand the need for better names than "pure" and "const".

Did you consider something more explicit and less loaded with terminology baggage?

How about NoMemoryEffectAndTotal ("total" as in "total function") or NoMemoryEffectAndAlwaysSpeculatable (verbose but more obvious)?