Proposed spec changes + rethrow question

[aheejin]

I did a presentation on why we need some spec changes to be extensible to future two-phase unwinding on 8/18 CG meeting: slides

I pre-uploaded slides on the spec changes I am planning to propose in the next week's 9/15 CG meeting: slides

This is basically the same as what I discussed in #123. The changes consist of:

• Restore the first version of the proposal
• Add catch_br instruction
• Add try-unwind instruction

If you have any feedback or comments, I'd appreciate them.

Also, I'm not sure if we still want the immediate argument of rethrow in the first version of the proposal. rethrow used to have an immediate argument that specifies which exception in the current EH pad stack to rethrow. I don't have a use case for this in C++, but other languages might need it, so if people have any opinions on keep this or not, I'd appreciate that.

[dschuff]

I agree that we should do this. The presentation and previous discussion show why, but here's my tl;dr version if it's helpful:

The 2 reasons we originally had for moving to use exnref were 1) Allowing the reference to escape the catch block was the way we solved the unwind mismatch problem, and 2) we thought exnref/event design would extend simply to resumable exceptions. However, as @rossberg developed the concept for resumable exceptions, they ended up being a separate mechanism rather than a simple extension. And, as @aheejin described in her presentation, the way we used exnref to solve unwind mismatches breaks 2-phase unwinding. So that invalidates both of the reasons we had for exnref, and furthermore I think a method without exnref is more likely to be easily compatible/composable with the various options that are currently on the table for stack-switching and other related functionality.

I think getting consensus on switching away from exnref is the critical thing (that's item 1 in @aheejin's list above). The proposed way to solve the unwind mismatch problem is catch_br but the exact name and semantics of that mechanism can be tweaked. And this proposal is also agnostic to the exact way we end up implementing the first phase (it can be straightforwardly extended to include a first phase, but it would also work to use a stack-switching mechanism). So we should be clear that we aren't committing to a mechanism yet.

[dschuff]

