truffle: doc/design/graal_compiler.tex comparison

comparison doc/design/graal_compiler.tex @ 2678:b9b0a0aa7ee8

Added addition sections on control flow and exceptions.

author	Thomas Wuerthinger <thomas@wuerthinger.net>
date	Mon, 16 May 2011 14:05:15 +0200
parents	1586b1b56f0c
children	07aa0a31fffb

comparison

equal deleted inserted replaced

-:0ea5f12e873a
+:b9b0a0aa7ee8
 \documentclass[twocolumn]{svjour3}
+\usepackage{listings}
 \usepackage[pdftex]{graphicx}
 \usepackage{environ}
 \usepackage{amsmath}
 \usepackage{amsfonts}
 \usepackage[english]{babel}
 \item Removal of the XIR template mechanism and replacement with a snippet mechanism that works with the compiler graph.
 \item Improvements for peak performance (loop optimizations, escape analysis, bounds check elimination, processing additional interpreter runtime feedback).
 \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.
 The graph deals out ids for new nodes and can be queried for the node corresponding to a given id as well as for an unordered list of nodes of the graph.
 Graphs can manage side data structures, which will be automatically invalidated and lazily recomputed whenever the graph changes. Examples for side data structures are dominator trees and temporary schedules. These side data structures will usually be understood by more than one optimization.
 \end{digraphenv}
 \caption{A node and its edges.}
 \label{fig:directions}
 \end{figure}
-\subsection{Project Source Structure}
+\section{Control Flow}
-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}).
+Control flow is managed in way where the predecessor node contains direct pointers to its successor nodes.
-\begin{description}
+This is opposite to the approach taken in the server compiler, where control flow and data flow edges point in the same direction.
-\item[graph] contains the abstract node implementation, the graph implementation and all the associated tools and auxiliary classes.
+The advantage that we see in our approach is that there is no need for projection nodes in case of control flow splits.
-\item[nodes] contains the implementation of known basic nodes (e.g., phi nodes, control flow nodes, \ldots).
+An \texttt{If} node can directly point to its true and false successors without any intermediate nodes.
-				 Additional node classes should go into separate projects and be specializations of the known basic nodes.
+This makes the graph more compact and simplifies graph traversal.
-\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.
+Listing \ref{lst:cfg2} shows an example Java program with an if statement where both paths do not contain any instruction with side effects.
-\item[compiler] contains the compiler, including:
+The \texttt{If} instruction can directly point its true and false successors to a \texttt{Merge} node.
-\begin{itemize}
+A \texttt{Phi} node that selects the appropriate value is appended to the \texttt{Merge} node.
-\item Scheduling of the compilation phases.
+The \texttt{Return} instruction then has a data dependency on the \texttt{Phi} node.
-\item Implementation of the \emph{compiler interface} (CI).
-\item Implementation of the final compilation phase that produces the low-level representation.
+\begin{lstlisting}[label=lst:cfg2, caption=Control flow in the graph, captionpos=b]
-\item Machine code creation, including debug info.
+if (condition) { return 0; }
-\end{itemize}
+else { return 1; }
-\end{description}
+\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}
+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.
 \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.
 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<n; ++i) { }
+\end{lstlisting}
 \begin{figure}[h]
 \centering
 \begin{digraphenv}{scale=0.5}{layout2}
 \textnode{BeforeLoop}{Loop entry}

Mercurial > hg > truffle

comparison doc/design/graal_compiler.tex @ 2678:b9b0a0aa7ee8