%==============================================================================
%TODO
%
%==============================================================================


\documentclass[a4paper]{article}

\newcommand{\Prog}[1]{\texttt{#1}}

\setlength\textwidth{6in}
\setlength\oddsidemargin{0in}
\setlength\evensidemargin{0in}

\setlength\textheight{9in}

\setlength\topmargin{0in}
\setlength\headheight{0in}
\setlength\headsep{0in}
\setlength\footskip{.3in}

\usepackage{latexsym}
\usepackage[spanish]{babel}

\title{Ejemplos de Transformaci\'on de un Programa Dgcl a ARC}
\author{B. Gonzalez Kriegel - N. Wolovick}


\begin{document}
\maketitle

\section{Algoritmo de la Divisi\'on Entera}

Queremos transformar el c\'odigo escrito en Dgcl - el lenguaje de los comandos guardados de
Dijkstra - obtenido en la p\'agina 134 del apunte ``C\'alculo de Programas'', que implementa el
algoritmo de la divisi\'on entera, en un c\'odigo ensamlador para la ISA de ARC.
	\Prog{
	\begin{small}
	\begin{center}
	\begin{tabbing}
		[ \= var x,y,q,r: Int \\
		\> $\{R: x\geq 0 \wedge y\geq 0\}$ \\
		\> q,r := 0,x \\
		\> $\{Q: x=q\times y+r \wedge 0\leq r\}$ \\
		\> {\bf do}\= \\
		\> \>	$\Box$ \= smtg. \kill
		\> \>	\> r$\geq$y $\rightarrow$ q,r := q+1,r-y \\
		\> {\bf od} \\
		\> $\{Q: x=q\times y+r \wedge 0\leq r \wedge r<y\}$ \\
		]
	\end{tabbing}
	\end{center}
	\end{small}
	}

	La primera l\'{\i}nea de c\'odigo declara 4 variables de tipo entero.
	\Prog{
	\begin{small}
	\begin{center}
	\begin{tabbing}
		[ \= var x,y,q,r: Int
	\end{tabbing}
	\end{center}
	\end{small}
	}
	Utilizamos 4 registros para almacenar el valor de cada variable.
	Tambi\'en indicamos al ensamblador el inicio de nuestro c\'odigo, asi como la direcci\'on de memoria
que elejimos para que comience a ensamblar.
	\Prog{
	\begin{small}
	\begin{center}
	\begin{tabbing}
		label: \= addcc \= \%r1,\%r2,\%r3 \kill
		\> ! x <-> \%r1 \\
		\> ! y <-> \%r2 \\
		\> ! q <-> \%r3 \\
		\> ! r <-> \%r4 \\
		\> .begin \\
		\> .org \> 2048
	\end{tabbing}
	\end{center}
	\end{small}
	}

	La siguiente sentencia es una multiasignaci\'on que hace verdadero el invariante en el inicio.
	\Prog{
	\begin{small}
	\begin{center}
	\begin{tabbing}
		[ \= var x,y,q,r: Int \kill
		\> q,r := 0,x \\
		\> $\{Q: x=q\times y+r \wedge 0\leq r\}$
	\end{tabbing}
	\end{center}
	\end{small}
	}
	La multiasignaci\'on puede ser desacoplada sin problemas, pues los \emph{rhs} no dependen de los \emph{lhs}.
	Para hacer 0 a $q$ y copiar $x$ en $r$, podemos usar \Prog{sethi} y \Prog{add} de la siguiente forma:
como \Prog{sethi} copia su operando inmediato de 22 bits en la parte superior del registro destino y
pone a 0 los 10 bits bajos, con asignar 0 a la parte alta alcanza para asignar 0 a
\Prog{\%r3} ($q$)\footnote{ A esto mismo lo podemos lograr de muchas formas distintas, utilizando
\Prog{\%r0} y las instrucciones aritm\'etico-l\'ogicas.}.
	Para la segunda asignaci\'on efectuamos una suma entre \Prog{\%r1} ($x$) y \Prog{\%r0} y ponemos el
resultado en \Prog{\%r4} ($r$).
	\Prog{
	\begin{small}
	\begin{center}
	\begin{tabbing}
		label: \= addcc \= \%r1,\%r2,\%r3 \ \ \ \ \= ! comentario \kill
		\> sethi \> 0, \%r3 \> ! q := 0 \\
		\> add \> \%r1, \%r0, \%r4 \> ! r := x
	\end{tabbing}
	\end{center}
	\end{small}
	}

\pagebreak
   	
	El inicio de la repetici\'on nos induce a introducir una etiqueta \Prog{loop},
para poder saltar aqu\'{\i} cuando el lazo deba repetirse.
	\Prog{
	\begin{small}
	\begin{center}
	\begin{tabbing}
		[ \= var x,y,q,r: Int \kill
		\> {\bf do}\= \\
		\> \>	$\Box$ \= smtg. \kill
		\> \>	\> r$\geq$y $\rightarrow \cdots$
	\end{tabbing}
	\end{center}
	\end{small}
	}
La comparaci\'on de la guarda la obtenemos con un \Prog{subcc} que modifica el registro de estado
y descarta el resultado.
En el caso que la guarda no sea verdadera saltamos a \Prog{endloop}, etiqueta de la primera
instrucci\'on fuera del ciclo.
	\Prog{
	\begin{small}
	\begin{center}
	\begin{tabbing}
		label: \= addcc \= \%r1,\%r2,\%r3 \ \ \ \ \= ! comentario \kill
		loop: \> subcc \%r4, \%r2, \%r0 \\
		\> bneg \> endloop \> ! do r>=y
	\end{tabbing}
	\end{center}
	\end{small}
	}

	La multiasignaci\'on que le sigue a la guarda del \Prog{{\bf do}\ldots{\bf od}}
	\Prog{
	\begin{small}
	\begin{center}
	\begin{tabbing}
		[ \= var x,y,q,r: Int \kill
		\> {\bf do}\= \kill
		\> \>	$\Box$ \= smtg. \kill
		\> \>	\> $\cdots \rightarrow$ q,r := q+1,r-y
	\end{tabbing}
	\end{center}
	\end{small}
	}
se logra f\'acilmente con instrucciones de suma y resta.
	\Prog{
	\begin{small}
	\begin{center}
	\begin{tabbing}
		label: \= addcc \= \%r1,\%r2,\%r3 \ \ \ \ \= ! comentario \kill
		\> add \> \%r3, 1, \%r3 \> ! q := q+1 \\
		\> sub \> \%r4, \%r2, \%r4 \> ! r := r-y
	\end{tabbing}
	\end{center}
	\end{small}
	}

	El final de la repetici\'on la logramos con un salto incondicional al inicio del lazo, marcado por
la etiqueta \Prog{loop}
	\Prog{
	\begin{small}
	\begin{center}
	\begin{tabbing}
		label: \= addcc \= \%r1,\%r2,\%r3 \ \ \ \ \= ! comentario \kill
		\> ba \> loop \> ! od
	\end{tabbing}
	\end{center}
	\end{small}
	}
	
	Finalmente ponemos la etiqueta de salida del lazo junto con la instrucci\'on \Prog{halt} que
detiene la ejecuci\'on de la m\'aquina, e indicamos al ensamblador que terminamos el programa.
	\Prog{
	\begin{small}
	\begin{center}
	\begin{tabbing}
		endloop: \= addcc \= \%r1,\%r2,\%r3 \ \ \ \ \= ! comentario \kill
		endloop: \> halt \\
		\> .end
	\end{tabbing}
	\end{center}
	\end{small}
	}

	
	El c\'odigo ARC completo se muestra a continuaci\'on, con el agregado de un par de instrucciones
que sirven para cargar \Prog{\%r1} y \Prog{\%r2} a fin de probar el programa.
	\Prog{
	\begin{small}
	\begin{center}
	\begin{tabbing}
		endloop: \= addcc \= \%r1,\%r2,\%r3 \ \ \ \ \= ! comentario \kill
		\> ! x <-> \%r1 \\
		\> ! y <-> \%r2 \\
		\> ! q <-> \%r3 \\
		\> ! r <-> \%r4 \\
		\> .begin \\
		\> .org \> 2048 \\
		\> ld \> [x], \%r1 \> ! cargo x \\
		\> ld \> [y], \%r2 \> ! cargo y \\
		\> sethi \> 0, \%r3 \> ! q := 0 \\
		\> add \> \%r1, \%r0, \%r4 \> ! r := x \\
		loop: \> subcc \%r4, \%r2, \%r0 \\
		\> bneg \> endloop \> ! do r>= y \\
		\> add \> \%r3, 1, \%r3 \> ! q := q+1 \\
		\> sub \> \%r4, \%r2, \%r4 \> ! r := r-y \\
		\> ba \> loop \> ! od \\
		endloop: \> halt \\
		x: \> 25 \\
		y: \> 6  \\
		\> .end
	\end{tabbing}
	\end{center}
	\end{small}
	}

	
%===============================================================================================

\pagebreak
\section{Suma de los Elementos de un Arreglo}

En la p\'agina 142 del mismo apunte se deriva, a partir de la especificaci\'on $Q$, un algoritmo para obtener
en la variable $r$ la suma de los elementos de un arreglo $A$.
	
	\Prog{
	\begin{small}
	\begin{center}
	\begin{tabbing}
		[ \= con N: Int, A: array [0,N) of Int; var n,r: Int \\
		\> $\{R: N \geq 0\}$ \\
		\> n,r := 0,0 \\
		\> $\{P: r=(\sum.i : 0\leq i<n : A.i) \wedge 0\leq n\leq N\}$ \\
		\> {\bf do}\= \\
		\> \>	$\Box$ \= smtg. \kill
		\> \>	\> n$\neq$N $\rightarrow$ n,r := n+1,r+A.n \\
		\> {\bf od} \\
		\> $\{Q: r=(\sum.i : 0\leq i<n : A.i) \}$ \\
		]
	\end{tabbing}
	\end{center}
	\end{small}
	}

	Vamos a obtener paso a paso el programa ARC a partir del c\'odigo anterior.
	La primera l\'{\i}nea contiene las declaraciones.
	\Prog{
	\begin{small}
	\begin{center}
	\begin{tabbing}
		[ \= con N: Int, A: array [0,N) of Int; var n,r: Int
	\end{tabbing}
	\end{center}
	\end{small}
	}

	El primer problema se presenta en como representar el tipo de datos \Prog{array} convenientemente.
	La implementaci\'on de bajo nivel m\'as inmediata y tambi\'en la m\'as usada, es pensar un pedazo de
la memoria como un arreglo de enteros, donde en \Prog{M[A]} tenemos el elemento cero, en \Prog{M[A+4]} el
uno y asi (recordar que cada entero ocupa 4 bytes).

	La constante \Prog{N} la podemos mapear a un s\'{\i}mbolo definido con el pseudo-op \Prog{.equ}.
	Para las variables enteras $n$ y $r$ elegimos mantenerlas en registros del microprocesador.
	\Prog{
	\begin{small}
	\begin{center}
	\begin{tabbing}
		endloop: \= addcc \= \%r1,\%r2,\%r3 \ \ \ \ \= ! comentario \kill
		\> ! n <-> \%r1 \\
		\> ! r <-> \%r2 \\
		\> .begin \\
		N \> .equ \> 5 \> ! el arreglo tendra 5 elementos \\
		\> .org \> 2048
	\end{tabbing}
	\end{center}
	\end{small}
	}
	El arreglo no lo definimos a\'un, pues queremos que est\'e al final del programa.
	
	La multiasignaci\'on siguiente, puede ser desacoplada en dos de manera directa.
	\Prog{
	\begin{small}
	\begin{center}
	\begin{tabbing}
		[ \= con N: Int, A: array [0,N) of Int; var n,r: Int \kill
		\> n,r := 0,0
	\end{tabbing}
	\end{center}
	\end{small}
	}
	Existen muchas formas de poner en 0 los registros \Prog{\%r1} y \Prog{\%r2}. Elegimos una de cada tipo.
	\Prog{
	\begin{small}
	\begin{center}
	\begin{tabbing}
		endloop: \= addcc \= \%r1,\%r2,\%r3 \ \ \ \ \= ! comentario \kill
		\> and \> \%r0, \%r0, \%r1 \> ! n := 0 \\
		\> sethi \> 0, \%r2 \> ! r := 0 \\
	\end{tabbing}
	\end{center}
	\end{small}
	}
	
	El inicio del constructor de repetici\'on lo mapeamos de la misma forma que en la secci\'on anterior.
	\Prog{
	\begin{small}
	\begin{center}
	\begin{tabbing}
		[ \= con N: Int, A: array [0,N) of Int; var n,r: Int \kill
		\> {\bf do}\= \\
		\> \>	$\Box$ \= smtg. \kill
		\> \>	\> n$\neq$N $\rightarrow \cdots$
	\end{tabbing}
	\end{center}
	\end{small}
	}
	Con una resta entre $n$ y $N$ que modifique el \Prog{\%psr} y un salto que salga del lazo en caso de
igualdad nos alcanza.
	Seguimos la estructura \Prog{loop}-\Prog{endloop} de las etiquetas que marcan el inicio y fin del bucle.
	\Prog{
	\begin{small}
	\begin{center}
	\begin{tabbing}
		endloop: \= addcc \= \%r1,\%r2,\%r3 \ \ \ \ \= ! comentario \kill
		loop: \> subcc \> \%r1, N, \%r0 \\
		\> be \> endloop \> ! do n!=N \\
	\end{tabbing}
	\end{center}
	\end{small}
	}
	
	La multiasignaci\'on siguiente si requiere cuidado en su desacople ya que un orden $(n,x)$
nos da un resultado que no es equivalente a la asignaci\'on m\'ultiple.
	\Prog{
	\begin{small}
	\begin{center}
	\begin{tabbing}
		[ \= con N: Int, A: array [0,N) of Int; var n,r: Int \kill
		\> {\bf do}\= \kill
		\> \>	$\Box$ \= smtg. \kill
		\> \>	\> $\cdots\rightarrow$ n,r := n+1,r+A.n
	\end{tabbing}
	\end{center}
	\end{small}
	}
	El incremento de $n$ es inmediato, no as\'{\i} la suma en $r$, pues tenemos que obtener por un lado el
\'{\i}ndice corregido a bytes en la memoria, y por el otro el valor de esa memoria para reci\'en poder sumarlo
con \Prog{\%r2} ($r$).
	\Prog{
	\begin{small}
	\begin{center}
	\begin{tabbing}
		endloop: \= addcc \= \%r1,\%r2,\%r3 \ \ \ \ \= ! comentario \kill
		\> sll \> \%r1, 2, \%r3 \> ! \%r3 := \%r1*4 \\
		\> ld \> A+\%r3, \%r4 \> ! \%r4 := A.\%r1 \\
		\> add \> \%r2, \%r4, \%r2 \> ! r := r+A.n \\
		\> add \> \%r1, 1, \%r1 \> ! n := n+1
	\end{tabbing}
	\end{center}
	\end{small}
	}

	El final del lazo se obtiene con un salto al inicio del mismo.
	\Prog{
	\begin{small}
	\begin{center}
	\begin{tabbing}
		endloop: \= addcc \= \%r1,\%r2,\%r3 \ \ \ \ \= ! comentario \kill
		\> ba \> loop
	\end{tabbing}
	\end{center}
	\end{small}
	}
	
	El final del programa ARC est\'a dado por la etiqueta \Prog{endloop} de finalizaci\'on de lazo junto
a la instrucci\'on de parada del programa, la definici\'on del arreglo \Prog{A} y la pseudo-op que indica
el final del ensamblado.
	\Prog{
	\begin{small}
	\begin{center}
	\begin{tabbing}
		endloop: \= addcc \= \%r1,\%r2,\%r3 \ \ \ \ \= ! comentario \kill
		endloop: \> halt \\
		A: \> 5 \\
		\> -2 \\
		\> 3  \\
		\> -5 \\
		\> 7  \\
		\> .end
	\end{tabbing}
	\end{center}
	\end{small}
	}

	Veamos el c\'odigo completo:
	
	\Prog{
	\begin{small}
	\begin{center}
	\begin{tabbing}
		endloop: \= addcc \= \%r1,\%r2,\%r3 \ \ \ \ \= ! comentario \kill
		\> ! n <-> \%r1 \\
		\> ! r <-> \%r2 \\
		\> .begin \\
		N \> .equ \> 5 \> ! el arreglo tendra 5 elementos \\
		\> .org \> 2048 \\
		\> and \> \%r0, \%r0, \%r1 \> ! n := 0 \\
		\> sethi \> 0, \%r2 \> ! r := 0 \\
		loop: \> subcc \> \%r1, N, \%r0 \\
		\> be \> endloop \> ! do n!=N \\
		\> sll \> \%r1, 2, \%r3 \> ! \%r3 := \%r1*4 \\
		\> ld \> A+\%r3, \%r4 \> ! \%r4 := A.\%r1 \\
		\> add \> \%r2, \%r4, \%r2 \> ! r := r+A.n \\
		\> add \> \%r1, 1, \%r1 \> ! n := n+1 \\
		\> ba \> loop \\
		endloop: \> halt \\
		A: \> 5 \\
		\> -2 \\
		\> 3  \\
		\> -5 \\
		\> 7 \\
		\> .end
	\end{tabbing}
	\end{center}
	\end{small}
	}



		
	

\end{document}
