introduce labeled continue syntax inside a switch expression #8220
Comments
andrewrk
added
the
proposal
And here it is in idiomatic zig form, no duplicated code or anything: const Inst = extern struct {
tag: Tag,
const Tag = extern enum {
end,
add,
addwrap,
alloc,
alloc_mut,
alloc_inferred,
alloc_inferred_mut,
anyframe_type,
array_cat,
array_mul,
};
};
export fn entry(inst_list: [*]const Inst, map: [*]u32) void {
var i: usize = 0;
while (true) : (i += 1) {
const inst = inst_list[i];
map[i] = switch (inst.tag) {
.end => return,
.add => analyze_add(inst),
.addwrap => analyze_addwrap(inst),
.alloc => analyze_alloc(inst),
.alloc_mut => analyze_alloc_mut(inst),
.alloc_inferred => analyze_alloc_inferred(inst),
.alloc_inferred_mut => analyze_alloc_inferred_mut(inst),
.anyframe_type => analyze_anyframe_type(inst),
.array_cat => analyze_array_cat(inst),
.array_mul => analyze_array_mul(inst),
};
}
}
extern fn analyze_add(inst: Inst) u32;
extern fn analyze_addwrap(inst: Inst) u32;
extern fn analyze_alloc(inst: Inst) u32;
extern fn analyze_alloc_mut(inst: Inst) u32;
extern fn analyze_alloc_inferred(inst: Inst) u32;
extern fn analyze_alloc_inferred_mut(inst: Inst) u32;
extern fn analyze_anyframe_type(inst: Inst) u32;
extern fn analyze_array_cat(inst: Inst) u32;
extern fn analyze_array_mul(inst: Inst) u32;It generates the ideal machine code. |
|
Did you consider indirectbr? |
|
Interestingly enough, C# has this feature with its Although the use cases are limited to certian situations. In those cases it can make a big difference. Interpreters and VMs are definitely a target audience for Zig, and low level code has plenty of other state machines where these sorts of dispatch tables might need this optimization. As someone expressed in #2162, sometimes computed goto can be slower than a regular switch statement in a loop. It would be odd to have performance pitfalls around these sorts of switch statements. I think Zig usually likes to make these performance choices explicit. On the other hand, this is generally considered a must-have optimization for fast interpreter implementations. In CPython it gives about a 15-20% speedup.
That is exactly how clang implements it :) In fact, this feature is the reason |
|
So I want to use this in semantic analysis of Zig self-hosted compiler. Here is: LLVM does not figure out how to generate the machine code that I want, and I suspect it would be a perf improvement. My plan is to implement this in order to benchmark it, and then we can make a decision, armed with some data. |
|
Check out https://dino-lang.github.io/learn/dino.pdf, section 3.1 "Byte Code Dispatch" |
|
As prior art I found PowerShell which uses |
An argument for tail callsBased on my experience with https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreters.html, I would strongly recommend offering guaranteed tail calls as one tool available to interpreter writers (I'm not arguing against other options). Getting the replicated decode/dispatch (as described above) is important, but it's only one part of the story. We also have to worry about the code quality for the operation itself -- the code that actually does the work. Optimizers struggle to generate good code when the entire interpreter is in one big function. In particular, they struggle to keep the most important state in registers. Mike Pall talked about this problem here: http://lua-users.org/lists/lua-l/2011-02/msg00742.html If each operation is in a separate function, with the most important state propagated in arguments (passed in registers on modern architectures), and each operation tail calling the next, we can get much better code out of the compiler. With this pattern, there is no Addressing open questions on Tail CallsTo answer the questions above:
For LLVM, musttail currently appears to be totally unsupported on powerpc (32 and 64). On ARM32 it runs into problems in some cases. There is a bit more information about this here: https://gcc.gnu.org/pipermail/gcc/2021-April/235903.html I don't know if these problems are fundamental or if they just need proper bug fixes.
If you mean stack traces, I don't think tail calls leave any less of a stack trace than a traditional switch()-based dispatch. In both cases the stack tells you where you are, but not where you've been.
I think efficiency argues for tail calls, not against them. The tail call pattern does not create any unnecessary jumps. I'll elaborate a bit on this point. Tail calls generate code comparable to hand-written assemblyTake this example from the article of implementing the "ADDVN" operation from LuaJIT, which aims to match this hand-written assembly code. The C compiler output almost exactly matches the hand-written assembly. It does not contain any jumps except the jump to the next operation, which is inherently necessary. When you are implementing byte code dispatch, you have a fundamental choice of whether to use replicated dispatch or shared dispatch. There are tradeoffs here, and the LuaJIT source discusses these tradeoffs a bit). Tail calls can support both options very naturally. All we have to do is flip the CaveatsI should mention one significant downside to this pattern: callee-save registers are not available to these functions without spilling them to the stack first. This means, in effect, that if we want the fastest code we can only use about half the registers. We also pay a steep price when making any non-tail call. Both of these problems can be solved if you also offer some specialized calling conventions (these are mostly supported in LLVM already). I can go into this more if you are interested. With the right calling conventions, I believe this pattern can generate code that even the most talented assembly language programmers would have a hard time beating. |
|
@haberman note that zig already allows forcing tail calls with the |
|
@ifreund that is great news, thanks for the info. :) |
|
I'm inclined to accept this proposal. Regardless of performance improvements, this provides a useful, intuitive tool for control flow. Another observation is that when the operand of This even would allow someone to implement Duff's Device in zig: fn send(to: *volatile u32, from_start: [*]u32, count: u32) void {
var from = from_start;
var n = (count + 7) / 8;
sw: switch (count % 8) {
0 => {
to.* = from[0];
from += 1;
continue :sw 7;
},
7 => {
to.* = from[0];
from += 1;
continue :sw 6;
},
6 => {
to.* = from[0];
from += 1;
continue :sw 5;
},
5 => {
to.* = from[0];
from += 1;
continue :sw 4;
},
4 => {
to.* = from[0];
from += 1;
continue :sw 3;
},
3 => {
to.* = from[0];
from += 1;
continue :sw 2;
},
2 => {
to.* = from[0];
from += 1;
continue :sw 1;
},
1 => {
to.* = from[0];
from += 1;
n -= 1;
if (n > 0) continue :sw 0;
},
}
}Reference example in C: send(to, from, count)
register short *to, *from;
register count;
{
register n = (count + 7) / 8;
switch (count % 8) {
case 0: do { *to = *from++;
case 7: *to = *from++;
case 6: *to = *from++;
case 5: *to = *from++;
case 4: *to = *from++;
case 3: *to = *from++;
case 2: *to = *from++;
case 1: *to = *from++;
} while (--n > 0);
}
}With #7224 it could even be shortened to this: fn send(to: *volatile u32, from_start: [*]u32, count: u32) void {
var from = from_start;
var n = (count + 7) / 8;
sw: switch (count % 8) {
inline 0...7 => |remainder| {
to.* = from[0];
from += 1;
if (remainder == 1) {
n -= 1;
if (n <= 0) break :sw;
}
continue :sw @as(u3, remainder) -% 1;
},
}
}What's interesting about this is that it lowers to the same machine code as the C version, even in debug mode. |
|
I am working on this. I already have modified parsing, AST, and formatting to support this (both stage1 & stage2). Example interpreterThe following parses sucessfully: https://gist.github.com/Techcable/dbcd7f7c3a708aa71d86031a1105db9c In particular, the core eval loop has no syntax errors: fn eval(ctx: *InsnCtx) Value {
// decode first oparg
ctx.oparg = ctx.ip[0].oparg;
while (true) {
evalLoop: switch (ctx.ip[0].opcode) {
.LOAD_IMM => {
load_imm(ctx).verify_continue();
continue :evalLoop ctx.ip[0].opcode;
},
.POP => {
pop(ctx).verify_continue();
continue :evalLoop ctx.ip[0].opcode;
},
.ADD, .SUB, .MUL => {
arithop(ctx).verify_continue();
continue :evalLoop ctx.ip[0].opcode;
},
.PRINT => {
print(ctx).verify_continue();
continue :evalLoop ctx.ip[0].opcode;
},
.RETURN => {
const done = @"return"(ctx);
if (done.return_value) |value| {
return value;
} else {
unreachable;
}
},
}
}
}Of course running any of this through semantic analysis (stage1) gives an error "label not found: 'evalLoop'" But this is progress! |
|
I think I understand the motivation behind this change, but I'd like to raise a concern I have with it. |
|
first comment here :) Even if the compiler always correctly optimized This construct would literally be redefining tail calls without the predefined input and output tool (which may actually feel like a loss in some cases), with the gain that it should make it more clear than tail calls when we are dealing with a single state in a loop (rather than with a fully abstracted function), and should in theory be less clunky to use in local scope than functions. And since "tail calls" = goto then if "while switch" = "tail calls" then "while switch" = goto. Same power as goto, but unlike goto, which usually feels as being used randomly, the state construct should make it clearer where the codeflow can go. Everyone should argue against the pitfalls of goto, but i don't think anyone can argue against an efficient state machine (unless you've never had to use a state machine). The clearest and most efficient way of doing it in C is to do something like this: while(1)
{
StateMachine_Init:
[set up and determine the first state to go to, either with computed goto or just goto]
break;
State_x:
[stateActions]
[determine the next state to goto]
break;
State_y:
[...]
break;
}Which works good enough, but having a Can it be abused? Also, this hasn't been previously directly specified, but by having a labeled And as a final concept, if we already know the initial state we want to start with, using If we want to avoid the functional way of recursive tail calls and get maximum performance and flexibility in an imperative way, then we need As Andrew showed above, by mirroring what a function tail call can do, you would also be able to merge states with the inline keyword: main()
{
enum { init, next }
int minimumDistance;
int i;
Loop: while switch (.init) {
inline else => |state| {
if (state == .init) {
i = 0;
}
else if (state == .next) {
i++;
}
if (i < n) {
int distance = calculateDistance(i);
if (state == .init || distance < minimumDistance) {
minimumDistance = distance;
}
continue :Loop .next;
}
else {
if (state == .next) {
//we finished without error
print("Success!");
}
}
}
}
}which should be inlined to this main()
{
enum { init, next }
int minimumDistance;
int i;
Loop: while switch (.init) {
.init => {
i = 0;
if (i < n) {
int distance = calculateDistance(i);
minimumDistance = distance;
continue :Loop .next;
}
else {
//exit
}
},
.next => {
i++;
if (i < n) {
int distance = calculateDistance(i);
if (distance < minimumDistance) {
minimumDistance = distance;
}
continue :Loop .next;
}
else {
//we finished without error
print("Success!");
}
}
}
}This feels easy, intuitive and efficient at first, by helping to avoid placing redundant checks / duplicated statements on each state. However, after further experimentation, i realized you may fall into a pitfall of always unnecessarily trying to merge states into an inlined version when it's quicker to just write them off completely separate. So i guess use Disclaimer: i say this as someone who just knows some C, and only heard bits and pieces of Zig. EDIT:(this is getting a bit long, but i blame the code examples) enum tokenStatus {ACCEPT, REJECT, ERROR, [etc...]};
enum tokenStatus verifyToken(Token_t token) {
if ([...]) {
return ACCEPT;
}
else if ([...]) {
return REJECT;
}
else if ([...]) {
return [etc...]
}
else {
return ERROR;
}
}
main()
{
for (int i = 0; i < maxN; i++) {
Token_t token = getToken(i);
switch (verifyToken(token)) {
ACCEPT => [...],
REJECT => [...],
[...] => [...],
ERROR => [...]
}
}assume verifyToken can be used by different libraries, each deciding their own action for token state. My assumption is that the above will process at run time and once verifyToken returns, the value will go into the computed goto generated by the switch. This computed goto is run in only one location for different tokens, and not only it doesn't have to be in one location, it doesn't even need to be a computed goto. What if verifyToken was able to move directly to the required action? enum tokenStatus {ACCEPT, REJECT, ERROR, [etc...]};
void tokenAction(Token_t token, comptime enum tokenStatus status) {
if (status == ACCEPT) {
[...]
}
else if (status == REJECT) {
[...]
}
else if (status == [...]) {
[...]
}
else if (status == ERROR) {
[...]
}
}
/*function input should use varargs, but this is fine for now*/
void verifyToken(Token_t token, void (*sequencedAction)(Token_t, enum tokenStatus)) {
if ([...]) {
return (*sequencedAction)(token, ACCEPT);
}
else if ([...]) {
return (*sequencedAction)(token, REJECT);
}
else if ([...]) {
return (*sequencedAction)(token, [etc...]);
}
else {
return (*sequencedAction)(token, ERROR);
}
}
main()
{
for (int i = 0; i < maxN; i++) {
Token_t token = getToken(i);
verifyToken(token, tokenAction);
}Now, the code should in theory just be translated to goto statements, which i find better. However, that solution is the functional way, and as before, we'd much rather have something that works quicker. So what if we had this? enum tokenStatus {ACCEPT, REJECT, ERROR, [etc...]};
void verifyToken(Token_t token) {
if ([...]) {
return next(ACCEPT);
}
else if ([...]) {
return next(REJECT);
}
else if ([...]) {
return next([etc...]);
}
else {
return next(ERROR);
}
}
main()
{
for (int i = 0; i < maxN; i++) {
Token_t token = getToken(i);
verifyToken(token) => |state| {
if (state == ACCEPT) {
[...]
}
else if (state == REJECT) {
[...]
}
else if (state == [...]) {
[...]
}
else if (state == ERROR) {
[...]
}
}
}"Next" should cause the compiler to move to the block following the function call, which i don't find a very wild concept, and i believe greatly follows the concepts of what make imperative code quick and easy to write. This also voids the requirement of manually transferring over block variables. Finally, i noticed that this would also allow a functionality that a lot of people would like. void safeCreate(object[...]) {
try create(object[...]) catch return next (-1);
next (0);
object.deInit();
/*create() is an incomplete function, in that it *requires* a follow up closure action,
unlike other functions that can return without any worries. So we should always automatically apply the closure. */
}
main()
{
safeCreate(object[...]) => |state| {
if (state == 0) {
/*object successfully created, so use it here. It will be automatically destroyed when the block returns.
If object is required out of scope, then you must initialize it with minimum memory in the full scope
where it's used, using the same automatic destruction, and then reallocate to the necessary memory
in local scope without the automatic destruction*/
}
else {
/*object creation failed*/
}
}
} |
|
@andrewrk is there a way to optimize my small interpreter to generate asm like computed gotos? |
|
As part of our Donor Bounty Program, I have confirmed a bounty for this issue with an anonymous donor. The anonymous donor has offered 4,000 USD to be donated to Zig Software Foundation if the criteria can be met by April 30, 2024. It doesn’t matter who implements it, or whether multiple people work together on implementing it, or how much help is needed from the core Zig team. As long as it gets done properly and the donor is satisfied with the results, the bounty will be awarded. |
|
I guess this proposal won't allow you to jump from a switch statement to another statement? I'm writing a ragel compatible state machine compiler and for the default code generation, I'm thinking of going with bunch of switch statements where cases itself are the event transitions and if transitioning to a sub-machine with different transitions it would jump to another switch statement, there is no forwards / backwards jumping here but any transition can jump to any machine. This essentially requires local goto for the most efficient (or perhaps trivial?) code generation. Roughly something like this in C: #define N_EVENTS 's'
#define EVENT_W_STATE(c, a, b) ((a * N_EVENTS * N_EVENTS) + b * N_EVENTS) + c
#define EVENT(a, b) EVENT_W_STATE(a, a, b)
int main() {
const char syote[] = "oispa kaljaa";
uint32_t state = 'o'; // starting state
const char *s = syote - 1;
oispa_machine:
for (s = s + 1; *s; ++s) {
const uint32_t event = EVENT_W_STATE(state, *s, s[1]);
switch (event) {
case EVENT('o', 'i'):
state = s[1];
break;
case EVENT('i', 's'):
state = s[1];
break;
case EVENT('s', 'p'):
state = s[1];
break;
case EVENT('p', 'a'):
state = s[1];
goto kalja_machine;
default:
errx(EXIT_FAILURE, "nojoo, oot jossaki iha oudossa siirtymässä");
break;
}
}
assert("unreachable" && false);
kalja_machine:
for (s = s + 1; *s; ++s) {
const uint32_t event = EVENT_W_STATE(state, *s, s[1]);
switch (event) {
case EVENT('a', ' '):
state = s[1];
break;
case EVENT(' ', 'k'):
state = s[1];
break;
case EVENT('k', 'a'):
state = s[1];
break;
case EVENT('a', 'l'):
state = s[1];
break;
case EVENT('l', 'j'):
state = s[1];
break;
case EVENT('j', 'a'):
state = s[1];
break;
case EVENT('a', 'a'):
state = s[1];
break;
case EVENT('a', 0):
goto last_state;
default:
errx(EXIT_FAILURE, "nojoo, oot jossaki iha oudossa siirtymässä");
break;
}
}
assert("unreachable" && false);
last_state:
errx(EXIT_SUCCESS, "vittu jes, nyt kaljalle");
} |
|
@Cloudef yea, your case looks like a nested labeled switch, so assuming the proposal would work like nested labeled loops, then it should automatically work unless intentionally removed |
|
True I guess you could have outer switch with the machines as cases for the same effect and then continue to those, and finally break out on final state, as long as the code gen would be essentially jmp it's fine. I could try generating some zig code based on this proposal and see how it looks. One thing I'm also interested into looking into is parallelization using SIMD and other techniques. Ragel allows mixing scanners with FSMs and the scanner could effectively do the longest matching in parallel. There's also interesting articles of essentially vectorizing switch like here: http://0x80.pl/notesen/2019-02-03-simd-switch-implementation.html |
|
Is anybody experimenting with / actively investing efforts into implementing this currently? |
Not sure where you got this idea from. Even in the most distant of future plans, Zig still has an LLVM backend that outputs an LLVM module as bitcode. |
@andrewrk Sorry, to clarify I wasn't talking about the LLVM parts of this proposal becoming optional, but rather the LLVM dependency whilst working on the compiler itself, aka being able to use the x86_64-backend for faster iteration times. |
|
Ah, I see. For some tasks it's already feasible, however at this point in time the debugging experience is still lacking. |
|
I'm working on it. |
|
how does the codegen of this interact with |
|
@N00byEdge Not sure how current codegen does this (you can already have multiple @EzequielRamis How's your progress? How confident are you in completing it before the deadline? |
|
@rohlem I don't think it will be completed before the deadline, but I'm not preoccupied. I was planning to upload today what I've done and the todos, I think the draft will be in a couple of hours. |
Ah right, that all checks out. I just get a little weirded out when I see language features that can't map nicely to machine code. But I guess if that already exists, then it's not too terrible. |
|
I'm having a hard time wrapping my head around the concepts involved. Is my understanding correct that the issue arises from wanting each prong to contain all of the operations to be done in each step rather than being shared across a common step? Would this generate the desired machine code? while(switch(inst_list[i].tag){
.end => false,
.add => sw: {
map[i] = analyze_add(inst_list[i]);
i += 1;
break :sw true;
},
.addwrap => sw: {
map[i] = analyze_addwrap(inst_list[i]);
i += 1;
break :sw true;
},
...
}){}EDIT: godbolt link sourceconst Inst = extern struct {
tag: enum(u8) {
end,
add,
addwrap,
alloc,
alloc_mut,
alloc_inferred,
alloc_inferred_mut,
anyframe_type,
array_cat,
array_mul,
},
};
export fn entry(inst_list: [*]const Inst, map: [*]u32) void {
var i: usize = 0;
while(switch(inst_list[i].tag){
.end => false,
.add => sw: {
map[i] = analyze_add(inst_list[i]);
i += 1;
break :sw true;
},
.addwrap => sw: {
map[i] = analyze_addwrap(inst_list[i]);
i += 1;
break :sw true;
},
.alloc => sw: {
map[i] = analyze_alloc(inst_list[i]);
i += 1;
break :sw true;
},
.alloc_mut => sw: {
map[i] = analyze_alloc_mut(inst_list[i]);
i += 1;
break :sw true;
},
.alloc_inferred => sw: {
map[i] = analyze_alloc_inferred(inst_list[i]);
i += 1;
break :sw true;
},
.alloc_inferred_mut => sw: {
map[i] = analyze_alloc_inferred_mut(inst_list[i]);
i += 1;
break :sw true;
},
.anyframe_type => sw: {
map[i] = analyze_anyframe_type(inst_list[i]);
i += 1;
break :sw true;
},
.array_cat => sw: {
map[i] = analyze_array_cat(inst_list[i]);
i += 1;
break :sw true;
},
.array_mul => sw: {
map[i] = analyze_array_mul(inst_list[i]);
i += 1;
break :sw true;
},
}){}
}
extern fn analyze_add(inst: Inst) u32;
extern fn analyze_addwrap(inst: Inst) u32;
extern fn analyze_alloc(inst: Inst) u32;
extern fn analyze_alloc_mut(inst: Inst) u32;
extern fn analyze_alloc_inferred(inst: Inst) u32;
extern fn analyze_alloc_inferred_mut(inst: Inst) u32;
extern fn analyze_anyframe_type(inst: Inst) u32;
extern fn analyze_array_cat(inst: Inst) u32;
extern fn analyze_array_mul(inst: Inst) u32;assembly# Compilation provided by Compiler Explorer at https://godbolt.org/
entry:
push r15
push r14
push rbx
mov rbx, rsi
mov r14, rdi
xor r15d, r15d
movzx eax, byte ptr [rdi + r15]
jmp qword ptr [8*rax + .LJTI0_0]
.LBB0_1:
mov edi, 1
call analyze_add@PLT
mov dword ptr [rbx + 4*r15], eax
inc r15
movzx eax, byte ptr [r14 + r15]
jmp qword ptr [8*rax + .LJTI0_0]
.LBB0_2:
mov edi, 2
call analyze_addwrap@PLT
mov dword ptr [rbx + 4*r15], eax
inc r15
movzx eax, byte ptr [r14 + r15]
jmp qword ptr [8*rax + .LJTI0_0]
.LBB0_3:
mov edi, 3
call analyze_alloc@PLT
mov dword ptr [rbx + 4*r15], eax
inc r15
movzx eax, byte ptr [r14 + r15]
jmp qword ptr [8*rax + .LJTI0_0]
.LBB0_4:
mov edi, 4
call analyze_alloc_mut@PLT
mov dword ptr [rbx + 4*r15], eax
inc r15
movzx eax, byte ptr [r14 + r15]
jmp qword ptr [8*rax + .LJTI0_0]
.LBB0_5:
mov edi, 5
call analyze_alloc_inferred@PLT
mov dword ptr [rbx + 4*r15], eax
inc r15
movzx eax, byte ptr [r14 + r15]
jmp qword ptr [8*rax + .LJTI0_0]
.LBB0_6:
mov edi, 6
call analyze_alloc_inferred_mut@PLT
mov dword ptr [rbx + 4*r15], eax
inc r15
movzx eax, byte ptr [r14 + r15]
jmp qword ptr [8*rax + .LJTI0_0]
.LBB0_7:
mov edi, 7
call analyze_anyframe_type@PLT
mov dword ptr [rbx + 4*r15], eax
inc r15
movzx eax, byte ptr [r14 + r15]
jmp qword ptr [8*rax + .LJTI0_0]
.LBB0_8:
mov edi, 8
call analyze_array_cat@PLT
mov dword ptr [rbx + 4*r15], eax
inc r15
movzx eax, byte ptr [r14 + r15]
jmp qword ptr [8*rax + .LJTI0_0]
.LBB0_9:
mov edi, 9
call analyze_array_mul@PLT
mov dword ptr [rbx + 4*r15], eax
inc r15
movzx eax, byte ptr [r14 + r15]
jmp qword ptr [8*rax + .LJTI0_0]
.LBB0_10:
pop rbx
pop r14
pop r15
ret
.LJTI0_0:
.quad .LBB0_10
.quad .LBB0_1
.quad .LBB0_2
.quad .LBB0_3
.quad .LBB0_4
.quad .LBB0_5
.quad .LBB0_6
.quad .LBB0_7
.quad .LBB0_8
.quad .LBB0_9 |
This commit modifies the representation of the AIR `switch_br` instruction to represent ranges in cases. Previously, Sema emitted different AIR in the case of a range, where the `else` branch of the `switch_br` contained a simple `cond_br` for each such case which did a simple range check (`x > a and x < b`). Not only does this add complexity to Sema, which -- as our secondary bottleneck -- we would like to keep as small as possible, but it also gets in the way of the implementation of ziglang#8220. This proposal turns certain `switch` statements into a looping construct, and for optimization purposes, we want to lower this to AIR fairly directly (i.e. without involving a `loop` instruction). That means we would ideally like a single instruction to represent the entire `switch` statement, so that we can dispatch back to it with a different operand as in ziglang#8220. This is not really possible to do correctly under the status quo system. For now, the actual lowering of `switch` is identical for the LLVM and C backends. This commit contains a TODO which temporarily regresseses all remaining self-hosted backends in the presence of switch case ranges. This functionality will be restored for at least the x86_64 backend before merge of this branch.
This commit introduces a new AIR instruction, `repeat`, which causes control flow to move back to the start of a given AIR loop. `loop` instructions will no longer automatically perform this operation after control flow reaches the end of the body. The motivation for making this change now was really just consistency with the upcoming implementation of ziglang#8220: it wouldn't make sense to have this feature work significantly differently. However, there were already some TODOs kicking around which wanted this feature. It's useful for two key reasons: * It allows loops over AIR instruction bodies to loop precisely until they reach a `noreturn` instruction. This allows for tail calling a few things, and avoiding a range check on each iteration of a hot path, plus gives a nice assertion that validates AIR structure a little. This is a very minor benefit, which this commit does apply to the LLVM and C backends. * It should allow for more compact ZIR and AIR to be emitted by having AstGen emit `repeat` instructions more often rather than having `continue` statements `break` to a `block` which is *followed* by a `repeat`. This is done in status quo because `repeat` instructions only ever cause the direct parent block to repeat. Now that AIR is more flexible, this flexibility can be pretty trivially extended to ZIR, and we can then emit better ZIR. This commit does not implement this. Support for this feature is currently regressed on all self-hosted native backends, including x86_64. This support will be added where necessary before this branch is merged.
This commit modifies the representation of the AIR `switch_br` instruction to represent ranges in cases. Previously, Sema emitted different AIR in the case of a range, where the `else` branch of the `switch_br` contained a simple `cond_br` for each such case which did a simple range check (`x > a and x < b`). Not only does this add complexity to Sema, which -- as our secondary bottleneck -- we would like to keep as small as possible, but it also gets in the way of the implementation of ziglang#8220. This proposal turns certain `switch` statements into a looping construct, and for optimization purposes, we want to lower this to AIR fairly directly (i.e. without involving a `loop` instruction). That means we would ideally like a single instruction to represent the entire `switch` statement, so that we can dispatch back to it with a different operand as in ziglang#8220. This is not really possible to do correctly under the status quo system. For now, the actual lowering of `switch` is identical for the LLVM and C backends. This commit contains a TODO which temporarily regresseses all remaining self-hosted backends in the presence of switch case ranges. This functionality will be restored for at least the x86_64 backend before merge of this branch.
This commit introduces a new AIR instruction, `repeat`, which causes control flow to move back to the start of a given AIR loop. `loop` instructions will no longer automatically perform this operation after control flow reaches the end of the body. The motivation for making this change now was really just consistency with the upcoming implementation of ziglang#8220: it wouldn't make sense to have this feature work significantly differently. However, there were already some TODOs kicking around which wanted this feature. It's useful for two key reasons: * It allows loops over AIR instruction bodies to loop precisely until they reach a `noreturn` instruction. This allows for tail calling a few things, and avoiding a range check on each iteration of a hot path, plus gives a nice assertion that validates AIR structure a little. This is a very minor benefit, which this commit does apply to the LLVM and C backends. * It should allow for more compact ZIR and AIR to be emitted by having AstGen emit `repeat` instructions more often rather than having `continue` statements `break` to a `block` which is *followed* by a `repeat`. This is done in status quo because `repeat` instructions only ever cause the direct parent block to repeat. Now that AIR is more flexible, this flexibility can be pretty trivially extended to ZIR, and we can then emit better ZIR. This commit does not implement this. Support for this feature is currently regressed on all self-hosted native backends, including x86_64. This support will be added where necessary before this branch is merged.
This commit modifies the representation of the AIR `switch_br` instruction to represent ranges in cases. Previously, Sema emitted different AIR in the case of a range, where the `else` branch of the `switch_br` contained a simple `cond_br` for each such case which did a simple range check (`x > a and x < b`). Not only does this add complexity to Sema, which -- as our secondary bottleneck -- we would like to keep as small as possible, but it also gets in the way of the implementation of ziglang#8220. This proposal turns certain `switch` statements into a looping construct, and for optimization purposes, we want to lower this to AIR fairly directly (i.e. without involving a `loop` instruction). That means we would ideally like a single instruction to represent the entire `switch` statement, so that we can dispatch back to it with a different operand as in ziglang#8220. This is not really possible to do correctly under the status quo system. For now, the actual lowering of `switch` is identical for the LLVM and C backends. This commit contains a TODO which temporarily regresseses all remaining self-hosted backends in the presence of switch case ranges. This functionality will be restored for at least the x86_64 backend before merge of this branch.
This commit introduces a new AIR instruction, `repeat`, which causes control flow to move back to the start of a given AIR loop. `loop` instructions will no longer automatically perform this operation after control flow reaches the end of the body. The motivation for making this change now was really just consistency with the upcoming implementation of ziglang#8220: it wouldn't make sense to have this feature work significantly differently. However, there were already some TODOs kicking around which wanted this feature. It's useful for two key reasons: * It allows loops over AIR instruction bodies to loop precisely until they reach a `noreturn` instruction. This allows for tail calling a few things, and avoiding a range check on each iteration of a hot path, plus gives a nice assertion that validates AIR structure a little. This is a very minor benefit, which this commit does apply to the LLVM and C backends. * It should allow for more compact ZIR and AIR to be emitted by having AstGen emit `repeat` instructions more often rather than having `continue` statements `break` to a `block` which is *followed* by a `repeat`. This is done in status quo because `repeat` instructions only ever cause the direct parent block to repeat. Now that AIR is more flexible, this flexibility can be pretty trivially extended to ZIR, and we can then emit better ZIR. This commit does not implement this. Support for this feature is currently regressed on all self-hosted native backends, including x86_64. This support will be added where necessary before this branch is merged.
This commit modifies the representation of the AIR `switch_br` instruction to represent ranges in cases. Previously, Sema emitted different AIR in the case of a range, where the `else` branch of the `switch_br` contained a simple `cond_br` for each such case which did a simple range check (`x > a and x < b`). Not only does this add complexity to Sema, which -- as our secondary bottleneck -- we would like to keep as small as possible, but it also gets in the way of the implementation of ziglang#8220. This proposal turns certain `switch` statements into a looping construct, and for optimization purposes, we want to lower this to AIR fairly directly (i.e. without involving a `loop` instruction). That means we would ideally like a single instruction to represent the entire `switch` statement, so that we can dispatch back to it with a different operand as in ziglang#8220. This is not really possible to do correctly under the status quo system. For now, the actual lowering of `switch` is identical for the LLVM and C backends. This commit contains a TODO which temporarily regresseses all remaining self-hosted backends in the presence of switch case ranges. This functionality will be restored for at least the x86_64 backend before merge of this branch.
This commit introduces a new AIR instruction, `repeat`, which causes control flow to move back to the start of a given AIR loop. `loop` instructions will no longer automatically perform this operation after control flow reaches the end of the body. The motivation for making this change now was really just consistency with the upcoming implementation of ziglang#8220: it wouldn't make sense to have this feature work significantly differently. However, there were already some TODOs kicking around which wanted this feature. It's useful for two key reasons: * It allows loops over AIR instruction bodies to loop precisely until they reach a `noreturn` instruction. This allows for tail calling a few things, and avoiding a range check on each iteration of a hot path, plus gives a nice assertion that validates AIR structure a little. This is a very minor benefit, which this commit does apply to the LLVM and C backends. * It should allow for more compact ZIR and AIR to be emitted by having AstGen emit `repeat` instructions more often rather than having `continue` statements `break` to a `block` which is *followed* by a `repeat`. This is done in status quo because `repeat` instructions only ever cause the direct parent block to repeat. Now that AIR is more flexible, this flexibility can be pretty trivially extended to ZIR, and we can then emit better ZIR. This commit does not implement this. Support for this feature is currently regressed on all self-hosted native backends, including x86_64. This support will be added where necessary before this branch is merged.
Background
The
gotokeyword was removed in #630. This remains the right call because all the control flow in Zig can be expressed in a better way:continueto goto backwards, andbreakto goto forwards.However, in C, there is another concept, called "computed goto". This is described in #5950 and briefly discussed in #2162. This concept is not currently possible in Zig. It is possible to model the desired semantics with existing control flow features quite simply, but it is not possible to obtain the desired machine code, even in optimized builds.
Problem Statement
For example (godbolt link):
In the generated machine code, each prong ends up jumping back to the loop condition, before getting re-dispatched to the next prong:
The reason this machine code is not what we desire is described in this paper in the section "Direct Threading" and "The Context Problem":
They explain it in a nice, intuitive way here:
So the problem statement here is that we want to be able to write zig code that outputs machine code that matches this Direct Threading pattern. In one sense, it is an optimization problem, since we can model the same semantics with other language constructs and other machine code. But in another sense, it is more fundamental than an optimization problem, because Zig is a language that wants to generate optimal machine code, meaning it is possible to write Zig code that generates machine code equivalent or better to what you could write by hand.
In short summary, we want to be able to express zig code where each switch prong jumps directly to the next prong, instead of all switch prongs sharing the same indirect jump, in order to benefit the branch predictor.
Research Dump
Can LLVM Do the Optimization?
In this example (godbolt link), I changed the loop to while(true) and manually inlined the continue expression into each switch prong, with a continue. It does not get much simpler than this; we are practically begging LLVM to do the optimization.
Snippet of assembly:
Here, LLVM actually figured out the continue expression was duplicated N times, and un-inlined it, putting the code back how it was! So crafty.
EDIT: New Discovery
Wrong!
After typing up this whole proposal, I realized that I did not try that optimization with using an "end" tag in the above code. Here is the case, modified (godbolt link):
Two example prongs from the machine code:
It's perfect! This is exactly what we wanted.
This compromises the entire proposal. I will still post the proposal but this new discovery makes it seem unnecessary, since, in fact, we are hereby observing #2162 already implemented and working inside LLVM.
Real Actual Use Case
Here's one in the self-hosted compiler:
zig/src/zir_sema.zig
Line 30 in e9a038c
This switch is inside a loop over ZIR instructions. In optimized builds, we noticed non-trivial amount of time spent in the overhead of this dispatch, when analyzing a recursive comptime fibonacci function call.
This pattern also exists in:
(pretty much in every stage of the pipeline)
Other Possible Solution: Tail Calls
Tail calls solve this problem. Each switch prong would
return foo()(tail call) andfoo()at the end of its business would inline call a function which would do the switch and then tail call the next prong.This is reasonable in the sense that it is doable right now; however there are some problems:
maybe you did not want in your hot path.
Proposal
I propose to add
continue :label expressionsyntax, and the ability to label switch expressions. Here is an example:The new labeled continue syntax is syntactically unambiguous at a glance that it jumps to a
switchexpression, because it is the only form wherecontinueaccepts an operand. More details:continuewith an operand on a loop would be a compile errorbreakwith a switch would be OK.How to Lower this to LLVM
Note: I wrote this section before the EDIT: New Discovery section.
One idea I had was to put the switchbr instruction inside each prong. I did some LLVM IR surgery to try out this idea (godbolt link):
The machine code for the prongs looks like this:
Pretty nice. This is exactly what we want - there is an indirect jump in each prong directly to the next prong. But the problem is that even though we should have the same jump table 9 times, LLVM duplicates the jump table 9 times:
The duplicated jump tables are problematic, because in reality there could reasonably be about 150-200 instruction tags, which makes the jump table 600-800 bytes. This is fine; for example my L1 cache size is 256 KiB. But I wouldn't want to multiply that jump table by 200! It would be 156 KiB just for the jump tables alone. That would wreak havoc on the cache.
Unless this improves upstream, the best strategy to lower this language feature will be for Zig to manually create the jump table itself instead of relying on LLVM to do it, using LLVM's ability to take the address of basic blocks and put them into an array. This will essentially generate the same code that you would get in Clang if you used computed goto in the traditional way.
How to Lower this in Self-Hosted Backends
We have lots of options here. It would be quite straightforward, since we have full control over AIR, as well as the backend code generation.
OK But Is The Perf Actually Good?
I don't know. I think realistically in order to benchmark this and find out if the machine code performs better we have to implement it first.
The text was updated successfully, but these errors were encountered: