Mercurial > hg > truffle

comparison doc/design/graal_compiler.tex @ 2688:3396862d4cee

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Minor design doc edits.
author Doug Simon <doug.simon@oracle.com>
date Wed, 18 May 2011 08:54:51 +0200
parents 77e106760633
children
comparison
equal deleted inserted replaced
2687:77e106760633 2688:3396862d4cee
52 \subtitle{Design and Strategy \\ \textcolor{red}{work in progress (Oracle internal)}} 52 \subtitle{Design and Strategy \\ \textcolor{red}{work in progress (Oracle internal)}}
53 53
54 \maketitle 54 \maketitle
55 55
56 \abstract{ 56 \abstract{
57 The Graal compiler (simply referred to as \emph{the compiler} in the rest of this document) aims at improving C1X, the Java port of the HotSpot client compiler, both in terms of modularity and peak performance. 57 The Graal compiler (simply referred to as \emph{the compiler} in the rest of this document) aims at improving upon C1X, the Java port of the HotSpot client compiler, both in terms of modularity and peak performance.
58 The compiler should work with the Maxine VM and the HotSpot VM. 58 The compiler should work with the Maxine VM and the HotSpot VM.
59 This document contains information about the proposed design and strategy for developing the compiler.} 59 This document contains information about the proposed design and strategy for developing the compiler.}
60 60
61 \section{Context} 61 \section{Context}
62 62
81 There is only a single node base class and every node has an associated graph object that does not change during the node's lifetime. 81 There is only a single node base class and every node has an associated graph object that does not change during the node's lifetime.
82 Every node is serializable and has an id that is unique within its graph. 82 Every node is serializable and has an id that is unique within its graph.
83 Every edge is classified as either a control flow edge (anti-dependency) or a data flow edge (dependency) and represented as a simple pointer from the source node to the target node. 83 Every edge is classified as either a control flow edge (anti-dependency) or a data flow edge (dependency) and represented as a simple pointer from the source node to the target node.
84 It is possible to replace a node with another node without traversing the full graph. 84 It is possible to replace a node with another node without traversing the full graph.
85 The graph does not allow data flow edge cycles or control flow edge cycles. 85 The graph does not allow data flow edge cycles or control flow edge cycles.
86 We achieve this by explicitely modelling loops (see Section~\ref{sec:loops}). 86 We achieve this by explicitly modeling loops (see Section~\ref{sec:loops}).
87 \item[Extensibility:] 87 \item[Extensibility:]
88 The compiler is extensible by allowing developers to add new compiler phases and new node subclasses without modifying the compiler's sources. 88 The compiler is extensible by allowing developers to add new compiler phases and new node subclasses without modifying the compiler's sources.
89 A node has an abstract way of expressing its semantics and new compiler phases can ask compiler nodes for their properties and capabilities. 89 A node has an abstract way of expressing its semantics and new compiler phases can ask compiler nodes for their properties and capabilities.
90 We use the ``everything is an extension'' concept. 90 We use the ``everything is an extension'' concept.
91 Even standard compiler optimizations are internally modeled as extensions, to show that the extension mechanism exposes all necessary functionality. 91 Even standard compiler optimizations are internally modeled as extensions, to show that the extension mechanism exposes all necessary functionality.
93 The compilation starts with a graph that contains nodes that represent the operations of the source language (e.g., one node for an array store to an object array). 93 The compilation starts with a graph that contains nodes that represent the operations of the source language (e.g., one node for an array store to an object array).
94 During the compilation, the nodes are replaced with more detailed nodes (e.g., the array store node is split into a null check, a bounds check, a store check, and a memory access). 94 During the compilation, the nodes are replaced with more detailed nodes (e.g., the array store node is split into a null check, a bounds check, a store check, and a memory access).
95 Compiler phases can choose whether they want to work on the earlier versions of the graph (e.g., escape analysis) or on later versions (e.g., null check elimination). 95 Compiler phases can choose whether they want to work on the earlier versions of the graph (e.g., escape analysis) or on later versions (e.g., null check elimination).
96 \item[Generality:] 96 \item[Generality:]
97 The compiler does not require Java as its input. 97 The compiler does not require Java as its input.
98 This is achieved by having a graph as the starting point of the compilation and not a Java bytecodes array. 98 This is achieved by having a graph as the starting point of the compilation and not a Java bytecode array.
99 Building the graph from the Java bytecodes must happen before giving a method to the compiler. 99 Building the graph from the Java bytecodes must happen before giving a method to the compiler.
100 This enables front-ends for different languages (e.g., Ruby or JavaScript) to provide their own graph. 100 This enables front-ends for different languages (e.g., Ruby or JavaScript) to provide their own graph.
101 Also, there is no dependency on a specific back-end, but the output of the compiler is a graph that can then be converted to a different representation in a final compiler phase. 101 Also, there is no dependency on a specific back-end, but the output of the compiler is a graph that can then be converted to a different representation in a final compiler phase.
102 \end{description} 102 \end{description}
103 103
104 \section{Milestones} 104 \section{Milestones}
105 \label{sec:mile} 105 \label{sec:mile}
106 The compiler is developed starting from the current C1X source code base. 106 The compiler is being developed starting from the current C1X source code base.
107 This helps us testing the compiler at every intermediate development step on a variety of Java benchmarks. 107 This helps us test the compiler at every intermediate development step on a variety of Java benchmarks.
108 We define the following development milestones and when they are considered to be achieved (see Section~\ref{sec:conclusions} for planned dates): 108 We define the following development milestones (see Section~\ref{sec:conclusions} for planned dates):
109 \begin{description} 109 \begin{description}
110 \item[M1:] We have a fully working Graal~VM version with a stripped down C1X compiler that does not perform any optimizations. 110 \item[M1:] We have a fully working Graal~VM version with a stripped down C1X compiler that does not perform any optimization.
111 \item[M2:] We modified the high-level intermediate representation to be based on the compiler graph data structure. 111 \item[M2:] We modified the high-level intermediate representation to be based on the compiler graph data structure.
112 \item[M3:] We have reimplemented and reenabled compiler optimizations in the compiler that previously existed in C1X. 112 \item[M3:] We have reimplemented and reenabled compiler optimizations in the compiler that previously existed in C1X.
113 \item[M4:] We have reintegrated the new compiler into the Maxine VM and can use it as a Maxine VM bootstrapping compiler. 113 \item[M4:] We have reintegrated the new compiler into the Maxine VM and can use it as a Maxine VM bootstrapping compiler.
114 \end{description} 114 \end{description}
115 115
140 140
141 141
142 \section{Graph} 142 \section{Graph}
143 143
144 The \emph{intermediate representation}~(IR) of the compiler is designed as a directed graph. 144 The \emph{intermediate representation}~(IR) of the compiler is designed as a directed graph.
145 The graph deals out ids for new nodes and can be queried for the node corresponding to a given id as well as for an unordered list of nodes of the graph. 145 The graph allocates unique ids for new nodes and can be queried for the node corresponding to a given id as well as for an unordered list of nodes of the graph.
146 Graphs can manage side data structures, which will be automatically invalidated and lazily recomputed whenever the graph changes. Examples for side data structures are dominator trees and temporary schedules. These side data structures will usually be understood by more than one optimization. 146 Graphs can manage side data structures (e.g. dominator trees and temporary schedules), which will be automatically invalidated and lazily recomputed whenever the graph changes. These side data structures will usually be understood by more than one optimization.
147 147
148 The nodes of the graph have the following properties: 148 The nodes of the graph have the following properties:
149 \begin{itemize} 149 \begin{itemize}
150 \item Each node is always associated with a single graph and this association is immutable. 150 \item Each node is always associated with a single graph and this association is immutable.
151 \item Each node has an immutable id that is unique within its associated graph. 151 \item Each node has an immutable id that is unique within its associated graph.
330 \caption{A simple loop with two exits.} 330 \caption{A simple loop with two exits.}
331 \label{fig:loop1} 331 \label{fig:loop1}
332 \end{figure} 332 \end{figure}
333 333
334 \subsection{Loop Phis} 334 \subsection{Loop Phis}
335 Data flow in loops is modelled with special phi nodes at the beginning and the end of the loop. 335 Data flow in loops is modeled with special phi nodes at the beginning and the end of the loop.
336 The \nodename{LoopEnd} instruction merges every value that flows into the next loop iteration in associated \nodename{LoopEndPhi} nodes. 336 The \nodename{LoopEnd} instruction merges every value that flows into the next loop iteration in associated \nodename{LoopEndPhi} nodes.
337 A corresponding \nodename{LoopBeginPhi} node that is associated with the loop header has a control flow dependency on the \nodename{LoopEndPhi} node. 337 A corresponding \nodename{LoopBeginPhi} node that is associated with the loop header has a control flow dependency on the \nodename{LoopEndPhi} node.
338 Listing~\ref{lst:loop} shows a simple counting loop that is used as an example in the rest of this section. 338 Listing~\ref{lst:loop} shows a simple counting loop that is used as an example in the rest of this section.
339 Figure~\ref{fig:loop2} shows how the loop is modelled immediately after building the graph. 339 Figure~\ref{fig:loop2} shows how the loop is modelled immediately after building the graph.
340 340