I experimented with --string-lowering --string-lifting before doing optimizations on j2wasm output, that is, lowering the stringref they currently emit, to represent what they could emit instead, and then lifting it back, and then optimizing. Overall there was no substantial difference in the final result, aside from not being able to infer stringref in as many places, but that would get lowered at the end anyhow. So this seems ok from an optimization perspective.

What do you think about building string lifting and lowering directly into the parsers (via IRBuilder) and the binary writer in the long term?

That seems to have downsides:

1. It would add complexity to the parser and writer.
2. It would mean that users have less control over when this transformation happens (e.g. maybe they want to run some general optimization cycles before any changes).
3. If the parser and writer did this automatically, we'd have no way to directly represent Binaryen IR strings in text format, so any debugging would end up having to consider that the IR is different from the wasm.

The upside is not having support for a nonstandard binary and text format, but I think the nonstandard stuff is exactly what we want in terms of serializing our IR, and that our IR with stringref operations is what we want as an IR (e.g. a string concat operation is literally an instruction string.concat and not some kind of import).

What do you think about building string lifting and lowering directly into the parsers (via IRBuilder) and the binary writer in the long term?

That seems to have downsides:

1. It would add complexity to the parser and writer.

I'm not too worried about adding complexity to IRBuilder since it's so well contained. For the writer, it could just call out automatically to the lowering pass.

2. It would mean that users have less control over when this transformation happens (e.g. maybe they want to run some general optimization cycles before any changes).

I don't see any reason not to perform lifting as early as possible and lowering as late as possible. That will get the best optimizations.

3. If the parser and writer did this automatically, we'd have no way to directly represent Binaryen IR strings in text format, so any debugging would end up having to consider that the IR is different from the wasm.

No problem, we can continue parsing and printing the non-standard string operations and types in the text parser and printer.

The upside is not having support for a nonstandard binary and text format, but I think the nonstandard stuff is exactly what we want in terms of serializing our IR, and that our IR with stringref operations is what we want as an IR (e.g. a string concat operation is literally an instruction string.concat and not some kind of import).

Not having to support a nonstandard binary format, yes, but as mentioned above, I think we should keep the text format for testing purposes. I agree that "our IR with stringref operations is what we want as an IR," and building lifting into the parser strongly aligns with that.

I don't see any reason not to perform lifting as early as possible and lowering as late as possible. That will get the best optimizations.

Debugging could be a reason, for example.

Another possible reason is interaction/ordering with other lifting and lowering operations (like say the lowering we have for intrinsics atm). I can't think of a bad interaction between them, though.

Not having to support a nonstandard binary format [is the benefit], yes, but as mentioned above, I think we should keep the text format for testing purposes.

I agree removing a nonstandard thing is nice, but it is also a small amount of code, and already written.

And the binary format is also useful. E.g. reduction is faster on the binary format, and it may even be needed, if the bug does not reproduce in the text format (which does happen sometimes, as our text format has some differences, like the unreachable type).

And, it is nice that the binary and text formats are as parallel as possible (which, again, we've already compromised on, but hopefully we can avoid adding more such divergences).

The main benefit I would want is that defaults matter, so having to manually remember to add these passes would be bad. That benefit could also be realized by adding lifting lowering passes at the beginning and end of the default optimization pipeline. (But in that case the lowering and lifting in the middle of e.g.g -O3 -O3 would be useless. Maybe we want a concept of early passes and late passes based on the maximum used optimization level or something like that?)

The main benefit I would want is that defaults matter, so having to manually remember to add these passes would be bad. That benefit could also be realized by adding lifting lowering passes at the beginning and end of the default optimization pipeline.

I get your point that it would be nice for this to "just work" for users. But losing some type information between cycles, or even between invocations of wasm-opt, is generally harmful.

In more detail: lifting + lowering is not "perfect". That is, the lowering at the end of one cycle and the lifting at the start of another may not perfectly cancel out. In fact, they do not, in general: we lower stringref to externref, and do not lift it back, so we depend on optimizations to re-refine things, which may take multiple cycles. Now, in VMs this does not matter because the user will lower stringref to externref at the very end anyhow, but it could help in the middle, say by proving a ref.test of stringref succeeds.

But lowering is the lossy path. Lifting actually recovers type information because the string operations get the more refined string type. So lifting as early as possible and lowering as late as possible is always optimal. I agree that doing a lowering in the middle of -O3 -O3 would be suboptimal, so we should find a way to lift by default while avoiding that problem.

But lowering is the lossy path. Lifting actually recovers type information because the string operations get the more refined string type. So lifting as early as possible and lowering as late as possible is always optimal.

Yes, but:

wasm-opt input.wasm -O3 -O3 --gufa -O3 -O3 -o mid.wasm
wasm-opt mid.wasm -O3 -O3 --type-finalizing -o final.wasm

With automatic lifting&lowering, the lowering at the end of the first line is the problem, as it undoes refinements. We may recoup them on the second line (after it lifts during load) but we may not.

What if we had a flag to allow opting out of the automatic lowering in the binary writer? Such users could use the flag for their intermediate stages, and users who just use a simple, default pass pipeline would get the optimal and standards-compliant behavior without having to be experts.

What if we had a flag to allow opting out of the automatic lowering in the binary writer?

It sounds like you're suggesting

wasm-opt input.wasm [..opts..] -o mid.wasm --opt-out-of-string-lowering
wasm-opt mid.wasm [..opts..] -o final.wasm

Is that right - so we do keep around the binary writing/reading logic for strings?

users who just use a simple, default pass pipeline would get the optimal and standards-compliant behavior without having to be experts

Users would need to be aware of the issue to know if they are getting the optimal pipeline, so I am not sure this helps much. But maybe there are more such users?

I don't follow the standards-compliant point? In my proposal if the user never uses --string-lifting --string-lowering then they are obviously standards-compliant (assuming they emit such code themselves), and if they do use it, they will still emit standards-compliant code (unless they forget the --string-lowering, but in your suggestion they could also leave an --opt-out-of-string-lowering at the end).

Yes, if we consider it a requirement that users can split their pipeline across multiple invocations without lowering in the middle, then we would need to keep the binary reading and writing around. I'm not quite convinced this is worth it, but I agree it removes the possibility of regressing current behavior, so I'm happy to start here.

I do think there are probably many users who just run -O3 and call it a day. Certainly we can't expect users who aren't toolchain maintainers to know anything about what the pipeline is doing.

Never mind the standards-compliant comment, it was indeed self-evident. My main point is that it would be good to do the best thing by default.

I do agree that most users likely just do -O3, so that would work well for them.

But I guess the question is what do we want to focus on - making the common case work well, or avoiding subtle issues in rarer cases? I agree you handle the common case well, but a toolchain author missing --opt-out-of-string-lowering is pretty subtle, far harder to notice than not getting string opts at all.

And I still feel that adding this magic in the binary reading and writing has more downsides than benefits. For example, how can we avoid adding overhead? Lifting can be very efficient - check for the imports, and if none exist, do nothing - but lowering requires scanning the entire module in general, to see if there is anything we need to lower. I can't think of a good way to avoid that overhead.

Code LGTM. Let's discuss automatic lifting and lowering offline. I don't think strings are the only thing we will want this for.