C
COMPILER
Fraser
and Hanson’s book is the literate source code
of their lcc retargetable C compiler.[1] I
downloaded the V.4.1 distribution and modified it
to target the nascent RISC, xr16.
Most
of lcc is machine independent; targets are defined
using machine description (md) files. Lcc ships with
’x86, MIPS, and SPARC md files, and my
job was to write xr16.md.
I
copied xr16.md from mips.md, added it to the makefile,
and added an xr16 target option. I designed xr16 register
conventions (see Table 1) and changed my md to target
them.
| Register
r0
r1
r2
r3–r5
r6–r9
r10–r12
r13
r14
r15
|
Use
always zero
reserved for assembler
function return value
function arguments
temporaries
register variables
stack pointer (sp)
interrupt return address
return address
|
| Table
1—The xr16 C language calling conventions
assign a fixed role to each register. To minimize
the cost of function calls, up to three arguments,
the return address, and the return value are
passed in registers. |
At
this point, I had a C compiler for a 32-bit 16-register
RISC, but needed to target a 16-bit machine with sizeof(int)=sizeof(void*)=2.
lcc obtains target operand sizes from md tables, so
I just changed some entries from 4 to 2:
Interface
xr16IR = {
1,
1, 0, /* char */
2,
2, 0, /* short */
2,
2, 0, /* int */
2,
2, 0, /* T* */
Next,
lcc needs operators that load a 2-byte int into a
register, add 2-byte int registers, dereference a
2-byte pointer, and so on. The lcc ops utility prints
the required operator set. I modified my tables and
instruction templates accordingly. For example:
reg:
CVUI2(INDIRU1(addr)) \
"lb r%c,%0\n" 1
uses
lb rd,addr to load an unsigned char at addr and zero-extend
it into a 16-bit int register.
stmt:
EQI2(reg,con) \
"cmpi r%0,%1\nbeq %a\n" 2
uses
a cmpi, beq sequence to compare a register to a constant
and branch to this label if equal.
I
removed any remaining 32-bit assumptions inherited
from mips.md, and arranged to store long ints in register
pairs, and call helper routines for mul, div, rem,
and some shifts.
My
port was up and running in just one day, but I had
already read the lcc book. Let’s see what she
can do. Listing 1 is the source for a binary tree
search routine, and Listing 2 is the assembly code
lcc-xr16 emits.
typedef struct TreeNode {
int key;
struct TreeNode *left, *right;
} *Tree;
Tree search(int key, Tree p) {
while (p && p->key != key)
if (p->key < key)
p = p->right;
else
p = p->left;
return p;
}
|
| Listing 1—This
sample C code declares a binary search tree
data structure and defines a binary search function.
Search returns a pointer to the tree node whose
key compares equal to the argument key, or NULL
if not found.
|
_search: br L3 ; r3=k r4=p
L2: lw r9,(r4)
cmp r9,r3 ; p->k < k?
bge L5
lw r4,4(r4) ; p = p->right
br L6
L5: lw r4,2(r4) ; p = p->left
L6:L3: mov r9,r4
cmp r9,r0 ; p==0?
beq L7
lw r9,(r4)
cmp r9,r3 ; p->k != k?
bne L2
L7: mov r2,r4 ; retval = p
L1: ret
|
| Listing 2—Here’s the
xr16 assembly code (with comments added) that
lcc generates from Listing 1. lcc has done a
good job, although a few register-to-register
moves are unnecessary. |
