# HG changeset patch # User Gilles Duboscq # Date 1305558725 -7200 # Node ID 9836845a75e690a7d8091198cd7884a9bb408901 # Parent 48496ba030c5bb6f977ecd09a404af5a2892c566# Parent 07aa0a31fffb3d3a7344932e0d12a15f95912173 Merge diff -r 48496ba030c5 -r 9836845a75e6 doc/design/graal_compiler.pdf Binary file doc/design/graal_compiler.pdf has changed diff -r 48496ba030c5 -r 9836845a75e6 doc/design/graal_compiler.tex --- a/doc/design/graal_compiler.tex Mon May 16 11:34:59 2011 +0200 +++ b/doc/design/graal_compiler.tex Mon May 16 17:12:05 2011 +0200 @@ -1,4 +1,5 @@ \documentclass[twocolumn]{svjour3} +\usepackage{listings} \usepackage[pdftex]{graphicx} \usepackage{environ} \usepackage{amsmath} @@ -119,6 +120,25 @@ \item Implementation of a prototype front-end for a different language, e.g., JavaScript. \end{itemize} +\section{Project Source Structure} +In order to support the goal of a modular compiler, the code will be divided into the following source code projects (as subprojects of \textbf{com.oracle.max.graal}). + +\begin{description} + \item[graph] contains the abstract node implementation, the graph implementation and all the associated tools and auxiliary classes. + \item[nodes] contains the implementation of known basic nodes (e.g., phi nodes, control flow nodes, \ldots). + Additional node classes should go into separate projects and be specializations of the known basic nodes. + \item[java] contains code for building graphs from Java bytecodes and Java-specific nodes. + \item[opt] contains optimizations such as global value numbering or conditional constant propagation. + \item[compiler] contains the compiler, including: + \begin{itemize} + \item Scheduling of the compilation phases. + \item Implementation of the \emph{compiler interface} (CI). + \item Implementation of the final compilation phase that produces the low-level representation. + \item Machine code creation, including debug info. + \end{itemize} +\end{description} + + \section{Graph} The \emph{intermediate representation}~(IR) of the compiler is designed as a directed graph. @@ -172,30 +192,109 @@ \label{fig:directions} \end{figure} -\subsection{Project Source Structure} -In order to support the goal of a modular compiler, the code will be divided into the following source code projects (as subprojects of \textbf{com.oracle.graal}). +\section{Control Flow} + +Control flow is managed in way where the predecessor node contains direct pointers to its successor nodes. +We reserve the term \textit{instruction} for nodes that are embedded in the control flow. +This is opposite to the approach taken in the server compiler, where control flow and data flow edges point in the same direction. +The advantage that we see in our approach is that there is no need for projection nodes in case of control flow splits. +An \texttt{If} instruction can directly point to its true and false successors without any intermediate nodes. +This makes the graph more compact and simplifies graph traversal. + +Listing \ref{lst:cfg2} shows an example Java program with an if statement where both paths do not contain any instruction with side effects. +The \texttt{If} instruction can directly point its true and false successors to a \texttt{Merge} instruction. +A \texttt{Phi} node that selects the appropriate value is appended to the \texttt{Merge} instruction. +The \texttt{Return} instruction then has a data dependency on the \texttt{Phi} node. + +\begin{lstlisting}[label=lst:cfg2, caption=Control flow in the graph, captionpos=b] +if (condition) { return 0; } +else { return 1; } +\end{lstlisting} + +\begin{figure}[h] + \centering +\begin{digraphenv}{scale=0.5}{cfg2} +\textnode{entry}{Entry} +\textnode{condition}{condition} +\textnode{const0}{0} +\textnode{const1}{1} +\nodesplit{if}{If} +\control{entry}{if} +\controllabel{if:succ1}{merge} +\controllabel{if:succ2}{merge} +\data{if}{condition} +\node{merge}{Merge} +\node{return}{Return} +\nodetri{phi}{Phi} +\datalabel{phi:in1}{merge} +\datalabel{phi:in2}{const0} +\datalabel{phi:in3}{const1} +\data{return}{phi} +\control{merge}{return} +\end{digraphenv} + \caption{A simple loop with two exits.} + \label{fig:exc1} +\end{figure} + +\section{Exceptions} +\label{sec:Exceptions} -\begin{description} - \item[graph] contains the abstract node implementation, the graph implementation and all the associated tools and auxiliary classes. - \item[nodes] contains the implementation of known basic nodes (e.g., phi nodes, control flow nodes, \ldots). - Additional node classes should go into separate projects and be specializations of the known basic nodes. - \item[java] contains code for building graphs from Java bytecodes and Java-specific nodes. - \item[opt] contains optimizations such as global value numbering or conditional constant propagation. - \item[compiler] contains the compiler, including: - \begin{itemize} - \item Scheduling of the compilation phases. - \item Implementation of the \emph{compiler interface} (CI). - \item Implementation of the final compilation phase that produces the low-level representation. - \item Machine code creation, including debug info. - \end{itemize} -\end{description} +We do not throw runtime exceptions (e.g., \texttt{IndexOutOf\-BoundsException}, \texttt{NullPointerException}, or \texttt{Out\-Of\-MemoryException}), but deoptimize instead. +This reduces the places in the compiled code where an exact bytecode location and debug information must be known. +Additionally, this greatly reduces the number of exception handler edges in the compiled code. +The main advantage of this technique is however, that we are free in moving around bounds checks, memory allocation, memory accesses with implicit null checks, etc. + +There are only two kinds of instruction that need explicit exception edges, because they are the only instructions that can throw exceptions in compiled code: \texttt{Throw} instructions and \texttt{Invoke} instructions. +They are modelled as instructions with an additional control flow continuation that points to an \texttt{ExceptionDispatch} instruction. +The exception dispatch instruction decides based on the type of the exception object whether the control should flow to the catch handler or to another exception dispatch. +If there is no catch handler in the currently compiled method, then the control flows into the \texttt{Unwind} instruction that handles the exception by forwarding it to the caller. +Listing \ref{lst:exc1} shows an example Java program with nested try blocks and Figure \ref{fig:exc1} shows the corresponding compiler graph. + +\begin{lstlisting}[label=lst:exc1, caption=Exception dispatch in the compiler graph, captionpos=b] +try { m1(); + try { m2(); + } catch(ExtendedException e) { ... } + m3(); + throw exception; +} catch(Exception e) { ... } +\end{lstlisting} + +\begin{figure}[h] + \centering +\begin{digraphenv}{scale=0.5}{exc1} +\textnode{entry}{Entry} +\textnode{catch1}{catch1} +\textnode{catch2}{catch2} +\nodesplit{m1}{Invoke m1} +\nodesplit{m2}{Invoke m2} +\nodesplit{m3}{Invoke m3} +\nodesplit{dispatch1}{ExceptionDispatch} +\nodesplit{dispatch2}{ExceptionDispatch} +\node{throw}{Throw} +\node{unwind}{Unwind} +\control{entry}{m1} +\controllabel{m1:succ1}{m2} +\controllabel{m1:succ2}{dispatch2} +\controllabel{m2:succ1}{m3} +\controllabel{m2:succ2}{dispatch1} +\controllabel{m3:succ1}{throw} +\controllabel{m3:succ2}{dispatch2} +\control{throw}{dispatch2} +\controllabel{dispatch1:succ2}{catch1} +\controllabel{dispatch1:succ1}{dispatch2} +\controllabel{dispatch2:succ2}{catch2} +\controllabel{dispatch2:succ1}{unwind} +\end{digraphenv} + \caption{A simple loop with two exits.} + \label{fig:exc1} +\end{figure} \section{Loops} \label{sec:loops} Loops form a first-class construct in the IR that is expressed by specialized IR nodes during all optimization phases. We only compile methods with a control flow where every loop has a single entry point. -This entry point is a \nodename{LoopBegin} node. -This node is connected to a \nodename{LoopEnd} node that merges all control flow paths that do not exit the loop. +This entry point is a \nodename{LoopBegin} instruction. +This instruction is connected to a \nodename{LoopEnd} instruction that merges all control flow paths that do not exit the loop. The edge between the \nodename{LoopBegin} and the \nodename{LoopEnd} is the backedge of the loop. It goes from the beginning to the end in order to make the graph acyclic. An algorithm that traverses the control flow has to explicitely decide whether it wants to incorporate backedges (i.e., special case of the treatment of \nodename{LoopEnd}) or ignore them. @@ -225,9 +324,14 @@ \subsection{Loop Phis} Data flow in loops is modelled with special phi nodes at the beginning and the end of the loop. -The \nodename{LoopEnd} node merges every value that flows into the next loop iteration in associated \nodename{LoopEndPhi} nodes. +The \nodename{LoopEnd} instruction merges every value that flows into the next loop iteration in associated \nodename{LoopEndPhi} nodes. A corresponding \nodename{LoopBeginPhi} node that is associated with the loop header has a control flow dependency on the \nodename{LoopEndPhi} node. -Figure \ref{fig:loop2} shows how a simple counting loop is modelled in the graph. +Listing \ref{lst:loop} shows a simple counting loop that is used as an example in the rest of this section. +Figure \ref{fig:loop2} shows how the loop is modelled immediately after building the graph. + +\begin{lstlisting}[label=lst:loop, caption=Loop example, captionpos=b] +for(int i=0; i #2:predecessors:n [color=red];} \newcommand{\controllabel}[2]{#1:s -> #2:predecessors:n [color=red];}