11. Optimization: Register stack (and assignments)

Today we will do the most fun part of all programming: premature optimization. Remember that the current code generation is pretty lousy and riddled with tons of pushes and pops? We'll get rid of them now.

Instead of using the stack we will use more registers. When we would normally push a value onto the stack to get space for a new value, we will now simply take a new register for the new value.

I made a new register manager (registers.pb) that allows us to easily get unused registers and dispose them when done with them. It's really simple.

#RegMax = 7 ; Highest valid register ID

Structure SRegister
  Name.s
  Used.i
EndStructure

Global Dim Registers.SRegister(#RegMax)
Registers(0)\Name = "Error: Null register"
Registers(1)\Name = "eax"
Registers(2)\Name = "edx"
Registers(3)\Name = "ecx"
Registers(4)\Name = "ebx"
Registers(5)\Name = "edi"
Registers(6)\Name = "ebp"
Registers(7)\Name = "esi"

Procedure RegGet()
  Protected I
  For I = 1 To #RegMax
    If Registers(I)\Used = 0
      Registers(I)\Used = 1
      ProcedureReturn @Registers(I)
    EndIf
  Next
  Error("Too complex expression (out of cpu registers)")
EndProcedure

Procedure.s RegStr(*Reg.SRegister)
  ProcedureReturn *Reg\Name
EndProcedure

Procedure RegDispose(*Reg.SRegister)
  *Reg\Used = 0
EndProcedure

Procedure.s RegUse(*Reg.SRegister)
  RegDispose(*Reg)
  ProcedureReturn RegStr(*Reg)
EndProcedure

This code is rather simple. RegGet() finds an unused register and returns a pointer to the corresponding item in the array. RegStr() converts the pointer into a string. RegDispose() sets the state of the register to unused again. RegUse() returns the corresponding string and sets the register as unused.

We will now implement this on var.pb. Copy var.pb into regstack.pb. But before we go any further, we need a macro to simplify code generation a bit. Put this into base2.pb:

Macro Emit2(Instruction, Op1, Op2)
  Emit(Instruction + Op1 +", " + Op2)
EndMacro

It works just like Emit(), except it takes separate parameters.

Now on to the real deal. AddExp() should now be able to use two arbitrary registers instead of eax and ebp. But how can it know _which_ registers? A good idea here is to let each procedure return which registers it left its result in. So if the result of MulExp() is in eax, it should return a pointer that, when passed to RegStr(), gives the string eax.

Here is the new AddExp():

Procedure AddExp()
  ; addexp     ::=  {+  }
  Protected *R1, *R2
  *R1 = MulExp()
  While Look = '+'
    GetLookWhite()
    *R2 = MulExp()
    Emit2("add  ", RegStr(*R1), RegUse(*R2))
  Wend
  ProcedureReturn *R1
EndProcedure

As you can see, the first register is the result of the first call to MulExp(). If Look is not +, then that register also contains the result of AddExp(). If Look IS +, then we take the other operand from MulExp(), perform an add operation (where we discard the register *R2, since we have the result in *R1), and the result is still in *R1. So we return *R1 at the end of the procedure.

AddExp() never allocates any registers, because it gets them from MulExp(). Which is nice and easy on AddExp(), but where does MulExp() get the registers from? Look here:

Procedure MulExp()
  ; mulexp     ::=  {* }
  Protected *R1, *R2
  *R1 = Value()
  While Look = '*'
    GetLookWhite()
    *R2 = Value()
    Emit2("imul ", RegStr(*R1), RegUse(*R2))
  Wend
  ProcedureReturn *R1
EndProcedure

MulExp() gets its registers from Value(). Which is the procedure that needs the biggest changes:

Procedure Value()
  ; value  ::=  |  | '('  ')'
  Protected *R1
  If IsDigit(Look)
    *R1 = RegGet()
    Emit2("mov  ", RegStr(*R1), GetInteger())
  ElseIf IsAlpha(Look)
    *R1 = RegGet()
    Emit2("mov  ", RegStr(*R1), VarValue(GetName()))
  ElseIf Look = '('
    MatchWhite('(')
    *R1 = Expression()
    MatchWhite(')')
  EndIf
  ProcedureReturn *R1
EndProcedure

As you can see, Value() allocates a new register to put its value into, except when the value is the result of an expression, which must of course already be in an allocated register. Speaking of which, Expression() must be changed to return which register the result is in:

Procedure Expression()
  ; expression ::= <AddExp>
  ProcedureReturn AddExp()
EndProcedure

This may be a bit confusing. Expression() gets its register from AddExp(), which gets its registers from MulExp(), which gets its register from Value(), which, in turn, gets its register from Expression()! This seems like it may run for ever. But Value() will only get its result from Expression() when it sees an opening parenthesis, so unless the source contains an unlimited amount of opening parenthesis (or we forget to throw them away with MatchWhite()) then our program will not run for ever.

Since we are on a roll now, why not implement an assignment statement to round it off nicely? Here is the syntax:

; assignment  ::= <name> = <expression>

That should be simple:

Procedure Assignment()
  ; assignment  ::= <name> = <expression>
  Protected *R
  Protected Name.s
  Name = GetName()
  MatchWhite('=')
  *R = Expression()
  Emit2("mov  ", VarValue(Name), RegUse(*R))
EndProcedure

I want to point out that for an expression like (543+54)*(28+48), we have reduced the number of instructions from 13 to 7. Additionally, using only registers are faster than using the stack, because the stack means memory accesses (slow).

Here is the listing (note that it accepts assignment statements only):

; regstack.pb
IncludeFile "..\base2.pb"
IncludeFile "..\registers.pb"

Procedure.s VarValue(Var.s)
  ProcedureReturn "[v_" + Var + "]"
EndProcedure

Declare Expression()
Procedure Value()
  ; value  ::=  |  | '('  ')'
  Protected *R1
  If IsDigit(Look)
    *R1 = RegGet()
    Emit2("mov  ", RegStr(*R1), GetInteger())
  ElseIf IsAlpha(Look)
    *R1 = RegGet()
    Emit2("mov  ", RegStr(*R1), VarValue(GetName()))
  ElseIf Look = '('
    MatchWhite('(')
    *R1 = Expression()
    MatchWhite(')')
  EndIf
  ProcedureReturn *R1
EndProcedure

Procedure MulExp()
  ; mulexp     ::=  {* }
  Protected *R1, *R2
  *R1 = Value()
  While Look = '*'
    GetLookWhite()
    *R2 = Value()
    Emit2("imul ", RegStr(*R1), RegUse(*R2))
  Wend
  ProcedureReturn *R1
EndProcedure

Procedure AddExp()
  ; addexp     ::=  {+  }
  Protected *R1, *R2
  *R1 = MulExp()
  While Look = '+'
    GetLookWhite()
    *R2 = MulExp()
    Emit2("add  ", RegStr(*R1), RegUse(*R2))
  Wend
  ProcedureReturn *R1
EndProcedure

Procedure Expression()
  ; expression ::= 
  ProcedureReturn AddExp()
EndProcedure

Procedure Assignment()
  ; assignment  ::=  = 
  Protected *R
  Protected Name.s
  Name = GetName()
  MatchWhite('=')
  *R = Expression()
  Emit2("mov  ", VarValue(Name), RegUse(*R))
EndProcedure

Init()
Assignment()
If Look <> 0
  Expected("End of line")
EndIf
Input()