Thanks for the writeup. It was nice to be able to get an idea of what’s going on with QBE without having to do all that investigation myself.
Regarding that weird switch at the end, it can make sense to do such things if you consider only obtaining the desired machine code, and don’t worry about humans having the reaction that you had upon seeing it for the first time. Since you’re a language designer yourself, I’m curious about what you think about labeled switch continue syntax, an upcoming Zig feature which provides the same control flow at a machine code level with a more intuitive syntax.
It forces you to organize your logic into functions. That’s another jump that
maybe you did not want in your hot path.
Does it? All tail call optimization really does is allow you to safely reuse the registers / stack space that the caller setup to call the function. You could “easily” inline the body of the functions, especially if they all have the same signature, and “just” jump around updating the registers before you jump. In the case you’re trying to optimize, could you build a dispatch table that does O(1) goto to labels based on the switch cases? That’s about as close to direct threading as you could get…
edit: The code I exampled was hilariously wrong, but a scratch pad of what I was thinking about. Removed.
Oooookay so it’s obviously intended for closure environments but how does this make life easier than just turning your closures into functions that take the environment as an explicit arg? This is what my compiler does already anyway.
It plays tricks by putting the env in a place that the C ABI doesn’t see it, which means that a C function pointer is transparently usable as a closure.
The fact that you have to pass -no-pie has nothing to do with ARM64 or Linux. I’m guessing your gcc was configured with --enable-default-pie, so it will try to link as PIE by default. QBE doesn’t generate position-independent code, so it can’t be linked as a PIE. This is why you have to pass -no-pie, and why gcc was complaining about the relocation types. The same thing will happen if you compile code with gcc -fno-PIE and then link it with gcc -pie.
Regarding the “bug” described, if you define a function with one set of parameters and call it with a different set of parameters, of course you’ll get incorrect code. QBE has no notion of “function declarations” and doesn’t do type checking. The function call syntax gives QBE all the information it needs to generate code for the function call, but you have to give it the correct information. It is up to the frontend to output correctly typed function calls.
Ignoring the env feature entirely, this also doesn’t work:
data $str = { b "%f", b 0 }
function $print_f64(d %x) {
@start
call $printf(l $str, ..., d %x)
ret
}
export function w $main() {
@start
call $print_f64(l 12)
ret 0
}
This is because print_f64 is defined to take a d parameter, so the code generated for it expects it in a floating point register, but it is called with an l parameter, so the code generated for the call puts the argument in an integer register.
The fact that you have to pass -no-pie has nothing to do with ARM64 or Linux…
It has something to do with ARM64 or Linux, because on my AMD64 system with the same Linux distro I don’t have to do it. QBE appears to generate code that is position independent on AMD64:
On the other hand the default cc command line args used in the unit test script all appear to include -no-pie by default. Soooooo I can only conclude that in this case it generates x86 asm code that is just coincidentally position-independent, and a different/more complex case would not.
QBE has no notion of “function declarations” and doesn’t do type checking.
…I could have sworn this was incorrect, and remember even seeing the code for arg type checking, but upon testing it appears that you are correct. I am quite confused, and annoyed. Thank you for the correction though. Maybe the code I was looking at was for checking the arg types of instructions rather than function calls?
I’d recommend LLVM. Generating LLVM IR from your AST can be a somewhat simple procedure (even simpler if you have your own SSA IR), and you can declare external functions in your LLVM IR modules to call anything compatible with the C ABI. This means you can attach libc, a GC, or other libraries very quickly. The LLVM API also has lots of bindings for various languages: C, C++, OCaml, Java, etc.
LLVM has its fair share of issues, but for a toy language I’ve yet to find a codegen library that’s as well equipped and easy to pickup as LLVM. I’ve spun up a good amount of toy languages with LLVM and nothing has convinced me to switch away from it so far. If LLVM is too bulky for you (which I think doesn’t really matter in the realm of “toy” languages), then QBE, CraneLift, or straight to WASM are other options. My general advice is pick something that maps well to the constructs in your language.
Webassembly has some bumps but is pretty easy to get going with. A high level language like C or Zig or whatever also isn’t a bad choice to get started with. At the moment, I’m literally compiling to Rust and it works far better than it really should. LLVM is maybe a bit more work but honestly probably worth knowing anyway, if you’re interested in it.
You can call it a cop-out, as I did to myself for a long time, but frankly there’s nothing wrong with focusing on the part of the compiler you’re really interested in. I’m going to bootstrap this compiler ASAP anyway, so I’ll have to rewrite the backend no matter what and there’s no real downside to leaning on another language until that time.
much easier than struggling through all the vagaries of a huge and complex IR and platform like LLVM
a C compiler is available on every conceivable platform, so you’re not restricted to e.g. x86_64 or arm64
you can expect a priori a good performance, because C compilers usually generate very good code
C ABI compatibility included
source level debugging is feasible e.g. with GDB
there are lean C compilers like TCC that integrate directly with your compiler
Cons:
less “fancy” than e.g. WASM
not suited for every kind of language
If you are planning a dynamic language and need a VM rather than an AOT compiler, you can generate e.g. Lua source code or bytecode and benefit from the lean, efficient and proven Lua engines available.
From what I understand from speaking to the QBE author, this whole thing was implemented as a hobby project for fun, and the author never thought it would take off like this. Which does explain why the code is so horrible (believe me, I know, I’m currently trying to implement a m68k backend for it and hack 32-bit support into it).
Since I’m looking for a backend, I’m curious over the relative benefits between QBE and TCC. Does anybody have experience with both and any thoughts on the matter?
I’m currently leaning a bit towards TCC, since I’m familiar with C and it emits object code directly.
It’s a compiler backend “that aims to provide 70% of the performance of industrial optimizing compilers in 10% of the code” https://c9x.me/compile/code.html
Thanks for the writeup. It was nice to be able to get an idea of what’s going on with QBE without having to do all that investigation myself.
Regarding that weird
switchat the end, it can make sense to do such things if you consider only obtaining the desired machine code, and don’t worry about humans having the reaction that you had upon seeing it for the first time. Since you’re a language designer yourself, I’m curious about what you think about labeled switch continue syntax, an upcoming Zig feature which provides the same control flow at a machine code level with a more intuitive syntax.from the linked issue:
Does it? All tail call optimization really does is allow you to safely reuse the registers / stack space that the caller setup to call the function. You could “easily” inline the body of the functions, especially if they all have the same signature, and “just” jump around updating the registers before you jump. In the case you’re trying to optimize, could you build a dispatch table that does O(1) goto to labels based on the switch cases? That’s about as close to direct threading as you could get…
edit: The code I exampled was hilariously wrong, but a scratch pad of what I was thinking about. Removed.
It plays tricks by putting the env in a place that the C ABI doesn’t see it, which means that a C function pointer is transparently usable as a closure.
The fact that you have to pass
-no-piehas nothing to do with ARM64 or Linux. I’m guessing your gcc was configured with--enable-default-pie, so it will try to link as PIE by default. QBE doesn’t generate position-independent code, so it can’t be linked as a PIE. This is why you have to pass-no-pie, and why gcc was complaining about the relocation types. The same thing will happen if you compile code withgcc -fno-PIEand then link it withgcc -pie.Regarding the “bug” described, if you define a function with one set of parameters and call it with a different set of parameters, of course you’ll get incorrect code. QBE has no notion of “function declarations” and doesn’t do type checking. The function call syntax gives QBE all the information it needs to generate code for the function call, but you have to give it the correct information. It is up to the frontend to output correctly typed function calls.
Ignoring the env feature entirely, this also doesn’t work:
This is because
print_f64is defined to take adparameter, so the code generated for it expects it in a floating point register, but it is called with anlparameter, so the code generated for the call puts the argument in an integer register.It has something to do with ARM64 or Linux, because on my AMD64 system with the same Linux distro I don’t have to do it. QBE appears to generate code that is position independent on AMD64:
On the other hand the default
cccommand line args used in the unit test script all appear to include-no-pieby default. Soooooo I can only conclude that in this case it generates x86 asm code that is just coincidentally position-independent, and a different/more complex case would not.…I could have sworn this was incorrect, and remember even seeing the code for arg type checking, but upon testing it appears that you are correct. I am quite confused, and annoyed. Thank you for the correction though. Maybe the code I was looking at was for checking the arg types of instructions rather than function calls?
What would you recommend as a compiler backend for implementing a toy language?
I’d recommend LLVM. Generating LLVM IR from your AST can be a somewhat simple procedure (even simpler if you have your own SSA IR), and you can declare external functions in your LLVM IR modules to call anything compatible with the C ABI. This means you can attach libc, a GC, or other libraries very quickly. The LLVM API also has lots of bindings for various languages: C, C++, OCaml, Java, etc.
LLVM has its fair share of issues, but for a toy language I’ve yet to find a codegen library that’s as well equipped and easy to pickup as LLVM. I’ve spun up a good amount of toy languages with LLVM and nothing has convinced me to switch away from it so far. If LLVM is too bulky for you (which I think doesn’t really matter in the realm of “toy” languages), then QBE, CraneLift, or straight to WASM are other options. My general advice is pick something that maps well to the constructs in your language.
QBE. The code is dense, but quite nice.
Webassembly has some bumps but is pretty easy to get going with. A high level language like C or Zig or whatever also isn’t a bad choice to get started with. At the moment, I’m literally compiling to Rust and it works far better than it really should. LLVM is maybe a bit more work but honestly probably worth knowing anyway, if you’re interested in it.
You can call it a cop-out, as I did to myself for a long time, but frankly there’s nothing wrong with focusing on the part of the compiler you’re really interested in. I’m going to bootstrap this compiler ASAP anyway, so I’ll have to rewrite the backend no matter what and there’s no real downside to leaning on another language until that time.
How about an interpreter instead of a backend?
Consider just generating C
Pros:
Cons:
If you are planning a dynamic language and need a VM rather than an AOT compiler, you can generate e.g. Lua source code or bytecode and benefit from the lean, efficient and proven Lua engines available.
From what I understand from speaking to the QBE author, this whole thing was implemented as a hobby project for fun, and the author never thought it would take off like this. Which does explain why the code is so horrible (believe me, I know, I’m currently trying to implement a m68k backend for it and hack 32-bit support into it).
Since I’m looking for a backend, I’m curious over the relative benefits between QBE and TCC. Does anybody have experience with both and any thoughts on the matter?
I’m currently leaning a bit towards TCC, since I’m familiar with C and it emits object code directly.
I’d give TCC a go and see how it feels, it’s a cool little project that needs more love.
Yes, TCC is a cool compiler; the generated code is only as fast as GCC with no optimization though; GCC optimized with -O2 is about twice as fast.
What is QBE? [I would have appreciated a link when it was mentioned at the beginning of the piece; Google was unhelpful.]
It’s a compiler backend “that aims to provide 70% of the performance of industrial optimizing compilers in 10% of the code” https://c9x.me/compile/code.html
Thanks!