On Monday, 7 August 2023 at 20:22:06 UTC, claptrap wrote:
Given code like this...
const int 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...
lea r13, [rip + .LJTI0_0]
cmp r14d, 7
movsxd rax, dword ptr [r13 + 4*r12]
add rax, r13
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.
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 switches (no default block) over enum members. The main problem is that you need to build a constant array made of
blockaddress, meaning that
- 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)
- 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), there's still a fallback with a runtime error.
Otherwise, more concretly in LDC, the work would have to be done here. At first glance you'll need to define a flag, similarly to the already existing
useSwitchInst (used for the infamous case where
cases are not compile-time constants), let's say
To conclude, that seems faisable even if that would only be beneficial for a few specific cases.