CIS 240 / CIT 593

Introduction to
Computer Systems
University of Pennsylvania
School of Engineering and Applied Science
Computer and Information Systems Department
Dr. Thomas Farmer

MODULE 9: Introduction to C & The Stack

Overview of Module
• Background
• What is C? The Big Ideas in C…C vs. Java

• Section 1: Intro to C
• A simple C program
• Compiling C Program into Assembly Language
• Introduction of the Stack

• Section 2: The Stack

• Stack Frames
• Maintenance of the Stack

• Section 3: How functions are implemented using the stack (a full call/return example)
• Prologue
• Function calling a function
• Function Body
• Function Epilogue
Property of Penn Engineering 2
Programming in C == Working without a net

A C program is like a fast dance on a newly waxed dance floor by

people carrying razors." — Waldi Ravens.
Property of Penn Engineering 8-4
The Big Ideas In C
• A High-Level / Low-Level Language
• A compiled language (C à Assembly à Machine)

• Imperative
• Assignment statements that explicitly change memory values (e.g. : C, C++, Java: c = a+ b)
• As opposed to declarative statements, which describe function (e.g.: SQL: SELECT * FROM users)

• Procedural
• All code statements contained in functions
• Functions can be bundled into libraries, which allow you to build large programs from smaller pieces
• Functions are implemented using a stack

• File-Oriented
• Files: a simple abstraction for permanent storage and I/O

• Portability
• The same C code can be compiled for different ISAs
Property of Penn Engineering 5
The Compilation Process
• The code files that you write are “compiled” into assembly code, which is then
“assembled” into machine code
• C Code: text files (.c, .h)
• Assembly Code: text files (.asm)
• Machine Code: binary files (e.g.s: .obj, .exe, [Link])

• LCC (the LC4 C compiler that produces just assembly, no .obj)

• Some compilers (like gcc ) perform both phases and simply output the binary,
executable result

C Asm Machine
Code Code Code

• Figure 11.2 on page 295 of the textbook has detailed steps!

Property of Penn Engineering 6

C versus Java
C Code Java Code

Java
Bytecode
Assembly
Code
Java Virtual
Machine

Machine Machine
Code Code

Property of Penn Engineering 7

History: 1969
• AT&T Bell Labs drops out of
MULTICS project

• Ken Thompson develops UNICS

• Ken Thompson writes interpreted

language: B

• Dennis Ritchie and Brian Kernighan

improve on B and call it "C”

A purported picture of Dennis Ritchie and Brian Kernighan, two of the

key developers of C, with a PDP-11 minicomputer

Property of Penn Engineering 8

History: PDP-11 Specs
• 16 bit words – 4K memory locations

• Memory mapped I/O

• 6 general registers

• Stack Pointer – register 6

• Instruction Pointer (PC) – register 7

• Sound familiar?

Property of Penn Engineering 9

SECTION 1: Intro to C

OUR FIRST C PROGRAM

Property of Penn Engineering 10

Our First LC4 C Program
/* multiply.c: multiply 2 integers a, b, store in c */

int main()
{
/* declare and initialize variables BEFORE program */
int a=20 ;
int b=10 ;
int c=0 ;

/* multiply numbers */
c=a*b ;

/* return from main */

return 0 ; /* success */

}
Property of Penn Engineering 11
Our First LC4 C Program: Let’s Dissect
/* multiply.c: multiply 2 integers a, b, store in c */

int main()
{
/* declare and initialize variables */
int a=20 ;
int b=10 function
; name: main
int c=0 ;• All C programs must start in the function main
• Recall that C is “procedural” i.e. everything is in a function
/* multiply numbers */
c=a*b ; • Note that this gets ‘converted’ to a label in assembly

/* return from main */

return 0 ; /* success */

}
Property of Penn Engineering 12
Our First LC4 C Program: Let’s Dissect
/* multiply.c: multiply 2 integers a, b, store in c */

int main()
{
/* declare and initialize variables */
int a=20 ;
int b=10 Arguments
; to function main: none
int c=0 ;We will soon encounter a variation on this, but LC4 has none

/* multiply numbers */
c=a*b ;

/* return from main */

return 0 ; /* success */

}
Property of Penn Engineering 13
Our First LC4 C Program: Let’s Dissect
/* multiply.c: multiply 2 integers a, b, store in c */

