truffle: doc/design/graal_compiler.tex comparison

comparison doc/design/graal_compiler.tex @ 2597:08cda6637103

More doc + conclusion.

author	Thomas Wuerthinger <thomas@wuerthinger.net>
date	Thu, 05 May 2011 15:55:11 +0200
parents	dac9bcc6bd4a
children	e4395464810e

comparison

equal deleted inserted replaced

-:dac9bcc6bd4a
+:08cda6637103
 This enables front-ends for different languages (e.g., Ruby) to provide their own graph.
 Also, there is no dependency on a specific back-end, but the output of the compiler is a graph that can then be converted to a different representation in a final compiler phase.
 \end{description}
 \section{Milestones}
+\label{sec:mile}
 The compiler is developed starting from the current C1X source code base.
 This helps us testing the compiler at every intermediate development step on a variety of Java benchmarks.
 We define the following development milestones and when they are considered achieved:
 \begin{description}
 \item[M1:] We have a fully working Graal~VM version with a stripped down C1X compiler that does not perform any optimizations.
 \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 different languages, e.g., JavaScript.
 \end{itemize}
-\section{Implementation}
+\section{Graph}
-\subsection{Nodes and Graphs}
+The \emph{intermediate representation}~(IR) of the compiler is designed as a directed graph.
-The most important aspect of a compiler is the data structure that holds information about an executable piece of code, called \emph{intermediate representation}~(IR).
+A 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.
-The IR used in the compiler was designed in such a way as to allow for extensive optimizations, easy traversal, compact storage and efficient processing.
+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.
-\subsubsection{The Graph Data Structure}
+The nodes of the graph have the following properties:
 \begin{itemize}
-\item A graph deals out ids for new nodes and can be queried for the node corresponding to a given id.
+\item Each node is always associated with a single graph and this association is immutable.
-\item 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.
+\item Each node has an immutable id that is unique within its associated graph.
-\end{itemize}
-\subsubsection{The Node Data Structure}
-\begin{itemize}
-\item Each node is always associated with a graph.
-\item Each node has an immutable id which is unique within its associated graph.
-\item Nodes represent either operations on values or control flow operations.
 \item Nodes can have a data dependency, which means that one node requires the result of some other node as its input. The fact that the result of the first node needs to be computed before the second node can be executed introduces a partial order to the set of nodes.
-\item Nodes can have a control flow dependency, which means that the execution of one node depends on some other node. This includes conditional execution, memory access serialization and other reasons, and again introduces a partial order to the set of nodes.
+\item Nodes can have a control flow dependency, which means that the execution of one node will be followed by the execution of another node. This includes conditional execution, memory access serialization and other reasons, and again introduces a partial order to the set of nodes.
 \item Nodes can only have data and control dependencies to nodes which belong to the same graph.
-\item Control dependencies and data dependencies each represent a \emph{directed acyclic graph} (DAG) on the same set of nodes. This means that data dependencies always point upwards, and control dependencies always point downwards. Situations that are normally incur cycles (like loops) are represented by special nodes (like LoopEnd).
+\item Control dependencies and data dependencies each represent a \emph{directed acyclic graph} (DAG) on the same set of nodes. This means that data dependencies always point upwards, and control dependencies always point downwards. Situations that are normally incur cycles (like loops) are represented by special nodes (see Section~\ref{sec:loops}).
-	\item Ordering between nodes is specified only to the extent which is required to correctly express the semantics of a given program. Some compilers always maintain a complete order for all nodes (called \emph{scheduling}), which impedes advanced optimizations. For algorithms that require a fixed ordering of nodes, a temporary schedule can always be generated.
+	\item Ordering between nodes is specified only to the extent which is required to correctly express the semantics of a given program. This gives the compiler flexibility for the possible scheduling of a node and therefore wriggle room for optimizations. For algorithms that require a fixed ordering of nodes, a temporary schedule can always be generated.
-\item Both data and control dependencies can be traversed in both directions, so that each node can be traversed in four directions:
+\item Both data and control dependencies can be traversed in both directions, so that each node can be traversed in four directions (see Figure~\ref{fig:directions}):
 \begin{itemize}
 \item \emph{inputs} are all nodes that this node has data dependencies on.
 \item \emph{usages} are all nodes that have data dependencies on this node, this is regarded as the inverse of inputs.
 \item \emph{successors} are all nodes that have a control dependency on this node.
 \item \emph{predecessors} are all nodes that this node has control dependencies on, this is regarded as the inverse of successors.
 \end{itemize}
 \item Only inputs and successors can be changed, and changes to them will update the usages and predecessors.
-\item The Node class needs to provide facilities for subclasses to perform actions upon cloning, dependency changes, etc.
+\item Every node must be able to support cloning and serialization.
-\item Inlining should always be performed as a combination of two graphs.
+\item Inlining should always be performed as embedding one graph into another graph.
 \item Nodes cannot be reassigned to another graph, they are cloned instead.
+\item The edges of a node also define \textit{happens-before} and \textit{happens-after} relationships as shown in Figure~\ref{fig:directions}.
 \end{itemize}
