%% -*- mode: latex; TeX-master: "compilerbau.tex"; -*-

\kopf{$ $Id: trafo.tex,v 1.1 2011-10-16 14:06:16 waldmann Exp $ $}

\subsection{{Code für Array-Zugriffe}

\subsection{Code-Transformationen}

\begin{slide}{Einfacher Matrix-Zugriff}
\begin{verbatim}
#include <stdio.h>
#define N 100

typedef int matrix [N][N];

// zum betrachten der index-rechnungen
int access (matrix a, int i) {
  int x = a[3][i];
  int y = a[i][5];
  return x + y;
}
\end{verbatim}
Compilieren mit \verb|gcc -S| ergibt:
\begin{verbatim}
diag:
        !#PROLOGUE# 0
        save    %sp, -120, %sp
        !#PROLOGUE# 1
        st      %i0, [%fp+68]    -- &a
        st      %i1, [%fp+72]    -- i
\end{verbatim}
\end{slide}

\begin{slide}{Constant folding}
Zugriff auf \verb|a[3][i]|.
\begin{verbatim}
        ld      [%fp+72], %o0    -- i
        mov     %o0, %o1         -- i
        sll     %o1, 2, %o0      -- 4*i
        ld      [%fp+68], %o1    -- &a
        add     %o0, %o1, %o0    -- &a + 4*i
        ld      [%o0+1200], %o1  -- mem [ &a + 4 * i + 4 * 3 * N ]
        st      %o1, [%fp-20]    -- x
\end{verbatim}
\end{slide}

\begin{slide}{strength reduction}
Zugriff auf \verb|a[i][5]|. 
\begin{verbatim}
        ld      [%fp+72], %o0    -- i
        mov     %o0, %o2         -- i
        sll     %o2, 1, %o1      -- 2*i
        add     %o1, %o0, %o1    -- 3*i
        sll     %o1, 3, %o2      -- 24*i
        add     %o2, %o0, %o2    -- 25*i
        sll     %o2, 4, %o0      -- 25*16*i = 4 * N * i
        ld      [%fp+68], %o1    -- &a
        add     %o0, %o1, %o0    -- &a + 4*N*i
        ld      [%o0+20], %o1    -- mem [&a + 4*N*i + 4*5]
        st      %o1, [%fp-24]    -- y
\end{verbatim}
\end{slide}

\begin{slide}{Rückgabe}
Ergebnis ausrechnen und zurückgeben:
\begin{verbatim}
        ld      [%fp-20], %o0
        ld      [%fp-24], %o1
        add     %o0, %o1, %o0
        mov     %o0, %i0
        b       .LL2
         nop
.LL2:
        ret
        restore
\end{verbatim}
\end{slide}

\begin{slide}{Stack-Frames}

Compiliere jetzt mit \verb|gcc -S -O|:
\begin{verbatim}
diag:
        !#PROLOGUE# 0
        !#PROLOGUE# 1
        sll     %o1, 2, %g2     -- 4*i
        add     %g2, %o0, %g2   -- &a + 4*i
        ld      [%g2+1200], %g3 -- mem [&a + 4*i + 4*3*N ]
        sll     %o1, 1, %g2     -- 2*i
        add     %g2, %o1, %g2   -- 3*i
        sll     %g2, 3, %g2     -- 24*i
        add     %g2, %o1, %g2   -- 25*i
        sll     %g2, 4, %g2     -- 16*25i = 4*N*i
        add     %g2, %o0, %g2   -- &a + 4*N*i
        ld      [%g2+20], %o0   -- mem [ &a + 4*N*i + 4*5]
        retl
        add     %g3, %o0, %o0
\end{verbatim}
wir rechen im Stack-Frame des Callers.

benutzen globale register.
\end{slide}


\begin{slide}{Schleifen, Code-Verschiebung}

\begin{verbatim}
// c := a + b
void add (matrix c, matrix a, matrix b) {
  int i; int j;
  for (i=0; i<N; i++) {
    for (j=0; j<N; j++) {
      c [i][j] = a[i][j] + b[i][j];
    }
  }
}
\end{verbatim}
Kompilieren mit \verb|gcc -S -O|

\begin{verbatim}
add:
        !#PROLOGUE# 0
        save    %sp, -112, %sp
        !#PROLOGUE# 1
        mov     %i0, %o7         -- &c
        mov     0, %g4           -- i
        mov     0, %i3           -- j
.LL14:                           -- for (i ..)
        sll     %g4, 1, %g2      -- 2*i
        add     %g2, %g4, %g2    -- 3*i
        sll     %g2, 3, %g2      -- 24*i
        add     %g2, %g4, %g2    -- 25*i
        sll     %g2, 4, %g2      -- 16*25*i = 4*N*i
        add     %g2, %o7, %g1    -- &c + 4*N*i = c[i][]
        add     %g2, %i1, %i5    -- &a + 4*N*i = a[i][]
        add     %g2, %i2, %i4    -- &b + 4*N*i = b[i][]
\end{verbatim}
Hier wurde die Index-rechnung vor die (innere) Schleife geschoben.
\begin{verbatim}
.LL11:                           -- for (j ..)
        sll     %i3, 2, %g2      -- 4*j
        ld      [%i5+%g2], %g3   -- a[i][j]
        ld      [%i4+%g2], %i0   -- b[i][j]
        add     %g3, %i0, %g3    -- a[i][j] + b[i][j]
        add     %i3, 1, %i3      -- j ++
        cmp     %i3, 99          -- < N ?
        ble     .LL11
        st      %g3, [%g1+%g2]   -- c[i][j] = ..
\end{verbatim}
Ende der äußeren schleife:
\begin{verbatim}
        add     %g4, 1, %g4      -- i++
        cmp     %g4, 99          -- < N ?
        ble     .LL14
        mov     0, %i3
        ret
        restore
\end{verbatim}
\end{slide}

\begin{slide}{Arithmetische Umformungen}

Gleiche Funktion \verb|add| jetzt mit \verb|gcc -S -O6|,
betrachte innere Schleife:
\begin{verbatim}
.LL11:
        ld      [%i3+%i5], %g2
        add     %i4, 1, %i4
        ld      [%i3+%i0], %g3
        cmp     %i4, 99
        add     %g2, %g3, %g2
        st      %g2, [%i3+%g1]
        ble     .LL11
        add     %i3, 4, %i3       -- Index weiterzählen
\end{verbatim}
\end{slide}


\begin{slide}{Mehr Schleifen}
\begin{verbatim}
// c := a * b
void times (matrix c, matrix a, matrix b) {
  int i; int j; int k;
  for (i=0; i<N; i++) {
    for (k=0; k<N; k++) {
      c[i][k] = 0.0;
      for (j=0; j<N; j++) {
        c[i][k] = c[i][k] + a[i][j] * b[j][k];
      }
    }
  }
}
\end{verbatim}
mit \verb|gcc -S -O6|:
\begin{verbatim}
times:
        !#PROLOGUE# 0
        save    %sp, -112, %sp
        !#PROLOGUE# 1
        mov     0, %o2        -- i
\end{verbatim}
for (i \dots)
\begin{verbatim}
        sll     %o2, 1, %o0   -- 2*i
.LL32:
        add     %o0, %o2, %o0 -- 3*i
        sll     %o0, 3, %o0   -- 24*i
        add     %o0, %o2, %o0 -- 25*i
        sll     %o0, 4, %o0   -- 4*N*i
        add     %o0, %i1, %l5 -- a[i]
        add     %o0, %i0, %l3 -- c[i]
        mov     0, %o1        -- k
        add     %o2, 1, %l6   -- i+1 ??
\end{verbatim}
for (k \dots)
\begin{verbatim}
        sll     %o1, 2, %o0   -- 4*k
.LL31:
        mov     %o0, %l2       -- 4*k
        add     %o1, 1, %l4    -- k+1 
        st      %g0, [%l3+%o0] -- c[i][k] = 0
        mov     0, %l1         -- j
        add     %i2, %l2, %l0  -- &b + 4*k
\end{verbatim}
for (j \dots)
\begin{verbatim}
.LL26:
        sll     %l1, 2, %o1    -- 4*j
        ld      [%l5+%o1], %o0 -- a[i][j]
        add     %l1, 1, %l1    -- j++
        call    .umul, 0       -- zweites argument folgt
        ld      [%l0], %o1     -- b[] [k]
        ld      [%l3+%l2], %o1 -- c[i][k]
        add     %l0, 400, %l0  -- offset für b weiter
        add     %o1, %o0, %o1  -- c[i][k] + produkt
        cmp     %l1, 99         
        ble     .LL26
        st      %o1, [%l3+%l2] -- c[i][k] = ..
\end{verbatim}
end for k
\begin{verbatim}
        mov     %l4, %o1       -- k
        cmp     %o1, 99
        ble,a   .LL31
        sll     %o1, 2, %o0    -- 4*k
\end{verbatim}
end for i
\begin{verbatim}
        mov     %l6, %o2       -- i
        cmp     %o2, 99
        ble     .LL32
        sll     %o2, 1, %o0    -- 2*i

        ret
        restore
\end{verbatim}

\end{slide}