(also direct ping of some folks who've expressed opinions or participated in discussion previously: @rossberg @RossTate @ioannad @lukewagner @takikawa @fgmccabe @tlively @conrad-watt @KronicDeth @taralx)

[taralx]

I find the example in the slides a bit confusing. Why would you not move callB out of the catchA block?

[KronicDeth]

I also am confused the same as @taralx.

I assumed the example was just an oversimplification to fit it all in a slide and there is some pattern where the try can’t surround just the one call.

[aheejin]

@taralx

I find the example in the slides a bit confusing. Why would you not move callB out of the catchA block?

Yes, that example is an oversimplification for the presentation purpose. There are cases that callB cannot be moved out of the inner catch.

The below is a portion from a real CFG. It looks a little complicated, but other than BB names are long and cumbersome (because it is from a real application), it is not that bad. This is just to show this kind of CFG exists, so people who aren't interested can skip it.

In this example,

• BBs encleanup54 and ehcleanup59 are EH pads, and catch instruction will be placed in the beginning of them.

• If any instruction from BB for.body.i.i.i.i.preheader.i.218 throws, we should unwind to ehcleanup59.

• If any instruction from BB for.body.i.i.i.i.preheader.i.247, for.body.i.i.i.i.preheader.i.283, or _ZN10PixelArrayIhED2Ev.exit163 throws, we should unwind to ehcleanup54.

• For ehcleanup54's catch instruction, its corresponding try should be placed in _ZN10PixelArrayIhE6ResizeERK16PixelArrayFormathi.exit (the top BB in the picture), because it is the nearest common dominator of all ehcleanup54's predecessors (for.body.i.i.i.i.preheader.i.247, for.body.i.i.i.i.preheader.i.283, and _ZN10PixelArrayIhED2Ev.exit163).

• ehcleanup59's catch's corresponding try should be placed in _ZN10PixelArrayIhE6ResizeERK16PixelArrayFormathi.exit too, but above ehcleanup54's matching try.

• The only possible sorting order is for.body.i.i.i.i.preheader.i.218 -> for.body.i.i.i.i.preheader.i.247 -> ehcleanup54 -> ehcleanup59, because of dependence edges.

• Now the instruction order is

try      ;; _ZN10PixelArrayIhE6ResizeERK16PixelArrayFormathi.exit / matching 'catch' at ehcleanup59
  try    ;; _ZN10PixelArrayIhE6ResizeERK16PixelArrayFormathi.exit / matching 'catch' at ehcleanup54
    ...
    code for for.body.i.i.i.i.preheader.i.218  ;; unwind destination mismatch!
    ...
    code for for.body.i.i.i.i.preheader.i.247
    ...
  catch  ;; ehcleanup54
  end
catch    ;; ehcleanup59
end

• Now, even though for.body.i.i.i.i.preheader.i.218 should unwind to ehcleanup59, it ends up being caught by ehcleanup54.

This is an example of "unwind mismatch problem".

[taralx]

For ehcleanup54's catch instruction, its corresponding try should be placed in _ZN10PixelArrayIhE6ResizeERK16PixelArrayFormathi.exit (the top BB in the picture), because it is the nearest common dominator of all ehcleanup54's predecessors (for.body.i.i.i.i.preheader.i.247, for.body.i.i.i.i.preheader.i.283, and _ZN10PixelArrayIhED2Ev.exit163).

I don't understand here. While it is true that this is the nearest common dominator, this CFG is irreducible even without the exception paths. So it's going to undergo rewriting, and any decision about where to put the try would have to be made after that rewriting.

Is it possible to distill this into a case with a reducible CFG and exception mismatch?

[aheejin]

@taralx Can I ask why this is irreducible? Currently our backend, which has our own pass for fixing irreducible CFGs, does not seem to rewrite this. I also tried LLVM's target-independent pass for fixing irreducible CFG and it doesn't seem to change the CFG either.

[taralx]

You're right, not irreducible. But still seems ok after lowering:

try      ;; _ZN10PixelArrayIhE6ResizeERK16PixelArrayFormathi.exit / matching 'catch' at ehcleanup59
  ... if
    code for for.body.i.i.i.i.preheader.i.218
  end
  try    ;; _ZN10PixelArrayIhE6ResizeERK16PixelArrayFormathi.exit / matching 'catch' at ehcleanup54
    ...
    code for for.body.i.i.i.i.preheader.i.247
    ...
  catch  ;; ehcleanup54
  end
catch    ;; ehcleanup59
end

[aheejin]

@taralx Not sure what you mean by 'lowering'. encleanup54's corresponding try cannot be placed after for.body.i.i.i.i.preheader.i.218, because the nearest common dominator of all ehcleanup54's predecessors is _ZN10PixelArrayIhE6ResizeERK16PixelArrayFormathi.exit, which has to precede for.body.i.i.i.i.preheader.i.218. Also I'm not sure how the if you placed before for.body.i.i.i.i.preheader.i.218 is supposed to work.

The reason try should be placed in the nearest common dominator BB of all predecessor of an EH pad is, otherwise there will be an incoming edge into the middle of a try. (This is the same for block placement.) In this CFG, suppose we place ehcleanup54's corresponding try right after for.body.i.i.i.i.preheader.i.218, as you suggested. But all three of ehcleanup54's predecessors can be reached without first reaching for.body.i.i.i.i.preheader.i.218, i.e, for.body.i.i.i.i.preheader.i.218 does not dominate ehcleanup54 and its predecessors. Where try is placed should dominate the corresponding EH pad; otherwise there should be an incoming edge that jumps into the middle of a try.

[aheejin]

cc @backes too

[taralx]

Here's my problem. If I try to convert your CFG into wasm, I get to this point:

call _ZN10PixelArrayIhE6ResizeERK16PixelArrayFormathi.exit
if
  call invoke.cont
  if
    call for.body.i.i.i.i.preheader.i.i218
    call invoke.cont16.thread
    if
      call if.end.i242.thread

And now what? I said "irreducible" earlier, but that was the wrong word -- it's not in a structured flow form.

[RossTate]

@taralx You can use block and br/br_if to encode this CFG (or any DAG) in wasm (ignoring exceptions).

[aheejin]

@taralx
As @RossTate said, we currently only generate br/br_if in in LLVM backend and does not use if. This does not necessarily mean the CFG cannot be lowered to wasm using if; I'm just explaining the status quo in our LLVM backend. Other tools, like Binaryen, creates if when necessary for optimization later.

And those long names in the CFG are BB names, and not function names, and each BB can have any number of instructions, including calls. The technique of placing try or block in the nearest common dominator works well when we use br/br_if. One slide in my first presentation gives a taste of what it looks like:

The algorithm is called CFG stackification, and the full code is here just in case you are interested, but reading this is not necessary for this discussion at all.

Maybe there exists a complicated general algorithm that can convert all CFGs that causes this mismatch problem so we don't need catch_br. But I don't know what that algorithm is, don't even know if that exists, or it will be compatible with our LLVM backend algorithm. Adding catch_br solves this in an easy way.

[taralx]

Ah, I see, this is an artifact of how LLVM converts its CFG, not an inherent limitation of the current model in wasm. FWIW, the Dream decompiler has an algorithm that reconstructs structured control flow from an arbitrary CFG. Importantly, it does so by constructing boolean predicates that can be used to linearize complex flows. That's where that if statement came from in my earlier comment.

[aheejin]

@taralx While our LLVM backend's CFG stackification isn't the only way to make structural control flow, I'm not sure other more powerful algorithms like you pointed out can solve our problem without any spec changes (if we remove exnref). (By the way, Binaryen's Relooper is also an algorithm that takes arbitrary CFG and transforms it into structured code.)

The restriction here is, try-catch and call are much more limited in their descriptive abilities than normal control flow: br, br_if, and if-then-else. Those powerful algorithms make use of direct branches (br and br_if) and ifs, which try-catch don't have. try is a big code block within which all call instructions that throw have to unwind to a specific catch. And unlike branches and ifs, calls don't have destinations specified in them. Where we should unwind to when a call throws is implied by the surrounding try-catch and not directly encoded as in the case of branches.

The currently proposed solution is one way to fix this, and we also think it can be a small addition to the first version of the proposal. But maybe there can be other alternative solutions, such as

• Create invoke instruction, which takes an unwind destination.
  • Cons: More code size. Also we should make invoke for every single call instruction, such as call, call_indirect, return_call, return_call_indirect, ..
• Split try and catch, and allow multiple try blocks can target a single catch block in arbitrary location.
  • Cons: More pervasive changes to the current model.
• ... and possibly more

What I'd like to say is, the unwind mismatch problem itself will very likely to be present even outside of out LLVM backend, as long as someone tries to convert a CFG, basically BB soup, to a linearized wasm. The specific solution we proposed might be more suited to our LLVM backend, but I think other compilers can easily make use of it too.