QBE - Compiler Backend: Version 1.3

# QBE - Compiler Backend Source: [https://c9x.me/compile/release/qbe-1.3.html](https://c9x.me/compile/release/qbe-1.3.html) - [Intro](https://c9x.me/compile/) - [Docs](https://c9x.me/compile/docs.html) - [Users](https://c9x.me/compile/users.html) - [Releases](https://c9x.me/compile/releases.html) - [Code](https://c9x.me/compile/code.html) ### QBE 1\.3 \- Release notes [qbe\-1\.3](https://c9x.me/compile/releases.html) QBE 1\.3 took a while to cook, but it is the most significant release since 1\.0 with around 7k new lines of code and 1\.5k deleted ones\. In addition to the usual bug fixes, QBE gained a new and original IL matching algorithm, new optimizations from Roland Paterson\-Jones, Scott Graham added support for the Windows ABI, and I implemented a plan suggested by Michael Forney to have QBE produce position\-independent code \(as in shared objects\)\. QBE is teamwork, and I am happy to thank all the contributors to this release\. In the rest of the notes we will take a closer look at some of the meat of the release\. #### Faster Every once in a while, the QBE fly stings an outstanding programmer\. This time, Roland was the victim\! Roland suggested we look at the[coremark](https://www.eembc.org/coremark/)benchmark to give us a concrete but simple playground to optimize\. Initial measurements with qbe\-1\.2 revealed that we were far behind our “70% of`gcc \-O2`” goal, closer to 40%\. We decided to address this for the 1\.3 release\. An early inspection of profiling data revealed that the performance gap boiled down in large part to how two functions are treated:[`ee\_isdigit`](https://github.com/eembc/coremark/blob/1f483d5b8316753a742cbf5590caf5bd0a4e4777/core_state.c#L197-L203)and[`crcu8`](https://github.com/eembc/coremark/blob/1f483d5b8316753a742cbf5590caf5bd0a4e4777/core_util.c#L164-L188)\. Interestingly, these functions are not really idiomatic C; for instance,`ee\_isdigit`is typically inlined textually, uses`&&`instead of`&`and skips the superfluous ternary operator; as for CRC, it is best implemented using a pre\-computed table\. This observation was a bit disappointing because, aside from QBE's lack of inlining, it did not point us to a general source of overhead that would apply to other compilation loads\. On the other hand, it is expected that CPU\-bound code spends a majority of time in compact code sections\. Nonetheless, we implemented numerous optimizations \(GVN/GCM, loop optimization, if\-elimination, CFG simplification, …\) that we could try on both coremark and more realistic usages like the[Hare](https://harelang.org/)test suite\. In the end, we decided to keep only a subset of vetted passes and now score more than 63% of the performance of commercial compilers on vanilla coremark\. Notably, we excluded inlining from the optimizations set to postpone solving its incompatibility with the streaming per\-function compilation model of QBE\. Modifying the coremark benchmark to inline the`ee\_isdigit`function and use a simpler branch\-free implementation of`crcu8`makes QBE reach its 70% goal\. The new optimizations should also benefit Hare users: I measured a 33% improvement on the Hare test suite against qbe\-1\.2 \(1\.7s vs 2\.6s\)\. #### Smarter Since its early days, QBE used a bottom\-up tree\-numbering algorithm inspired by Ken Thompson's[Plan9 C compiler](https://c9x.me/compile/bib/new-c.pdf)\(see 5\.5\. Addressability\)\. The algorithm is fairly generic but has some subtleties in dealing elegantly with associativity and commutativity of arithmetic operators\. It has been a long\-standing goal of mine to implement a metaprogramming solution to this problem\. QBE 1\.3 sees the realization of this goal\. A new OCaml tool called`mgen`is used to compile lispy IL patterns into idiomatic C code that matches them\. The`mgen`tool will look for special comment blocks containing IL patterns and inline the matching C code right below these blocks\. The generated C code is designed to look idiomatic in qbe and works similarly to the hand\-written logic pre 1\.3\. See the[`isel\.c`](https://c9x.me/git/qbe.git/tree/amd64/isel.c?id=c0818978acec60ebb6167fade60fb7012cbf20ca#n667)file for the current use of`mgen`\. In more detail, instruction DAGs are matched by following a numbering approach like in Ken Thompson's compiler\. Then,`mgen`associates each number with a bitset indicating which of the toplevel user patterns are matched by the current IL node \(temporary\); the most suitable pattern can then be selected by handwritten logic\. Patterns can include variables which can be collected by running a matcher program\. These programs are also generated by`mgen`in a simple bytecode language which the[`runmatch\(\)`](https://c9x.me/git/qbe.git/tree/util.c?id=c0818978acec60ebb6167fade60fb7012cbf20ca#n723)function can interpret\. I expect that in the future`mgen`is used to simplify instruction selection in more backends and maybe even to recognize IL patterns such as bit rotations in optimization passes\. #### Nicer For the 1\.3 release, QBE also stung[Scott Graham](https://scot.tg/)\. Scott generously upstreamed his implementation of the Windows ABI, originally found in a fun[derivative work](https://github.com/sgraham/sqbe)\. The assembly generated by QBE remains AT&T syntax and is best compiled by the mingw assembler, although I have not tried it myself on Windows\. Compiling for Windows is now as simple as passing`\-t amd64\_win`to QBE\. Last but not least, QBE improved its support for position\-independent code and is now able to link smoothly with and even produce shared objects on most targets\. The main blocker to date has been the lack of support for indirect access to globals \(e\.g\., global offset table on ELF\)\. This is now possible at the level of IL through the support of a new`extern`“dynamic constant” flag \(`DYNCONST`in the IL spec\)\. For example, to access a variable`dlvar`from a dynamically\-linked library, one would use ``` function w $load() { @start %v =w load extern $dlvar ret %v } ``` And, in case you wonder, we use the oxymoron “dynamic constant” to speak about address symbols \(constant through execution\) that can only be known at runtime \(dynamic\) because they are allocated by either the runtime or the dynamic linker rather than by the regular linking phase of compilation\. Thanks for reading this far and happy hacking\.