Right, shift!

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 10/03/2019 at 20:510 Comments

C supports bit operations on integers of various widths, including left and right shift. Unfortunately on the 8080, shifts are only supported on the accumulator and comes in two varieties, shift using and not using the carry bit. The former is needed for two byte (int) and four byte (long) shifts to carry the leaving bit from one byte to enter the next.

Left shift is the less troublesome operation and is already supported in the code generator for the general case which also works for the 8080. Some shifts can be turned into doubling operations as a single left shift is a doubling. Some shifts which are not powers of two can be more efficiently composed from two or more shifts instead of using a loop. Some shifts by multiples of 8 on multibyte data are just byte shifts.

Note that the above applies for shifts by constants. For a shift by a variable a loop needs to be generated. The case of shifting a constant by a constant should not happen as the compiler would have eliminated this by constant folding. This happens often due to macro expansion, less from the programmer writing it.

Right shift is harder because while you can add something to itself to double it, there is no corresponding opcode to halve something.

I was stuck here for months agonising over how to generate the (possibly unrolled) loops to right shift. Eventually taking the lead from the Amsterdam Compiler Kit, I decided to fob right shifts off to library routines. Perhaps later I might inline some simple cases like right shift by one. Get something working first.

A note here on efficiency: There are two aspects: code size and machine cycles. For code size, except in the simplest cases such as a shift by one on a byte, less instructions will be generated because a bunch of inline instructions is replaced by subroutine calls and returns. For machine cycles, there is the overhead of the call and return, but again, except for the simplest cases, the proportion of time spent in the call and return is not significant compared to the time doing the shifting as the shift gets larger. There is no stack variable access overhead as the library routines expect arguments in registers. (Reentrancy is not an issue as these routines are leaf routines.) Anyway as I wrote, get something general working first, then optimise as necessary.

Six routines are needed, for signed and unsigned shifts for char, int, and long. In signed shifts the sign bit is preserved. In unsigned shifts there is no sign bit. Operands are expected in registers. These routines were tested separately, but the backend routines to plug them into the code stream have not been completed. TODO number 1  Unfortunately there is scant documentation on the backend routines I need to call to go from the iCode (the internal representation of the C code) to assembler code. I just have to work it out by trial and error. ☹️