afl-material: comparison handouts/ho07.tex

equal deleted inserted replaced

-:64ec1884d860
+:c7009356ddd8
 good enough for improving the speed of a program to target a virtual
 machine instead. This produces not the fastest possible code, but code
 that is often pretty fast. This way of producing code has also the
 advantage that the virtual machine takes care of things a compiler would
 normally need to take care of (hairy things like explicit memory
 management).
 As a first example in this module we will implement a compiler for the
 very simple WHILE-language that we parsed in the last lecture. The
 compiler will target the Java Virtual Machine (JVM), but not directly.
 Pictorially the compiler will work as follows:
 \begin{center}
 \begin{tikzpicture}[scale=1,font=\bf,
 node/.style={
 rectangle,rounded corners=3mm,
 ultra thick,draw=black!50,minimum height=18mm,
 minimum width=20mm,
 top color=white,bottom color=black!20}]
 \node (0) at (-3,0) {};
 \node (A) at (0,0) [node,text width=1.6cm,text centered] {our compiler};
 \node (B) at (3.5,0) [node,text width=1.6cm,text centered] {Jasmin / Krakatau};
 \node (C) at (7.5,0) [node] {JVM};
 \draw [->,line width=2.5mm] (0) -- node [above,pos=0.35] {*.while} (A);
 \draw [->,line width=2.5mm] (A) -- node [above,pos=0.35] {*.j} (B);
 \draw [->,line width=2.5mm] (B) -- node [above,pos=0.35] {*.class} (C);
 \end{tikzpicture}
 \end{center}
 \noindent
 The input will be WHILE-programs; the output will be assembly files
-(with the file extension .j). Assembly files essentially contain
+(with the file extension *.j). Assembly files essentially contain
 human-readable low-level code, meaning they are not just bits and
 bytes, but rather something you can read and understand---with a bit
 of practice of course. An \emph{assembler} will then translate the
 assembly files into unreadable class- or binary-files the JVM or CPU
-can run.  Unfortunately, the Java ecosystem does not come with an
+can run, i.e.~bits and bytes.  Unfortunately, the Java ecosystem does not come with an
 assembler which would be handy for our compiler-endeavour (unlike
 Microsoft's Common Language Infrastructure for the .Net platform which
 has an assembler out-of-the-box). As a substitute we shall use the
