==================================
Stack Frame for Non-leaf functions				[TOC]
==================================


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


Proof of Concept for Non-Leaf Function
======================================

Here the assembler program with the proof of concept

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

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


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

\SetMargin{5}{10}{0}{3}
\renewcommand\BoxWidth {3}


\PutStatement{0}{initialize stack}
\PutLabel[above=-0.1]{0}{\_start}
\PutCallStatement[red!50]{1}{ call main }
\PutStatement{2}{putc 'r'}
\PutStatement{3}{putc '\textbackslash n'}
\PutStatement{4}{halt}
\AddPath{0}{1}
\AddPath{2}{3}
\AddPath{3}{4}
\PutAnnotation{0}{\text{Entry point}}


% next flow chart column
\renewcommand\FlowCol{1}

\PutStatement{0}{putc 'f'}
\PutLabel[above=-0.1]{0}{main}
\PutCallStatement[orange!50]{1}{ call foo }
\PutStatement{2}{putc 'a'}
\PutStatement{3}{return}

\AddPath{0}{1}
\AddPath{2}{3}


% next flow chart column
\renewcommand\FlowCol{2}

\PutStatement{0}{putc 'o'}
\PutLabel[above=-0.1]{0}{foo}
\PutCallStatement[blue!50]{1}{ call bar }
\PutStatement{2}{putc 'b'}
\PutStatement{3}{return}
\AddPath{0}{1}
\AddPath{2}{3}


% next flow chart column
\renewcommand\FlowCol{3}

\PutStatement{0}{putc 'o'}
\PutLabel[above=-0.1]{0}{bar}
\PutStatement{1}{return}
\AddPath{0}{1}



\DrawCallPointer[red!50]{0}{1}{1}{0}
\DrawReturnPointer[red!50]{0}{2}{1}{3}

\renewcommand{\CallPointerPadToY}{0}
\DrawCallPointer[orange!50]{1}{1}{2}{0}
\DrawReturnPointer[orange!50]{1}{2}{2}{3}

\DrawCallPointer[blue!50]{2}{1}{3}{0}
\DrawReturnPointer[blue!50]{2}{2}{3}{1}

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


Idea for Using the Stack Implementation
=======================================
For storing and retrieving return address we use a stack data type. For its
implementation the directive

--- CODE (type=s) --------------------------------------------------------------
    .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:

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

\renewcommand\MemCellWidth { 0.6}

\DrawMemArrayOpenLeft{-40}{-1}

\DrawPointer{0}{\%SP}

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

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

---- TIKZ --------------------------------------------------------------------
\begin{tikzpicture}
\input{memory.tex}
  
\renewcommand\MemCellWidth { 0.6}
  
\DrawMemArrayOpen{-40}{-1}
  
\DrawQuadVariable[red!40]{-8}{Used}
\DrawMemVariable[red!50]{-16}{-8}{}
\DrawMemVariable[gray!10]{-40}{-16}{Unused }
  
\DrawPointer{-16}{\%SP}
  
\end{tikzpicture}
------------------------------------------------------------------------------

For a push of a register _%DATA_ two operations are required:

- First the stack pointer gets decremented (_first half of the push_)

  ---- TIKZ --------------------------------------------------------------------
  \begin{tikzpicture}
  \input{memory.tex}
  
  \renewcommand\MemCellWidth { 0.6}
  
  \DrawMemArrayOpen{-40}{-1}
  
  \DrawQuadVariable[red!40]{-8}{Used}
  \DrawMemVariable[red!50]{-16}{-8}{}
  \DrawMemVariable[gray!10]{-40}{-16}{Unused }
  
  \DrawPointer{-16}{\%SP}
  
  \end{tikzpicture}
  ------------------------------------------------------------------------------

- Then (_second half of the push operation_) the data stored at the stack
  pointer

  ---- TIKZ --------------------------------------------------------------------
  \begin{tikzpicture}
  \input{memory.tex}
  
  \renewcommand\MemCellWidth { 0.6}
  
  \DrawMemArrayOpen{-40}{-1}
  
  \DrawQuadVariable[red!40]{-8}{Used}
  \DrawMemVariable[red!50]{-16}{-8}{stored \%DATA}
  \DrawMemVariable[gray!10]{-40}{-16}{Unused }
  
  \DrawPointer{-16}{\%SP}
  
  \end{tikzpicture}
  ------------------------------------------------------------------------------

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_:

  ---- TIKZ --------------------------------------------------------------------
  \begin{tikzpicture}
  \input{memory.tex}
  
  \renewcommand\MemCellWidth { 0.6}
  
  \DrawMemArrayOpen{-40}{-1}
  
  \DrawQuadVariable[red!40]{-8}{Used}
  \DrawMemVariable[red!50]{-16}{-8}{stored \%DATA}
  \DrawMemVariable[gray!10]{-40}{-16}{Unused }
  
  \DrawPointer{-8}{\%SP}
  
  \end{tikzpicture}
  ------------------------------------------------------------------------------

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.