int main()
{
/* declare and initialize variables */
int a=20 ;
int b=10 Return
; type of function main: int
int c=0 ;• After function completes, it will return an integer to the caller
• Recall that C functions can only return one value
/* multiply numbers */
c=a*b ;

/* return from main */

return 0 ; /* success */

}
Property of Penn Engineering 14
Our First LC4 C Program: Let’s Dissect
/* multiply.c: multiply 2 integers a, b, store in c */

int main()
{
/* declare and initialize variables */
int a=20 ;
int b=10 ;
int c=0 ;

A “block”numbers
/* multiply of code */
c=a*b ;
• The entirety of the function main() is defined between these two curly braces: {}
• The curly braces tell the compiler where main ends and where it begins!
/* return from main */
return 0 ; /* success */

}
Property of Penn Engineering 15
Our First LC4 C Program: Let’s Dissect
/* multiply.c: multiply 2 integers a, b, store in c */

int main()
{
/* declare and initialize variables BEFORE program */
int a=20 ;
int b=10 ;
int c=0 ; Local variables
• The “scope” of these variables exists only within the {}
• After
/* multiply numbers */main() is called, these variables cease to exist
c=a*b ;
We have both declared: int a
and initialized
/* return from main */ the variable: a=20; can do it separately
return 0 ; /* success */ in C are not initialized to 0!
Local variables
} Variables MUST be declared at the top of block!
Property of Penn Engineering 16
Our First LC4 C Program: Let’s Dissect
/* multiply.c: multiply 2 integers a, b, store in c */

int main()
{
/* declare and initialize variables */
int a=20 ;
int b=10 ;
int c=0 ;

/* multiply numbers */
c=a*b ; Arithmetic operation
• RHS of equals sign is evaluated and then assigned to LHS
/* return from main */
return 0 ; /* Recall: C is*/
• success imperative
• This changes state of the actual machine (reg file)
}
Property of Penn Engineering 17
Our First LC4 C Program: Let’s Dissect
/* multiply.c: multiply 2 integers a, b, store in c */

int main()
{
/* declare and initialize variables */
int a=20 ;
int b=10 ;
int c=0 ;

/* multiply numbers */
c=a*b ;

/* return from main */

Return value
return 0 ;
• C doesn’t have true/false
} • Typically 0 indicates “success”
• Non-0 indicates “failure”
Property of Penn Engineering 18
Our First LC4 C Program: Let’s Dissect
/* multiply.c: multiply 2 integers a, b, store in c */

int main()
{
/* declare and initialize variables BEFORE program */
int a=20 ;
int b=10 ;
int c=0 ;

/* multiply numbers */
c=a*b ;

/* return from main */

return 0 ; /* success */

}
Property of Penn Engineering 19
SECTION 1: Intro to C

COMPILING C INTO ASSEMBLY

Property of Penn Engineering 20

Our First LC4 C Program: Let’s Compile!
/* multiply.c: multiply 2 integers a, b, store in c */

int main()
{
/* declare and initialize variables BEFORE program */
int a=20 ;
int b=10 ;
int c=0 ;

/* multiply numbers */
c=a*b ;

/* return from main */

return 0 ; /* success */

}
Property of Penn Engineering 21
How Would You Translate into Assembly?

;; [Link]: multiply 2 integers a, b, store in c ;;

main
CONST R0, #20 ; a = 20
CONST R1, #10 ; b = 10
CONST R2, #0 ; c = 0
MUL R2, R0, R1 ; c = a*b
CONST R3, #0 ; return 0 ß caller must check R3
RET
• “main” is just a label for a subroutine

• Since it can be called, it must have a “RET” at the end

• Caller would have invoked main using JSSR

Property of Penn Engineering 22

SECTION 1: Intro to C

COMPILING C INTO ASSEMBLY

- USING A STACK!

Property of Penn Engineering 23

C uses a STACK to Store Data (not register file)
• Functions (like main) build a simple stack in data memory as they run
• It will hold: local variables, return values, and arguments!

Stack of
books
c=0
Data Memory:
0
b=1
0
a=2

Property of Penn Engineering 24

