Lab: Stack Frames

Summary: In a recent class, we discussed the ways in which different kinds of variables (global vs. local vs. semi-local vs. parameter vs. return value; primitive vs. compound) can be stored. In today's lab, you will explore the ways in which our Pascal compiler stores parameters and local variables. You will also attempt to derive other information about the structure of the stack frame our compiler uses.

Contents:

• Preliminaries
• Background
  • The Basics
  • Addressing
  • Registers
  • Instructions
• Exercises
  • Exercise 1: Stack Frames and Function Calls
  • Exercise 2: Variable and Parameter Locations
  • Exercise 3: Variable Parameters
  • Exercise 4: Local Variables
  • Exercise 5: Compound Expressions
  • Exercise 6: Local Functions

Preliminaries

Collaboration: Feel free to work on this lab in pairs or trios.

Grading: We will discuss this lab at the end of today's lab session and the beginning of tomorrow's class. You will gain more insight from doing the lab and having it discussed than from me grading your work.

Compiling Pascal Programs: In order to compile Pascal programs, you will need to use the pc or gpc compiler on lovelace. You should use the -S flag to generate assembly code.

Background

In order to complete today's lab, you'll need some guidance in reading GNU x86 assembly. Here are some key points.

The Basics

• Assembler directives (instructions that help set up the environment, but are not used during execution) usually begin with a period.
• Assembly instructions don't.
• Labels end with a colon.
• Register names are preceded by a percent sign, as in %ebp.
• Constant values are preceded by a dollar sign, as in $24.

Addressing

• Variables declared by .local var can be referenced by name.
• If one of those variable names is preceded by a dollar sign, you get the address of that variable.
• Indirect addressing is given by (%reg); that is, the memory location stored in the given register.
• You can also take offsets from those addresses with either num(%reg) or %reg(num).

Registers

• %esp is the stack pointer.
• %ebp is the beginning of frame pointer (what I usually call fp).
• %eax through %edx are general purpose registers.

Instructions

The following are some of the key instructions you'll encounter.

movl source, destination

Copy information from source to destination.

pushl reg

Push the contents of the register on the stack.

popl reg

Pop the top of the stack and store it in reg.

call label

Call a procedure.

ret

Return from a procedure.

addl increment location

Add the increment to the value stored in the location.

jmp label

Transfer control to the code starting at the given lable.

cmpl val1 val2

Compare two values (used with conditional jumps, like ce).

je label

If the result of the last comparison was the two values are equal, jump to the given label.

call procname

Remember the current instruction pointer (presumably, by shoving it on the stack) and branch to the beginning of the given procedure.

return

Return from a procedure call.

Exercises

Here's a simple Pascal program that reads a value, applies a function to that value, and prints out the result.

program example(input,output);
  var
    inval: integer;
    result1,result2: integer;
  function increment(val: integer): integer;
  begin
    val := val + 5;
    increment := val;
  end;
  function decrement(val: integer; delta: integer): integer;
  begin
    decrement := val - delta;
  end;
begin
  readln(inval);
  result1 := increment(inval);
  result2 := decrement(inval,10);
  writeln(inval);
  writeln(result1);
  writeln(result2);
end.

Exercise 1: Stack Frames and Function Calls

a. What steps does a caller typically do before it calls the funtion?

b. What steps does a caller typically do after that function returns?

c. What steps are done at the beginning of the code for each function?

d. What steps are done at the end of the code for each function?

e. Does the stack grow from low addresses to high addresses or from high to low? What evidence do you have for this answer?

f. What do your previous answers tell you about stack frames in this compiler?

Exercise 2: Variable and Parameter Locations

a. Where are inval and result1 stored?

b. Where is val stored?

c. Where is the return value from increment stored?

Exercise 3: Variable Parameters

a. Compile your program to an executable and run it with input of 5.

b. Change the header for increment to read

function increment(var val: integer): integer

What change do you expect this to have to the output of the program?

c. Verify your results experimentally.

d. Examine the assembly code for the modified program to see what the compiler has done differently.

Exercise 4: Local Variables

Add some local variables to increment or decrement and determine where those variables are stored.

Exercise 5: Compound Expressions

Add a new function (and function call), zebra, that includes some interesting expression involving multiple subexpressions. Determine where the intermediate results are stored. Make sure that zebra has at least one local variable.

Exercise 6: Local Functions

Add another function, stripes, within the scope of zebra. Make sure that it has at least one local variable and that it uses both the parameters and local variables from zebra.

a. Where are the parameters to stripes stored in a call?

b. Where are the local variables stored?

c. How does stripes access the parameters of zebra?

d. How does stripes access the local variables of zebra?