% $Id: example.tex,v 1.17 1997/02/01 20:57:49 cierniak Exp $

\newpage
\appendix

\section{Example of code structure recovery}
\label{sec:example:recovery}

To illustrate how Briki recovers high-level structure from a bytecode
representation of a method, we will show the process of structure
recovery for a simple example.  Relatively large sizes of our
benchmark applications used to produce the results shown in
Section~\ref{sec:exp} make it impractical to present them here.  We
chose a very short method to show here.  Our example is a function
which computes the $n$th Fibonacci number:
\begin{verbatim}
public static int fibonacci(int n) {
   int p1 = 0;
   int p2 = 1;
   for(int i = 0; i < n; i++) {
      int nextVal = p1 + p2;
      p1 = p2;
      p2 = nextVal;
   }
   return p2;
}
\end{verbatim}
The bytecode representation of that method (after compiling with {\tt
  javac}) is:
\begin{verbatim}
Method int fibonacci(int)
   0 iconst_0
   1 istore_1
   2 iconst_1
   3 istore_2
   4 iconst_0
   5 istore_3
   6 goto 22
   9 iload_1
  10 iload_2
  11 iadd
  12 istore 4
  14 iload_2
  15 istore_1
  16 iload 4
  18 istore_2
  19 iinc 3 1
  22 iload_3
  23 iload_0
  24 if_icmplt 9
  27 iload_2
  28 ireturn
\end{verbatim}
Basic blocks start at 0, 9, 22 and 27.  We label them as {\bf BB0},
{\bf BB9}, {\bf BB22} and {\bf BB27} accordingly.
Figure~\ref{fig:example:cfg:one} shows the basic blocks arranged in a
control flow graph
%         B0
%         |
%         V
%	B22 <-----      
%      /     \     |
%     /       \    |
%    V         V   |
%   B27        B9--|

\begin{figure}[hbt]
  \centerline{\psfig{figure=cfg1.eps,height=3.5in,width=3.2in}}
  \caption{A control flow graph for {\tt fibonacci}}
  \label{fig:example:cfg:one}
\end{figure}
The next step replaces branches with structured control flow
constructs as described in Section~\ref{sec:recovery:goto}.
There are no short-circuit operators in this code.  One loop is
identified with a {\em back edge\/} from node {\bf BB9} to {\bf BB22}
and so a {\bf repeat} node is inserted before {\bf BB22}.
%Figure~\ref{fig:example:cfg:two} shows the CFG after inserting {\bf
%  repeat} nodes step.
%         B0
%         |
%         V
%	 R4 <------|
%         |        |
%         V        |
%	B22        |
%      /     \     |
%     /       \    |
%    V         V   |
%   B27        B9--|
%\begin{figure}[hbt]
%  \centerline{\psfig{figure=cfg2.eps,height=2.5in,width=2.1in}}
%  \caption{The control flow graph after inserting a {\bf repeat} node}
%  \label{fig:example:cfg:two}
%\end{figure}
Next, as described in~\ref{sec:recovery:alg:overview}, we interpret
each basic block converting the bytecode sequences to JavaIR.  The CFG
after this step is shown in Figure~\ref{fig:example:cfg:three} (JavaIR
is shown as Java source).
\begin{figure}[hbt]
  \centerline{\psfig{figure=cfg3.eps,height=2.8in,width=2.7in}}
  \caption{The CFG for {\tt fibonacci} after translating basic blocks
    to JavaIR}
  \label{fig:example:cfg:three}
\end{figure}


After the structuring algorithm, the code for {\tt fibonacci} may be
presented (using the notation from~\cite{Baker-JACM-1977}) as:
\begin{verbatim}
BB0
repeat R4
  if(BB22)
    BB9
  else
    BB27
  continue(1)
end of repeat R4
\end{verbatim}



JavaIR form of {\tt fibonacci} can be presented as the following
source fragment.
\begin{verbatim}
   public static int fibonacci ( int a0 )
   {
      int v0, v1, v2, v4;
      v0 = 0;
      v1 = 1;
      for(v2 = 0; v2 < a0; v2 = (v2 + 1)) {
         v4 = (v0 + v1);
         v0 = v1;
         v1 = v4;
      } //for
      return v1;
   } // fibonacci
\end{verbatim}




\section{Example of an array transformation}
\label{sec:example:opt}

We will show here a much simplified version of the matrix multiply
used in our experiments.  The version shown here is big enough to show
how the transformation is performed.  
The full benchmark is too big to be presented here.

\begin{verbatim}
static public void mult(int A[][], int B[][], int C[][]) {
   int n = A.length;   // Assume A, B, C are square.
   int i, j, k;
   for(j = 0; j < n; j++) {
      for(k = 0; k < n; k++) {
         for(i = 0; i < n; i++) {
            C[i][k] += A[i][j]*B[j][k];
         }
      }
   }
} //mult
\end{verbatim}


%The bytecode representation of that method (after compiling with {\tt
%  javac}) is:
%\begin{verbatim}
%Method void mult(int [][],int [][],int [][])
%   0 aload_0
%   1 arraylength
%   2 istore_3
%   3 iconst_0
%   4 istore 5
%   6 goto 67
%   9 iconst_0
%  10 istore 6
%  12 goto 58
%  15 iconst_0
%  16 istore 4
%  18 goto 49
%  21 aload_2
%  22 iload 4
%  24 aaload
%  25 iload 6
%  27 dup2
%  28 iaload
%  29 aload_0
%  30 iload 4
%  32 aaload
%  33 iload 5
%  35 iaload
%  36 aload_1
%  37 iload 5
%  39 aaload
%  40 iload 6
%  42 iaload
%  43 imul
%  44 iadd
%  45 iastore
%  46 iinc 4 1
%  49 iload 4
%  51 iload_3
%  52 if_icmplt 21
%  55 iinc 6 1
%  58 iload 6
%  60 iload_3
%  61 if_icmplt 15
%  64 iinc 5 1
%  67 iload 5
%  69 iload_3
%  70 if_icmplt 9
%  73 return
%\end{verbatim}

