goto in WebAssembly can be tricky

本站添加: 2026-05-15

[00:00:00]Hello internet. Um, so today I wanted to talk about how to implement go-to's in WebAssembly.

[00:00:06]So the thing about go-to's is that in more traditional assembly architectures, you're able to put a label and you have you can have jump instructions basically anywhere that jump to those labels.

[00:00:19]Uh but in WebAssembly, you don't have that.

[00:00:23]Uh basically, you have two two constructs, right? You have the block where if you branch from a block, you get you you go to the end. Essentially, it's like breaking out of a loop in C.

[00:00:34]Or is a loop where when you branch, you you go to the top.

[00:00:40]Right?

[00:00:41]Um So yeah, so like going through a simple example of how how it works. You You see the instructions lined up on the right side.

[00:00:49]Uh Right, so you have block and loop, right? Uh so like when you have a while loop, you need to be able to go up, right? Go go back at the end of the while loop to to the top. Uh the way that you achieve that is you you create a loop block and then you have a a branch instruction that will take you to the to the top of the uh the the loop.

[00:01:09]Uh alternatively, like when you're in test after you've tested your condition, you want to be able to jump if your condition has failed, right? So you you can test your condition here and then you conditionally branch.

[00:01:22]Uh and then when when you branch from there, you have the the uh the blocks uh construct here uh kind of wrapping the whole thing and then you exit the the the the entire block.

[00:01:34]Now, like go-to's by themselves actually are not so bad to model, right?

[00:01:41]If you like the problem actually arises when you interact when they start interacting with other things, but by themselves, conceptually, this is all you really need to do. When you do a go-to uh that jumps forward, it's essentially the same thing as wrapping a the thing the thing you need to jump into uh in a while loop and then the go to is kind of like the break. You're breaking out of that that while loop and then uh as long as the end of your while loop matches where the label is uh you you've got your go to, right? And you have the other thing as well. Um if you need to have a a go to that jumps to uh somewhere earlier in the code then really what you have is a continue, right? As long as the start of your while loop matches the start of the start loop.

[00:02:29]Uh but yeah, so you might actually be asking like sure, you could in those simple examples you could use a while loop to to, you know, kind of basically jump the way that a go to could.

[00:02:41]But like aren't there like a whole bunch of crazy ways that you can you can like combine go tos uh that make it basically impossible to do that? And the answer is yes, right? So so you have this sort of example uh where you have a go to um uh B where you have multiple places where where you uh where you jump forward to a label B.

[00:03:05]And then you have a a a label A and then you have a you have a go to that jumps backwards to to label A.

[00:03:12]Right?

[00:03:14]Essentially like uh you know, if you try to directly map this code into the the while analogy you essentially need a situation where you need to break out of a loop that you have not started yet.

[00:03:29]And you need to continue back into a loop that you've already exited.

[00:03:35]Right? Like this doesn't work, right?

[00:03:37]Fundamentally. So so um how do you solve that, right?

[00:03:42]Uh and there's another case where it's like okay it actually is possible to to use this while loop trick but you you actually do have need to rearrange a little bit, right? So if you think about it like in this example, you have a go you have go twos that go go forward. Fine, there's only one label here, so you might think oh okay, I can have a while loop. But the problem is that the label is nested inside of of another block, right? So you really have to jump across blocks from this if branch into the else branch, right? This turns out to be relatively common of a construct and see in real code.

[00:04:25]And yeah, like you you have this impossible situation where like I need to somehow construct a while loop where like breaking out of the loop will will get you to jump into a scope that opens inside your body, but also needs to end outside of your body, right? Like that's that's not going to work.

[00:04:47]So okay, so for this case, this is what my compiler does. My compiler will detect it has to be somewhat conservative about it, but it will detect that you know, okay, this is actually pretty safe to move around. And if it's safe to move around, I'll hoist it out so that the go to actually lands at a location that is outside the scope of so so that you really don't need to cross scopes when you do the jumps.

[00:05:17]Okay, so we talked about a couple things.

[00:05:20]Reducible but tricky, that's the example we just saw.

[00:05:23]Yeah, so we'll try best effort, but if if that fails, I'll fall back to the irreducible case.

[00:05:29]In the irreducible case, uh you can still implement it using a giant while and switch loop, right? So essentially the idea kind of looks like this, right? Um this function is chunked up into pieces.

[00:05:44]You can see like the x equals one section here uh to case four, x = 2 section here with starting with label B maps to uh section three. So, like the entire function is chopped up into pieces.

[00:05:58]Um and then each piece becomes a a little segment under the switch. This This approach essentially allows you to like implement any sort of go to. But But the problem with this is that it's quite It's actually very inefficient. You know, um it kills performance and it bloats your code and it's just Honestly, it's a little bit ugly.

[00:06:20]Um okay, so like just as just I think just to cover when we're on this topic it's just kind of fun to cover uh Duff's device. Um but yeah, so the fun thing about Duff's device is that you have a switch statement where you have a So, you start with a switch statement, but you have a do while loop that kind of like like intermingles with the switch cases in such a strange in a in a bit of a strange way.

[00:06:49]Um so, you think like, "Oh, wow. Is this even valid legal C?"

[00:06:54]It It turns out it is. It is legal [laughter] C.

[00:06:58]Uh the state machine actually can handle this as well. So, uh if you try to compile this with uh Duff's device with my compiler, you get a giant state machine. While not the prettiest thing, uh it it will still compile and it will still uh It'll handle It'll handle the the code.

[00:07:16]Uh as a part of this, I thought it was kind of interesting to be able to demo the way that um the compiler will transform the code.

[00:07:23]So, as you can uh So, I extended the the disassembler to actually allow not fully compiling, but have the compiler just uh do some of the lowering passes that converts the code into to uh uh a more WebAssembly friendly form.

[00:07:41]And uh like like this one where uh we saw earlier.

[00:07:45]Uh so uh to make it easier to kind of visualize kind of what's happening.

[00:07:50]Uh yeah, and the code for this is available in in the C C compiler repository.

[00:07:56]Uh but yeah.

[00:07:58]I hope that was interesting. Um I thought it was interesting. I thought it was interesting. I don't know.

[00:08:05]I don't know.