Compilers are highly complex machines with two areas that deserve extra scrutiny. They are the register allocator and the calling convention. While register allocation is the subject of countless research papers, the calling convention is considered part of the plumbing – a necessary evil that gets in the way of supreme performance. Yet, the two are closely intertwined and their correct operation is essential to the reliable translation of source code to target instructions.
The first microprocessors only had a few registers – high speed specialized storage that was fully integrated into the CPU’s data path. With the advent of RISC architectures, register banks grew larger but were still limited in size. Registers are high-speed silicon real estate, the optimal use of which is crucial to a program’s performance. The task of mapping source program variables and the results of intermediate computations to registers is called register allocation. It’s an intriguing challenge that can be mapped to the ‘NP-Complete graph coloring problem’. You can even win money if you find the ultimate solution (P vs. NP) because there is no known efficient algorithm capable of solving it.
The calling convention, on the other hand, is a straightforward contract. It tells the compiler how to pass values from one function (the caller) to another (the callee) and back – no creativity allowed. Its benefit is pragmatic. The calling convention enables modular compilation and library calls, both of which represent two indispensable tasks in the underbelly of today’s computing systems. This contract can have a lot of fine print, and if you get it wrong the performance of your program will almost certainly suffer. And guess what: optimal passing of values between functions uses registers too, which puts the calling convention smack in the middle of the register allocator.
The Calling Convention Tester in SuperTest generates pairs of test files that together form a program. One file contains the caller, the other contains the callee. You can compile both with the same compiler and then link them to verify the internal consistency of the compiler. More interestingly, you can compile the files with two different compilers, or two different versions of the same compiler. That will tell you if the two compilers abide by the same contract. By generating function calls with many different variants of argument lists, the Calling Convention Tester stretches the complex inner pipework of the compiler to its limits. Not only does it verify that the implementations stick to the contract, it also provides a good workout to register allocator.
Dr. Marcel Beemster, CTO