Add a document on side effects & speculation in MLIR

[sanjoy]

• Add note about Pure

[silvas]

This is really great Sanjoy. Thanks! I have a few comments.

mlir/docs/Rationale/SideEffectsAndSpeculation.md

19

can we introduce an appropriate generalization of the notion of "heap" here? It seems overly specific to talk about "heap"/"stack" in a document about MLIR broadly.

22

Is there an appropriate generalization of this that includes graph regions as well? cc @mehdi_amini

[mravishankar]

Thanks LGTM, but please wait for other folks to weigh in.

[kuhar]

mlir/docs/Rationale/SideEffectsAndSpeculation.md

20

How about something like this:

• These operations are not defined on certain inputs. We do not define what happens when such illegal inputs are passed, and instead say that behavior is undefined and can assume it does not happen.
• In practice, in such cases these ops may be considered unreachable or do anything from producing garbage results to crashing the program or corrupting memory.
• Examples of operations with well-known UB include division by zero or loading from an already freed pointer.

[mehdi_amini]

Can you format the markdown to wrap on 80 lines? (ideally just run mdformat on it)

Also we should link to this doc from other places (like the SideEffect interface doc).

mlir/docs/Rationale/SideEffectsAndSpeculation.md

19

We should likely add something like "or any other global state for a program, usually matching some HW (modifying memory or other resources)". Keeping "heap" isn't a big deal in a "rationale" document I think (it's not a spec).

20

I like the suggestion here. In particular "can assume it does not happen" is important to mention.

In practice, in such cases these ops may be considered unreachable

That can be misunderstood because the condition is really dynamic in general, the "can assume it does not happen" should be enough though?

21

More broadly speaking: any operation that may not terminate (infinite loop is a specific construct that won't terminate).

22

I am not sure: without control-flow (a graph region...) it gets weird to have non-local control flow!

[sanjoy]

• reformat
• address review comments

[sanjoy]

Also we should link to this doc from other places (like the SideEffect interface doc).

I don't see a doc, do you mean the .td file?

mlir/docs/Rationale/SideEffectsAndSpeculation.md

19

Generalized the language here a bit, PTAL.

20

Agreed -- folks might read "unreachable" to mean "statically unreachable" which isn't correct.

22

I don't think any of this makes sense generically in a graph region.

For instance, an graph region could be modeling a "sea of nodes"-style IR where all memory effects are explicitly sequenced via an explicit MemorySSA representation. Or it could be represent something that's not even an IR in the traditional sense.

So for now I've added a disclaimer that this doc only applies to CFG regions. LMK if I should remove this.

[sanjoy]

• Add disclaimer about graph regions

[lattner]

+1 for revising the name "pure" :-)

[kuhar]

Overview + categorization LGTM

[mehdi_amini]

LG, but please wait for @rriddle to take a look as well

[jpienaar]

mlir/docs/Rationale/SideEffectsAndSpeculation.md

35

Micro nit: "E.g.,"

37

Ha good example for %s case :)

43

Micro nit: Only one space after period.

45

And here there is no differentiator between where the op produces value/has side effects or not? E.g., in the scf.while case, given it has recursive side effect, it can still be removed in some cases today even I believe. [But Mehdi has good point above, this is a rationale doc not a spec]

84

So, for clarification, if your op expects rank-3 inputs but gets a rank-4 input then you have an invalid module/function. The op has undefined behavior there, where your program as a whole is wrong. (effectively all ops which allow dynamic shapes need this and mostly only speculated in static shape case).

[rriddle]

This LGTM. I would still love for us to have a non-rationale/user facing doc that details how/when/etc. to use things.

mlir/docs/Rationale/SideEffectsAndSpeculation.md

33

Does the resource have to be mutable?

49

[sanjoy]

mlir/docs/Rationale/SideEffectsAndSpeculation.md

33

I think so -- reading from immutable resources seems pure. Under the assumption that freeing memory counts as mutating a resource.

LMK if I missed something.

43

