Proposal on the spec changes

[aheejin]

Proposal on the Spec Changes

I would like to propose some changes to the current proposal.

Propsed Changes

Try with Relative Depth Argument

try now can have a relative depth argument as in the case of branches. The
'normal' try - a try in which calls unwind to a catch next to the try -
has a depth of 0.

Here are examples. For brevity, only one catch instruction is shown for each
try instruction.

# Example 1
try 0
  throw
catch i         # Control goes here
  ...
end

# Example 2
try 0
  try 1
    throw
  catch i
    ...
  end
catch i         # Control goes here
  ...
end

# Example 3
try 0
  try 0
    try 2
      throw
    catch i
      ...
    end
  catch i
    ...
  end
catch i         # Control goes here
  ...
end

Catchless Try Block

When an argument (relative depth) of a try instruction is greater than 0, its
matching catch block does not have any uses. For example,

try 0
  try 1
    throw
  catch i       # Not used!
    ...
  end
catch i         # Control goes here
  ...
end

In this case, when an exception occurs within try 1 block, the program control
is transferred to the outer catch block. So in this case the inner catch
block is not used, so if we do not generate this kind of catch blocks, it will
help reduce the code size. Effectively, a catchless try block is the same as a
catch with an immediate rethrow. So this code

try 0
  try 1
    throw
  end
catch i         # Control goes here
  ...
end

has the same effect as

try 0
  try 1
    throw
  catch i
    rethrow 0
  end
catch i         # Control goes here
  ...
end

Actually, try 1 would not have a real use, because code inside try 1 would
go to the one-level outer catch, in which case we can just omit try 1 and
place the call inside try 0 outside.

The relative depth argument of try instruction only counts the number of try
nests: it does not count block or loop nests. For example,

try 0
  block
    try 1
      block
        throw
      end
    end
  end
catch i         # Control goes here
  ...
end

In this case, when the throw instruction throws, the control is still
transferred to the outer catch i block, even though now there are two block
nests in the code.

Motivation

Background

In LLVM IR, when a function call can throw, it is represented as an
invoke instruction
which has two successors in CFG: its 'normal' destination BB and 'unwind'
destination BB. When an exception does not occur, the control goes to the
'normal' BB, and when it does, the control goes to the 'unwind' BB. Here is a
couple LLVM-IR level CFG examples:

C++ code:

try {
  foo();
} catch (...) {
}

LLVM IR-like pseudocode:

entry:
  invoke @foo to label %try.cont unwind label %lpad

lpad:
  %0 = landingpad ...
  ...

try.cont:
  ...

C++ code:

try {
  foo();
  foo();
} catch (int n) {
}

LLVM IR-like pseudocode:

entry:
  invoke @foo to label %invoke.cont unwind label %lpad

invoke.cont:
  invoke @foo to label %try.cont unwind label %lpad

lpad:
  %0 = landingpad ...
  ...
  if caught type is int br label %catch else br label %eh.resume

catch:
  ...
  br label %try.cont

try.cont:
  ...

eh.resume:
  resume ...

invoke instructions are lowered to calls in the backend, but they still have
a landing pad BB as their successor. landingpad instructions disappear in the
lowering phase, and the compiler inserts a catch instruction in the beginning
of each landing pad BB.

In terms of control flow, an invoke, or a call lowered from it, is similar
to that of a conditional branch br_if. When a branch is taken, br_if jumps
out of the current enclosing block(s) by the number of relative depth specified
as an argmuent. When an exception is thrown within a function call, the control
flow jumps out of the current enclosing try block. But the difference, in
the current EH proposal, is it can only break out of a single depth, because
call does not take a relative depth as an argument and the VM transfers the
control flow to the nearest matching catch instruction.

Structured Control Flow

To make a control flow structured, there should not be an incoming edge from
outside of a block-like context (block, loop, or try), to the middle of
it. So it is required that the first BB of a block-like context should dominate
the rest of the BBs within it (otherwise there can be an incoming edge to the
middle of the context).