C uses a STACK to Store Data (not register file)
• Functions (like main) build a simple stack in data memory as they run
• It will hold: local variables, return values, and arguments!
• C-Compiler will generate assembly code to use data memory as a stack
• Why do this?
• Because the register file is too small; if more than 8 variables, OR if we wish to call other subroutines
Address Contents Purpose
x7FF6
x7FF7
x7FF8
Stack grows
Data Memory: x7FF9 0 c=0 backwards in
x7FFA 10 b=10 memory
x7FFB 20 a=20
x7FFC 0 return value
x7FFD
How does main() know where in data memory to write to?
we tell it by setting a register before main() starts (e.g. R5 = x7FFC) Property of Penn Engineering 25
How LC4 Compiler (LCC) translates into Assembly
; BEFEORE we call main(), let’s pick a space in data memory to write to:
CONST R5, xFC ; setup R5 to point to a place in data mem
HICONST R5, x7F ; R5 = x7FFC
JSR main ; R7 = PC + 1, PC = main

main
; PROLOGUE – save R7 to stack & save local vars. to stack
STR R7, R5, #1 ; store R7 so we can use R7
CONST R7, #20 ; a = 20
STR R7, R5, #-1 ; then store A in stack
CONST R7, #10 ; b = 10
STR R7, R5, #-2 ; then store B in stack
CONST R7, #0 ; c = 0
STR R7, R5, #-3 ; then store C in stack

; BODY – where the work of the function is done!

LDR R7, R5, #-1 ; load A into R7
LDR R0, R5, #-2 ; load B into R0
MUL R7, R7, R0 ; c=a*b
STR R7, R5, #-3 ; update variable C in stack

; EPILOGUE – packup return values, restore R7, & return

CONST R7, #0 ; setup return value
STR R7, R5, #0 ; save return value in stack
LDR R7, R5, #1 ; restore R7, so that RET will work!
RET Property of Penn Engineering 26
C uses a STACK to Store Data (not register file)
• Functions (like main) build a simple stack in data memory as they run
• It will hold: local variables, return values, and arguments!
• The stack may also hold return address!

Address Contents Purpose

x7FF6
x7FF7
x7FF8
Stack grows
Data Memory: x7FF9 0 c=0 backwards in
x7FFA 10 b=10 memory
x7FFB 20 a=20
x7FFC 0 return value
x7FFD R7=PC+1 return address
How does main() know where in data memory to write to?
we tell it by setting a register before main() starts (e.g. R5 = x7FFC) Property of Penn Engineering 27
Where Does the Stack Live On the LC4?
• For C programs, divide LC4 data memory into 3 regions:
x0000
• Global variables
Program Memory
• Dynamic storage (“heap”)
x1FFF
• The stack x2000

Global Variables
x3FFF
User Data Memory x4000
partitioned further for C:
globals, heap, stack Dynamic Storage
(“heap”)

x6FFF
x7000 Local Variables
x7FFF (“stack”)
Property of Penn Engineering 28
C Uses a STACK to Store Data
• Functions build a simple stack in data memory as they run
• It will hold: local variables, return values, and arguments
• On the LC4, the stack will live in User data memory: x7000 to x7FFF

Address Contents Purpose

x7FF6
x7FF7
x7FF8
Stack grows
Data Memory: x7FF9 0 c=0 backwards in
x7FFA 10 b=10 memory
x7FFB 20 a=20
x7FFC 0 return value
x7FFD

Property of Penn Engineering 29

Where on the Stack is my Data?
Enter: The Symbol Table!
• To record where items are placed on the stack for a function
• The compiler creates a “symbol table” as it parses the .C file
• Instead of recording exact addresses for variables, it uses an offset
• This way a function could use any starting place in data memory and build its stack
Variable Type Location Scope Other
Name (as an offset) info…
a int -1 main
b int -2 main
c int -3 main

• Notice the “memory” location is just an offset

• Recall, we set R5 = x7FFC before we called main(),
• Where a, b, and c are stored, are relative the starting location (R5 for example)

Property of Penn Engineering 30

SECTION 2: The Stack

WHAT IS A STACK FRAME?

Property of Penn Engineering 31

 The Stack, Frames, and Pointers…Oh My!
• Functions build a simple stack in data memory as they run
• They do this to hold: local variables, return values, and arguments
• A Frame - A logical grouping of the data, on the stack, that belongs to a single function
• as one function calls another, each function will have its own frame
• Frame Pointer - A register that holds a starting address for the frame
Address Contents Purpose
x7FF6
x7FF7
x7FF8
Data x7FF9 0 c=0
Memory x7FFA 10 b=10
x7FFB 20 a=20
Frame Pointer (R5)
starting address x7FFC 0 return value
for the frame
x7FFD R7=PC+1 return address

Property of Penn Engineering 32

