Binary file doc/design/graal_compiler.pdf has changed

--- a/doc/design/graal_compiler.tex	Tue May 03 15:13:19 2011 +0200
+++ b/doc/design/graal_compiler.tex	Wed May 04 16:36:09 2011 +0200
@@ -25,6 +25,7 @@
 
 \newcommand\TODO[1]{\mynote{TODO}{#1}}
 \newcommand\cw[1]{\mynote{CW}{#1}}
+\newcommand\nodename[1]{\texttt{#1}}
 
 
 
@@ -117,6 +118,178 @@
 
 \section{Implementation}
 
+\subsection{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.
+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 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]
+  \label{fig:loop1}
+  \centering
+\begin{digraphenv}{scale=0.5}{layout1}
+\textnode{BeforeLoop}{Loop entry}
+\textnode{Exit1}{First loop exit}
+\textnode{Exit2}{Second loop exit}
+\nodesplit{LoopBegin}{LoopBegin}
+\node{LoopEnd}{LoopEnd}
+\nodesplit{If1}{If}
+\nodesplit{If2}{If}
+\controllabel{LoopBegin:succ1}{LoopEnd}
+\controllabel{LoopBegin:succ2}{If1}
+\controllabel{If1:succ1}{If2}
+\controllabel{If2:succ1}{LoopEnd}
+\controllabel{BeforeLoop}{LoopBegin}
+\controllabel{If1:succ2}{Exit1}
+\controllabel{If2:succ2}{Exit2}
+\end{digraphenv}
+  \caption{A simple loop with two exits.}
+\end{figure}
+
+\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 is 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.
+
+\begin{figure}[h]
+  \label{fig:loop2}
+  \centering
+\begin{digraphenv}{scale=0.5}{layout2}
+\textnode{BeforeLoop}{Loop entry}
+\textnode{Exit}{Loop exit}
+\textnode{n}{n}
+\textnode{Constant0}{0}
+\textnode{Constant1}{1}
+\nodesplit{LoopBegin}{LoopBegin}
+\node{LoopEnd}{LoopEnd}
+\nodesplit{If1}{If}
+\controllabel{LoopBegin:succ1}{LoopEnd}
+\controllabel{LoopBegin:succ2}{If1}
+\nodebi{Compare}{<}
+\nodebi{LoopBeginPhi}{LoopBeginPhi}
+\nodebi{Add}{+}
+\datalabel{Add:in1}{LoopBeginPhi}
+\datalabel{Add:in2}{Constant1}
+\nodebi{LoopEndPhi}{LoopEndPhi}
+\control{LoopBeginPhi}{LoopEndPhi}
+\data{LoopEndPhi:in1}{LoopEnd}
+\data{LoopEndPhi:in2}{Add}
+\datalabel{LoopBeginPhi:in1}{LoopBegin}
+\datalabel{LoopBeginPhi:in2}{Constant0}
+\datalabel{Compare:in1}{LoopBeginPhi}
+\datalabel{Compare:in2}{n}
+\data{If1}{Compare}
+\controllabel{If1:succ1}{LoopEnd}
+\controllabel{BeforeLoop}{LoopBegin}
+\controllabel{If1:succ2}{Exit}
+\end{digraphenv}
+  \caption{Graal compiler graph for a loop counting from 0 to n-1.}
+\end{figure}
+
+\subsection{Loop Counters}
+The compiler is capable of recognizing variables that are only increased within a loop.
+A potential overflow of such a variable is guarded with a trap before the loop.
+Figure \ref{fig:loop3} shows the compiler graph of the example loop after the loop counter transformation.
+
+
+\begin{figure}[h]
+  \label{fig:loop3}
+  \centering
+\begin{digraphenv}{scale=0.5}{layout3}
+\textnode{BeforeLoop}{Loop entry}
+\textnode{Exit}{Loop exit}
+\textnode{n}{n}
+\textnode{Constant0}{0}
+\textnode{Constant1}{1}
+\nodesplit{LoopBegin}{LoopBegin}
+\node{LoopEnd}{LoopEnd}
+\nodesplit{If1}{If}
+\controllabel{LoopBegin:succ1}{LoopEnd}
+\controllabel{LoopBegin:succ2}{If1}
+\nodebi{Compare}{<}
+\nodetri{LoopCounter}{LoopCounter}
+\datalabel{LoopCounter:in1}{LoopBegin}
+\datalabeltext{LoopCounter:in2}{Constant0}{init}
+\datalabeltext{LoopCounter:in3}{Constant1}{stride}
+\datalabel{Compare:in1}{LoopCounter}
+\datalabel{Compare:in2}{n}
+\data{If1}{Compare}
+\controllabel{If1:succ1}{LoopEnd}
+\controllabel{BeforeLoop}{LoopBegin}
+\controllabel{If1:succ2}{Exit}
+\end{digraphenv}
+  \caption{Graal compiler graph after loop counter transformation.}
+\end{figure}
+
+\subsection{Bounded Loops}
+
+If the total maximum number of iterations of a loop is fixed, then the loop is converted into a bounded loop.
+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 totel 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]
+  \label{fig:loop4}
+  \centering
+\begin{digraphenv}{scale=0.5}{layout4}
+\textnode{BeforeLoop}{Loop entry}
+\textnode{Exit}{Loop exit}
+\textnode{n}{n}
+\textnode{Constant0}{0}
+\textnode{Constant1}{1}
+\nodesplittri{LoopBegin}{BoundedLoopBegin}
+\node{LoopEnd}{LoopEnd}
+\controllabel{LoopBegin:succ1}{LoopEnd}
+\controllabel{LoopBegin:succ2}{LoopEnd}
+\controllabel{LoopBegin:succ3}{Exit}
+\nodetri{LoopCounter}{LoopCounter}
+\datalabel{LoopCounter:in1}{LoopBegin}
+\datalabeltext{LoopCounter:in2}{Constant0}{init}
+\datalabeltext{LoopCounter:in3}{Constant1}{stride}
+\data{LoopBegin}{n}
+\controllabel{BeforeLoop}{LoopBegin}
+\end{digraphenv}
+  \caption{Graal compiler graph after bounded loop transformation.}
+\end{figure}
+
+\subsection{Vectorization}
+
+If we have now a bounded loop with no additional loop exit and no associated phi nodes (only associated loop counters), we can vectorize the loop.
+We replace the loop header with a normal instruction that produces a vector of values from 0 to the number of loop iterations minus 1.
+The loop counters are replaced with \texttt{VectorAdd} and \texttt{VectorMul} nodes.
+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 like any other node.
+
+
+\begin{figure}[h]
+  \label{fig:loop5}
+  \centering
+\begin{digraphenv}{scale=0.5}{layout5}
+\textnode{Entry}{Entry}
+\textnode{Exit}{Exit}
+\textnode{n}{n}
+\textnode{Constant0}{0}
+\textnode{Constant1}{1}
+\node{Vector}{Vector}
+\nodebi{VectorAdd}{VectorAdd}
+\nodebi{VectorMul}{VectorMul}
+\control{Entry}{Vector}
+\control{Vector}{Exit}
+\datalabel{VectorAdd:in1}{Vector}
+\datalabel{VectorAdd:in2}{Constant0}
+\datalabel{VectorMul:in1}{VectorAdd}
+\datalabel{VectorMul:in2}{Constant1}
+\data{Vector}{n}
+\end{digraphenv}
+  \caption{Graal compiler graph after bounded loop transformation.}
+\end{figure}
 
 \subsection{Project Source Structure}
 In order to have clear interfaces between the different parts of the compiler, the code will be divided into the following source code projects:
@@ -188,7 +361,7 @@
 
 \subsection{Frame States}
 Frame states capture the state of the program, in terms of the source representation (e.g., Java state: local variables, expressions, ...).
-Whenever a safepoint is reached or \cwi{why is that an ``or'', both is basically the same} a deoptimization is needed a valid frame state needs to be available.
+Whenever a safepoint is reached or \cw{why is that an ``or'', both is basically the same} a deoptimization is needed a valid frame state needs to be available.
 A frame state is valid as long as the program performs only actions that can safely be reexecuted (e.g., operations on local variables, etc.).
 Thus, frame states need only be generated for bytecodes that cannot be reexecuted: putfield, astore, invoke, monitorenter/exit, ...
 

--- a/doc/design/graphdrawing.tex	Tue May 03 15:13:19 2011 +0200
+++ b/doc/design/graphdrawing.tex	Wed May 04 16:36:09 2011 +0200
@@ -27,7 +27,9 @@
 \newcommand{\controllabel}[2]{#1:s -> #2:predecessors:n [color=red];}
 \newcommand{\data}[2]{#2:usages:s -> #1:inputs [color=black,dir=back];}
 \newcommand{\datalabel}[2]{#2:usages:s -> #1:n [color=black,dir=back];}
+\newcommand{\datalabeltext}[3]{#2:usages:s -> #1:n [color=black,dir=back,label="#3"];}
 
+\newcommand{\textnode}[2]{#1 [shape=plaintext, label="#2"]}
 \newcommand{\genericnodestart}[1]{#1 [shape=plaintext, label=< <TABLE BORDER="0" CELLSPACING="0"><TR><TD CELLPADDING="0"><TABLE BORDER="0" CELLSPACING="2" CELLPADDING="0"><TR><TD WIDTH="15" HEIGHT="5" PORT="predecessors" BGCOLOR="rosybrown1"></TD></TR></TABLE></TD><TD COLSPAN="2" CELLPADDING="0" ALIGN="RIGHT"><TABLE BORDER="0" CELLSPACING="2" CELLPADDING="0"><TR>}
 \newcommand{\genericnodeend}[0]{</TR></TABLE></TD><TD CELLPADDING="0"><TABLE BORDER="0" CELLSPACING="2" CELLPADDING="0"><TR><TD WIDTH="15" HEIGHT="5" PORT="usages" BGCOLOR="lightgrey"></TD></TR></TABLE></TD></TR></TABLE>>]}
 \newcommand{\portinput}[1]{<TD WIDTH="15" HEIGHT="5" PORT="#1" BGCOLOR="lightgrey"></TD>}
@@ -49,7 +51,7 @@
 \newcommand{\nodequad}[2]{\genericnodestart{#1} \portinput{in1} \portinput{in2} \portinput{in3} \portinput{in4} \genericnodelabel{#2}{white} \portsuccessor{successors} \portempty \portempty \portempty \genericnodeend }
 \newcommand{\nodesplit}[2]{\genericnodestart{#1} \portempty \portinput{inputs} \genericnodelabel{#2}{white} \portsuccessor{succ1} \portsuccessor{succ2} \genericnodeend }
 \newcommand{\nodequadsplit}[2]{\genericnodestart{#1} \portinput{in1} \portinput{in2} \portinput{in3} \portinput{in4} \genericnodelabel{#2}{white} \portsuccessor{succ1} \portsuccessor{succ2} \portempty \portempty \genericnodeend }
-
+\newcommand{\nodesplittri}[2]{\genericnodestart{#1} \portempty \portinput{inputs} \genericnodelabel{#2}{white} \portsuccessor{succ1} \portsuccessor{succ2} \portsuccessor{succ3} \genericnodeend }
 \newcommand{\nodetrap}[2]{\cnodebi{#1}{#2}{rosybrown1}}
 
 \newcommand{\cnode}[3]{\genericnodestart{#1} \portempty \portinput{inputs} \genericnodelabel{#2}{#3} \portsuccessor{successors} \portempty \genericnodeend }