% $Id: recovery.tex,v 1.12 1997/02/01 20:16:15 cierniak Exp $


\section{Recovering high-level structure}
\label{sec:recovery}


One of the important features of our compiler is the ability to
recover high-level structure of a source Java program given its
bytecode representation.  Section~\ref{sec:impl} explains why it is
necessary.  In this section we discuss the process of that recovery as
performed by our bytecode to JavaIR front-end.  We start by giving a
simple example of a bytecode sequence and the recovered source code.
Note that our front-end actually recovers an internal representation
which is not directly printable.  However, since for our applications
there is a straightforward mapping between the JavaIR described in
Section~\ref{sec:javair} and a Java source, we simply show the
recovered source code.  The rest of this section shows a selection of
more interesting problems which must be addressed for the recovery to
take place.  The problem of high-level structure recovery is very
similar to the problem of decompilation.  
Previous work on
decompilation addressed this issue primarily for reverse-engineering
reasons.
%
While our goal is different (we want to recover the high-level
structure to enable some compiler optimizations), we borrow from
existing decompilation techniques in our design.
%
Existence of many decompilation tools shows that high-level structure
recovery from low level code is possible.  Indeed there exists a
decompiler for Java~\cite{Mocha-1996} which given a {\tt class} file
will produce its representation as Java source.  Another interesting
decompiler is described in~\cite{Cifuentes-LNCS-1996}.
%
In our work, we have identified the
following problems.
\begin{itemize}
\item Converting a stack-based code without branches to a syntax tree.
  This is generally straightforward.  The only problem that required
  extra attention was the use of temporary variables during the
  evaluation of a complex expression on the stack.  Dataflow analysis
  is needed to ensure that flow dependencies are not violated.
  Section~\ref{sec:recovery:expr} discusses this issue.
\item Identifying types of local variables.  Again, dataflow analysis
  is used to disambiguate types of variables.  The disambiguation may
  be needed due to one of the two reasons: the same variable may be
  used to store values of different types or assignments which are
  allowed in the bytecode must be changed to narrow down expression
  types (e.g., Boolean values are represented internally as integers,
  but in JavaIR, we want to represent them as Boolean values).
%  Section~\ref{sec:recovery:types} presents more details of our
%  solution.
\item Converting short-circuit operators into expression form.  This
  is performed by a flow patterns recognition mechanism similar to the
  one used in~\cite{Cifuentes-LNCS-1996}.
  Section~\ref{sec:recovery:short:circuit} contains further
  discussion.