The bytecode representation of that method (after compiling with {\tt
  javac}) is shown in Figure~\ref{fig:example:mxm:bc}:
\begin{figure}[hbt]
  \begin{minipage}[hbt]{1.8in}
\begin{verbatim}
void mult(int [][],
          int [][],
          int [][])
   0 aload_0
   1 arraylength
   2 istore_3
   3 iconst_0
   4 istore 5
   6 goto 67
   9 iconst_0
  10 istore 6
  12 goto 58
  15 iconst_0
  16 istore 4
  18 goto 49
  21 aload_2
  22 iload 4
  24 aaload
  25 iload 6
  27 dup2
  28 iaload
  29 aload_0
  30 iload 4
\end{verbatim}
  \end{minipage}
  \hspace{1in}
  \begin{minipage}[hbt]{1.8in}
\begin{verbatim}
  32 aaload
  33 iload 5
  35 iaload
  36 aload_1
  37 iload 5
  39 aaload
  40 iload 6
  42 iaload
  43 imul
  44 iadd
  45 iastore
  46 iinc 4 1
  49 iload 4
  51 iload_3
  52 if_icmplt 21
  55 iinc 6 1
  58 iload 6
  60 iload_3
  61 if_icmplt 15
  64 iinc 5 1
  67 iload 5
  69 iload_3
  70 if_icmplt 9
  73 return
\end{verbatim}
  \end{minipage}
  \caption{The bytecode representation of the method {\tt mult}}
  \label{fig:example:mxm:bc}
\end{figure}
%The textual representation of the CFG for {\tt mult} is presented in
%Figure~\ref{fig:example:mxm:cfg}.  
%\begin{figure}[hbt]
%  \centerline{\psfig{figure=mxmcfg1.eps,height=4.2in,width=4.0in}}
%  \caption{The control flow graph after translating basic blocks to JavaIR}
%  \label{fig:example:mxm:cfg}
%\end{figure}
The JavaIR form of the body of {\tt mult}
 is presented in
Figure~\ref{fig:example:mxm:javair}.  
\begin{figure}[hbt]
  \centerline{\psfig{figure=mxmjavair.eps,height=4.0in,width=4.0in}}
  \caption{The JavaIR form of the body of {\tt mult}}
  \label{fig:example:mxm:javair}
\end{figure}
The goto elimiantion phase of Briki constructs the JavaIR form, so
that it is equivalent to the original source shown earlier.

Our data remapping pass analyzes the JavaIR form of the method and
first determines which arrays may be safely remapped.  At the same
time desired mappings for all multidimensional array references are
found.  This information is used to decide which (if any) arrays will
be remapped.  The next stage remaps all those arrays.

In our model we assume that array references with stride 1 in the
innermost loop will have better locality properties than references
with larger strides.  A {\em stride\/} for a given reference is the
distance between addresses of the two array elements accessed in
consecutive iterations of the loop being considered.

For our example, the innermost-loop strides for references {\tt
  C[i][k]} and {\tt A[i][j]} are greater than 1 and the stride for
{\tt B[j][k]} is 0.  A data transformation cannot change the innermost
stride the reference to array {\tt B} since the loop index variable is
not used in any of its subscripts, we can however improve the strides
for the other two references.

The transformations used by us will correspond to swapping the two
dimensions of arrays {\tt A} and {\tt C}.  This will change the
innermost loop to:
\begin{verbatim}
         for(i = 0; i < n; i++) {
            C[k][i] += A[j][i]*B[j][k];
         }
\end{verbatim}
Note that for the simplified example used in
this section, this transformation alone would not be legal and our
compiler would not perform it.  
Remapping of arrays {\tt A} and {\tt C} would be valid only if either:
\begin{itemize}
\item We would at run-time verify at the beginning of {\tt mult} that
  the arrays are rectangular and insert code fragments at the
  beginning and at the end of {\tt mult} to convert the arrays between
  the original and optimized mappings.  The runtime overhead incurred
  by this approach may eliminate any benefits we got from the improved
  locality in the body of {\tt mult}.
\item We would at compile-time analyze a broader context in which the
  arrays of interest are used.  Then, we can ensure that all other
  references to the transformed arrays (including their allocation)
  will be changed accordingly.
\end{itemize}


%   public static void mult (
%         int a0[][],
%         int a1[][],
%         int a2[][]
%      )
%   {
%      int v1;
%      int v4;
%      int v2;
%      int v3;
%      v1 = (a0.length);
%      v2 = 0;
%      L18:
%      while((v2 < v1)) {
%         v3 = 0;
%         L14:
%         while((v3 < v1)) {
%            v4 = 0;
%            L11:
%            while((v4 < v1)) {
%               a2[v4][v3] = (a2[v4][v3] + (a0[v4][v2] * a1[v2][v3]));
%               v4 = (v4 + 1);
%            } //while
%            v3 = (v3 + 1);
%         } //while
%         v2 = (v2 + 1);
%      } //while
%      return;
%   } // mult
