From b35d88cd661978dcc8d118edbd184eecdbd3e714 Mon Sep 17 00:00:00 2001
From: Camil Staps
Date: Mon, 2 Jan 2017 21:52:25 +0100
Subject: Expand on note about tail recursion

---
 thesis/storing-pc.tex | 43 +++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 41 insertions(+), 2 deletions(-)

diff --git a/thesis/storing-pc.tex b/thesis/storing-pc.tex
index 4bae7fb..d3fc474 100644
--- a/thesis/storing-pc.tex
+++ b/thesis/storing-pc.tex
@@ -173,14 +173,53 @@ A general comparison of running time under ARM and Thumb is made in \cref{sec:re
 
 \subsection{Other solutions}
 \label{sec:storing-pc:other-solutions}
-Another solution than the one we present makes use of the link register.
+Another solution than the one we have considered here makes use of the link register.
 Some branch instructions, like \ual{bl}, store the address of the next instruction in the link register.
 We could therefore imagine a setup where the callee gets the return address from that register rather than from the stack.
 This is the approach taken by GCC.
 The code of a typical C subroutine starts with \ual{push {...,lr}} and ends with \ual{pop {...,pc}}.
 
 When generating code for a functional language, it is not straightforward to do this, due to tail recursion.
-It is an easier solution to have the caller responsible for storing the return address,
+An example of this can be found in the following basic function:
+
+\begin{minted}{clean}
+	length :: !Int ![a] -> Int
+	length n []     = n
+	length n [_:xs] = length (n+1) xs
+\end{minted}
+
+The current Thumb backend generates the following code:
+
+\begin{minted}{ual}
+slength_P2:
+	ldr   r0,[r6]         @ Load top of A-stack (the list)
+	ldr   r14,=__Nil+2    @ Check if it is Nil
+	cmp   r0,r14
+	bne   case_P2
+case_P1:                    @ If the list is Nil
+	ldr   pc,[sp],#4      @ Simply return
+	.ltorg
+case_P2:                    @ If the list is not Nil
+	ldr   r6,[r6,#8]      @ Load the Cons part of the list
+	ldr   r0,[r6]         @ Check if it has been evaluated already
+	tst   r0,#2
+	bne   e_0
+	str   r4,[sp,#-4]!    @ If the Cons part has not been evaluated
+	.align
+	add.w r14,pc,#7       @ Evaluate the cons part
+	str.w r14,[sp,#-4]!
+	blx   r0
+	ldr   r4,[sp],#4
+e_0:                        @ If / after the Cons part has been evaluated
+	add   r4,r4,#1        @ Increase counter
+	b     slength_P2      @ Tail recursively jump back to start of function
+	.ltorg
+\end{minted}
+
+In this setup, it is not easily possible to let the callee store the return address,
+	since we enter the function as many times as there are elements in the list,
+	while we only return from it once, in \texttt{case\_P1}.
+A more straightforward solution to have the caller responsible for storing the return address,
 	which is why this approach is taken in Clean's ARM code generator~\parencite{armcg}
 	and why we continue along these lines for the Thumb backend.
 
-- 
cgit v1.2.3