-3rd-party programs Jasmin or Krakatau (Jasmin is the preferred
+3rd-party program Jasmin, or alternatively Krakatau (Jasmin is the preferred
 option---a \texttt{jasmin.jar}-file is available on KEATS):
 \begin{itemize}
 \item \url{http://jasmin.sourceforge.net}
 \item \url{https://github.com/Storyyeller/Krakatau}
 The first is a Java program and the second a program written in Python.
 Each of them allow us to generate \emph{assembly} files that are still
 readable by humans, as opposed to class-files which are pretty much just
 (horrible) zeros and ones. Jasmin (respectively Krakatau) will then take
 our assembly files as input and generate the corresponding class-files for
 us.
 What is good about the JVM is that it is a stack-based virtual machine,
 a fact which will make it easy to generate code for arithmetic
 expressions. For example when compiling the expression $1 + 2$ we need
 to generate the following three instructions
 \begin{lstlisting}[language=JVMIS,numbers=none]
 ldc 1
 ldc 2
 iadd
 \end{lstlisting}
 \noindent The first instruction loads the constant $1$ onto the stack,
 the next one loads $2$, the third instruction adds both numbers together
 replacing the top two elements of the stack with the result $3$. For
 node---this traversal in \emph{post-order} fashion will produce code for
 a stack-machine (which is what the JVM is). Doing so for the tree above
 generates the instructions
 \begin{lstlisting}[language=JVMIS,numbers=none]
 ldc 1
 ldc 2
 ldc 3
 imul
 ldc 4
 ldc 3
 isub
 iadd
 iadd
 \end{lstlisting}
 \noindent If we ``run'' these instructions, the result $8$ will be on
 top of the stack (I leave this to you to verify; the meaning of each
 instruction should be clear). The result being on the top of the stack
 will be an important convention we always observe in our compiler. Note,
 that a different bracketing of the expression, for example $(1 + (2 *
 3)) + (4 - 3)$, produces a different abstract syntax tree and thus also
 a different list of instructions.
 Generating code in this post-order-traversal fashion is rather easy to
 implement: it can be done with the following recursive
 \textit{compile}-function, which takes the abstract syntax tree as an
 argument:
 \begin{center}
 \begin{tabular}{lcl}
 $\textit{compile}(n)$ & $\dn$ & $\instr{ldc}\; n$\\
 $\textit{compile}(a_1 + a_2)$ & $\dn$ &
 $\textit{compile}(a_1) \;@\;\textit{compile}(a_2)\;@\; \instr{iadd}$\\
 $\textit{compile}(a_1 - a_2)$ & $\dn$ &
 $\textit{compile}(a_1) \;@\; \textit{compile}(a_2)\;@\; \instr{isub}$\\
 $\textit{compile}(a_1 * a_2)$ & $\dn$ &
 $\textit{compile}(a_1) \;@\; \textit{compile}(a_2)\;@\; \instr{imul}$\\
 $\textit{compile}(a_1 \backslash a_2)$ & $\dn$ &
 $\textit{compile}(a_1) \;@\; \textit{compile}(a_2)\;@\; \instr{idiv}$\\
 \end{tabular}
 \end{center}
 \noindent
 \begin{lstlisting}[language=JVMIS,mathescape,numbers=none]
 iload $index$
 \end{lstlisting}
 \noindent
 which places the content of the local variable $index$ onto
 the stack. Storing the top of the stack into a local variable
 can be done by the instruction
 \begin{lstlisting}[language=JVMIS,mathescape,numbers=none]
 istore $index$
 \end{lstlisting}
 and an environment, $E$, that maps identifiers to index-numbers.
 \begin{center}
 \begin{tabular}{lcl}
 $\textit{compile}(n, E)$ & $\dn$ & $\instr{ldc}\;n$\\
 $\textit{compile}(a_1 + a_2, E)$ & $\dn$ &
 $\textit{compile}(a_1, E) \;@\;\textit{compile}(a_2, E)\;@\; \instr{iadd}$\\
 $\textit{compile}(a_1 - a_2, E)$ & $\dn$ &
 $\textit{compile}(a_1, E) \;@\; \textit{compile}(a_2, E)\;@\; \instr{isub}$\\
 $\textit{compile}(a_1 * a_2, E)$ & $\dn$ &
 $\textit{compile}(a_1, E) \;@\; \textit{compile}(a_2, E)\;@\; \instr{imul}$\\
 $\textit{compile}(a_1 \backslash a_2, E)$ & $\dn$ &
 $\textit{compile}(a_1, E) \;@\; \textit{compile}(a_2, E)\;@\; \instr{idiv}$\\
 $\textit{compile}(x, E)$ & $\dn$ & $\instr{iload}\;E(x)$\\
 \end{tabular}
 \end{center}
 This is reflected in the clause for compiling assignments, say
 $x := a$:
 \begin{center}
 \begin{tabular}{lcl}
 $\textit{compile}(x := a, E)$ & $\dn$ &
 $(\textit{compile}(a, E) \;@\;\instr{istore}\;index, E')$
 \end{tabular}
 \end{center}
 \noindent We first generate code for the right-hand side of the
 ldc 1
 iadd
 istore $n_x$
 \end{lstlisting}
 \noindent
 where $n_x$ is the index (or pointer to the memory) for the variable
 $x$. The Scala code for looking-up the index for the variable is as follow:
 \begin{center}
 \begin{tabular}{lcl}
 \node [below=of cs1] {\raisebox{-5mm}{\small{}conditional jump}};
 \end{tikzpicture}
 \end{center}
 \noindent where we now need a conditional jump (if the
 if-condition is false) from the end of the code for the
 boolean to the beginning of the instructions $cs_2$. Once we
 are finished with running $cs_2$ we can continue with whatever
 code comes after the if-statement.
 The \instr{goto} and the conditional jumps need addresses to
 where the jump should go. Since we are generating assembly
 code for the JVM, we do not actually have to give (numeric)
 addresses, but can just attach (symbolic) labels to our code.
-These labels specify a target for a jump. Therefore the labels
+These labels specify a target for a jump---essentially they mark
+a location in our code. Therefore the labels
 need to be unique, as otherwise it would be ambiguous where a
 jump should go to. A label, say \pcode{L}, is attached to assembly
 code like
 \begin{lstlisting}[mathescape,numbers=none]
+$\textit{instr\_1}$
 L:
-$\textit{instr\_1}$
 $\textit{instr\_2}$
+$\textit{instr\_3}$
 $\vdots$
 \end{lstlisting}
 \noindent where the label needs to be followed by a colon. The task of
 the assembler (in our case Jasmin or Krakatau) is to resolve the labels
 to actual (numeric) addresses, for example jump 10 instructions forward,
-or 20 instructions backwards.
+or 20 instructions backwards, or jump to this particular address.
 Recall the ``trick'' with compiling boolean expressions: the
 \textit{compile}-function for boolean expressions takes three
 arguments: an abstract syntax tree, an environment for
-variable indices and also the label, $lab$, to where an conditional
+variable indices and also the label, which I called $lab$, to where an conditional
 jump needs to go. The clause for the expression $a_1 = a_2$,
 for example, is as follows:
 \begin{center}
 \begin{tabular}{lcl}
 $\textit{compile}(a_1 = a_2, E, lab)$ & $\dn$\\
 \multicolumn{3}{l}{$\qquad\textit{compile}(a_1, E) \;@\;\textit{compile}(a_2, E)\;@\; \instr{if_icmpne}\;lab$}
 \end{tabular}
 \end{center}
 \noindent where we are first generating code for the
 To sum up, the third argument in the compile function for booleans
 specifies where to jump, in case the condition is \emph{not} true. I
 leave it to you to extend the \textit{compile}-function for the other
 boolean expressions. Note that we need to jump whenever the boolean is
 \emph{not} true, which means we have to ``negate'' the jump
 condition---equals becomes not-equal, less becomes greater-or-equal.
 Other jump instructions for boolean operators are
 \begin{center}
 \begin{tabular}{l@{\hspace{10mm}}c@{\hspace{10mm}}l}
 $\not=$ & $\Rightarrow$ & \instr{if_icmpeq}\\
 layout of the code and first give the code for the else-branch and then
 for the if-branch. However in the case of while-loops this
 ``upside-down-inside-out'' way of generating code still seems the most
 convenient.
 We are now ready to give the compile function for
 if-statements---remember this function returns for statements a
 pair consisting of the code and an environment:
 \begin{center}
 \begin{tabular}{lcl}
 $\textit{compile}(\pcode{if}\;b\;\pcode{then}\; cs_1\;\pcode{else}\; cs_2, E)$ & $\dn$\\
 \multicolumn{3}{l}{$\qquad L_\textit{ifelse}\;$ (fresh label)}\\
 \multicolumn{3}{l}{$\qquad L_\textit{ifend}\;$ (fresh label)}\\
 \multicolumn{3}{l}{$\qquad (is_1, E') = \textit{compile}(cs_1, E)$}\\
 \multicolumn{3}{l}{$\qquad (is_2, E'') = \textit{compile}(cs_2, E')$}\\
 \multicolumn{3}{l}{$\qquad(\textit{compile}(b, E, L_\textit{ifelse})$}\\
 \noindent In the first two lines we generate two fresh labels
 for the jump addresses (just before the else-branch and just
 after). In the next two lines we generate the instructions for
 the two branches, $is_1$ and $is_2$. The final code will
 be first the code for $b$ (including the label
 just-before-the-else-branch), then the \pcode{goto} for after
-the else-branch, the label $L_\textit{ifelse}$, followed by
+the else-branch, the label $L_\textit{--ifelse}$, followed by
 the instructions for the else-branch, followed by the
 after-the-else-branch label. Consider for example the
 if-statement:
 \begin{lstlisting}[mathescape,numbers=none,language=While]
 if 1 == 1 then x := 2 else y := 3
 \end{lstlisting}
 \noindent
 The generated code is as follows:
 \begin{lstlisting}[language=JVMIS,mathescape,numbers=left]
 ldc 1
 ldc 1
 istore 1
 L_ifend: $\quad\tikz[remember picture] \node[] (B) {\mbox{}};$
 \end{lstlisting}
 \begin{tikzpicture}[remember picture,overlay]
 \draw[->,very thick] (A) edge [->,to path={-- ++(10mm,0mm)
 -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (B.east);
 \draw[->,very thick] (C) edge [->,to path={-- ++(10mm,0mm)
 -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (D.east);
 \end{tikzpicture}
 \noindent The first three lines correspond to the the boolean
 expression \texttt{1 == 1}. The jump for when this boolean expression
 is false is in Line~3. Lines 4-6 corresponds to the if-branch;
 the else-branch is in Lines 8 and 9.
 Note carefully how the environment $E$ is threaded through the recursive
 calls of \textit{compile}. The function receives an environment $E$, but
 it might extend it when compiling the if-branch, yielding $E'$. This
 happens for example in the if-statement above whenever the variable
 \code{x} has not been used before. Similarly with the environment $E''$
 for the second call to \textit{compile}. $E''$ is also the environment
 that needs to be returned as part of the answer.
-The compilation of the while-loops, say
+The compilation of the while-loops of the form
-\pcode{while} $b$ \pcode{do} $cs$, is very similar. In case
+\pcode{while} $b$ \pcode{do} $cs$ is very similar. In case
 the condition is true and we need to do another iteration,
 and the control-flow needs to be as follows
 \begin{center}
 \begin{tikzpicture}[node distance=2mm and 4mm,line cap=round,
 block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm,
 \end{tikzpicture}
 \end{center}
 \noindent Again we can use the \textit{compile}-function for
 boolean expressions to insert the appropriate jump to the
-end of the loop (label $L_{wend}$ below).
+end of the loop (label $L_\textit{--wend}$ below).
 \begin{center}
 \begin{tabular}{lcl}
 $\textit{compile}(\pcode{while}\; b\; \pcode{do} \;cs, E)$ & $\dn$\\
-\multicolumn{3}{l}{$\qquad L_{wbegin}\;$ (fresh label)}\\
+\multicolumn{3}{l}{$\qquad L_\textit{--wbegin}\;$ (fresh label)}\\
-\multicolumn{3}{l}{$\qquad L_{wend}\;$ (fresh label)}\\
+\multicolumn{3}{l}{$\qquad L_\textit{--wend}\;$ (fresh label)}\\
 \multicolumn{3}{l}{$\qquad (is, E') = \textit{compile}(cs_1, E)$}\\
-\multicolumn{3}{l}{$\qquad(L_{wbegin}:$}\\
+\multicolumn{3}{l}{$\qquad(L_\textit{--wbegin}$}\\
-\multicolumn{3}{l}{$\qquad\phantom{(}@\;\textit{compile}(b, E, L_{wend})$}\\
+\multicolumn{3}{l}{$\qquad\phantom{(}@\;\textit{compile}(b, E, L_\textit{--wend})$}\\
 \multicolumn{3}{l}{$\qquad\phantom{(}@\;is$}\\
-\multicolumn{3}{l}{$\qquad\phantom{(}@\; \text{goto}\;L_{wbegin}$}\\
+\multicolumn{3}{l}{$\qquad\phantom{(}@\; \text{goto}\;L_\textit{--wbegin}$}\\
-\multicolumn{3}{l}{$\qquad\phantom{(}@\;L_{wend}:, E')$}\\
+\multicolumn{3}{l}{$\qquad\phantom{(}@\;L_\textit{--wend}, E')$}\\
 \end{tabular}
 \end{center}
 \noindent I let you go through how this clause works. As an example
 you can consider the while-loop
 iadd
 istore 0
 goto L_wbegin $\quad\tikz[remember picture] \node (LA) {\mbox{}};$
 L_wend: $\quad\tikz[remember picture] \node[] (LD) {\mbox{}};$
 \end{lstlisting}
 \begin{tikzpicture}[remember picture,overlay]
 \draw[->,very thick] (LA) edge [->,to path={-- ++(10mm,0mm)
 -- ++(0mm,17.3mm) |- (\tikztotarget)},line width=1mm] (LB.east);
 \draw[->,very thick] (LC) edge [->,to path={-- ++(10mm,0mm)
 -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (LD.east);
 \end{tikzpicture}
 \noindent
-As said, I leave it to you to decide whether the code implements
+As said, I leave it to you to check that the code really implements
 the usual controlflow of while-loops.
 Next we need to consider the WHILE-statement \pcode{write x}, which can
 be used to print out the content of a variable. For this we shall use a
 Java library function. In order to avoid having to generate a lot of
 just call this method with an appropriate argument (which of course
 needs to be placed onto the stack). The code of the helper-method is as
 follows.
 \begin{lstlisting}[language=JVMIS,numbers=left,basicstyle=\ttfamily\small]
 .method public static write(I)V
 .limit locals 1
 .limit stack 2
 getstatic java/lang/System/out Ljava/io/PrintStream;
 iload 0
 invokevirtual java/io/PrintStream/println(I)V
 return
 .end method
 \end{lstlisting}
 \noindent The first line marks the beginning of the method, called
 \pcode{write}. It takes a single integer argument indicated by the
 \pcode{write} was called. This method needs to be part of a header
 that is included in any code we generate. The helper-method
 \pcode{write} can be invoked with the two instructions
 \begin{lstlisting}[mathescape,language=JVMIS]
 iload $E(x)$
 invokestatic XXX/XXX/write(I)V
 \end{lstlisting}
 \noindent where we first place the variable to be printed on
 top of the stack and then call \pcode{write}. The \pcode{XXX}
 \begin{figure}[p]
 \begin{framed}
 \lstinputlisting[language=JVMIS,mathescape,basicstyle=\ttfamily\small]{../progs/test-small.j}
 \begin{tikzpicture}[remember picture,overlay]
 \draw[|<->|,very thick] (LA.north) -- (LB.south)
 node[left=-0.5mm,midway] {\footnotesize\texttt{x\,:=\,1\,+\,2}};
 \draw[|<->|,very thick] (LC.north) -- (LD.south)
 node[left=-0.5mm,midway] {\footnotesize\texttt{write x}};
 \end{tikzpicture}
 \end{framed}
 \caption{The generated code for the test program \texttt{x := 1 + 2; write
 \subsection*{Arrays}
 Maybe a useful addition to the WHILE-language would be arrays. This
 would allow us to generate more interesting WHILE-programs by
-translating BF*** programs into equivalent WHILE-code. Therefore in this
+translating BF*** programs into equivalent WHILE-code. Yeah! Therefore in this
 section let us have a look at how we can support the following three
 constructions
 \begin{itemize}
 \item \lstinline|new(arr[15000])|
 \item \lstinline|x := 3 + arr[3 + y]|
 \item \lstinline|arr[42 * n] := ...|
 \end{itemize}
 \noindent
 The first construct is for creating new arrays. In this instance the
 name of the array is \pcode{arr} and it can hold 15000 integers. We do
 not support ``dynamic'' arrays, that is the size of our arrays will
 always be fixed. The second construct is for referencing an array cell
 inside an arithmetic expression---we need to be able to look up the
 contents of an array at an index determined by an arithmetic expression.
 Similarly in the line below, we need to be able to update the content of
 an array at a calculated index.
 For creating a new array we can generate the following three JVM
 instructions:
 \begin{lstlisting}[mathescape,language=JVMIS]
 ldc number
 newarray int
 astore loc_var
 \end{lstlisting}
 \noindent
 First we need to put the size of the array onto the stack. The next
 section). The use of a local variable for each array allows us to have
 multiple arrays in a WHILE-program. For looking up an element in an
 array we can use the following JVM code
 \begin{lstlisting}[mathescape,language=JVMIS]
 aload loc_var
 $\textit{index\_aexp}$
 iaload
 \end{lstlisting}
 \noindent
 The first instruction loads the ``pointer'', or local variable, to the
 will be the index into the array we need. Finally we need to tell the
 JVM to load the corresponding element onto the stack. Updating an array
 at an index with a value is as follows.
 \begin{lstlisting}[mathescape,language=JVMIS]
 aload loc_var
 $\textit{index\_aexp}$
 $\textit{value\_aexp}$
 iastore
 \end{lstlisting}
 \noindent
 Again the first instruction loads the local variable of
 by an identifier and the brackets. There are two new rules for statements,
 one for creating an array and one for array assignment:
 \begin{plstx}[rhs style=, margin=2cm, one per line]
 : \meta{Stmt} ::=  \ldots
 | \texttt{new}(\meta{Id}\,[\,\meta{Num}\,])
 | \meta{Id}\,[\,\meta{E}\,]\,:=\,\meta{E}\\
 \end{plstx}
 With this in place we can turn back to the idea of creating
 WHILE-programs by translating BF-programs. This is a relatively easy
 case ']'  => "skip};"
 case _ => ""
 }
 \end{lstlisting}
 \noindent
 The idea behind the translation is that BF-programs operate on an array,
 called here \texttt{mem}. The BF-memory pointer into this array is
 represented as the variable \texttt{ptr}. As usual the BF-instructions
 \code{>} and \code{<} increase, respectively decrease, \texttt{ptr}. The
 instructions \code{+} and \code{-} update a cell in \texttt{mem}. In
 with writing out any array-content directly. Lines 7 and 8 are for
 translating BF-loops. Line 8 is interesting in the sense that we need to
 generate a \code{skip} instruction just before finishing with the
 closing \code{"\}"}. The reason is that we are rather pedantic about
 semicolons in our WHILE-grammar: the last command cannot have a
 semicolon---adding a \code{skip} works around this snag.
 Putting this all together and we can generate WHILE-programs with more
 than 15K JVM-instructions; run the compiled JVM code for such
 programs and marvel at the output\ldots\medskip
 BF-mandelbrot program on the JVM (after nearly 10 minutes of parsing the
 corresponding WHILE-program; the size of the resulting class file is
 around 32K---not too bad). The generation of the picture completes
 within 20 or so seconds. Try replicating this with an interpreter! The
 good point is that we now have a sufficiently complicated program in our
-WHILE-language in order to do some benchmarking. Which means we now face
+WHILE-language in order to do some benchmarking (your task!). Having done
-the question about what to do next\ldots
+this, we now face the question about what to do next in our compiler\ldots?
 \subsection*{Optimisations \& Co}
 Every compiler that deserves its name has to perform some optimisations
 on the code: if we put in the extra effort of writing a compiler for a
 in the class file. While this is a sensible strategy for ``large''
 constants like strings, it is a bit of overkill for small integers
 (which many integers will be when compiling a BF-program). To counter
 this ``waste'', the JVM has specific instructions for small integers,
 for example
 \begin{itemize}
 \item \instr{iconst_0},\ldots, \instr{iconst_5}
 \item \instr{bipush n}
 \end{itemize}
 also have no clue how the JVM is implemented.} This means when
 generating code for pushing constants onto the stack, we can use the
 following Scala helper-function
 \begin{lstlisting}[language=Scala]
 def compile_num(i: Int) =
 if (0 <= i && i <= 5) i"iconst_$i" else
 if (-128 <= i && i <= 127) i"bipush $i"
 else i"ldc $i"
 \end{lstlisting}
 \noindent
 It generates the more efficient instructions when pushing a small integer
 constant onto the stack. The default is \instr{ldc} for any other constants.
 The JVM also has such special instructions for
 loading and storing the first three local variables. The assumption is
 \hspace{5mm}unoptimised: & 33296 & 21 secs\\
 \hspace{5mm}optimised:   & 21787 & 16 secs\\
 \end{tabular}
 \end{center}
 \noindent
 Quite good! Such optimisations are called \emph{peephole optimisations},
 because they involve changing one or a small set of instructions into an
 equivalent set that has better performance.
 If you look careful at our generated code you will quickly find another
 source of inefficiency in programs like
 \begin{lstlisting}[mathescape,language=While]
 where our code first calculates the new result the for \texttt{x} on the
 stack, then pops off the result into a local variable, and after that
 loads the local variable back onto the stack for writing out a number.
 \begin{lstlisting}[mathescape,language=JVMIS]
 ...
 istore 0
 iload 0
 ...
 \end{lstlisting}
 \begin{lstlisting}[mathescape,language=While]
 new(arr[10]);
 arr[14] := 3 + arr[13]
 \end{lstlisting}
 \noindent
 Admittedly this is a contrived program, and probably not meant to be
 like this by any sane programmer, but it is supposed to make the
 following point: The program generates an array of size 10, and then
 tries to access the non-existing element at index 13 and even updating
 the element with index 14. Obviously this is baloney. Still, our
 this would be to rewrite the WHILE-programs and insert the necessary
 if-conditions for safely reading and writing arrays. Another way
 is to modify the code we generate.
 \begin{lstlisting}[mathescape,language=JVMIS2]
 $\textit{index\_aexp}$
 aload loc_var
 dup2
 arraylength
 if_icmple L1
 pop2
 iconst_0
 swap
 iaload
 L2:
 \end{lstlisting}
+\textbf{TBD}
 \begin{lstlisting}[mathescape,language=JVMIS2]
 $\textit{index\_aexp}$
 aload loc_var
 dup2
 arraylength
 if_icmple L1
 pop2
 goto L2
 \begin{tikzpicture}[every text node part/.style={align=left},
 stack/.style={rectangle split,rectangle split parts = 5,
 fill=black!20,draw,text width=1.6cm,line width=0.5mm}]
 \node (A)  {};
 \node[stack,right = 80pt] (0) at (A.east) {$\textit{index}$\nodepart{two} \ldots\phantom{l}};
 \node[stack,right = 60pt] (1) at (0.east)
 {array\nodepart{two}
 $\textit{index}$\nodepart{three} \ldots\phantom{l}};
 \node[stack,below = 40pt] (2) at (1.south)
 {array\nodepart{two}
 $\textit{index}$ \nodepart{three}
 array \nodepart{four}
 $\textit{index}$\nodepart{five} \ldots\phantom{l}};
 \node[stack,left = 90pt] (3) at (2.west)
 {array\_len\nodepart{two}
 $\textit{index}$ \nodepart{three}
 array \nodepart{four}
 $\textit{index}$\nodepart{five} \ldots\phantom{l}};
 \node[stack,below right of = 3,node distance = 130pt,rectangle split parts = 3] (4b) at (3.south)
 {array\nodepart{two}
 $\textit{index}$\nodepart{three} \ldots\phantom{l}};
 \node[stack,below left of = 3,node distance = 130pt,rectangle split parts = 3] (4a) at (3.south)
 {array\nodepart{two}
 $\textit{index}$\nodepart{three} \ldots\phantom{l}};
 \node[stack,below of = 4a,node distance = 70pt,rectangle split parts = 3] (5a) at (4a.south)
 {$\textit{index}$\nodepart{two}
 array\nodepart{three} \ldots\phantom{l}};
 \node[stack,below of = 5a,node distance = 60pt,rectangle split parts = 2] (6a) at (5a.south)
 {$\textit{array\_elem}$\nodepart{two} \ldots\phantom{l}};
 \node[stack,below of = 4b,node distance = 65pt,rectangle split parts = 2] (5b) at (4b.south)
 {\ldots\phantom{l}};
 \node[stack,below of = 5b,node distance = 60pt,rectangle split parts = 2] (6b) at (5b.south)
 {0\nodepart{two} \ldots\phantom{l}};
 \draw [|->,line width=2.5mm] (A) -- node [above,pos=0.45] {$\textit{index\_aexp}$} (0);
 \draw [->,line width=2.5mm] (0) -- node [above,pos=0.35] {\instr{aload}} (1);
 \draw [->,line width=2.5mm] (1) -- node [right,pos=0.35] {\instr{dup2}} (2);
 \draw [->,line width=2.5mm] (2) -- node [above,pos=0.40] {\instr{arraylength}} (3);
 \path[->,draw,line width=2.5mm]
 let \p1=(3.south), \p2=(4a.north) in (3.south) -- +(0,0.5*\y2-0.5*\y1) node [right,pos=0.50] {\instr{if_icmple}} -| (4a.north);
 \path[->,draw,line width=2.5mm]
 let \p1=(3.south), \p2=(4b.north) in (3.south) -- +(0,0.5*\y2-0.5*\y1) -| (4b.north);
 \draw [->,line width=2.5mm] (4a) -- node [right,pos=0.35] {\instr{swap}} (5a);
 \draw [->,line width=2.5mm] (4b) -- node [right,pos=0.35] {\instr{pop2}} (5b);
 \draw [->,line width=2.5mm] (5a) -- node [right,pos=0.35] {\instr{iaload}} (6a);
 \draw [->,line width=2.5mm] (5b) -- node [right,pos=0.35] {\instr{iconst_0}} (6b);
 \end{tikzpicture}
 \end{center}
 \end{figure}
 goto\_w problem solved for too large jumps
 \end{document}
 %%% Local Variables:
 %%% mode: latex
 %%% TeX-master: t
 %%% End:

changeset 960	c7009356ddd8
parent 943	5365ef60707e