-\subsection{Loops}
+\begin{figure}[h]
+\label{fig:directions}
+\centering
+\begin{digraphenv}{scale=0.5}{graphdirections}
+\node{node1}{Node}
+\textnode{inputs}{inputs}
+\textnode{usages}{usages}
+\textnode{successors}{successors}
+\textnode{predecessors}{predecessors}
+\data{node1}{inputs}
+\control{node1}{successors}
+\data{usages}{node1}
+\control{predecessors}{node1}
+\node{node2}{Node}
+\textnode{before}{happens before}
+\textnode{after}{happens after}
+\data{node2}{before}
+\control{node2}{after}
+\data{after}{node2}
+\control{before}{node2}
+\end{digraphenv}
+\caption{A node and its edges.}
+\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}).
+\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 seperate 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 Schedules the compilation phases.
+\item Implementation of the \emph{compiler interface} (CI).
+\item Implements the final compilation phase that produces the low-level representation.
+\item Machine code creation, including debug info.
+\end{itemize}
+\end{description}
+\section{Loops}
 \label{sec:loops}
 Loops form a first-class construct in the IR that is expressed in specialized IR nodes during all optimization phases.
 We only compile methods with a control flow where every loop has only one 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.
 \data{Vector}{n}
 \end{digraphenv}
 \caption{Graph after bounded loop transformation.}
 \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{Frame States}
-\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 seperate 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 Schedules the compilation phases.
-\item Implementation of the \emph{compiler interface} (CI).
-\item Implements the final compilation phase that produces the low-level representation.
-\item Machine code creation, including debug info.
-\end{itemize}
-\end{description}
-\subsection{Frame States}
 A frame state captures the state of the program in terms of the Java bytecode specification (i.e., the values of the local variables, the operand stack, and the locked monitors).
 Every deoptimization point needs a valid frame state.
 A frame state is valid as long as the program performs only actions that can safely be reexecuted (e.g., operations on local variables, loads, etc.).
 Thus, frame states need only be generated for bytecodes that cannot be reexecuted:
 \controllabel{store2:succ2}{fs2}
 \end{digraphenv}
 \caption{Simple example using two frame states.}
 \end{figure}
-FrameStates also have data dependencies on the contents of the state: the local variables and the expression stack.
+Frame states also have data dependencies on the contents of the state: the local variables and the expression stack.
 \subsection{Traps}
 A trap node is a node that deoptimizes based on a conditional expression.
 Trap nodes are not fixed to a certain frame state node, they can move around freely and will always use the correct frame state.
 The node that is guarded by the deoptimization has a data dependency on the trap, and the trap in turn has a data dependency on the condition and on the most distant node that is postdominated by the guarded node.
 The trap is now anchored to the most distant node of which the If was a postdominator.}
 \end{figure}
 At some point during the compilation, trap nodes need to be fixed, which means that appropriate data and control dependencies will be inserted so that they cannot move outside the scope of the associated frame state.
 This will generate deoptimization-free zones that can be targeted by the most aggressive optimizations.
-A simple algorithm for this removal of FrameStates would be to move all traps as far upwards as possible.
+A simple algorithm for this removal of frame states would be to move all traps as far upwards as possible.
+Multiple traps with the same condition and anchor can be merged:
-Multiple Traps with the same condition and anchor can be merged:
 \begin{figure}[h]
 \label{fig:trap3}
 \centering
 \begin{digraphenv}{scale=0.5}{trap3}
 \datalabel{trap:in2}{cmpnull}
 \datalabel{load2:in1}{trap}
 \datalabel{load1:in1}{trap}
 \datalabel{trap:in1}{split2}
 \end{digraphenv}
-\caption{Two loads guarded by the same Trap.}
+\caption{Two loads guarded by the same trap.}
 \end{figure}
-Also, if two Traps that are anchored to the true and false branch of the same If have the same condition, they can be merged, so that the resulting Trap is anchored at the most distant node of which the If is a postdominator.
+Also, if two traps that are anchored to the true and false branch of the same \texttt{If} node have the same condition, they can be merged, so that the resulting trap is anchored at the most distant node of which the \texttt{If} node is a postdominator.
-\subsection{Graphical Representation}
+\section{Conclusions}
-The graphs in this document use the following node layout:
+This document sketched the strategy for the Graph compiler.
+We already reached M1 (as defined in Section~\ref{sec:mile}) and have the following plans for M2 to M4:
-\begin{digraphenv}{scale=0.5}{graphrep1}
+\begin{description}
-\node{node1}{nop}
+\item[M2:] June 30th, 2011
-\nodebi{node2}{+}
+\item[M3:] August 15th, 2011
-\nodetri{node3}{phi}
+\item[M4:] September 30th, 2011
-\nodesplit{node4}{if}
+\end{description}
-\end{digraphenv}
+After we reached M4, we want to create a new project road map that further improves the Graal compiler with respect to its two main goals: Modularity and peak performance.
-Red arrows always represents control dependencies, while black arrows represent data dependencies:
-\begin{digraphenv}{scale=0.5}{graphrep2}
-\node{a}{a}
-\node{b}{b}
-\nodesplit{if}{if}
-\node{nop}{nop}
-\nodebi{add}{+}
-\controllabel{if:succ1}{nop}
-\controllabel{if:succ2}{add}
-\datalabel{add:in1}{a}
-\datalabel{add:in2}{b}
-\end{digraphenv}
 \end{document}

Mercurial > hg > truffle

comparison doc/design/graal_compiler.tex @ 2597:08cda6637103