andrewrk
commented
3 years ago EDIT: New Discovery
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.
sighoya
Techcable
Mouvedia
haberman
ifreund
hollmmax
marler8997
ghost
AnataBakka
Ev1lT3rm1nal
Cloudef
rohlem
EzequielRamis
N00byEdge
expikr
SimonMeskens
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: https://github.com/ziglang/zig/blob/e9a038c33bbf171695b08540536f307b9e418173/src/zir_sema.zig#L30 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:
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.