Re: Jack W. Crenshaw - Any clues how to optimize ?

Sten D. Sørsdal wrote:


>I am working on simple compiler (currently only a "basic" to x86 asm
>converter). It is based on the model by Jack W. Crenshaw. (Author of
>"Let's build a compiler" or something very similar). I am having
>problems to accept the inefficiency on the expression calculations.


>The code output is way below acceptable. Now i was wondering, how do i
>optimize this to be any better? I was thinking about a postfix
>solution, but since this compiler is going to a singleparse, i have to
>do this exclusivly for expressions. I havent been able to write a good
>solution for this problem, as if often tend to "fixing" the postfix
>routine. Could someone help me with this?


Stack-based postfix code for expressions tend to be fairly inefficient
as there is a lot of memory traffic. It is usually better to use
registers to hold the values during expression evaluation.


A simple way of achieving this is to use some of the registers for a
small stack. To do this, you have to keep track of the stack-top
pointer during compile time. Most expressions can be evaluated using
only 4 registers, so you could simply reserve 4 registers for
expression evaluation and "overflow" to memory when needed. If we
assume that you use registers 0-3 for this, then
expression-translation code could look like:


    expression | compile-time actions | code
-------------+----------------------+--------------------
    x | reg_no = reg_no+1 | load x to reg_no
-------------+----------------------+--------------------
    e1+e2 | compile e1; |
                          | compile e2; |
                          | reg_no = regno-1 | ADD reg_no reg_no+1


Initially, reg_no is set to -1, so the first variable is loaded to
register 0 (the actions are performed before the code is generated).
To handle overflow, the actions should test if reg_no is greater than
3 and then use some fixed memory locations based at adress BASE to
hold the excess values. The translation for variable x now becomes


    reg_no = reg_no+1
    if reg_no<4 then
        code = load x to reg_no
    else
        code = move x to BASE+(reg_no-4)*4 /* assume byte-addressing */


For e1+e2 you have to distinguish three cases:


  1) both arguments in registers
  2) first argument in register, 2nd in memory
  3) both arguments in memory.


Note that you will need an auxiliary register for moving values from
variables to memory locations and for doing arithmetic on values in
memory. If you can't reserve a total of 5 registers for expression
evaluation, you can reduce this to 4 by using only 3 for the stack.


There are a few inefficiencies in the above strategy for using fixed
registers and memory locations to hold stack values. For example, if
the stack has overflowed to memory, then you first use a
memory-to-memory move for getting a variable to the stack and then
later take it from there to operate on it. It is better instead to
take it directly from the variable loation when you need to operate on
it. To achieve this, a "lazy" loading scheme can be used. In this, you
don't load variables into registers or stack-slots until you need to
operate on them, and at that point you exploit the x86 instructions
that can take an argument from memory to avoid doing so in some of the
cases.


The idea is to keep a compile-time model of the stack, where the model
for each stack-entry tells where the value can be found. This can be
in a register, in a variable or in a memory-based stack slot.
Additionally, you keep track of which registers and stack-slots hold
values that are needed later on. When compiling a variable, no code is
generated but the compile-time stack is updated to indicate that the
stack-top is to be found in the variables location. When compiling
(say) an addition, the generated code depends on where the operands
are found:


  1) If one operand is in a register and the other in memory, an
        instruction that adds the memory-contents to the register is
        generated and the compile-time stack description is updated to
        indicate that the new stack-top is in the register.


  2) If both arguments are in registers, a prely register-based
        addition instruction is generated using one register as both
        operand and destination and the register description now indicates
        that the register holding the other operand is free. The
        compile-time stack is updated as indicated above.


  3) If both arguments are in memory, a register for doing the
        operation needs to be found. We hence look in the register
        description for a free register, mark it as used and load one
        operand into this and proceed as in case 1. If no free register is
        available, one is made so by moving a register to memory. The
        compile-time stack is updated to reflect the new location of the
        stack element that used to be in the register (hence, the register
        description must also record which stack element is held in a used
        register).


Torben Mogensen (torbenm@diku.dk)

Return to the comp.compilers page.
Search the comp.compilers archives again.