Bounded loops in BPF programs

Bounded loops in BPF programs

The Relooper algorithm isn't much better, if at all. Per the original paper, Emscripten: an LLVM-to-JavaScript compiler:

In general though, this is not always easy or even practical – there may not be a straightforward high-level loop structure corresponding to the low-level one, if for example the original C code relied heavily on goto instructions. In practice, however, almost all real-world C and C++ code tends to be amenable to loop recreation.

Of course "almost all" code is amenable because very little code comprises the more critical, performant inner loops and state machines--the parts which often heavily rely on goto.

Arguably if JavaScript had goto there likely never would have been a need to create and rely on the Relooper, and WebAssembly may have turned out differently. Lua 5.2 added a goto construct precisely because it made code generation so much easier. I suspect that eventually much BPF code will be generated from high-level DSLs. Not everybody will be using the same toolchains and libraries, and not having a goto construct is a serious headache when machine generating code. Generating performant assembly from a task-specific, declarative DSL is often trivial; much less so if you now need to implement a relooper or integrate a relooper library.

WebAssembly was originally envisioned as a simple, pure stack-based VM where variable scoping and structured blocks naturally aligned with the overall design. A goto construct was unfathomable. But then WebAssembly got much more complex and the simple stack-based design fell away. I suspect adding a goto construct could have been possible after the original, simpler concept gave way, and I wouldn't rule out its addition in the future. Gotos (including computed gotos) are still very useful in performant C code because optimizing compilers still can't do the job--in real-world code the best switch-statement optimizations still can't come close to idiomatic use of gotos and computed gotos. Like with JIT compiling, microbenchmarks and theoretical optimizations never quite make the transition to the real-world undiminished. Performance demands may still necessitate goto.