tableswitch case labels?

[kripken]

While implementing tableswitch in wasm-emscripten, I realized that cases have labels. Can they be br-ed to? Asking @sunfishcode , there wasn't an obvious answer, so this looks unspecified, opening this for discussion.

• One option is no, one cannot br on the labels of cases. But one can do so on the switch itself to exit it.
• Another option is yes, but then what does the br do? Normally a br to name: {} gets to right after those {}. But @sunfishcode said he thought maybe it should go inside. In other words, inside switches, case blocks could goto to other case blocks?

[titzer]

I think they should work like an implicit block around each case; i.e. one can only br out of them from inside that block. The reasoning for that is that one can already arrange the cases to fall through to each other and the indirection of the table up front can allow sharing of cases.

[AndrewScheidecker]

case can be defined as syntax sugar for nested blocks, right? That's the approach that makes the most sense to me. That means that they can be targeted by br, but only from preceding cases, and the label introduced by case denotes the beginning of the case's expression rather than the end.

[sunfishcode]

@AndrewScheidecker's suggestion has the advantage of handling the case in C where one writes goto to jump from one case to another. We still wouldn't support the irreducible control flow case, but we could support more reducible cases directly this way.

[kripken]

When trying to branch to a later case, though, we are doing something we can't do otherwise, if I am not mistaken? We can't do the following, can we:

block A {
  branch C;
}
block B {
}
block C {
  ..
}

?

If I'm not confused here, then that means that tableswitch has multiple special powers - not just a jump table that we switch on, but also basic-block-like cases that can branch to each other (even if just forward). That seems like an odd mixture of a lot of separate stuff to me.

[titzer]

On Mon, Nov 2, 2015 at 6:15 PM, Alon Zakai [email protected] wrote:

When trying to branch to a later case, though, we are doing something we
can't do otherwise, if I am not mistaken? We can't do the following, can we:

block A {
branch C;
}
block B {
}
block C {
..
}

?

If I'm not confused here, then that means that tableswitch has multiple
special powers - not just a jump table that we switch on, but also
basic-block-like cases that can branch to each other (even if just
forward). That seems like an odd mixture of a lot of separate stuff to me.

I agree. I think a tableswitch should be just that, with the ability to
fallthrough, but not to jump arbitrarily far forward. AFAICT that last
ability is not necessary to implement, e.g. a C-style switch.

—
Reply to this email directly or view it on GitHub
#439 (comment).

[sunfishcode]

Ok. I'm ok keeping it simple for now. Producers can "stackify" for cases reached by goto. I'll prototype this and report back if there are any complications.

[rossberg]

I just created #443, as discussed earlier, which avoids this question.

[AndrewScheidecker]

When trying to branch to a later case, though, we are doing something we can't do otherwise, if I am not mistaken? We can't do the following, can we:

block A {
  branch C;
}
block B {
}
block C {
  ..
}

A tableswitch's cases would desugar to blocks more like this:

block C {
  block B {
    block A {
      branch C;
    }
  }
}

I thought the original reason for tableswitch having cases instead of only branching to external labels was to reduce the nesting level for parsers (and humans)?

[sunfishcode]

I created #444 to address the wording concerns here.

@AndrewScheidecker For my part, I'm looking to keep things simple for now. I expect producers will be able to translate C switches with gotos between the cases with stackification -- I haven't implemented it yet, but I don't anticipate major complications. Once the binary format prototyping progresses more, it will be easier to experiment and demonstrate advantages of various variations that we might make.

[ghost]

Could you explain what 'stackification' means here? How did it work our? Might it be possible to just include two tables, one for the switch entry targets and another to encode the exit paths for each case, and then to verify that they meet the requirements for a single pass SSA parser, making it a validation error if they don't.

[sunfishcode]

Stackification is what I've been calling the technique for converting arbitrary acyclic control flow into nested blocks with labeled breaks / branches. In JS-style syntax:

  L4: { L3: { L2: { L1: { L0: {   // stack up a bunch of blocks to use
  now();
  we();
  get();
  arbitrary();
  acyclic();
  code();
  }
  with();
  }
  labels();
  inserted();
  }
  wherever();
  }
  we();
  want();
  }

Syntactically it looks funny, but it directly corresponds to a valid form in JS, so it satisfies whatever constraints we may have from that. There's a risk that if we stack up too many blocks, it could cause problems for strictly recursive parsers, but if producers can eg. make effective use of tableswitch cases for most things, it shouldn't be a big problem in practice.

In terms of the binary encoding, it's not entirely optimal if taken literally, but that's something that can be refined.

[sunfishcode]

The original issue here was whether cases can be branched to from arbitrary branches. The current design is that they cannot, and this is now clarified in the documentation.

[ghost]

Thank you for the explanation. So it looks like any DAG dominated by a switch could be encoded this way, sorting the DAG and emitting nested blocks in the sorted order with the switch-table emitted first. This would seem to handle a switch with multi-way goto's in the cases so long as this created no loops. Cool idea, and seems worthy of a note somewhere, if I understand correctly.