Looks like mdformat fixed all such instances.

45

Not sure I totally understood your concern, but I added a note that operations may exhibit multiple kinds of side effects. Let me know if I misunderstood.

84

invalid module/function.

I'd rather frame this as the entire _execution_ is invalid.

mlir/docs/Rationale/SideEffectsAndSpeculation.md

+# Side Effects & Speculation
+
+This document outlines how MLIR models side effects and how speculation works in MLIR.
+
+[TOC]
+
+## Overview
+
+Many MLIR operations don't exhibit any behavior other than consuming and producing SSA values.  These operations can be reordered with other operations as long as they obey SSA dominance requirements and can be eliminated or even introduced (e.g. for [rematerialization](https://en.wikipedia.org/wiki/Rematerialization)) as needed.
+
+However, a subset of MLIR operations have implicit behavior than isn't reflected in their SSA data-flow semantics.  These operations need special handing, and cannot be reordered, eliminated or introduced without additional analysis.
+
+This doc introduces a categorization of these operations and shows how these operations are modeled in MLIR.
+
+## Categorization
+
+Operations with implicit behaviors can be broadly categorized as follows:
+
+1. Operations with memory effects.  These operations read from and write to memory on the heap, the stack or an abstract resource like the console.  They may also interact with the heap in other ways, like by allocating and freeing memory.  E.g. standard memory reads and writes, `printf` (which can be modeled as "writing" to the console and reading from the input buffers).
+1. Operations with undefined behavior.  These operations are not defined on certain inputs or in some situations -- in such cases these ops may do anything, e.g. crash the program, silently corrupt, the heap, produce garbage results etc.  E.g. integer division which has UB when dividing by zero, loading from a pointer that has been freed.
+1. Operations with infinite loops.  E.g. an `scf.while` where the condition is always true.
+1. Operations with non-local control flow.  These operations may pop their current frame of execution and return directly to an older frame.  E.g. `longjmp` , operations that throw exceptions.
+
+## Modeling
+
+Modeling these behaviors has to walk a fine line -- we need to empower more complicated passes to reason about the nuances of such behaviors while simultaneously not overburdening simple passes that only need a coarse grained "can this op be freely moved" query.
+
+MLIR has two op interfaces to represent these implicit behaviors:
+
+1. The [`MemoryEffectsOpInterface` op interface](https://github.com/llvm/llvm-project/blob/main/mlir/include/mlir/Interfaces/SideEffectInterfaces.td#L26) is used to track memory effects.
+1. The [`ConditionallySpeculatable` op interface](https://github.com/llvm/llvm-project/blob/main/mlir/include/mlir/Interfaces/SideEffectInterfaces.td#L105) is used to track undefined behavior and infinite loops.
+
+Both of these are op interfaces which means operations can dynamically introspect themselves (e.g. by checking input types or attributes) to infer what memory effects they have and whether they are speculatable.
+
+We don't have proper modeling yet to fully capture non-local control flow semantics.
+
+When adding a new op, ask:
+
+1. Does it read from or write to the heap or stack?  It should probably implement `MemoryEffectsOpInterface`.
+1. Does it have side effects that must be preserved, like a volatile store or a syscall?  It should probably implement `MemoryEffectsOpInterface` and model the effect as a read from or write to an abstract `Resource`.  Please start an RFC if your operation has a novel side effect that cannot be adequately captured by `MemoryEffectsOpInterface`.
+1. Is it well defined in all inputs or does it assume certain restrictions on its inputs, e.g. the pointer operand must point to valid memory?  It should probably implement `ConditionallySpeculatable`.
+1. Can it infinitely loop on certain inputs?  It should probably implement `ConditionallySpeculatable`.
+1. Does it have non-local control flow (e.g. `longjmp`)?  We don't have proper modeling for these yet, patches welcome!
+1. Is your operation free of side effects and can be freely hoisted, introduced and eliminated?  It should probably be marked `Pure`. (TODO: revisit this name since it has overloaded meanings in C++.)