Exact Order of An LC4 Frame
• Frames (aka activation records) must have an exact order
• We know a frame will hold 3 basic things:
• Local variables, return value, arguments
• A frame will also hold a few more items:
1. Return address (where to return after function completes)
2. A copy of the “calling functions” frame pointer (so we can restore it when our function completes)
3. Temporary data (in case we run out of registers in the function)
4. Arguments to other functions (in case we call another function from our function)

temporaries, arguments to callees

local variables
caller’s frame pointer (FP)
return address (RA)
return value (RV)
arguments

Property of Penn Engineering 33

Addressing Items In the Frame With Pointers
• We’ll use register R5 and R6 to point to items in the frame
• R6 will be used to point to the “top of the frame” (actually, it will point to the top of the stack!)
• R5 will be used to point to where we saved the calling function’s frame pointer
• We’ll use R5 to compute the address of any of the items in blue
• We’ll use R6 to compute the address of any of the items in red

temporaries, arguments to callees R6

local variables
caller’s frame pointer (FP) R5
return address (RA)
return value (RV)
arguments

Property of Penn Engineering 34

SECTION 2: The Stack

THE OPERATION OF THE STACK

Property of Penn Engineering 35

How Does the Stack Work for
Two Functions?
int pow(int a, int p) {
int c ;
for (c = 1; p > 0; p--)
c = c * a ; /* multiplies a by itself p times */
return c ;
}

int main() {
int a=2 ;
int b=3 ;
int c=0 ;
c = pow (a, b) ; /* raises a to the b power: ab */
}
Property of Penn Engineering 36
Growing & Shrinking of the Stack
• As a program runs, the stack will grow and shrink
• When a function is called by another, the called function will “push” its frame onto the stack
• Arguments to function are pushed by the caller
• Everything else is pushed on the stack by the function itself
• Many frames can exist on the stack at a time
• When a function returns, it “pops” its frame off the stack
R6
some
other
func()
R5
R6 R6
pow pow pow
R5 R5
R6 R6
main main main main main
R5 R5
Only main()’s main() calls pow() calls Other func() pow()
Frame on pow() some_other returns returns
the stack func()

Stack grows & shrinks over time

(as program is running on CPU) Property of Penn Engineering 37
SECTION 3: The Stack Call / Return Sequence

A FUNCTION’S PROLOGUE
--EX: MAIN()

Property of Penn Engineering 38

Let’s Manually Compile This Program For The LC4
int pow(int a, int p) {
int c ;
for (c = 1; p > 0; p--)
c = c * a ; /* multiplies a by itself p times */
return c ;
}
Filename: my_program.c
int main() {
int a=2 ;
int b=3 ;
int c=0 ;
c = pow (a, b) ; /* raises a to the b power: ab */
}

Property of Penn Engineering 39

Begin with main()’s Prologue
Prologue is where a function begins to construct its frame
• main() is a subroutine, it must be called using JSR; let’s assume R7=x0005 for this example
• before main() was called, assume R6 = x7FFF (start of the stack), R5=x0000 (no frames)

STACK:
x7FFC
x7FFD
x7FFE
x7FFF R6
Property of Penn Engineering 40
Begin with main()’s Prologue
Prologue is where a function begins to construct its frame
• main() is a subroutine, it must be called using JSR; let’s assume R7=x0005 for this example
• before main() was called, assume R6 = x7FFF (start of the stack), R5=x0000 (no frames)
my_program.asm - (part 1)

