WebAssembly
HeapStoreOptimization: Fix a bug with jumping from the later value
The pass does this:
(local.set $x (struct.new X Y Z))
(struct.set (local.get $x) X')
=>
(local.set $x (struct.new X' Y Z))
This is wrong, however, if X' branches inside the function. In the optimized form
the branch is before the local.set, so if we use that local later, we can notice the
difference.
Simply disallowing possible branches in the later value X' would have been a
simple solution that avoids the need for a control-flow analysis, but it is not
good enough: it is common in e.g. Java to have function calls as the value, and
with exceptions enabled those can branch.
Loop handling fixed + tests, and other feedback should also be addressed now.
I don't want to further block landing this, but I do think it would be nice if this called out to a separate liveness analysis utility instead of reimplementing the analysis. It looks like we already have such a utility in cfg/liveness-traversal.h. WDYT?
I do think it would be nice if this called out to a separate liveness analysis utility instead of reimplementing the analysis.
This pass doesn't reimplement liveness - it does a flow to see if the struct.set can be skipped. We could use liveness to make that analysis fully precise, but we don't atm.
Example:
(block $out
(local.set $x (struct.new X Y Z))
;; $x is live here.
(struct.set (local.get $x) (..br $out..))
;; $x is live here.
(struct.set (local.get $x) (..))
;; $x is live here.
)
;; $x is live here.
(struct.set (local.get $x) (..))
Liveness by itself can't help us here, unless I am missing something: $x is live in all those paths. And that liveness is not necessarily bad by itself: only the fact that that br can skip the first struct.set is a problem (it is a problem because then merging that struct.set into the struct.new would miscompile: the br would happen before the local.set). What this pass does is flow to see if we skip, not flow to see if we are live.
Put another way, we can't just use liveness to see if there is a problem: first we need to flow to find the blocks that skip past the first struct.set. Only there is liveness an issue (and we don't compute it atm as mentioned above).
With all that said, I am unhappy with this code, and have been thinking of how to make it better, but I have not thought of a nice solution, sadly.
Yeah, sorry, I guess I got myself confused about the liveness. I can't think of anything principled to do here short of a full-fledged dead store analysis, ideally using the lattice framework.