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:

https://github.com/WebAssembly/binaryen/blob/f03044981fad2c1c4d366485b25995c6b4bb4052/src/ir/intrinsics.h#L42-L56

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 https://github.com/WebAssembly/binaryen/pull/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 :+1: 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.

[kripken]

@gkdn

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).

Thanks, makes sense. We should support that too.

Such a boxing function is what Binaryen calls "generative", a function that might not have side effects but that can return different values (it "generates" values, e.g. reading a sensor, allocating, etc). I suppose another way to look at it is that allocating a box is a side effect. (Binaryen itself doesn't consider allocations to be effects, though - we intentionally don't try to model host limitations like OOMs - but we can pick a name regardless of that, since we should look into adding this name to the tool-convention repo eventually.)

[gkdn]

I suppose another way to look at it is that allocating a box is a side effect. (Binaryen itself doesn't consider allocations to be effect

To clarify, the boxing code has also has caching so from compiler perspective they have real side effect (not due to allocation). We mark them side effect free since we don't care about the side effect there.

[gkdn]

but I'm not aware of any functions that would be "idempotent" but not "pure".

@osa1 one example might be static initialization (assuming Dart needs something like that). Those wouldn't be pure but idempotent.

[osa1]

but I'm not aware of any functions that would be "idempotent" but not "pure".

@osa1 one example might be static initialization (assuming Dart needs something like that). Those wouldn't be pure but idempotent.

Right, we have those (in top-level variables and static fields), and also non-static fields with non-constant RHSs. Getters for these members are compiled to functions that evaluate the initializers only on the first call. Those would be idempotent but not pure in Dart as well. Marking those as idempotent could be beneficial.

[bashor]

+1 for an annotation on functions.

Here are some examples for the discussed groups from Kotlin:

• No side effects

  • Some specific functions and constructors (e.g., boxes for primitives, lambdas, etc.)
  • Simple getters, but inline usually helps for this
  • Access to simple (pure) objects

• No visible side effects

  • Cases where we have a runtime cache, e.g., for string literals, callable references, etc.

• Idempotent (with visible side effects)

  • Initializers for top/file-level property. Called on the first access to something in a file.
  • Initializers for enum entries, objects. Called on the first access to a declaration.

--

What do you think about paired/inverse operations or functions like externalize-internalize, box-unbox? Would you find information about them useful?

[kripken]

Thanks @bashor , good to know!

Ok, based on that, I think the following might make sense for us to have, as function-level annotations:

• @binaryen.no.side.effects - optimizer can assume this has no side effects.
• @binaryen.idempotent - optimizer can assume that subsequent calls to this do nothing at all / return the same result as before.

I also wrote this up in the tool-conventions repo: https://github.com/WebAssembly/tool-conventions/issues/255 - if there is interest in documenting this there, we may want more general names than @binaryen.* (and maybe other changes based on feedback). So let's see how discussion goes there first, I think, before making any changes here.

What do you think about paired/inverse operations or functions like externalize-internalize, box-unbox? Would you find information about them useful?

Interesting... With that, we could optimize away the pairs. So IIUC

function box(x) { .. }
function unbox(y) { .. }

foo(box(unbox(x)))
=>
foo(x)

Perhaps something like marking a function as the side-effect-free-inverse of another.

Would other toolchains find that useful?

[tlively]

• @binaryen.no.side.effects - optimizer can assume this has no side effects.

Can we clarify this by calling it either @binaryen.no.write.effects or @binaryen.pure?

Also, should we require, allow, or disallow the @metadata.code.* prefix on the attribute names?

[kripken]

"Write effects" sgtm, though isn't that a synonym of "side effects"? (That is how Binaryen calls things, at least, in effects.h.)

I don't have strong feelings about @metadata.code.* or other prefixing, though I think it could make sense to use a different prefix to differentiate VM hints from toolchain hints. @toolchain.metadata.code.* perhaps? (assuming the toolchain conventions repo is interested; if not, @binaryen.* seems good enough)

[Tacodiva]

I'm not sure if this is the right place to put this, but I have another edge case where I would like to mark a function with some of the properties of call.without.effects, but not all of them. I would like a way to have a call.without.effects function, but have binaryen preserve conditions to the call to that function. I'm not sure how to word it, so look at this example.

local.get $condition
if (result i32)
    local.get $argument
    ref.func $my_func ;; my_func (param i32) (result i32)
    call $call.without.effects
else
    i32.const 0
end

Right now with call.without.effects, that will optimize into:

local.get $condition
local.get $argument
call $my_func  ;; my_func (param i32) (result i32)
i32.const 0
select

Before, the function was only called if $condition but the optimizer has made the call unconditional. If the i32 result here is not used, I would still like the whole thing to be eliminated, however if the call is kept and has a condition, I would want that condition to be kept as well. I want to be able to say something like "Binaryen can remove this call, but it must not call it when the unoptimized code would not have called it". I can think of two situations this distinction would be helpful:

1. If the call to the function is expensive. Getting rid of the conditional execution means binaryen will eliminate any faster paths trying to avoid the call.
2. If the call to the function may have effects when the condition is not kept. For example, a function which crashes for inputs less than 0 might be guarded by a check to make sure the input is less than 0, avoiding the call if so. This call can still be removed if the result is dropped (because it has no other effects), but the condition must not be removed.

I have run into both of these cases trying to implement call.without.effects into my compiler. I think distinction between 'this call can be removed' and 'this call will do nothing except return a value' are related, but different and should be separate.

[kripken]

@Tacodiva Interesting case. Please open a separate issue for it, as I think the underlying problem is separate: call.without.effects makes it possible to call it unconditionally, but we should still not do so because of the overhead. It looks like cost.h just has too low a value for the estimated cost of a call - raising that should fix things for you.

[kripken]

The issue with making calls unconditional (@Tacodiva 's point 2 from 2 comments back) is something I didn't fully appreciate before. Yes, this seems significant, and didn't come up before because I guess things like Java ctors are ok to run unconditionally.

As a metaphor, to fix this, we'd want to make such functions behave like traps-never-happen and not like ignore-implicit-traps: tnh will not unconditionalize code, while iit just ignores the effect entirely, and might. We have deprecated iit for that reason. (See more in pass.h when it compares them.)

For these intrinsics, however, I'm not sure if we don't need both. Probably we would want to see if the change causes regressions to Java before doing anything. As to how we would do it internally, we could probably extend EffectAnalyzer::hasUnremovableSideEffects which is where tnh is handled, to make that handle not just tnh but also these calls.