In the CFGStackify
pass,
here is how roughly block markers are placed:

1. For each BB that has a non-fallthrough branch to it (this BB will be where
   end marker will be)
2. Compute the nearest common dominator of all forward non-fallthrough
   predecessors.
3. If the nearest common dominator computed is inside a more deeply nested
   context, walk out to the nearest scope which isn't more deeply nested. For
   example,

   A
   block
     B    <- nearest common dom. is inside this block!
   end
   BB     <- we are processing this BB. end marker will be here
   

   In this case, we can't place a block marker in B. So we walk out of the
   scope to reach A.
4. Place a block marker in the discovered block (the nearest common
   dominator of branches or some block found by the process in 2) and place a
   end marker in BB.

For loops, a loop header is by definition dominates all the BBs within the loop,
so we just place a loop marker there and end marker in the latch.

Problems with the Current Proposal

A try/catch block is divided into two parts: a try part and a catch part.
What we should do for grouping a try part is similar to grouping a block,
because we also want try to be structured.

1. For each landing pad, where catch instruction is
2. Compute the nearest common dominator of all call instructions that has this
   landing pad as its successor
3. If the nearest common dominator is inside a more deeply nested context,
   walk out to the nearest scope that more isn't nested.
4. Place a try marker in the discovered block.
   (Grouping catch part is not covered here because it is not relevant)

The problem is, unlike branches, call instructions do not have a relative
depth argument so cannot break out of multiple contexts. But from the nearest
common dominator to the landing pad it is possible some call instructions that
might throw unwind to outer landing pads (landing pads ouside of the nearest
common dominator of throwing calls ~ current landingpad scope) or do not unwind
to any landing pad, which means when they throw, the exception should be
propagated out to the caller. For example,

try
  try
    call @foo()    # if it throws, unwinds to landing pad 1
    ...
    call @bar()    # if it throws, unwinds to landing pad 2
    ...
    call @baz()    # if it throws, propagates to the caller
  catch i          # landing pad 1
    ...
  ...
catch i            # landing pad 2
  ...
end

Because it is not possible for a call instruction that might throw to specify a
relative depth, or in other words, it cannot specify which landing pads to go,
in the current EH proposal, this does not work.

Why the New Scheme is Better

The only way that can make the current scheme work is to split landing pads
until all the possibly-throwing calls within a try block unwind to the a
single landing pad or landing pads that's in the nested context of the try
block. Minimizing the number of split landing pads will require nontrivial CFG
analysis, but still, it is expected to increase code size compared to when we
use the new proposed scheme above.

Code Size

For a simple example, suppose we have a call that unwinds to an outer landing
pad in case it throws.

try
  call @foo    # unwinds to the current landing pad
  call @bar    # unwinds to outer landing pad
  call @baz    # unwinds to the current landing pad
catch i        # current landing pad
  some code
end

If we split this landing pad, the code will look like the below. Here we assumed
that we factored out the some code part in the original catch part to reduce
code size.

block
  try
    call @foo
  catch i
    br 1
  end
  call @bar
  try
    call @baz
  catch i
    br 1
  end
end
some code

So roughly, when we split a landing pad into n landing pads, there will be n
trys + n catchs + n brs + n ends that have to be added.

If we use our new scheme:

try 0
  call @foo    # unwinds to the current landing pad
  try 2
    call @bar  # unwinds to outer landing pad
  end
  call @baz    # unwinds to the current landing pad
catch i        # current landing pad
  some code
end

In the same case that we should split a landing pad into n, if we use the new
scheme, roughtly we will need to add (n-1) trys and (n-1) ends. (trys now
take an argument, so it may take a bit more space though.)

Easier Code Generation

Generating Wasm code is considerably easier for the new scheme. For our current
scheme, the code generation wouldn't be very hard if we attach a catch
instruction to every call that might throw, which boils down to a try/catch
block for every call. But it is clear that we shouldn't do this and if we want
to optimize the number of split landing pads, we would need a nontrivial CFG
analysis to begin with.

