Binary file doc/design/graal_compiler.pdf has changed

--- a/doc/design/graal_compiler.tex	Mon May 02 11:00:33 2011 +0200
+++ b/doc/design/graal_compiler.tex	Wed May 04 16:34:28 2011 +0200
@@ -25,6 +25,7 @@
 
 \newcommand\TODO[1]{\mynote{TODO}{#1}}
 \newcommand\cw[1]{\mynote{CW}{#1}}
+\newcommand\nodename[1]{\texttt{#1}}
 
 
 
@@ -121,6 +122,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:

--- a/doc/design/graphdrawing.tex	Mon May 02 11:00:33 2011 +0200
+++ b/doc/design/graphdrawing.tex	Wed May 04 16:34:28 2011 +0200
@@ -27,7 +27,9 @@
 \newcommand{\controllabel}[2]{#1 -> #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>}
@@ -42,7 +44,9 @@
 \newcommand{\node}[2]{\genericnodestart{#1} \portempty \portinput{inputs} \genericnodelabel{#2}{white} \portsuccessor{successors} \portempty \genericnodeend }
 \newcommand{\nodebi}[2]{\genericnodestart{#1} \portinput{in1} \portinput{in2} \genericnodelabel{#2}{white} \portsuccessor{successors} \portempty \genericnodeend }
 \newcommand{\nodetri}[2]{\genericnodestart{#1} \portinput{in1} \portinput{in2} \portinput{in3} \genericnodelabel{#2}{white} \portsuccessor{successors} \portempty \portempty \genericnodeend }
+\newcommand{\nodequad}[2]{\genericnodestart{#1} \portinput{in1} \portinput{in2} \portinput{in3} \portinput{in4} \genericnodelabel{#2}{white} \portsuccessor{successors} \portempty \portempty \genericnodeend }
 \newcommand{\nodesplit}[2]{\genericnodestart{#1} \portempty \portinput{inputs} \genericnodelabel{#2}{white} \portsuccessor{succ1} \portsuccessor{succ2} \genericnodeend }
+\newcommand{\nodesplittri}[2]{\genericnodestart{#1} \portempty \portinput{inputs} \genericnodelabel{#2}{white} \portsuccessor{succ1} \portsuccessor{succ2} \portsuccessor{succ3} \genericnodeend }
 
 \newcommand{\cnode}[3]{\genericnodestart{#1} \portempty \portinput{inputs} \genericnodelabel{#2}{#3} \portsuccessor{successors} \portempty \genericnodeend }
 \newcommand{\cnodebi}[3]{\genericnodestart{#1} \portinput{in1} \portinput{in2} \genericnodelabel{#2}{#3} \portsuccessor{successors} \portempty \genericnodeend }