Mercurial > hg > graal-jvmci-8
diff doc/design/graal_compiler.tex @ 2573:6d99b909696d
Documentation: More content and graphs on loops and vectorization.
author | Thomas Wuerthinger <thomas@wuerthinger.net> |
---|---|
date | Wed, 04 May 2011 16:34:28 +0200 |
parents | 28a8b3c8b9b4 |
children | d1ea2563836d |
line wrap: on
line diff
--- 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: