How the SDCC register allocator works

A project log for Targeting SDCC to the 8080

Writing a code generator for the 8080 microprocessor for Small Device C Compiler (SDCC)

Ken YapKen Yap 06/09/2020 at 13:210 Comments

Ok, this is subject to amendment, but I think I understand how the register allocator in SDCC works.

I did not find any score assignments to alternative code generation paths. In retrospect, this was to be expected as usually there is just one and at most a small number of ways a particular operation can be done. If the code calls for an arithmetic shift left, you can implement this with the arithmetic left shift operation or alternatively by add. And you see this reflected statically in the code generator, the programmer choses which instruction is better for a given situation. But if the code calls for an unsigned shift right, you just have to use the logical shift right instruction because there is no cheap divide by two instruction.

What the allocator does is try to find the best registers to leave intermediate results at every stage. It does this by doing a dry run pass over the iCode and optimising for a measure. In the case of the SDCC, which is targeted at Small Devices, the measure is code size.

So what the code generator writer has to do for each mapping from an iCode to machine instructions is to cope with the previous state. If the previous iCode left the intermediate result in register C and you now need the result in register L for the current iCode, you generate a move. If it's already in L, then you don't generate a move. The allocator will then, if all other things are equal, prefer to leave the result in L, for the previous iCode. Similarly if there is a register with an intermediate result to be preserved for later use you generate a spill which will increase the code size. So the act of providing alternate paths with different costs will make the allocator self-optimise in the dry run pass. That explains why in my dumps of the iCode, usually the result was left in C, as C is the first candidate considered and I provided no preference gradient. What Philipp Klaus Krause showed in his thesis is that this allocation can be done in polynomial time rather than a worst-case exponential time.