# HG changeset patch # User Thomas Wuerthinger # Date 1304519668 -7200 # Node ID 6d99b909696d4e3cbaffdf11674e5e238b9bf75c # Parent 28a8b3c8b9b4d70c5db7c02fbfe0301e39930028 Documentation: More content and graphs on loops and vectorization. diff -r 28a8b3c8b9b4 -r 6d99b909696d doc/design/graal_compiler.pdf Binary file doc/design/graal_compiler.pdf has changed diff -r 28a8b3c8b9b4 -r 6d99b909696d doc/design/graal_compiler.tex --- 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: diff -r 28a8b3c8b9b4 -r 6d99b909696d doc/design/graphdrawing.tex --- 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=<
} \newcommand{\genericnodeend}[0]{
>]} \newcommand{\portinput}[1]{} @@ -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 }