Stack Frame for Non-leaf functions

Proof of Concept for Non-Leaf Function

Here the assembler program with the proof of concept

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

    # conventions
    .equ    FP,         1
    .equ    SP,         2
    .equ    RET_ADDR,   3

    # for the demo
    .equ    FUNC_ADDR,  4


    /*
     * function: _start
     */
_start:
    ldzwq   0,      %SP

    // call: main()
    ldzwq   main,           %FUNC_ADDR
    subq    8,              %SP,        %SP # first half: push %RET_ADDR
    call    %FUNC_ADDR,     %RET_ADDR
    addq    8,              %SP,        %SP # second half: pop %RET_ADDR

    putc    'r'
    putc    '\n'


    halt    %0

    /*
     * function: main()
     */
main:
    movq    %RET_ADDR,      (%SP)           # second half: push %RET_ADDR

    // begin of function body

    putc    'f'
    // call: foo()
    ldzwq   foo,            %FUNC_ADDR
    subq    8,              %SP,        %SP # first half: push %RET_ADDR
    call    %FUNC_ADDR,     %RET_ADDR
    addq    8,              %SP,        %SP # second half: pop %RET_ADDR

    putc    'a'

    // end of function body

    movq    (%SP),          %RET_ADDR       # first half: pop %RET_ADDR
    ret     %RET_ADDR

    /*
     * function: foo()
     */
foo:
    movq    %RET_ADDR,      (%SP)           # second half: push %RET_ADDR

    // begin of function body

    putc    'o'
    // call: bar()
    ldzwq   bar,            %FUNC_ADDR
    subq    8,              %SP,        %SP # first half: push %RET_ADDR
    call    %FUNC_ADDR,     %RET_ADDR
    addq    8,              %SP,        %SP # second half: pop %RET_ADDR

    putc    'b'

    // end of function body

    movq    (%SP),          %RET_ADDR       # first half: pop %RET_ADDR
    ret     %RET_ADDR

    /*
     * function: bar()
     */
bar:
    movq    %RET_ADDR,      (%SP)           # second half: push %RET_ADDR

    // begin of function body

    putc    'o'

    // end of function body

    movq    (%SP),          %RET_ADDR       # first half: pop %RET_ADDR
    ret     %RET_ADDR

and here a flow chart that combines the call graph with the control flow:

Idea for Using the Stack Implementation

For storing and retrieving return address we use a stack data type. For its implementation the directive

1

    .equ    SP,     2

specifies that some register %SP is used as stack pointer. At start up the stack pointer gets zero initialized so that it points to the end of the virtual memory:

Typical Stack Operations

The typical operation are push for adding an element, and pop to remove the most recently added element.

Let's assume that this is the current state of the stack

For a push of a register %DATA two operations are required:

• First the stack pointer gets decremented (first half of the push)

• Then (second half of the push operation) the data stored at the stack pointer

The pop operation restores a register with the value stored at the top of the frame and also takes this element of the stack.

• The first half of the pop operation is a fetch from the top of the stack

• Taking of an element from the stack means to increment the stack pointer. This is done in the second half of the pop operation:

Implementation Specific Operations

On the next page you will see that we will exploit our stack implementation to also access elements that are not at the top of the stack and without removing them from the stack.