Mercurial > hg > truffle

comparison doc/design/graal_compiler.tex @ 2588:26ecba0ead6d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Update on doc.
author Thomas Wuerthinger <thomas@wuerthinger.net>
date Thu, 05 May 2011 13:59:43 +0200
parents 999407dbfe10
children 795df30f979d
comparison
equal deleted inserted replaced
2580:70d8d239eb89 2588:26ecba0ead6d
77 \item[Graph Representation:] 77 \item[Graph Representation:]
78 The compiler's intermediate representation is modeled as a graph with nodes that are connected with directed edges. 78 The compiler's intermediate representation is modeled as a graph with nodes that are connected with directed edges.
79 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. 79 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.
80 Every node is serializable and has an id that is unique within its graph. 80 Every node is serializable and has an id that is unique within its graph.
81 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. 81 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.
82 There is no cycle in the graph that contains only control flow edges or only data flow edges. \cw{What does that sentence mean? I can certainly think of a loop that has a control-flow cycle, but no data-flow cycle.}
83 It is possible to replace a node with another node without traversing the full graph. 82 It is possible to replace a node with another node without traversing the full graph.
83 The graph does not allow data flow edge cycles or control flow edge cycles.
84 We achieve this by explicitely modelling loops (see Section~\ref{sec:loops}).
84 \item[Extensibility:] 85 \item[Extensibility:]
85 The compiler is extensible by adding new compiler phases and new node subclasses without modifying the compiler's sources. 86 The compiler is extensible by adding new compiler phases and new node subclasses without modifying the compiler's sources.
86 A node has an abstract way of expressing its effect and new compiler phases can ask compiler nodes for their properties and capabilities. 87 A node has an abstract way of expressing its effect and new compiler phases can ask compiler nodes for their properties and capabilities.
87 \cw{Add: We use the ``everything is an extension'' concept. Even standard compiler optimizations are internally modeled as extensions, to show that the extension mechanism exposes all necessary functionality.} 88 We use the ``everything is an extension'' concept.
89 Even standard compiler optimizations are internally modeled as extensions, to show that the extension mechanism exposes all necessary functionality.
88 \item[Detailing:] 90 \item[Detailing:]
89 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). 91 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).
90 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). 92 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).
91 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). 93 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).
92 \cw{In general, I agree that the lowering should happen without changing the style of IR. However, I don't agree that optimizations such as null check elimination should work on a lower level graph. Isn't it bette to model ``needs null check'' as a capability of high-level instructions? Then the eliminator just sets a property that no null check is necessary. But that is a good discussion point: How much optimization do we want to do by augmenting a high-level IR, and how much do we want to do by rewriting a low-level IR.}
93 \item[Generality:] 94 \item[Generality:]
94 The compiler does not require Java as its input. 95 The compiler does not require Java as its input.
95 This is achieved by having a graph as the starting point of the compilation and not a Java bytecodes array. 96 This is achieved by having a graph as the starting point of the compilation and not a Java bytecodes array.
96 Building the graph from the Java bytecodes must happen before giving a method to the compiler. 97 Building the graph from the Java bytecodes must happen before giving a method to the compiler.
97 This enables front-ends for different languages (e.g., Ruby) to provide their own graph. 98 This enables front-ends for different languages (e.g., Ruby) to provide their own graph.
98 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. 99 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.
99 \cw{Here we are getting into the nits of terminology. I think the term ``compiler'' should always refer to the whole system that goes from bytecodes to machine code. Yes, there will be additional parsers for different bytecode formats. But still, the compiler doesn't have graphs as input and outputs, but still bytecodes and machine code, respectively.}
100 \end{description} 100 \end{description}
101 101
102 \section{Milestones} 102 \section{Milestones}
103 The Graal compiler is developed starting from the current C1X source code base. 103 The Graal compiler is developed starting from the current C1X source code base.
104 This helps us testing the compiler at every intermediate development step on a variety of Java benchmarks. 104 This helps us testing the compiler at every intermediate development step on a variety of Java benchmarks.
118 \end{itemize} 118 \end{itemize}
119 119
120 \section{Implementation} 120 \section{Implementation}
121 121
122 \subsection{Loops} 122 \subsection{Loops}
123 \label{sec:loops}
123 Loops form a first-class construct in the IR that is expressed in specialized IR nodes during all optimization phases. 124 Loops form a first-class construct in the IR that is expressed in specialized IR nodes during all optimization phases.
124 We only compile methods with a control flow where every loop has only one single entry point. 125 We only compile methods with a control flow where every loop has only one single entry point.
125 This entry point is a \nodename{LoopBegin} node. 126 This entry point is a \nodename{LoopBegin} node.
126 This node is connected to a \nodename{LoopEnd} node that merges all control flow paths that do not exit the loop. 127 This node is connected to a \nodename{LoopEnd} node that merges all control flow paths that do not exit the loop.
127 The edge between the \nodename{LoopBegin} and the \nodename{LoopEnd} is the backedge of the loop. 128 The edge between the \nodename{LoopBegin} and the \nodename{LoopEnd} is the backedge of the loop.
291 \end{digraphenv} 292 \end{digraphenv}
292 \caption{Graal compiler graph after bounded loop transformation.} 293 \caption{Graal compiler graph after bounded loop transformation.}
293 \end{figure} 294 \end{figure}
294 295
295 \subsection{Project Source Structure} 296 \subsection{Project Source Structure}
296 In order to have clear interfaces between the different parts of the compiler, the code will be divided into the following source code projects: 297 In order to support the goal of a modular compiler, the code will be divided into the following source code projects (as subprojects of \textbf{com.oracle.graal}).
297 \cw{Use new naming scheme com.oracle.graal...} 298
298 \begin{description} 299 \begin{description}
299 \item[Graph] contains the abstract node implementation, the graph implementation and all the associated tools and auxiliary classes. 300 \item[graph] contains the abstract node implementation, the graph implementation and all the associated tools and auxiliary classes.
300 \item[Nodes] contains the node implementations, ranging from high-level to machine-level nodes. \cw{Can't we just stay with the name ``instruction'', which everyone understands, instead of ``Node''? I strongly vote for that.} 301 \item[nodes] contains the implementation of known basic nodes (e.g., phi nodes, control flow nodes, \ldots).
301 \item[GraphBuilder] contains helpers for building graphs from Java bytecodes and other source representations. 302 Additional node classes should go into seperate projects and be specializations of the known basic nodes.]
302 \item[Assembler] contains the assembler classes that are used to generate the compiled code of methods and stubs. 303 \item[java] contains code for building graphs from Java bytecodes and Java-specific nodes.
303 \item[Optimizations] contains all the optimizations, along with different optimization plans. 304 \item[opt] contains optimizations such as global value numbering or conditional constant propagation.
304 \item[GraalCompiler] contains the compiler, including: 305 \item[compiler] contains the compiler, including:
305 \begin{itemize} 306 \begin{itemize}
306 \item Handling of compilation phases. 307 \item Schedules the compilation phases.
307 \item Compilation-related data structures.
308 \item Implementation of the \emph{compiler interface} (CI). 308 \item Implementation of the \emph{compiler interface} (CI).
309 \item Register allocation. 309 \item Implements the final compilation phase that produces the low-level representation.
310 \item Machine code creation, including debug info. 310 \item Machine code creation, including debug info.
311 \item Debug output and compilation observation.
312 \item Compiler options management.
313 \end{itemize} 311 \end{itemize}
314 \cw{So you want to keep the backend as part of the ``main compiler'' at first. Seems OK for me.} 312 \cw{So you want to keep the backend as part of the ``main compiler'' at first. Seems OK for me.}
315 \end{description} 313 \end{description}
316
317 \subsection{Initial Steps}
318 \begin{itemize}
319 \item Restructuring of the project to include the compiler and the modified HotSpot code within one repository. The CRI project will remain in the Maxine repository, because it will remain mostly unchanged.
320 \item Stripping optimizations from the existing compiler, they will be reimplemented later on using the new infrastructure.
321 \item Creating Node and Graph classes, along with the necessary auxiliary classes.
322 \item Writing documentation on the design of the compiler.
323 \item Use the Node class as the superclass of the existing Value class.
324 \item Identify (and later: remove) extended bytecodes.
325 \item Implement the new frame state concept.
326 \item Remove LIR - in the long run there should only be one IR, which will be continually lowered until only nodes that can be translated into machine code remain. \cw{That cannot be an initial step, because you have nothing yet that could replace the LIR.}
327 \end{itemize}
328 314
329 \subsection{Nodes and Graphs} 315 \subsection{Nodes and Graphs}
330 The most important aspect of a compiler is the data structure that holds information about an executable piece of code, called \emph{intermediate representation}~(IR). 316 The most important aspect of a compiler is the data structure that holds information about an executable piece of code, called \emph{intermediate representation}~(IR).
331 The IR used in the Graal Compiler (simply referred to as \emph{the compiler} in the rest of this document) was designed in such a way as to allow for extensive optimizations, easy traversal, compact storage and efficient processing. 317 The IR used in the Graal Compiler (simply referred to as \emph{the compiler} in the rest of this document) was designed in such a way as to allow for extensive optimizations, easy traversal, compact storage and efficient processing.
332 318
367 353
368 \begin{itemize} 354 \begin{itemize}
369 \item Array stores: {\tt IASTORE, LASTORE, FASTORE, \\DASTORE, AASTORE, BASTORE, CASTORE, SASTORE} 355 \item Array stores: {\tt IASTORE, LASTORE, FASTORE, \\DASTORE, AASTORE, BASTORE, CASTORE, SASTORE}
370 \item Field stores: {\tt PUTSTATIC, PUTFIELD} 356 \item Field stores: {\tt PUTSTATIC, PUTFIELD}
371 \item Method calls: {\tt INVOKEVIRTUAL, INVOKESPECIAL, \\INVOKESTATIC, INVOKEINTERFACE} 357 \item Method calls: {\tt INVOKEVIRTUAL, INVOKESPECIAL, \\INVOKESTATIC, INVOKEINTERFACE}
372 \item Memory allocations: {\tt NEW, NEWARRAY, ANEWARRAY, \\MULTIANEWARRAY}
373 \item Synchronization: {\tt MONITORENTER, MONITOREXIT} 358 \item Synchronization: {\tt MONITORENTER, MONITOREXIT}
374 \end{itemize} 359 \end{itemize}
375 360
376 Within the node graph a frame state is represented as a node that is fixed to the node that caused it to be generated (control dependency). 361 Within the node graph a frame state is represented as a node that is fixed to the node that caused it to be generated (control dependency).
377 362