main ; int main() {

;; prologue
STR R7, R6, #-2 ; save caller’s return address
STR R5, R6, #-3 ; save caller’s frame pointer
ADD R6, R6, #-3 ; updates stack pointer
ADD R5, R6, #0 ; creates/updates frame pointer

STACK: R5 main()’s stack frame:

x7FFC FP (x0000) R6 caller’s frame pointer
x7FFD RA (x0005) caller’s return address
x7FFE main’s return value
x7FFF R6 arguments to main from caller
Property of Penn Engineering 41
Continue with main()’s Prologue – local variables
my_program.asm - (part 2)

main (continued...) ; int a=2, b=3, c=0

ADD R6, R6, #-3 ; allocate space for local vars
CONST R7, #2
STR R7, R5, #-1 ; save a=2 on stack
CONST R7, #3
STR R7, R5, #-2 ; save b=3 on stack
CONST R7, #0
STR R7, R5, #-3 ; save c=0 on stack
x7FF9 c (0) R6
x7FFA b (3) local variables for main
x7FFB a (2) R5
x7FFC FP (x0000) R5
R6 caller’s frame pointer
x7FFD RA (x0005) caller’s return address
x7FFE main’s return value
x7FFF arguments to main from caller
Recall R5 points to “bottom” of frame and R6 to top of stack Property of Penn Engineering 42
SECTION 3: The Stack Call / Return Sequence

FUNCTION CALLING A FUNCTION

--EX: MAIN() CALLS POW()

Property of Penn Engineering 43

Continuing Our Compilation: main()’s body
int pow(int a, int p) {
int c ;
for (c = 1; p > 0; p--)
c = c * a ; /* multiplies a by itself p times */
return c ;
}
Filename: my_program.c
int main() {
int a=2 ;
int b=3 ;
int c=0 ;
c = pow (a, b) ;
}

Property of Penn Engineering 44

main()’s body – main() calls pow()
my_program.asm - (part 3)
main (continued...) ; ...pow (a, b) ;
LDR R7, R5, #-2 ; get right-most param. (p)=(b)
ADD R6, R6, #-1 ; allocate space for param (p)
STR R7, R6, #0 ; copy param (b) on top of stack
LDR R7, R5, #-1 ; get 1st parameter (a)=(a)
ADD R6, R6, #-1 ; allocate space for param (a)
STR R7, R6, #0 ; copy param (a) on top of stack
x0061 JSR pow ; sets R7=PC+1 (x0062), PC=pow
x7FF7 a (2) R6
R6 Arguments to pow
x7FF8 p (3)
x7FF9 c (0) R6 Side Note:
x7FFA b (3) local variables for main arguments are
pushed onto
x7FFB a (2)
stack from
x7FFC FP (x0000) R5 caller’s frame pointer right to left
x7FFD RA (x0005) caller’s return address
x7FFE main’s return value
x7FFF arguments to main from caller
Assumed: PennSim loaded JSR pow into Memory @row: x0061 Property of Penn Engineering 45
SECTION 3: The Stack Call / Return Sequence
PUSHING A 2ND STACK FRAME ON THE STACK

Property of Penn Engineering 47

Continuing Our Compilation: looking at pow()
int pow(int a, int p) {
int c ;
for (c = 1; p > 0; p--)
c = c * a ; /* multiplies a by itself p times */
return c ;
}
Filename: my_program.c
int main() {
int a=2 ;
int b=3 ;
int c=0 ;
c = pow (a, b) ;
}

Property of Penn Engineering 48

Creation of pow()’s Stack Frame (Prologue)
C-Code for function: pow()
int pow (int a, int p) {
int c ;
for (c = 1; p > 0; p--)
c = c * a ;
return c ;
}
ASSEMBLY: notice that the first portion is nearly identical to subroutine main()
pow
;; prologue
STR R7, R6, #-2 ; save caller’s return address Identical
STR R5, R6, #-3 ; save caller’s frame pointer for all
ADD R6, R6, #-3 ; updates stack pointer functions
ADD R5, R6, #0 ; creates/updates frame pointer

ADD R6, R6, #-1 ; allocate space for local vars

CONST R7, #1 ; only 1 local var: c Setup
STR R7, R5, #-1 ; c=1 – initialized in the for loop local vars.
Property of Penn Engineering 49
When main() Calls pow(), This Is What Stack Looks Like:
STACK: pow()’s frame pushed on top of main()'s

x7FF3 c (1) local variables for pow

x7FF4 FP (x7FFC) caller’s (main’s) frame pointer
x7FF5 RA (x0062) caller’s (main’s) return address pow’s
x7FF6 RV (X) pow’s future return value frame
x7FF7 a (2) R6
Arguments to pow
x7FF8 p (3)
x7FF9 c (0)
x7FFA b (3) local variables for main
x7FFB a (2)
main’s
x7FFC FP (x0000) R5 caller’s frame pointer frame
x7FFD RA (x0005) caller’s return address
x7FFE main’s return value
x7FFF arguments to main from caller
Recall, in main(): JSR pow is @row: x0061, thus RA=x0062
Property of Penn Engineering 50
SECTION 3: The Stack Call / Return Sequence

A FUNCTION’S BODY
--EX: A FOR LOOP USING THE STACK

Property of Penn Engineering 51

pow()’s Function Body
pow()’s for loop :
int pow(int a, int p) {
int c ; Stack:
for (c = 1; p > 0; p--) x7FF3 c (2)
(1) R6
c = c * a ;
return c ; x7FF4 FP (x7FFC) R5
} x7FF5 RA (x0062)
pow()’s ASSEMBLY of the for loop x7FF6 RV (X)
JMP L5_my_program ; jump to compare x7FF7 a (2)
L2_my_program ; body of loop { x7FF8 p (3)
(2)
LDR R7, R5, #-1 ; loads c into R7 x7FF9 c (0)
LDR R3, R5, #3 ; loads a into R3
MUL R7, R7, R3 ; R7 = c * a x7FFA b (3)
STR R7, R5, #-1 ; update c = R7 } x7FFB a (2)
; DECREMENT LOOP COUNTER: p--
LDR R7, R5, #4 ; load p into R7 x7FFC FP (x0000)
ADD R7, R7, #-1 ; decrement p x7FFD RA (x0005)
STR R7, R5, #4 ; update p
L5_my_program ;for loop (compare) x7FFE
LDR R7, R5, #4 ; loads p into R7 x7FFF
CONST R3, #0 ; loads 0 into R3
CMP R7, R3 ; is p > 0 ?
BRp L2_my_program ; if yes, goto body
Property of Penn Engineering 52
pow()’s Function Body Notice, pow()’s copy
of c = 8, but it didn’t
pow()’s for loop : impact main()’s copy
int pow(int a, int p) {
int c ; Stack:
for (c = 1; p > 0; p--) x7FF3 c (1)
(8) R6
c = c * a ; // c=8 when finished
return c ; x7FF4 FP (x7FFC) R5
} x7FF5 RA (x0062)
pow()’s ASSEMBLY of the for loop x7FF6 RV (X)
JMP L5_my_program ; jump to compare x7FF7 a (2)
L2_my_program ; body of loop { x7FF8 p (3)
(0)
LDR R7, R5, #-1 ; loads c into R7 x7FF9 c (0)
LDR R3, R5, #3 ; loads a into R3
MUL R7, R7, R3 ; R7 = c * a x7FFA b (3)
STR R7, R5, #-1 ; update c = R7 } x7FFB a (2)
; DECREMENT LOOP COUNTER: p-- Side Note:
LDR R7, R5, #4 ; load p into R7 x7FFC FP (x0000) Notice that R5
ADD R7, R7, #-1 ; decrement p x7FFD RA (x0005) is used to find
STR R7, R5, #4 ; update p local variables
L5_my_program ;for loop (compare) x7FFE
LDR R7, R5, #4 ; loads p into R7 and arguments
x7FFF
CONST R3, #0 ; loads 0 into R3
CMP R7, R3 ; is p > 0 ? Loop repeats 3 times
BRp L2_my_program ; if yes, goto body p = 0 at the end
c = 8 Property of Penn Engineering 53
SECTION 3: The Stack Call / Return Sequence

A FUNCTION’S EPILOGUE
--RETURNING DATA FROM A FUNCTION

Property of Penn Engineering 54

pow()’s Epilogue
pow()’s - C code for return (c)
int pow(int a, int p) {
int c ; Stack:
for (c = 1; p > 0; p--) x7FF3 c (8) R6
c = c * a ;
return c ; x7FF4 FP (x7FFC) R5
} x7FF5 RA (x0062)
pow()’s - ASSEMBLY of epilogue x7FF6 RV (0)
(8)
; function body is complete, time to return x7FF7 a (2) R6
x7FF8 p (0)
LDR R7, R5, #-1 ; load C into R7 x7FF9 c (0)
;; epilogue x7FFA b (3)
ADD R6, R5, #0 ; pop local variables x7FFB a (2)
ADD R6, R6, #3 ; decrease stack
STR R7, R6, #-1 ; update return value x7FFC FP (x0000) R5
LDR R5, R6, #-3 ; restore base ptr x7FFD RA (x0005)
LDR R7, R6, #-2 ; restore R7 for RET
RET ; now PC = R7 x7FFE
x7FFF
After epilogue
Notice: Stack, R5, R6, and R7 look like they did before main() called it! PC = R7, = x0062
Property of Penn Engineering 55
After pow() Return, Back Inside Main()
remainder of main()’s C code
Stack:
int main() {
int a=2 ; x7FF3 c (8)
int b=3 ; x7FF4 FP (x7FFC)
int c=0 ; x7FF5 RA (x0062)
c = pow (a, b) ;
} x7FF6 RV (8)
remainder of main()’s function body
x7FF7 a (2) R6
x7FF8 p (0)
; “pow()” has returned...back in main()
x7FF9 c (8)
(0) R6
... x7FFA b (3)
x0061 JSR pow() ; pow has returned!
x7FFB a (2)
x0062 LDR R7, R6, #-1 ; get return value x7FFC FP (x0000) R5
x0063 ADD R6, R6, #2 ; pop arguments x7FFD RA (x0005)
x0064 STR R7, R5, #-3 ; update “c”
x7FFE
Recall that when pow()’s RET is executed: x7FFF
PC = x0062

Property of Penn Engineering 56

Main()’s Epilogue
remainder of main()’s C code
Stack:
int main() {
int a=2 ; x7FF3 c (8)
int b=3 ; x7FF4 FP (x7FFC)
int c=0 ; x7FF5 RA (x0062)
c = pow (a, b) ;
} x7FF6 RV (8)
x7FF7 a (2)
remainder of main()’s function body & epilogue
x7FF8 p (0)
; function body is complete, time to return
CONST R7, #0 ; clear R7 x7FF9 c (8) R6
x7FFA b (3)
;; epilogue
ADD R6, R5, #0 ; pop local variables x7FFB a (2) R6
ADD R6, R6, #3 ; decrease stack x7FFC FP (x0000) R5
STR R7, R6, #-1 ; update return value RA (x0005)
LDR R5, R6, #-3 ; restore base ptr x7FFD
LDR R7, R6, #-2 ; restore R7 for RET x7FFE RV(0)
RV(X)
RET ; now PC = R7 x7FFF R6
R5=x0000
Notice the stack is never actually cleaned up.
R7=x0005
Any address lower than R6 is just invalid.
Property of Penn Engineering 57
SECTION 3: The Stack Call / Return Sequence

SUMMARY OF SEQUENCE

Property of Penn Engineering 58

Prologue, Body, and Epilogue
• Function prologue
• Boilerplate code generated for each function
• Runs each time a function is called
• “Pushes” activation record onto the stack
• More sophisticated compilers can generate tighter prologues

• Code that follows is a translation of function body

• LCC does this statement-by-statement
• Results in many inefficiencies
• More sophisticated compilers view entire function (at least)

• When explicit body finishes, it needs function epilogue

• Another boilerplate code generated for each function
• Runs each time a function exits
• “Pops” activation record from stack and puts return value on top

Property of Penn Engineering 59

Things To Remember
1) Arguments are pushed onto stack from right to left
• So that the first argument from the left is closest to the callee
• This is called “C convention” (left-to-right is called PASCAL)
• Needed for functions with variable argument counts (e.g. printf)
• Can also lead to order of evaluation being right-to-left
• Example: pow (a, ++a) may become pow (3, 3)

2) C is pass-by-value (not pass-by-reference)

• Functions receive “copies” of local variables
• Recall that arguments to functions were copies of local vars
• Protects local variables from being modified accidentally

3) We see why variables must be declared at the start of function