And there are many cases that need separate ad-hoc handlings. For example,
there can be a loop that has two calls that unwind to different landing pads
outside of the loop:

loop
  call @foo   # unwinds to landing pad 1
  call @bar   # unwinds to landing pad 2
end
landing pad 1
...
landing pad 2
...

It is not clear how to solve this case, because, already a part of a try is
inside an existing loop but catch part is outside of the loop, and there are
even another call that jumps to a different landing pad that's also outside of
the loop.

There can be ways to solve this, but there are many more tricky cases. Here, the
point is, the code generation algorithm for the new scheme will be a lot easier
and very straightforward. Code generation for the new scheme can be very similar
to that of block marker placement in CFGStackify. We place try markers in
a similar way to placing block markers, and if there is a need to break out of
multiple contexts at once, we can wrap those calls in a nested try N context
with an appropriate depth N. Optimizing the number of newly added try N
markers will be also straightforward, because we can linearly scan the code to
check if any adjacent try blocks can be merged together.

[binji]

Thanks for explaining this so well, I think I can understand the problem much better now. I believe you (or perhaps @dschuff) mentioned that another solution would be to provide an invoke primitive instead, can you talk a little bit about how that would be worse than this solution?

[aheejin]

@binji Oh, I think I was confused about the code size thing when I was talking about the new scheme in the meeting today. (The code size was an advantage of this new scheme compared to some other alternative, which is the same but in this case try's argument N includes not only try nests but also block and loop nests), So, nevermind that part.

Anyway, the arguments against to that solution are:

1. @dschuff suggested that in case we want to use try/catch to handle hardware traps in the future, we would need to provide an alternative instruction for every possibly-trapping instruction, like,invoke-load, invoke-blah, ...
2. According to @KarlSchimpf, in the V8 implementation, it is OK to have a catchless try (which is proposed here), because it is effectively the same as try with a catch with an immediate rethrow, but it wouldn't be possible to have a tryless catch.

[KarlSchimpf]

I actually support this proposal (with minor tweaks).

In response to @binji, the current implementation allows neither catchless tries, nor tryless catches. However, I think it would not be that hard to add both to V8. The runtime support for these concepts are basically needed even in the current implementation. To handle rethrows, which have a label defining the enclosing try block to rethrow, a stack of possible thrown exceptions need to be kept. This stack should be easy to extend to handle the generalization of labeled try blocks (where the label defines the catch block to apply if an instruction (like a call) throws).

The minor nit is the numbering of try blocks. I would prefer the use of block nesting to be consistent with other uses of labels (including rethrow).

[aheejin]

@KarlSchimpf The reasons I chose to only count try nesting levels are

1. There are going to be invalid depth arguments. For example, in the code below, the second try cannot have 1 as an argument because its outer level is not a try but a block.

try 0
  block
    try 1        # 1 is an invalid argument here
      throw    # Where should this go?
    end
  end
catch
  ...
end

2. More importantly, it will increase code size. Suppose that all the calls to foo, bar, and baz should land on the outermost catch block when an exception is thrown.

try 0
  block
    call @foo()
    block
      call @bar()
      block
        call @baz()
      end
    end
  end
catch                # All the calls should land here if an exception is thrown
  ...
end

If we count all the block nests, the code will look like this:

try 0
  try 2
    block
      call @foo()
      try 4
        block
          call @bar()
          try 6
            block
              call @baz()
            end
          end
        end
      end
    end
  end
catch                # All the calls should land here if an exception is thrown
  ...
end

Do you think it makes sense?

[rossberg]

I understand the motivation for this proposal from the point of view of a CFG-based producer. However, from a language perspective its implications are a bit more profound than may be apparent at first.

One of the defining characteristics of structured exception handling is the following. If you have a program, and pick any instruction sequence instr* in it, then you can wrap that into a handler,

try instr* catch … end

and you are guaranteed that any exception produced by instr* will be caught by the handler. That sort of composability is what makes it structured. It is important to observe that this proposal destroys that basic property: you can now throw exceptions such that they bypass surrounding handlers: plainly, try N throw end is a throw that ignores the innermost N (lexical) handlers at will, thereby inverting authority over who handles what.

In particular, it is not true that this form of try is just equivalent to a try with a rethrow, as suggested in the motivation. A rethrow by itself cannot bypass intermediate handlers (those would need to “consent” by ways of being transformed themselves).

Another view on the proposal is that it introduces a new form of control transfer that is neither a branch nor a throw. An instruction like

try N instr* end

essentially means

try instr* catch_all (br_to_try_with_current_exception N) end

There are several things that are special about this new form of “branch": it can only occur in a handler, it can only target a try block, and it magically takes an “unhandled" exception with it.

Introducing a new form of control transfer is not a small thing, especially when it is rather special-cased and has no precedent in existing languages. It is not immediately clear how it will interfere with other possible extensions, how it affects transformability of Wasm code itself, and to what extent the loss of structure makes reasoning more difficult.

I think it will take some time to properly investigate and understand the semantics, implications and trade-offs of such a proposal, and be confident that it doesn't paint us into some corner. To be honest, right now I wouldn't feel quite comfortable with it just yet (you probably have guessed so by now :) ).

