Switch codegen.

[Basile B.]

On Monday, 7 August 2023 at 20:22:06 UTC, claptrap wrote:
> Given code like this...
>
> ```d
> const int x;
> while(...)
> {
>     switch (x)
>     {
>         case 0: whatever; break;
>         case 1: whatever; break;
>         case 2: whatever; break;
>         case 3: whatever; break;
>         case 4: whatever; break;
>     }
> }
> ```
>
> It generates a jump table if there's at least 4 or 5 cases, but 
> at the start of the switch it generates 6 instructions (x64), 
> check the bounds, lookup / calc the destination, and the actual 
> jump. Like this...
>
> ```d
>         lea     r13, [rip + .LJTI0_0]
>         cmp     r14d, 7
>         ja      .LBB0_11
>         movsxd  rax, dword ptr [r13 + 4*r12]
>         add     rax, r13
>         jmp     rax
> ```
>
> So the point is if the switch is in a loop and x is constant, 
> most of that could be done ahead, outside the loop. It could 
> actually be reduced to a single indirect jump inside the loop. 
> It seems there is a LLVM IR instruction that may be useful for 
> this, "indirectbr", it's a sort of computed goto.
>
> https://llvm.org/docs/LangRef.html#indirectbr-instruction
>
> Is this at all feasible? If so how would this be done? In the 
> actual IR codegen or as an optimization pass? I willing to do 
> the work if it's possible.

As I've heard good feedback about that alternative to LLVM 
`switch` and also because I'm also interested to implement that 
in another compiler, I've made a comparison of both way here : 
https://godbolt.org/z/G41P88EY7 (D code at the end as comments)

It seems that this would only work well for `final switch`es (no 
default block) over enum members. The main problem is that you 
need to build a constant array made of `blockaddress`, meaning 
that

1. if the first member value is not 0 then you'll need to apply 
an offset for the index used to select the right `blockaddress`. 
(Source 1, line 13)
2. if there are gaps between members, you'll need to use a dummy 
block, containing `unreachable`, to fill them.

A note about the fact that I think that this would only works for 
enums: `final switch` over a value of an integral type is 
currently a lie [(see issue 
6060)](https://issues.dlang.org/show_bug.cgi?id=6060), there's 
still a fallback with a runtime error.

Otherwise, more concretly in LDC, the work would have to be done 
[here](https://github.com/ldc-developers/ldc/blob/cf32bac668540f3dd022493b3ba89b598a485dfb/gen/statements.cpp#L953). At first glance you'll need to define a flag, similarly to the already existing `useSwitchInst` (used for the infamous case where `case`s are not compile-time constants), let's say `useIndirectBrInst`.

To conclude, that seems faisable even if that would only be 
beneficial for a few specific cases.