\item Converting branches to high-level statements (loops, conditional
  statements, {\tt break}, and {\tt continue} statements.  We have
  based our approach on the algorithm presented
  in~\cite{Baker-JACM-1977}.  Some modifications to the algorithm were
  necessary to more completely eliminate branches.
  Section~\ref{sec:recovery:goto} show our approach.
\end{itemize}
Our general approach is to first recover simple expressions and
statements within basic blocks (bytecode sequences without branches).
This process creates a {\em control flow graph\/} (CFG --- see
Section~\ref{sec:recovery:short:circuit} for a simple example) with
high-level constructs in its nodes.  Then we convert CFG edges to
structured control flow constructs using techniques described in
Sections~\ref{sec:recovery:short:circuit} and~\ref{sec:recovery:goto}.


\subsection{An example}
\label{sec:recovery:example}

Consider the following code fragment of a disassembled {\tt class}
file.  It is not apparent what this sequence of bytecodes does.
%Consider the following code fragment of a {\tt class} file as
%disassembled by {\tt javap}~\cite{JDK-1.0.2-1996}.  It is not apparent
%what this sequence of bytecodes does.
\begin{verbatim}
   0 iload_1
   1 iconst_1
   2 if_icmpeq 10
   5 iload_1
   6 iconst_3
   7 if_icmpne 18
  10 aload_0
  11 iconst_1
  12 putfield #4 <Field cond1.i I>
  15 goto 23
  18 aload_0
  19 iconst_2
  20 putfield #4 <Field cond1.i I>
  23 aload_0
  24 dup
  25 getfield #4 <Field cond1.i I>
  28 iconst_1
  29 iadd
  30 putfield #4 <Field cond1.i I>
\end{verbatim}
One can of course understand this code with some effort.
Most traditional compiler optimizations can operate on an intermediate
representation which closely corresponds to the bytecode.

This paper deals with compiler algorithms which are best expressed in
terms of high-level constructs like a for-loop or a multi-dimensional
array reference.  Neither of those two constructs is explicit in the
bytecode which implements them with low level operations.  In many
cases it is however possible to recover a representation of a method
with those high-level constructs.

Consider again the above sequence of Java VM instructions.  Our
compiler parses it and generates an equivalent JavaIR representation
which can be printed as the following Java source fragment (as
described earlier the internal JavaIR representation is not directly
printable since it is a collection of Java objects with references to
each other).

\begin{verbatim}
  if(((a1 == 1) || (a1 == 3))) {
     this.i = 1;
  } else {
     this.i = 2;
  } //if
  this.i = (this.i + 1);
\end{verbatim}

Note that {\tt a1} is used to represent the first argument to the
method containing this sequence of bytecodes.  The identifier used by
the programmer in the source cannot be recovered.  
%This makes a
%difference only if we intend to decompile the source for human use.
%For the compiler the identifier is not relevant.  What is important is
%the type of the parameter and this can be easily recovered from the
%bytecode representation of a class.




\subsection{Extracting expressions and simple statements}
\label{sec:recovery:expr}

The design of Java bytecodes makes it relatively easy to recover
expressions and simple statements (assignments and method
invocations).  Recovering statements which change the control flow
requires more work since their implementation in the bytecodes uses
branches which we do not want to use in JavaIR.  We show in
Sections~\ref{sec:recovery:short:circuit} and~\ref{sec:recovery:goto}
how to convert branches to structured control flow constructs.

To convert a sequence of bytecodes contained in a basic block to
high-level expressions and statements, we symbolically execute each
basic block using a temporary stack to emulate a Java virtual machine.
For instance the following basic block from the example shown in 
Section~\ref{sec:recovery:example}
\begin{verbatim}
  23 aload_0
  24 dup
  25 getfield #4 <Field cond1.i I>
  28 iconst_1
  29 iadd
  30 putfield #4 <Field cond1.i I>
\end{verbatim}
is converted to
\begin{verbatim}
  this.i = (this.i + 1);
\end{verbatim}
To see how the symbolic emulation works, consider the instruction {\tt
  iadd} above.  Processing of the previous instructions have placed
two references at the top of the stack, one for the expression
representing the constant 1 and another one for the expression {\tt
  this.i}.  Our front-end creates a new JavaIR object for integer
addition and initializes its two operand fields to the two values from
the top of the stack which are being removed from the stack.  The new
object is being pushed on the top of the stack.

This approach generally works for the application we looked at.  The
only interesting problem that must be solved is caused by using the
stack for storage of variable and field values which have been
overwritten during a calculation of a complex stack expression.
Consider the following example
\begin{verbatim}
aload_0                             z
getfield #4 <Field cond1.i I>       z
aload_0                           x
iconst_1                          x
putfield #4 <Field cond1.i I>     x
aload_0                             z
getfield #4 <Field cond1.i I>       z
iadd                                z
aload_0                             z
putfield #5 <Field cond1.j I>       z
\end{verbatim}
The sequence marked with {\tt x} is converted to
\begin{verbatim}
  this.i = 1;
\end{verbatim}
and the sequence marked with {\tt z} is converted to
\begin{verbatim}
  this.j = (this.i + this.i);
\end{verbatim}
but the first occurrence of {\tt this.i} on the right-hand side of the
second assignment should have the value that the field {\tt i} had
{\em before\/} the assignment of 1, and the second occurrence should
have the value that the field {\tt i} had {\em after\/} the assignment
of 1.  Our solution keeps track of the flow of values and when
necessary creates temporary variables to hold the values that the Java
VM stores on the stack.  For the example above, we recover a sequence
corresponding to the following source fragment:
\begin{verbatim}
  tmp = this.i;
  this.i = 1;
  this.j = (tmp + this.i);
\end{verbatim}




%\SubSection{Type identification}
%\label{sec:recovery:types}

%Another problem which requires dataflow analysis is caused by re-using
%the same local variable for values of different types and 




\subsection{Short-circuit operators}
\label{sec:recovery:short:circuit}

Consider again the bytecode sequence shown in
Section~\ref{sec:recovery:example}.  An alternative representation
called a control flow graph (CFG) is shown in
Figure~\ref{fig:short:circuit}.
%0..4  ---> 5,10
%5..9  ---> 10,18
%10..17 --->23
%18..22 --->23
%23..32
\begin{figure}[hbt]
%  \centerline{\psfig{figure=ex1.eps,height=2.2in,width=1.6in}}
  \centerline{\psfig{figure=shortcirc1.eps,height=2.2in,width=2.4in}}
  \caption{A control flow graph for a short-circuit operator}
  \label{fig:short:circuit}
\end{figure}
A CFG contains a node for every straight-line code sequence (a {\em
  basic block\/}) and an edge for every branch (a conditional branch
results in two edges, an unconditional branch corresponds to a single
edge).  Nodes in Figure~\ref{fig:short:circuit} are labeled with the
numbers corresponding to the address of the first instruction of every
basic block.  Labels on the edges mark ``true'' and ``false''
branches.

Our recovery mechanism recognizes patterns in the CFG corresponding
to different short-circuit operators in the manner similar to the
technique described in~\cite{Cifuentes-LNCS-1996}

\subsection{Goto elimination}
\label{sec:recovery:goto}

%We have implemented the algorithm described in~\cite{Baker-JACM-1977}.
%That algorithm fails for some control flow graphs and leaves the
%branches in place.  We have considered using one of the
%goto-elimination algorithms which are guaranteed to eliminate all
%branches, but we have decided against it, since all such algorithms
%eliminate goto's by means which do not make the code any better
%structured than the CFG for our purposes (in those algorithms branches
%are eliminated by inserting new code or code replication).

%We have designed a set of heuristics which will eliminate all branches
%while not introducing any new code.  Our method is not general, but we
%verified it on a range of application of interest.  If our structuring
%algorithm fails, we simply do not optimizes the corresponding code.
%Our goto-elimination heuristics have worked for all applications of
%interest to us.


%\subsubsection{Goto elimination}
%\label{sec:recovery:alg:goto}

This step is based on the algorithm described
in~\cite{Baker-JACM-1977}.
We have extended this algorithm to eliminate branches in some cases in
which the original algorithm failed.  Nevertheless, for some CFG's we
are not able to completely eliminate branches.  For reducible flow
graphs, it is always possible to completely eliminate branches, but
sometimes doing requires inserting new loop statements or duplicating
code.  While those approaches would be acceptable if our goal was to
recover legal Java source for the widest possible range of {\tt class}
files, adding new loops or duplicating code would not help us in any
high-level compiler optimizations.  Therefore, we decide to allow
branches in JavaIR at the cost of not being able to optimize those
programs with the current, preliminary version of Java (since our
compilation process involves compiling Java source generated from
JavaIR).  Branches will not however be a problem in the JIT version of
Briki which will be the next step of our research.

\begin{enumerate}
\item Collapse short-circuit operators.
\item Find natural loops.
\item Insert repeat nodes.
%\item Find dominators.
%%\item Push returns.
%\item Find heads.
%\item Find immediate dominators.
%\item Find follow sets.
\item Find dominators, heads and follow sets.
\item Expand loops.
\item Call {\tt getform}.
\item Call {\tt addbranch}.
\item Clean the graph (push loop termination conditions into loop
  headers, unify types, etc.)
\end{enumerate}



\subsection{Difficulties in structure recovery}
\label{sec:recovery:problems}

%It is important to note that although currently we recover the Java
%source for a given {\tt class} file during our
%optimization process, that step will not be present in the final
%version of our compiler.

The  current implementation of Briki parses a {\tt class} file,
represents it in JavaIR, performs the desired optimizations and prints
the optimized source to a file.  We later use a standard compiler to
convert the resulting source file to the bytecode form.  The
off-line process was chosen by us for the ease of debugging and more
flexibility experimenting with new optimization techniques.
Ultimately, we want to build a JIT version of Briki which would
perform the same optimizations on JavaIR, but it would directly
generate machine code from the optimized JavaIR rather than generating
the source first.

For the {\tt class} files we looked at so far, it is possible to
efficiently recover a JavaIR form of those applications which
can be printed out as legal Java source.  It is however possible to
create {\tt class} files for which this process would be expensive or
would not yield any benefit for our optimizations techniques.  It is
important to stress here that for our optimizations we are interested
in recovering a {\em high-level structure}.  Some bytecode sequences
do not have such structure and although it would be possible to for
instance eliminate all branches and generate legal Java source for such
programs, the {\em structure\/} created by the branch-elimination
process would be artificial and would not enable any additional
high-level optimizations.

We also note that it is possible that a given application distributed
in the {\tt class} file form would not be representable as legal Java
source (one such example is given in Section 13.4.6
of~\cite{Java-Language-Specification-1996}).  While this would cause
problems for the current implementation of Briki, it would not affect
the JIT version of our compiler.






\subsection{Recovery algorithm}
\label{sec:recovery:alg}


\subsubsection{High-level overview}
\label{sec:recovery:alg:overview}


We sketch here the process of high-level structure recovery.  We
assume that all data structures for classes and class members have
been initialized.

The algorithm performs the following steps for every non-native
method.

\begin{enumerate}
\item Scan all opcodes and mark basic blocks.
\item Parse the exception table (see Section 4.7.4
  of~\cite{Java-VM-1996}) to mark portions of the bytecode stream
  handled by specific handlers and to mark the handlers themselves.
\item Create a control flow graph (CFG) for the method.  The CFG has
  at least one {\em entry node\/} --- for the main entry to the method
  --- but may also contain additional entry nodes for every exception
  handler of that method.
\item Structure the CFG by identifying short-circuit operators and
  creating high-level control flow nodes as described in
  Sections~\ref{sec:recovery:short:circuit} and
  \ref{sec:recovery:goto} accordingly.
\item Starting from the entry nodes, visit all nodes of the CFG and
  interpret the code of each of them.  This step creates the JavaIR
  nodes for every basic block.  Every node of the structured CFG has
  two lists of JavaIR nodes: statements and expressions.  The
  expressions are needed for values passed on the Java VM stack across
  basic block boundaries.  The values left on the stack at the end of
  a basic block are being used in the successor nodes as initial stack
  content.
\item The information extracted in the previous two steps is used to
  create the complete JavaIR form for this method.
\end{enumerate}


