readme.markdown

Trying to avoid quadratic work in 1b

(context: WebAssembly/function-references#44)

An idea I've had is to annotate validated branches. The key thing is that the set of validated branch targets is monotonic - just like the set of set locals. That is, once we see that a branch to $b validates, any subsequent branch must also validate, since we can only add more locals that are set. So as an optimization, the validator could track those until the end of the current block. That basically means to handle the set of valid branch targets in a 1a-like manner, and could be a nice speedup on stuff like this:

  (br_if $b ..) ;; Linear time here.
  (br_if $b ..) ;; But constant time here
  (br_if $b ..) ;; and here!

And we could handle this data also in a 1b like manner by adding explicit annotations:

(block $inner (locals_set $1 $2 $3) (brs_checked $a $b $c)
  ..

This block annotates that locals $1,$2,$3 are all set by its exit, and also branches to blocks $a,$b,$c have appeared and been checked. Subsequent brs to those blocks can be done in constant rather than linear time.

This helps, but it doesn't handle splitting of control flow. That is, if identical brs appear after a split, we'd want to do the check once for all of them at the split points. That could be done with additional entry annotations instead of just exit. Yet, even this is not quite enough for a guarantee. Also, we have linear work to validate the brs_checked annotation.

Another path I tried is more traditional compiler liveness annotations. That is:

• local.set starts a live range implicitly. (We can assume that in an optimized binary any dead set would not exist.)
• local.get may or may not end a live range, so we need to annotate the ending of a live range, perhaps using an instruction right after it, say (local.end_live_range $x).

In principle this guarantees at most a linear number of annotations (one annotation per local.get). However, it's not enough since we also need to annotate whether liveness continues at each control flow split, which means quadratic worse cases. Also, br_if taking linear time remains an issue.