truffle: graal/com.oracle.max.graal.doc.initial/graal

comparison graal/com.oracle.max.graal.doc.initial/graal_compiler.tex @ 2896:5d4aa5672d3d

Small fix to design document.

author	Thomas Wuerthinger <thomas@wuerthinger.net>
date	Wed, 08 Jun 2011 14:50:07 +0200
parents	5005a5607506
children	4db4e8cb6bd6

comparison

equal deleted inserted replaced

-:5fd2b31f50ee
+:5d4aa5672d3d
 \newcommand\TODO[1]{\mynote{TODO}{#1}}
 \newcommand\cw[1]{\mynote{CW}{#1}}
 \newcommand\ls[1]{\mynote{LS}{#1}}
 \newcommand\nodename[1]{\texttt{#1}}
+\hyphenpenalty=0
+\doublehyphendemerits=0
+\finalhyphendemerits=0
+\clubpenalty10000
+\widowpenalty10000
 \smartqed  % flush right qed marks, e.g. at end of proof
 \journalname{Graal Compiler Design}
 \item Only inputs and successors can be changed, and changes to them will update the usages and predecessors.
 \item Every node must be able to support cloning and serialization.
 \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}
-\begin{figure}[h]
+\begin{figure}[ht]
 \centering
 \begin{digraphenv}{scale=0.5}{graphdirections}
 \node{node1}{Node}
 \textnode{inputs}{inputs}
 \textnode{usages}{usages}
 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.
+Figure~\ref{fig:loopexits} shows the corresponding compiler graph.
 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]
+\begin{figure}[ht]
 \centering
 \begin{digraphenv}{scale=0.5}{cfg2}
 \textnode{entry}{Entry}
 \textnode{condition}{condition}
 \textnode{const0}{0}
 \datalabel{phi:in3}{const1}
 \data{return}{phi}
 \control{merge}{return}
 \end{digraphenv}
 \caption{A simple loop with two exits.}
-\label{fig:exc1}
+\label{fig:loopexits}
 \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.
+We do not throw runtime exceptions (e.g., \texttt{IndexOutOf\-BoundsException}, \texttt{Null\-Pointer\-Exception}, or \texttt{Out\-Of\-Memory\-Exception}), 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.
 m3();
 throw exception;
 } catch(Exception e) { ... }
 \end{lstlisting}
-\begin{figure}[h]
+\begin{figure}[ht]
 \centering
 \begin{digraphenv}{scale=0.5}{exc1}
 \textnode{entry}{Entry}
 \textnode{catch1}{catch1}
 \textnode{catch2}{catch2}
 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.
 Figure \ref{fig:loop1} shows a simple example with a loop with a single entry and two exits.
-\begin{figure}[h]
+\begin{figure}[ht]
 \centering
 \begin{digraphenv}{scale=0.5}{layout1}
 \textnode{BeforeLoop}{Loop entry}
 \textnode{Exit1}{First loop exit}
 \textnode{Exit2}{Second loop exit}
 \begin{lstlisting}[label=lst:loop, caption=Loop example that counts from 0 to n-1., captionpos=b]
 for(int i=0; i<n; ++i) { }
 \end{lstlisting}
-\begin{figure}[h]
+\begin{figure}[ht]
 \centering
 \begin{digraphenv}{scale=0.5}{layout2}
 \textnode{BeforeLoop}{Loop entry}
 \textnode{Exit}{Loop exit}
 \textnode{n}{n}
 The compiler is capable of recognizing variables that are only increased within a loop.
 A potential overflow of such a variable is prohibited with a guard before the loop (this is not necessary in this example, because the loop variable cannot overflow).
 Figure \ref{fig:loop3} shows the compiler graph of the example loop after the loop counter transformation.
-\begin{figure}[h]
+\begin{figure}[ht]
 \centering
 \begin{digraphenv}{scale=0.5}{layout3}
 \textnode{BeforeLoop}{Loop entry}
 \textnode{Exit}{Loop exit}
 \textnode{n}{n}
 The total number of iterations always denotes the number of full iterations of the loop with the control flowing from the loop begin to the loop end.
 If the total number of iterations is reached, the loop is exited directly from the loop header.
 In the example, we can infer from the loop exit with the comparison on the loop counter that the total number of iterations of the loop is limited to n.
 Figure \ref{fig:loop4} shows the compiler graph of the example loop after the bounded loop transformation.
-\begin{figure}[h]
+\begin{figure}[ht]
 \centering
 \begin{digraphenv}{scale=0.5}{layout4}
 \textnode{BeforeLoop}{Loop entry}
 \textnode{Exit}{Loop exit}
 \textnode{n}{n}
 The vectorization is only possible if every node of the loop can be replaced with a corresponding vector node.
 Figure \ref{fig:loop5} shows the compiler graph of the example loop after vectorization.
 The vector nodes all work on an ordered list of integer values and are subject to canonicalization and global value numbering like any other node.
-\begin{figure}[h]
+\begin{figure}[ht]
 \centering
 \begin{digraphenv}{scale=0.5}{layout5}
 \textnode{Entry}{Entry}
 \textnode{Exit}{Exit}
 \textnode{n}{n}
 The frame state at the method beginning does not have to be explicitely in the graph, because it can always be reconstructed at a later stage.
 We save the frame state at control flow merges if there is at least one frame state on any control flow path between a node and its immediate dominator.
-\begin{figure}[h]
+\begin{figure}[ht]
 \centering
 \begin{digraphenv}{scale=0.5}{fs1}
 \nodetrisplit{store1}{ArrayStore}
 \nodebi{load1}{ArrayLoad}
 \controllabel{store1:succ1}{load1}
 }
 p.y = 0;
 }
 \end{lstlisting}
-\begin{figure}[h]
+\begin{figure}[ht]
 \centering
 \begin{digraphenv}{scale=0.5}{guard0}
 	\textnode{entry}{Entry}
 \nodesplit{if}{If}
 \node{merge}{Merge}
 Figure~\ref{fig:guard1} shows the example graph at a later compilation phase when the field store instructions are lowered to memory store instructions and explicitely modelled null check guards.
 The guards are attached to anchor instructions that delimit their possible schedule.
 The first guard must not be moved outside the \texttt{if} block; the second guard may be moved before the \texttt{If} instruction, because at this point it is already guaranteed that the second store is executed.
-\begin{figure}[h]
+\begin{figure}[ht]
 \centering
 \begin{digraphenv}{scale=0.5}{guard1}
 	\textnode{entry}{Entry}
 \node{anchor1}{Anchor}
 \node{anchor2}{Anchor}
 Therefore we can remove the guard and the anchor from the graph and this gives us the graph shown in Figure \ref{fig:guard2}.
 There is another optimization for guard instructions: If two guards that are anchored to the true and false branch of the same \texttt{If} instruction have the same condition, they can be merged, so that the resulting guard is anchored at the most distant node of which the \texttt{If} instruction is a postdominator.
-\begin{figure}[h]
+\begin{figure}[ht]
 \centering
 \begin{digraphenv}{scale=0.5}{guard2}
 	\textnode{entry}{Entry}
 \node{anchor1}{Anchor}
 \nodesplit{if}{If}
 The remaining guard can now be moved above the \texttt{If} condition and be used to eliminate the need for the \texttt{If} node.
 From this point on, the guard can however no longer be moved below the first memory store.
 We use a control dependency from the guard to the field store to express this condition.
 The link between the second store and the guard and the control flow merge instruction is no longer necessary.
-\begin{figure}[h]
+\begin{figure}[ht]
 \centering
 \begin{digraphenv}{scale=0.5}{guard3}
 	\textnode{entry}{Entry}
 \node{anchor1}{Anchor}
 \node{return}{Return}
 This will generate deoptimization-free zones that can be targeted by the most aggressive optimizations.
 A simple algorithm for this removal of frame states would be to move all guards as far upwards as possible and then the guards are fixed using anchor nodes.
 In our example, the guard is already fixed, so there is no deoptimization point that uses any of the memory store frame states.
 Therefore we can delete the frame states from the graph (see Figure \ref{fig:guard4}).
-\begin{figure}[h]
+\begin{figure}[ht]
 \centering
 \begin{digraphenv}{scale=0.5}{guard4}
 	\textnode{entry}{Entry}
 \node{anchor1}{Anchor}
 \node{return}{Return}
 Now we can use memory coalescing to combine the two stores without frame state to adjacent locations in the same object.
 This is only possible if the first store does not have a frame state.
 Figure \ref{fig:guard5} shows the resulting graph.
-\begin{figure}[h]
+\begin{figure}[ht]
 \centering
 \begin{digraphenv}{scale=0.5}{guard5}
 	\textnode{entry}{Entry}
 \node{anchor1}{Anchor}
 \node{return}{Return}
 A memory store that immediately follows a null check guard instruction on the same object, can be combined into a store with an implicit null check (that deoptimizes instead of throwing the exception).
 Therefore, we can remove the guard again and also the anchor is no longer necessary.
 Figure~\ref{fig:guard6} shows now that fully optimized graph that is generated for Listing~\ref{lst:guard1}.
-\begin{figure}[h]
+\begin{figure}[ht]
 \centering
 \begin{digraphenv}{scale=0.5}{guard6}
 	\textnode{entry}{Entry}
 \node{return}{Return}
 \textnode{p}{p}

Mercurial > hg > truffle

comparison graal/com.oracle.max.graal.doc.initial/graal_compiler.tex @ 2896:5d4aa5672d3d