• Size of static/automatic variables are known at compile time:
• ADD R6, R6, #-1 ; allocate space for local vars
• Also, compiler may compile line-by-line, hence right up front!

Property of Penn Engineering 60

Is There a Better Way? Efficiency
• A lot of extra instructions involved in function call
• Many compilers try to inline functions

• Which means…expand function body at call site

• Removes most of call overhead

• Introduces other overheads

• Multiple static copies of same function

• Partial Register Based Calling Conventions

• Using the stack to hold everything (like the LCC compiler does) is not the most efficient technique!

• This is the “calling convention” of the LCC

• “Partial Register” based calling conventions are more efficient

• Using the register file to hold lots of data before going to the stack – common practice now

Property of Penn Engineering 61

Implications of Stack Mechanism
• Stack mechanism makes it easy to have functions that call other functions.
We can even have functions that call themselves “recursive functions,”
which must be supported by every serious programming language.

• Stack space is finite, so if we allocate too many local variables or have call
chains that are too deep, we can blow the stack.
• In LC4, this can cause us to overwrite the heap with unpredictable results.
• Be careful about declaring large data structures as local variables. Instead, consider
using globals or the heap.
• You program differently once you realize the overhead of stack!

• The details of stack handling, its calling conventions, may differ from one
compiler to another or from one language to another, but the basic idea
remains the same.

Property of Penn Engineering 62