============================================
Parameters, Return Value and Local Variables				[TOC]
============================================

---- VIDEO ------------------------------
https://www.youtube.com/embed/Vtf1giXQ0G8
-----------------------------------------

Quiz 14: Computing the greatest common divisor (Again)
======================================================
Rewrite the program `gcd.s` from quiz 13 such that all functions conform to
the new conventions for functions. Functions that do not return a value simply
do not use the space reserved on the stack for the return value.

All labels are in general 64-bit literals. If you require a 64-bit literal as an
absolute address fetch it from the literal pool.

Your program should have an exit code of 0.

Submit your program with

---- CODE (type=txt) ----------
submit hpc quiz14 isa.txt gcd.s
-------------------------------


Provided Material
=================
Here an __ULM Instruction Set__ and its `isa.txt` source code that contains all
the instructions shown in the video (and in addition a _divq_ variant where all
operands are registers):

:import: session14/stack/0_ulm_variants/stack/isa.txt [fold]

---- SHELL (path=session14/stack/, hide) --------------------------------------
make
make refman
mkdir -p /home/www/htdocs/numerik/hpc/ss22/hpc0/session14/stack/
cp 1_ulm_build/stack/refman.pdf /home/www/htdocs/numerik/hpc/ss22/hpc0/session14/stack/
--------------------------------------------------------------------------------

The program _func2.s_ shown in the video:

:import: session14/stack/func2.s [fold]

:links: ULM Instruction Set -> https://www.mathematik.uni-ulm.de/numerik/hpc/ss22/hpc0/session14/stack/refman.pdf


Using the Stack for Parameters and the Return Value
===================================================
Functions receive copies of the arguments on the stack and return a value on
the stack.  Consider a function that receives just two arguments. Then the
callee expects in its prologue the following stack:

--- TIKZ ----------------------------------------------------------------------
\begin{tikzpicture}
\input{memory.tex}

\renewcommand\MemCellWidth { 0.4}

\DrawMemArrayOpen{-16}{39}

\DrawQuadVariable[red!20]{32}{variable arg1}
\DrawQuadVariable[red!20]{24}{variable arg0}
\DrawQuadVariable[green!40]{16}{return value}
\DrawQuadVariable[green!40]{8}{reserved \%FP}
\DrawQuadVariable[green!40]{0}{reserved \%RET}

\DrawPointer{0}{\%SP}

\end{tikzpicture}
--------------------------------------------------------------------------------

Directives for Reserved Registers
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The calling convention relies on a stack pointer (_SP_), a frame pointer (_FP_)
and a register for storing the return address (_RET_ADDR_):

---- CODE (type=s) -------------------------------------------------------------
    .equ    FP,         1
    .equ    SP,         2
    .equ    RET_ADDR,   3
--------------------------------------------------------------------------------

Directives for Offsets
~~~~~~~~~~~~~~~~~~~~~~
The following directives define symbols for the stack offsets. Depending on the
contex these offsets are either releative to _SP_ or _FP_:

---- CODE (type=s) -------------------------------------------------------------
    .equ    ret,        0
    .equ    fp,         ret + 8
    .equ    rval,       fp + 8
    .equ    fparam0,    rval + 8
    .equ    fparam1,    fparam0 + 8

    .equ    local0,     -8
    .equ    local1,     local0 - 8
--------------------------------------------------------------------------------

