Class 36: Steps in Compilation, Continued

Held Friday, April 27, 2001

Summary

Today we continue our translation of a simple recursive Pascal program.

Notes

• Today is the last day to turn in homework 2. Please get something to Rachel today.
• Monday is the preferred due date for the type checker. Wednesday is the last day to get something in.
• The CS barbeque is Saturday, May 12. Please let me know whether or not you're coming.
• The Math/CS picnic is on Friday, May 4
• Mr. Stone willl be visiting class this week and next.
• Handout: fact.p

Overview

• What we've done so far.
• Procedure initialization and cleanup
• Factorial
• Helper

Where We've Been

• We've written a Pascal program for tail-recursive factorial.
• We've figured out how to generate code for the write and read statements.
• We've figured out how to generate code for the procedure call.
• We've decided that we return values from procedure calls in a particular register (%eax).

Procedure Wrappers

• What should happen at the start of a procedure?
  • Remember the old base pointer
  • Update the base pointer to the stack pointer
  • Update the stack pointer for local variables and return value
• Where on the stack will the parameters be?
  • "Above" the base pointer
• Where on the stack will the return value be?
  • Below the base pointer
• So, what does the stack look like? Recall that stacks grow downward.

  +---------+
  | param_1 |
  +---------+
  | param_1 |
  +---------+
     ...
  +---------+
  | param_n |
  +---------+
  | ret-add |
  +---------+
  | old-ebp |
  +---------+ <-- ebp
  | retval  |
  +---------+
  | local_1 |
  +---------|
     ...
  +---------+
  | local_m |
  +---------+ <-- esp
  

• What should happen at the end of a procedure?
  • Make sure the result is in %eax
  • Restore the stack pointer
  • Restore the base pointer
  • Return
• So, for the start of factorial, we use

    push Register(ebp)                # Remember old base pointer
    move Register(esp) Register(ebp)  # Update base pointer
  ...
    move Register(ebp) Register(esp)  # Restore stack pointer
    pop  Register(ebp)                # Restore base pointer
    ret                               # Return
  

• What about the body of factorial, which just consists of a recursive call.
• We need to push n

    push Offset(Register(ebp,Constant(-8)))
  

• We need to push 1

    push Constant(1)
  

• We need to call the helper

    call Helper
  

• We need to put the result (which is in %eax) into our result location (which is right below the base pointer)

    move %eax Offset(Register(ebp),Constant(4))
  

Other Activities

• Setup and recursive calls in helper
• ...

Putting it All Together

  ivar Val 0
  svar STRING1 "Please enter a number: "
  svar STRING2 "The factorial of "
  svar STRING3 " is "
  svar STRING4 "."
Label Program_Factorial
  # write('Please enter a number: ')
  push Constant(23)
  push Address(STRING1)
  push Constant(WRITE_A_STRING)
  push Constant(1)
  push Address(_p_stdout)
  call _p_write
  popn Constant(5)
  # readln(Val)
  pushl Constant(READ_A_NEWLINE)
  pushl Address(Val)
  pushl Constant(READ_A_STRING)
  pushl Constant(2)
  call _p_read
  popn Constant(4)
  # write('The factorial of ');
  ...
  # write(val:1)
  push Constant(1)
  push Value(Val)
  push Constant(WRITE_A_NUMBER)
  push Constant(1)
  push Address(_p_stdout)
  call _p_write
  popn Constant(5)
  # write(' is ');
  ...
  # write(factorial(val):1) becomes
  #   T1 := factorial(val)
  #   write(T1:1)
  # T1 := factorial(val)
  push Value(Val)
  call Factorial
  move Register(eax) into T1
  popn Constant(1)
  # write(T1:1)
  ...
  # writeln('.')
  push Constant(WRITE_A_NEWLINE)
  push Constant(1)
  push Address(STRING4)
  push Constant(WRITE_A_STRING)
  push Constant(2)
  push Address(_p_stdout)
  call _p_write
  popn Constant(6)
  # end
  return
Label Factorial
# Initialization
  push Register(ebp)
  move Register(esp) Register(ebp)
  push Constant(0)
# factorial := helper(n,1)
  push Offset(Register(ebp),Constant(8))
  push Constant(1)
  call Factorial_Helper
  move Register(%eax) Offset(register(ebp),Constant(-4))
# Cleanup
  move Offset(register(ebp),Constant(-4)) Register(%eax)
  move Register(ebp) Register(esp)
  pop  Register(esp)
  ret
Label Factorial_Helper
# Initialization
  push Register(ebp)
  move Register(esp) Register(ebp)
  push Constant(0)
# if (n = 0) then
  cmp  Offset(register(ebp),Constant(-8)) Constant(0)
  je   LABEL_1
  jump LABEL_2
label LABEL_1
# helper := acc
  move Offset(register(ebp),Constant(-4)) Offset(register(ebp),Constant(4))
  jump LABEL_3
label LABEL_2
# helper := helper(n-1,n*acc)
# T2 := n-1
  sub  Offset(register(ebp),Constant(-8)) constant(1) T2
# T3 := n*
  mul  Offset(register(ebp),Constant(-8)) Offset(register(ebp),Constant(-4)) T3
# helper(T2,T3)
  push T2
  push T3
  call Factorial_Helper
# helper :=
  move Register(eax) Offset(register(ebp),Constant(-4))
  jump LABEL_3
label LABEL_3
# Cleanup
  move Offset(register(ebp),Constant(-4)) Register(%eax)
  move Register(ebp) Register(esp)
  pop  Register(esp)
  ret