optimize state machine inside loop into computed goto

[andrewrk]

Related issues:

• removal of goto
• introduction of labeled break, labeled continue

One remaining use case for computed goto is performance. This pattern:

const State = enum {
    one,
    two,
};
while (true) {
    switch (state) {
        .one => {
            state = .two;
        },
        .two => {
            // ...
        },
    }
}

Here the code relies on setting the state variable and a loop iteration. In C the code could directly goto another switch label. In Zig this is not available, and the code generated is worse than in C due to the optimizer's inability to detect this pattern.

Upstream bug, reported by @shawnl: https://bugs.llvm.org/show_bug.cgi?id=39043

Potential solutions include:

• (ideal) send upstream patch to LLVM making it able to detect this pattern and optimize it. It seems reasonable that this should work, given that both gcc and icc are able to do it.
• make zig detect this pattern and emit different LLVM IR

I don't consider this to be blocking a 1.0.0 release.

[PavelVozenilek]

Performance of computed goto highly depends on processor and the task. It is not always faster then the ordinary switch.

Perhaps the compiler should be given a hint in form of designated tests. Depending on timing of these tests, it would then pick up the best performing implementation.

This topic gets sometimes discussed on Forth forums, they found that the old truths are not absolute, as they once were.

[shawnl]

@PavelVozenilek
There are times where a state only leads to an error condition, or to the next state, however, and clang is incapable of in-lining these cases.

[andrewrk]

Perhaps the compiler should be given a hint in form of designated tests. Depending on timing of these tests, it would then pick up the best performing implementation.

Profile guided optimization is #237

[tgschultz]

I personally am not a fan of having to rely on the optimizer to do the right thing, and then trying to fool it into doing the right thing when it doesn't. While allowing the compiler to make this optimization is a good idea, I feel that that is not sufficient to cover the computed goto use case and some explicit mechanism should still be available.

[PavelVozenilek]

@shawnl: as I understand it, computed goto performance advantage depends on ability of the processor to predict which code path would be executed next (and start speculative execution of this path in advance). With one big switch such prediction is not feasible.

In Forth interpreter code paths are few and short, and common patterns of code are frequent. The processor prediction could then make a big difference.

I do not see how inlining could play a role here, but could be easily wrong.

[shawnl]

A good benchmark for this issue would be a re2c lexer.

[andrewrk]

Closing in favor of #8220