Out of interest, were there other possible solutions that have been discussed? On a higher level it seems like the underlying motivation here is to work around limitations on the way the “current exception” can be used in the exception proposal: it is always scoped implicitly to a catch block and cannot escape it — if it could you might be able to use conventional branches and nested blocks. Perhaps there are ways to relax that without resorting to control-flow extensions?

FWIW, I agree with @KarlSchimpf that the immediate should be an ordinary label -- consistency is important (I didn't understand the code size argument -- how does the indexing scheme affect it?). I also think that this new form should be a separate instruction from an ordinary try, so that it would not have catch blocks by construction, and you avoid the off-by-one discrepancy with its immediate compared to other labels (where 0 refers to the innermost enclosing one).

[aheejin]

Thank you very much for comments. Currently I'll try to work around the problem
with the existing spec. It will basically be going to simulate the proposed spec here
with the current spec.

Original problematic code: (which is not valid)

try
  try
    call @foo       # if it throws, unwinds to landing pad 2
  catch             # landing pad 1
    code_1
  end
catch               # landing pad 2
  code_2
end

Proposed spec in this issue:

try
  try
    try 2
      call @foo     # if it throws, unwinds to landing pad 2
    end
  catch             # landing pad 1
    code_1
  end
catch               # landing pad 2
  code_2
end

Workaround 1: (in pseudocode)
Wrap calls that unwind to an outer landing pad with an additional try, set a
local 'depth' appropriately, and add depth-checking code to each outer try until
it reaches the correct try.

try
  try
    try
      call @foo    # if it throws, unwinds to landing pad 2
    catch
      depth = 2
      rethrow
    end
  catch             # landing pad 1
    if (depth > 0)
      depth--
      rethrow
    code_1
  end
catch               # landing pad 2
  code_2
end

Workaround 2: (in pseudocode)
Wrap calls that unwind to an outer landing pad with an additional try, stores
the caught exception object (which is on top of stack at the start of a catch
block) to a local, factor out the code in the outer catch block (code_2 in
this example), and add branches to both a newly added inner catch and the outer
catch that was supposed to be the destination of the call.

block $label0
  try
    try
      try
        call @foo
      catch
        exn = current exception
        br $label0
      end
    catch
      code_1
    end
  catch
    br $label0
  end
end
code_2 (use exn here)

As can be seen, both workaround 1 and 2 are expected to incur code side
increases. But it looks like at least it can be done without the spec change.
I'll try to experiment with one of these workaround and estimate the code size
increase compared to the proposed spec, and if it's too large, I guess maybe we
can talk more on this proposal.

[eholk]

@rossberg - I want to make sure I fully understand your argument structured try with a label is unstructured. Would a similar argument also apply to blocks and br? Isn't wrapping an arbitrary sequence of instructions in a block also not something that can be done in general, without renumbering inner breaks?

The difference seems to be that with wrapping instructions in a block, it is straightforward to modify the body to preserve the existing behavior or create the intended behavior. In wrapping instructions with a try, it's not clear how you should renumber the inner tries. Presumably you are adding the new try because you want your handler to run, so you should cap the inner tries at the new level, but this is likely to break other things.

Is that the key distinction?

[rossberg]

@eholk, yes, that's one perspective. Inserting a block may require shifting some indices, but that is merely a (alpha-)renaming that keeps all structure as is. Inserting a try that works "as expected", however, generally requires structural changes to the wrapped instruction sequence under this proposal.

This isn't necessarily a show stopper, but it is a significant change that requires careful consideration and modelling IMO.

I kind of see why this is desirable, though. In a way, it fills a hole in the "control flow matrix": currently, an instruction can have (1) a regular or (2) an exceptional result, and an instruction can pass on results to either (A) to its implicit continuation, or (B) an explicit continuation. But in fact, only regular results can be passed to an explicit continuation, via branches. That is the 1B combination. This proposal adds the missing 2B -- it is a bit funny, and I'm not aware of any precedent, but it might still be reasonable.

Here is how I would reframe this feature. Leave the existing try alone, and add a new block instruction, strawman syntax:

try_br $label  instr*  end

This executes instr* and falls off the end when terminating normally. When throwing, it will transfer exceptional control to the end of the block referenced by $label, essentially rethrowing the exception there. Consequently, if the targeted block is a try, it will end up passing control to the appropriate handler (if any); otherwise it will just continue propagating the exception from there, skipping intermediate handlers. (Note how this semantically decouples the statement from any concrete catch mechanism and makes any label in scope legal.)

[rossberg]

An even simpler and more flexible option would be to merely add a label to rethrow, meaning that it would reraise the exception in the targeted block. Then the above can be expressed as

try  instr*  catch_all rethrow $label end

The current rethrow semantics is equivalent to rethrow 0.

Such an instruction can be compiled exactly as the original proposal in the case where the label denotes a try block.

[eholk]

@rossberg - One idea I was thinking of yesterday seems in line with your try_br proposal, but also combines it with exception values on the stack. Basically, try would take a label, which becomes the exceptional control flow target. On an exception, there would be an exception value on the stack, meaning instead of catch blocks we just have regular blocks with type exception.

It sounds like a key requirement for @aheejin is to be able to rethrow an exception from outside the try block where it was caught. Having exception values is one way to do this, but it does seem to come with some cost in the VM (although I think in V8 we are already paying this). It seems like the rethrow $label idea might work too; basically, you'd rethrow to an outer block where you would catch the exception again. Would that work?

[rossberg]

@eholk, yes that's the idea. Plus, the compiler can trivially recognise the common case where the target is a try block, such that it can generate code to jump to the outer handler directly instead of actually rethrowing.

[aheejin]

@rossberg Thank you for the suggestion. But isn't it basically the same as try N proposal? The difference seems yours uses not a relative depth but a label as an argument. But if we recall how br and br_if are structured, they use labels in wast files, but they become relative depth immediates in the real binary files. For example,

In s2wasm-style wast file:

block $label0
  br $label0
end

In the real encoding, this becomes

block
  br 0
end

[aheejin]

@rossberg Oh but I like the idea of a separate try_br instruction, because that way we don't need to add the immediate 0 for normal trys, so it can save the code space.

[rossberg]

@aheejin, well, yes, just using a symbolic label for exposition. Point is, it works like any regular label index, especially with 0 referring to the enclosing block. Also, it can target any block, not just try.

But I would actually like to draw attention away from try_br and to the second proposal: just adding a label to rethrow. That is much simpler and more focused an extension.