Suma de los Elementos de un Arreglo

En la página 142 del mismo apunte se deriva, a partir de la especificación $Q$, un algoritmo para obtener en la variable $r$ la suma de los elementos de un arreglo $A$.

[ 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\}$ 
 do
	n$\neq$N $\rightarrow$ n,r := n+1,r+A.n 
 od
$\{Q: r=(\sum.i : 0\leq i<n : A.i) \}$
]

Vamos a obtener paso a paso el programa ARC a partir del código anterior. La primera línea contiene las declaraciones.

[ con N: Int, A: array [0,N) of Int; var n,r: Int

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

La constante N la podemos mapear a un símbolo definido con el pseudo-op .equ. Para las variables enteras $n$ y $r$ elegimos mantenerlas en registros del microprocesador.

	! n <-> %r1
	! r <-> %r2
	.begin
N	.equ	5		! el arreglo tendra 5 elementos
	.org	2048

El arreglo no lo definimos aún, pues queremos que esté al final del programa.

La multiasignación siguiente, puede ser desacoplada en dos de manera directa.

 		 n,r := 0,0 

Existen muchas formas de poner en 0 los registros %r1 y %r2. Elegimos una de cada tipo.

	and	%r0, %r0, %r1		! n := 0
	sethi	0, %r2			! r := 0

El inicio del constructor de repetición lo mapeamos de la misma forma que en la sección anterior.

 do
	n$\neq$N $\rightarrow \cdots$

Con una resta entre $n$ y $N$ que modifique el %psr y un salto que salga del lazo en caso de igualdad nos alcanza. Seguimos la estructura loop-endloop de las etiquetas que marcan el inicio y fin del bucle.

loop:	subcc	%r1, N, %r0
	be	endloop		! do n!=N

La multiasignación siguiente si requiere cuidado en su desacople ya que un orden $(n,x)$ nos da un resultado que no es equivalente a la asignación múltiple.

		$\cdots \rightarrow$ n,r := n+1,r+A.n 

El incremento de $n$ es inmediato, no así la suma en $r$, pues tenemos que obtener por un lado el índice corregido a bytes en la memoria, y por el otro el valor de esa memoria para recién poder sumarlo con %r2 ($r$).

	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

El final del lazo se obtiene con un salto al inicio del mismo.

	ba	loop

El final del programa ARC está dado por la etiqueta endloop de finalización de lazo junto a la instrucción de parada del programa, la definición del arreglo A y la pseudo-op que indica el final del ensamblado.

endloop:halt
A:	5
	-2
	3
	-5
	7
	.end

Veamos el código completo:

! 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