Ex3FunctionsCodeGenerator.lhs

> module Ex3FunctionsCodeGenerator where
> import Ex3FunctionsTypes
> import Data.List

----------------------------------------------------------- 
Solution for Compilers exercise 3
Paul Kelly Imperial College London 2009 
-----------------------------------------------------------

Fill in the gaps...

Part (1): translate function declaration
-- First create the Define node, representing the function name
-- Then concatenate this list with the result of translating the
   body, given all but D0 as available regs
-- Finally concatenate the list containing the return command
   which will represent the return to the calling function

> transFunction (Defun fname paramname body) 
>   = [Define fname] ++ transExp body (tail allRegs) ++ [Ret]


Part (2): saving registers
-- Given all registers that are in use, the unused registers
   are calculated by allRegs \\ regsNotInUse
-- Map the function saveReg across all the registers that are
   currently in use, generating the command
-- Return the list that represents the sequence of all the
   register saving commands

> saveRegs :: [Register] -> [Instr] 
> saveRegs regsNotInUse 
>   = [saveReg r | r <- allRegs \\ regsNotInUse]
>     where 
>       saveReg reg = Mov (Reg reg) Push

   Restoring Registers
-- The opposite precedure of the save registers, important to
-- remember to pop the registers in reverse order of how they
-- were pushed.

> restoreRegs :: [Register] -> [Instr] 
> restoreRegs regsNotInUse
>   = [restoreReg r | r <- (reverse regsInUse)]
>     where 
>       regsInUse = allRegs \\ regsNotInUse
>       restoreReg reg = Mov Pop (Reg reg)

   Arithmetic Precedence Selection
-- Deals with choosing which expressions to process first.
-- Both addition and subtraction will have equivilant precedence
-- hence the equivilant pattern match for both.

> pre (Const x) = 1 
> pre (Var str) = 1
> pre (Plus  e1 e2) = preArithmetic e1 e2
> pre (Minus e1 e2) = preArithmetic e1 e2
> pre (Apply func e) = pre e
> preArithmetic e1 e2
>   = min p1 p2 
>     where 
>       p1 = max (pre e1) ((pre e2) + 1) 
>       p2 = max ((pre e1) + 1) (pre e2) 

Part (3): translate expression (ie function body, perhaps including function calls)
-- Given an expression and list of available registers, return a
   list of instructions in assembly
-- For Reference:  Exp  =  Const Int 
                        |  Var String
                        |  Plus Exp Exp
                        |  Minus Exp Exp
                        |  Apply String Exp

   Exhausted Registers
-- List of available registers is empty, call translate expression
-- again but with all registers (as we need not handle running out
-- of registers - yay!)

> transExp e [] = transExp e allRegs 
 
   Immediates
-- When accessing a constant, move the constant into the next
-- available register as an immediate number.

> transExp (Const a) (r:rs) = [ Mov (ImmNum a) (Reg r) ] 

   Assignment 
-- We are to assume that functions may only have a single parameter
-- which is to be stored in the register D0. As such, when we attempt
-- to assign a value to the param, use mov to move the value of the
-- first given reg into D0 (referenced here as paramReg, see types:93)

> transExp (Var string) (r:rs) = [ Mov (Reg paramReg) (Reg r) ] 

   Addition
-- First time precedence needs to be taken into account. Using
-- the `pre` function to evaluate a particular types precedence.

> transExp (Plus e1 e2) (r1:r2:rs)
>   = transExp e' (r':r'':rs) ++ transExp e'' (r'':rs)
>     ++ [ Add (Reg r') (Reg r'') ]
>     where
>       (e', e'', r', r'') = selectExp e1 e2 r1 r2

   Subtraction
-- Very similar to the addition, just using the Minus token.

> transExp (Minus e1 e2) (r1:r2:rs)
>   = transExp e' (r':r'':rs) ++ transExp e'' (r'':rs)
>     ++ [ Sub (Reg r') (Reg r'') ]
>     where
>       (e', e'', r', r'') = selectExp e1 e2 r1 r2

   Function Calls
-- First, save all the available registers.
-- Second, evaluate the expression to pass as the param.
-- Move the result of the expression into the param register.
-- Jump to the function given by func.
-- Move the value of result register into the destination.
-- Restore all the registers.

> transExp (Apply func e) (r:rs) 
>   = saveRegs (r:rs) ++ transExp e (r:rs) 
>     ++ [ Mov (Reg r) (Reg paramReg) ] ++ [Jsr func] 
>     ++ [ Mov (Reg resultReg) (Reg r) ] 
>     ++ restoreRegs (r:rs)

   Expression Selection
-- Both addition and subtraction requires selecting the leaf that
-- has the highest precedence. `selectExpr` will return a tuple
-- that switches the expressions for that of the highest precedence.

> selectExp e1 e2 r1 r2
>   | pre e1 > pre e2 = (e1, e2, r1, r2)
>   | otherwise       = (e2, e1, r2, r1)