Pure calls / future of call.without.effects

[kripken]

Atm we provide a way to say that a call has no side effects with an intrinsic, which is just an imported function:

binaryen/src/ir/intrinsics.h

Lines 42 to 56 in f030449

	//
	// (import "binaryen-intrinsics" "call.without.effects"
	// (func (..params..) (param $target funcref) (..results..)))
	//
	// call.without.effects can take any parameters, and in addition a funcref,
	// and return any result.
	//
	// Precise semantics:
	//
	// * The optimizer will assume this instruction has no side effects.
	// * Final lowering turns a call.without.effects into a call of the given
	// function with the given parameters. (This will either be a direct call,
	// or a call_ref; note that either way, the function reference that appears
	// here must have the proper type - if not, you will get an error.)
	//

The wasm spec has been adding similar code metadata in the form of branch hints and compilation hints. While call.without.effects is not meant to be used by VMs (it only make sense at the toolchain level), it may be nice to implement it similarly, to be consistent. That is, instead of the current intrinsic which is a specially-named function import, we could annotate the code the way those two proposals do:

• In the text format, using custom annotations, something like:

(@metadata.code.pure "\00")
(call $target)

• In the binary format, add a custom section, and the binary offsets there point to the instructions that are annotated.

The binary format takes more work this way - in particular, it is easy to get the offsets wrong - but it is more consistent with other things in wasm. Thoughts on the tradeoff?

Separately, there are two changes we may want to make to call.without.effects if we make a new version of it:

• We can annotate the function itself (once) rather than all calls to it (many). That is, unless there are cases where some calls to the same target should be considered effect-free, but not others?
• Atm call.without.effects only considers side effects (discussion), but it does not guarantee that it returns the same value for the same inputs. In particular, marking a call to a JS export that does Math.random() as call.without.effects would be wrong - two such calls cannot be folded together. We could make the new version also assume it returns the same value, and call it "pure", perhaps?

[rluble]

We can annotate the function itself (once) rather than all calls to it (many). That is, unless there are cases where some calls to the same target should be considered effect-free, but not others?

It makes sense to make it a function property rather than a callsite property and thatit is the way we model the internally in J2CL. While in a function could be be side-effectfull or not depending on the values passed making it a callsite property, we don't really do an analysis that can determine that property.

Atm call.without.effects only considers side effects (discussion), but it does not guarantee that it returns the same value for the same inputs. In particular, marking a call to a JS export that does Math.random() as call.without.effects would be wrong - two such calls cannot be folded together. We could make the new version also assume it returns the same value, and call it "pure", perhaps?

I think returning the same value on the same params (i.e. being really a function :) is a different property. Math.random is for sure side-effectfull, since each time it is called it will change the global state.

We do mark some functions that change the global state as side-effect free, when it makes sense, for example, for lazy initialization. So these are conceptually side-effect free even though they change the global state.

[kripken]

@rluble

It makes sense to make it a function property rather than a callsite property

👍

We do mark some functions that change the global state as side-effect free, when it makes sense, for example, for lazy initialization. So these are conceptually side-effect free even though they change the global state.

Do all the functions you use call.without.effects on behave that way?

The specific question I am looking for an answer for is if we need two properties:

1. A property where (drop (call $target)) can be removed.
2. A property where we can also assume that if x = (call $target); y = (call $target) then x == y, and we can turn that into x = (call $target); y = x. (necessary for call.without.effects is always possible for CSE #7568)

The current call.without.effects has property 1, but not 2 (so we may have been missing some optimization opportunity, and if all users want 2 anyhow, maybe the new version can include 2.)

[rluble]

The functions that we mark as side effect free fall into property 1; we also mark some that don't modify the global state nor escape values so that binaryen also removes nested calls (drop (call $target1 (call $target2)) where both targets are marked as having no side-effects. The main reason we need this hint is because these function have side-effects but it is ok to ignore that fact (caching, ...)

IMHO Property 2 in should probably be determined by an analysis and it would cover most of the cases. In J2Wasm we are currently marking some functions that would be of this property as side effect free to aid the removal of nested calls but I don't think it would make much difference to have a more precise marking here.

One pattern that comes to mind for property 2 is that of property accessors for immutable objects (or more complex computations that only depend on immutable objects as their parameters, since simple accessors are probably inlined in many scenarios).

My intuition is that we are getting a lot of the benefits already by inlining but if we had such an analysis it might allow to dial inlining down and still get the same level of optimization (same performance, smaller code size).

[tlively]

To bikeshed the annotations a bit, I think it would make the most sense to use (@binaryen.pure). I also agree it would make the most sense to annotate the function as pure rather than its calls.

We could have another annotation (@binaryen.idempotent) for things like clinits that have side effects on the first call but not on subsequent calls.

Both these annotations could be either supplied in the input or inferred via analysis.

[kripken]

@rluble

Thanks for the info. To make sure I follow, you would want both 1 and 2 as options, that is both (@binaryen.pure) and (@binaryen.other-name)? (or however we choose to name them)

@tlively

Which of 1 and 2 would pure and idempotent be? (my confusion is that "idempotent" doesn't quite match up to either 1 or 2 IIUC)

One option might be 1 = effectless (no effects, hence can remove a dropped call) and 2 = pure (pure function, returns the same output for the same inputs, so two call's results can be merged).

[tlively]

(drop (call $target)) can be removed if $target is pure because it will never have any side effects.

x = (call $target); y = (call $target) can be turned into x = (call $target); y = x if $target is idempotent because the initial call might have side effects, but the subsequent call will not. (This optimization is also valid if $target is pure because pureness implies idempotency.)

Furthermore, (drop (call $target)); (drop (call $target)) can be optimized to (nop) if $target is pure, but only to (drop (call $target)) if $target is idempotent and not pure.

[tlively]

One option might be 1 = effectless (no effects, hence can remove a dropped call) and 2 = pure (pure function, returns the same output for the same inputs, so two call's results can be merged).

I don't think it makes any sense for a function to be effectless but not pure. If a function is not pure, then it must observe some global state to determine what different results to produce.

[rluble]

I think all the usages we currently have for sideeffect-free functions could also classify as pure. Calls can be dropped if the return value is not used, and they can be assumed that they are real functions in the mathematical sense; i.e. @binaryen.pure should be enough.

I am not sure I like the term idempotent (although we have also used it in J2CL to mean exactly what you are proposing), since in math it has a very specific meaning Vx. f(f(x)) = f(x).

[kripken]

@rluble

Makes sense, thanks. Ok, maybe we just need @pure then.

@tlively

Oh, I was confused by your first definition of "idempotent":

have side effects on the first call but not on subsequent calls.

That by itself isn't enough to merge x = (call $target); y = (call $target) since the second call might have no effects but also return another value. But we could define it to include that property too.

[kripken]

@tlively

I don't think it makes any sense for a function to be effectless but not pure. If a function is not pure, then it must observe some global state to determine what different results to produce.

Sorry, I wasn't clear enough. I meant "effectless" in the sense of not having side effects / write effects, but perhaps having read effects. A pure function would also not have read effects.

E.g. a function that reads a sensor would be effectless (in that sense) but not pure.

[tlively]

@rluble, for better or worse, "idempotent" appears to be standard with the meaning in a computer science context: https://en.wikipedia.org/wiki/Idempotence#Computer_science_meaning

[dschuff]

For more fun variations, check out all the options gcc has for similar properties in C: https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html (e.g. const, pure, and reproducible).

[gkdn]

+1 to using functions annotations. Current approach required explicit handling to see beyond "call.without.effects"; for example I had a note about checking the impact of OnceReduction not seeing through such "call.without.effects" calls.

re. pure vs. side effect free:
Currently not all our usages conform to pure functions though we might be able to get away with the introduced behavior difference for the current usage set. (for example we would like to drop Integer "boxing" call as a side effect free call, however different boxing calls would return different box instances so it is not pure).

And if we map HasNoSideEffects (our annotation) to Binaryen's "pure", we can potentially introduce similar problems like above. It might be good idea to keep the "side effect free" and introduce another property for "idempotence". Also to me it makes sense since they also imply different optimizations. And I think one can annotate with both to cover "pure" function scenarios.

(FWIW we already sneaked idempotence property to binaryen with naming convention in J2clOpts.cpp "isOnceFunction" 😁. I think OnceReduction is also another attempt to detect and take advantage of idempotence.)

[osa1]

We don't use call.without.effects in dart2wasm yet but we want to use it.

Adding hints for "pure" and "idempotent" (instead of importing per-function-type wasm-opt primitives) has some advantages for us:

• Generating hints are easier than generating per-function-type imports. (though this may say more about dart2wasm code than imports vs. hints)
• We currently don't run wasm-opt when not optimizing. With imports, we either have to run it always (so that when not optimizing the imports will be removed), or make dart2wasm aware of optimization levels and not generate the imports. With hints, we don't have to change anything, hints will just be ignored when not running wasm-opt.

So 👍 from me for having hints instead of imports.

Regarding the use cases, we have use cases for "pure", but I'm not aware of any functions that would be "idempotent" but not "pure".

Two use cases for "pure":

• For complicated type checking operations we generate functions (instead of inline code) to avoid generating large amounts of duplicate code. When we have a type-switch (or if-then-else chain) for checking type of a value and branching, sometimes wasm-opt is able to prune branches, but it leaves the type checking function calls behind. We know those functions are "pure" and ideally we'd like to drop them as well. That saves both binary space and runtime.

• In the JS value wrapper classes we have many methods that are pure, but since those methods are just imports to JS code, wasm-opt is unable to do CSE the calls or eliminate them. For example, the TypedArray.prototype.length exposed via Dart members for the typed array wrapper classes, and String.length property. Being able move length calls out of loops would be great.