How to implement delegate's target

[aheejin]

The following is the new instruction delegate's semantics, taken from my LLVM CL's comment:

Linearizing the control flow by placing TRY / END_TRY markers can create
mismatches in unwind destinations for throwing instructions, such as calls.

We use the 'delegate' instruction to fix the unwind mismatches. 'delegate'
instruction delegates an exception to an outer 'catch'. It can target not
only 'catch' but all block-like structures including another 'delegate',
but with slightly different semantics than branches. When it targets a
'catch', it will delegate the exception to that catch. It is being
discussed how to define the semantics when 'delegate''s target is a non-try
block: it will either be a validation failure or it will target the next
outer try-catch. But anyway our LLVM backend currently does not generate
such code. The example below illustrates where the 'delegate' instruction
in the middle will delegate the exception to, depending on the value of N.
try
  try
    block
      try
        try
          call @foo
        delegate N    ;; Where will this delegate to?
      catch           ;; N == 0
      end
    end               ;; N == 1 (invalid; will not be generated)
  delegate            ;; N == 2
catch                 ;; N == 3
end
                      ;; N == 4 (to caller)

So delegate's immediate field can target all control flow structures including blocks and loops, like brs. But if the target is block or loop, it will be a validation failure. When it targets a try, it is really targetting not try but its catch.

Then here comes the catch: Currently if and try do not take label names; they use wrapping blocks or inner blocks to achieve the same semantics, mostly because there are too many places to handle if we add a new control flow structure that can have a label. But if we want to give delegate a label, it should target a try (more precisely its catch), and if it targets a block, it will be a validation failure. But I'm not sure if we want to give try a label and add its handling in a bunch of places, which is exactly what we wanted to avoid when we implemented if and try this way.

We are already doing some ugly things to implement try-catch.

1. We create an inner block within catch, but we assume that block is removed when we print the text/binary. The reason it should be removed is catch body should start with a pop instruction (or a value on the stack in binary), and block should not interfere in between. This is easily done when there's no branch that targets the inner block.
2. When there is br 0 within a catch, we wrap the whole try-catch with a block and make the br target it, not the inner block within catch, for the reason I described in 1. (Fix inner block problem with 'catch' #3129)

We can probably do a similar thing for delegate's target... Like, wrap the target try-catch with a block and make delegate target that instead, and we delete that block when we write the binary/text...? But unlike the wrapping block we created for br, delegate targetting a block is a validation failure and it must be removed when we write that out. Also in this case we should maintain the relationship between the wrapping block and try for the whole optimization pipeline, i.e., no other instruction should interfere between them and the block should not be removed.

Not sure what is the cleaniest way. Any ideas?
@kripken @tlively

[kripken]

What happens in the case of N == 2 in that example, where the nested delegate targets the outer delegate? Does it simply continue to run from the outer delegate's position? And what does that outer delegate do when reached normally - is it the same as delegate 0? Or are delete N and delegate two fundamentally different instructions, one that sends and one that receives..?

(delegate is not in the EH overview so I'm not sure where to read about it?)

[tlively]

One option would be to give try expressions labels that don't participate in normal branching. So for normal branches to the end of a try, you would still need to wrap it in a block, just like we do with if-else. All code that only deals with normal branching would be able to ignore the try labels, which would be used only by code dealing with delegate. I don't know how much that would help in practice, but that's the best I've come up with so far.

[aheejin]

@kripken

(delegate is not in the EH overview so I'm not sure where to read about it?)

Sorry I should've been clearer. This instruction was named catch_br when I presented it in the CG meeting but later renamed to delegate. Its informal semantics is written here: WebAssembly/exception-handling#137, which was not merged yet. But what I wrote in this issue description is actually more detailed.

What happens in the case of N == 2 in that example, where the nested delegate targets the outer delegate? Does it simply continue to run from the outer delegate's position?

It goes to the outer delegate. The outer delegate should also have its own immediate argument (though not written in this comment), so it will be transferred from there using the same rule.

And what does that outer delegate do when reached normally - is it the same as delegate 0? Or are delete N and delegate two fundamentally different instructions, one that sends and one that receives..?

(You mean not delete but delegate right?)
Sorry, delegate always has an immediate argument. I just didn't write that in the outer delegate, which made it confusing. And delegate cannot be reached normally. It is kind of an EH pad. In the MVP spec,

try
  ...
delegate N

is similar to

try
  ...
catch_all
  rethrow to somewhere (currently rethrow can only rethrow to the immediate outer scope, but delegate can bypass scope by its argument N)
end

[kripken]

Thanks!

Can a try have both catches and a delegate? That is, is this possible? (I don't see such an example here or in the links)

try
  ...
catch ...
  ...
delegate N

[aheejin]

@kripken No a try can only have either catches or a delegate.

[kripken]

I see, thanks. So is it accurate to say that a delegate targets a try, really, and not a catch or a delegate? (As I think one cannot target a specific catch of a try's catches? So if an exception is delegated to a try, we go through the catches one by one as if it were thrown in that try originally?)

edit: to be clear, I'm not sure I follow

But if we want to give delegate a label, it should target a try (more precisely its catch),

can catch be replaced with catches?

[kripken]

If that's correct, then I think I understand the semantics. And then I think we should maybe add a label to try - not a normal block label, but a new kind of identifier, that is only used in try and in delegate, to connect them.

The other options worry me, in particular we have optimizations that want to optimize out blocks or move them around. Furthermore, adding a block that cannot be removed would not model the binary size as well, since it would not appear in the output.

[aheejin]

I see, thanks. So is it accurate to say that a delegate targets a try, really, and not a catch or a delegate?

Semantically, delegate only targets catches or another delegate.
The reason I somewhat described like it targets try is when writing wast files and also in the internal representation of Binaryen in which branch-like instructions has Name as a target, only try (or a block wrapping try has a label) but not a catch. I don't think we can add a label in catch in the wast files...

The reason we made it also target block ends, which is a validation failure, is because VM people thought it would be convenient to not maintain a separate EH pad stack; this way they can use the stack they use to calculate branch depths the same.

(As I think one cannot target a specific catch of a try's catches? So if an exception is delegated to a try, we go through the catches one by one as if it were thrown in that try originally?)

Yes you're correct. It cannot target a specific catch within a group of catches within a try. It can only target a group of catches within a try as a whole.

edit: to be clear, I'm not sure I follow

But if we want to give delegate a label, it should target a try (more precisely its catch),

can catch be replaced with catches?

Yes. Sorry that my initial description was not very precise.