Calling a function
~~~~~~~~~~~~~~~~~~
Lets assume that every parameter has a size of 8 bytes. Then the caller first
has to decrement the stack pointer by $8 \cdot (3 + \text{"number of
parameters"})$. Before the call the parameters are copied to the stack. Here an
example for a function call _foo(1, 2)_:

---- CODE (type=s) -------------------------------------------------------------
    subq    5 * 8,	%SP,	    %SP
    ldzwq   1,		%4
    movq    %4,		24(%SP)		    // store arg0
    ldzwq   2,		%4
    movq    %4,		32(%SP)		    // store arg1
    ldzwq   foo,	%4
    jmp	    %4,		%RET
    addq    5 * 8,	%SP,	    %SP
--------------------------------------------------------------------------------

Using the directives this can be rewritten more readable as

---- CODE (type=s) -------------------------------------------------------------
    subq    5 * 8,	%SP,	    %SP
    ldzwq   1,		%4
    movq    %4,		fparam0(%SP)	    // store arg0
    ldzwq   2,		%4
    movq    %4,		fparam1(%SP)	    // store arg1
    ldzwq   foo,	%4
    jmp	    %4,		%RET
    addq    5 * 8,	%SP,	    %SP
--------------------------------------------------------------------------------


Implementation of a function
~~~~~~~~~~~~~~~~~~~~~~~~~~~
The prologue and epilogue are the same a for subprograms or procedure. Assume
the function uses two local variables `local0` and `local1` then after the
prologue

---- CODE (type=s) -------------------------------------------------------------
    // function prologue (with 2 local variables, each 8 bytes)
    movq    %RET_ADDR,	ret(%SP)
    movq    %FP,	fp(%SP)
    addq    0,		%SP,	    %FP
    subq    8 * 2,	%SP,	    %SP
--------------------------------------------------------------------------------

the stack can be described by

--- TIKZ ----------------------------------------------------------------------
\begin{tikzpicture}
\input{memory.tex}

\renewcommand\MemCellWidth { 0.4}

\DrawMemArrayOpen{-16}{39}

\DrawMemVariable[red!40]{-8}{0}{Used}
\DrawQuadVariable[red!20]{32}{variable arg1}
\DrawQuadVariable[red!20]{24}{variable arg0}
\DrawQuadVariable[green!40]{16}{for return value}
\DrawQuadVariable[green!40]{8}{\%FP}
\DrawQuadVariable[green!40]{0}{\%RET}
\DrawQuadVariable[gray!20]{-8}{variable local0}
\DrawQuadVariable[gray!20]{-16}{variable local1}

\DrawMemLabel{32}{\%FP + 32}
\DrawMemLabel{24}{\%FP + 24}
\DrawMemLabel{16}{\%FP + 16}
\DrawMemLabel{8}{\%FP + 8}
\DrawMemLabel{0}{\%FP}
\DrawMemLabel{-8}{\%FP - 8}
\DrawMemLabel{-16}{\%FP - 16}


\DrawPointer{0}{\%FP}
\DrawPointer{-16}{\%SP}

\end{tikzpicture}
--------------------------------------------------------------------------------


Using the directives for offset all relevant memory locations can be accessed
relative to the frame pointer in the same uniform way

---- TIKZ ----------------------------------------------------------------------
\begin{tikzpicture}
\input{memory.tex}

\renewcommand\MemCellWidth { 0.4}

\DrawMemArrayOpen{-16}{39}

\DrawMemVariable[red!40]{-8}{0}{Used}
\DrawQuadVariable[green!40]{32}{arg1(\%FP)}
\DrawQuadVariable[green!40]{24}{arg0(\%FP)}
\DrawQuadVariable[green!40]{16}{rval(\%FP)}
\DrawQuadVariable[green!40]{8}{fp(\%FP)}
\DrawQuadVariable[green!40]{0}{ret(\%FP)}
\DrawQuadVariable[gray!20]{-8}{local0(\%FP)}
\DrawQuadVariable[gray!20]{-16}{local1(\%FP)}

\DrawPointer{0}{\%FP}
\DrawPointer{-16}{\%SP}

\end{tikzpicture}
--------------------------------------------------------------------------------

Skeleton of a Function Implementation
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In the following skeleton replace `FUNC_OR_PROC_LABEL` with the function or
procedure name, and replace `NUM_LOCALS` with the number of local variables:

---- CODE (type=s) -------------------------------------------------------------
FUNC_OR_PROC_LABEL:
    // function prologue
    movq	%RET_ADDR,	ret(%SP)
    movq	%FP,		fp(%SP)
    movq	%SP,		%FP

    // reserve space for local variables.
    subq	NUM_LOCALS*8,	%SP,		%SP

    // begin of the function body

    /*

	Implementation of the function or procedure

    */

    // end of the function body

    // function epilogue
    movq	%FP,		%SP
    movq	fp(%SP),	%FP
    movq	ret(%SP),	%RET_ADDR
    jmp		%RET_ADDR,	%0
--------------------------------------------------------------------------------