Mercurial > hg > truffle

annotate doc/design/graal_compiler.tex @ 2577:ac2029d0898f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
doc: framestate and deopt changes
author Lukas Stadler <lukas.stadler@jku.at>
date Wed, 04 May 2011 16:39:06 +0200
parents c59db1f02893
children 999407dbfe10
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
2517
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
1 \documentclass[twocolumn]{svjour3}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
2 \usepackage[pdftex]{graphicx}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
3 \usepackage{environ}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
4 \usepackage{amsmath}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
5 \usepackage{amsfonts}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
6 \usepackage[english]{babel}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
7 \usepackage[utf8]{inputenc}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
8 \usepackage{lmodern}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
9 \usepackage[T1]{fontenc}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
10 \usepackage{color}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
11
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
12 \input{graphdrawing}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
13
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
14 \renewcommand*\descriptionlabel[1]{\hspace\labelsep\normalfont\bf #1}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
15
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
16 \newcommand{\Sa}{{\Large$^*$}}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
17 \newcommand{\Sb}{{\Large$^\dag$}}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
18 \newcommand{\Sc}{{\Large$^\S$}}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
19
2562
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
20
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
21 \newcommand{\mynote}[2]{
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
22 \textcolor{red}{\fbox{\bfseries\sffamily\scriptsize#1}
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
23 {\small\textsf{\emph{#2}}}
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
24 \fbox{\bfseries\sffamily\scriptsize }}}
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
25
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
26 \newcommand\TODO[1]{\mynote{TODO}{#1}}
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
27 \newcommand\cw[1]{\mynote{CW}{#1}}
2576
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
28 \newcommand\ls[1]{\mynote{LS}{#1}}
2562
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
29
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
30
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
31
2517
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
32 \smartqed % flush right qed marks, e.g. at end of proof
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
33
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
34 \journalname{Graal Compiler Design}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
35 \def\makeheadbox{{%
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
36 \hbox to0pt{\vbox{\baselineskip=10dd\hrule\hbox
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
37 to\hsize{\vrule\kern3pt\vbox{\kern3pt
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
38 \hbox{\bfseries The Graal Compiler - Design and Strategy}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
39 \kern3pt}\hfil\kern3pt\vrule}\hrule}%
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
40 \hss}}}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
41
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
42 \begin{document}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
43
2561
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
44 \author{Thomas W\"{u}rthinger \Sa, Lukas Stadler \Sc, Gilles Duboscq \Sa}
2517
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
45 \institute{\Sa Oracle, \Sc Johannes Kepler University, Linz}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
46
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
47 \date{Created: \today}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
48
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
49 \title{The Graal Compiler}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
50 \subtitle{Design and Strategy \\ \textcolor{red}{work in progress}}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
51
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
52 \maketitle
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
53
2561
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
54 \abstract{
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
55 The Graal compiler aims at improving C1X, the Java port of the HotSpot client compiler, both in terms of modularity and peak performance.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
56 The compiler should work with the Maxine VM and the HotSpot VM.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
57 This document contains information about the proposed design and strategy for developing the Graal compiler.}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
58
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
59 \section{Context}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
60
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
61 In 2009, the Maxine team started with creating C1X, a Java port of the HotSpot client compiler, and integrate it into the Maxine VM.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
62 Part of this effort, was the development of a clear and clean compiler-runtime interface that allows the separation of the compiler and the VM that enables the use of one compiler for multiple VMs.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
63 In June 2010, we started integrating C1X into the HotSpot VM and we called the resulting system Graal~VM.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
64 Currently, the Graal~VM is fully functional and runs benchmarks (SciMark, DaCapo) at a similar speed to the HotSpot client compiler.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
65
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
66 \section{Goals}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
67 The Graal compiler effort aims at rewriting the high-level intermediate representation of C1X with two main goals:
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
68 \begin{description}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
69 \item[Modularity:] A modular design of the compiler should simplify the implementation of new languages, new back-ends, and new optimizations.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
70 \item[Peak Performance:] A more powerful intermediate representation should enable the implementation of heavy-weight optimizations that impact the peak performance of the resulting machine code.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
71 \end{description}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
72
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
73 \section{Design}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
74 For the implementation of the Graal compiler, we rely on the following design decisions:
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
75 \begin{description}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
76 \item[Graph Representation:]
2562
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
77 The compiler's intermediate representation is modeled as a graph with nodes that are connected with directed edges.
2561
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
78 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.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
79 Every node is serializable and has an id that is unique within its graph.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
80 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.
2562
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
81 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.}
2561
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
82 It is possible to replace a node with another node without traversing the full graph.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
83 \item[Extensibility:]
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
84 The compiler is extensible by adding new compiler phases and new node subclasses without modifying the compiler's sources.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
85 A node has an abstract way of expressing its effect and new compiler phases can ask compiler nodes for their properties and capabilities.
2562
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
86 \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.}
2561
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
87 \item[Detailing:]
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
88 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).
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
89 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).
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
90 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).
2562
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
91 \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.}
2561
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
92 \item[Generality:]
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
93 The compiler does not require Java as its input.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
94 This is achieved by having a graph as the starting point of the compilation and not a Java bytecodes array.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
95 Building the graph from the Java bytecodes must happen before giving a method to the compiler.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
96 This enables front-ends for different languages (e.g., Ruby) to provide their own graph.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
97 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.
2562
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
98 \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.}
2561
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
99 \end{description}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
100
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
101 \section{Milestones}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
102 The Graal compiler is developed starting from the current C1X source code base.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
103 This helps us testing the compiler at every intermediate development step on a variety of Java benchmarks.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
104 We define the following development milestones and when they are considered achieved:
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
105 \begin{description}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
106 \item[M1:] We have a fully working Graal VM version with a stripped down C1X compiler that does not perform any optimizations.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
107 \item[M2:] We modified the high-level intermediate representation to be based on the Graal compiler graph data structure.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
108 \item[M3:] We have reimplemented and reenabled compiler optimizations in the Graal compiler that previously existed in C1X.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
109 \item[M4:] We have reintegrated the new Graal compiler into the Maxine VM and can use it as a Maxine VM bootstrapping compiler.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
110 \end{description}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
111
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
112 After those four milestones, we see three different possible further development directions that can be followed in parallel:
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
113 \begin{itemize}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
114 \item Removal of the XIR template mechanism and replacement with a snippet mechanism that works with the Graal compiler graph.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
115 \item Improvements for Graal peak performance (loop optimizations, escape analysis, bounds check elimination, processing additional interpreter runtime feedback).
2562
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
116 \item Implementation of a prototype front-end for different languages, e.g., JavaScript.
2561
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
117 \end{itemize}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
118
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
119 \section{Implementation}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
120
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
121
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
122 \subsection{Project Source Structure}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
123 In order to have clear interfaces between the different parts of the compiler, the code will be divided into the following source code projects:
2562
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
124 \cw{Use new naming scheme com.oracle.graal...}
2561
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
125 \begin{description}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
126 \item[Graph] contains the abstract node implementation, the graph implementation and all the associated tools and auxiliary classes.
2562
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
127 \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.}
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
128 \item[GraphBuilder] contains helpers for building graphs from Java bytecodes and other source representations.
2561
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
129 \item[Assembler] contains the assembler classes that are used to generate the compiled code of methods and stubs.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
130 \item[Optimizations] contains all the optimizations, along with different optimization plans.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
131 \item[GraalCompiler] contains the compiler, including:
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
132 \begin{itemize}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
133 \item Handling of compilation phases.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
134 \item Compilation-related data structures.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
135 \item Implementation of the \emph{compiler interface} (CI).
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
136 \item Register allocation.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
137 \item Machine code creation, including debug info.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
138 \item Debug output and compilation observation.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
139 \item Compiler options management.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
140 \end{itemize}
2562
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
141 \cw{So you want to keep the backend as part of the ``main compiler'' at first. Seems OK for me.}
2561
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
142 \end{description}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
143
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
144 \subsection{Initial Steps}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
145 \begin{itemize}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
146 \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.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
147 \item Stripping optimizations from the existing compiler, they will be reimplemented later on using the new infrastructure.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
148 \item Creating Node and Graph classes, along with the necessary auxiliary classes.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
149 \item Writing documentation on the design of the compiler.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
150 \item Use the Node class as the superclass of the existing Value class.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
151 \item Identify (and later: remove) extended bytecodes.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
152 \item Implement the new frame state concept.
2562
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
153 \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.}
2561
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
154 \end{itemize}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
155
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
156 \subsection{Nodes and Graphs}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
157 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).
2562
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
158 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.
2561
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
159
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
160 \subsubsection{The Node Data Structure}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
161 \begin{itemize}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
162 \item Each node is always associated with a graph.
2562
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
163 \item Each node has an immutable id which is unique within its associated graph. \cw{The server compiler supports ``renumbering'' of nodes to make the ids dense again after large graph manipulations that deleted many nodes.}
2561
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
164 \item Nodes represent either operations on values or control flow operations.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
165 \item Nodes can have a data dependency, which means that one node requires the result of some other node as its input. The fact that the result of the first node needs to be computed before the second node can be executed introduces a partial order to the set of nodes.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
166 \item Nodes can have a control flow dependency, which means that the execution of one node depends on some other node. This includes conditional execution, memory access serialization and other reasons, and again introduces a partial order to the set of nodes.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
167 \item Nodes can only have data and control dependencies to nodes which belong to the same graph.
2562
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
168 \item Control dependencies and data dependencies each represent a \emph{directed acyclic graph} (DAG) on the same set of nodes. This means that data dependencies always point upwards, and control dependencies always point downwards. Situations that are normally incur cycles (like loops) are represented by special nodes (like LoopEnd).
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
169 \cw{I don't like that item. Cycles are a normal thing for control flow and for phi functions. I would phrase it as something like that: Nodes can only have data and control dependencies to nodes that are dominators. The only exception of that are control loop headers and phi functions}
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
170 \item Ordering between nodes is specified only to the extent which is required to correctly express the semantics of a given program. Some compilers (notably the HotSpot client compiler \cw{Wrong: the client compiler only has a fixed order of pinned instructions, most instructions are not pinned and can be moved around freely}) always maintain a complete order for all nodes (called \emph{scheduling}), which impedes advanced optimizations. For algorithms that require a fixed ordering of nodes, a temporary schedule can always be generated.
2561
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
171 \item Both data and control dependencies can be traversed in both directions, so that each node can be traversed in four directions:
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
172 \begin{itemize}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
173 \item \emph{inputs} are all nodes that this node has data dependencies on.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
174 \item \emph{usages} are all nodes that have data dependencies on this node, this is regarded as the inverse of inputs.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
175 \item \emph{successors} are all nodes that have a control dependency on this node.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
176 \item \emph{predecessors} are all nodes that this node has control dependencies on, this is regarded as the inverse of successors.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
177 \end{itemize}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
178 \item Only inputs and successors can be changed, and changes to them will update the usages and predecessors.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
179 \item The Node class needs to provide facilities for subclasses to perform actions upon cloning, dependency changes, etc.
2562
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
180 \item Nodes cannot be reassigned to another graph, they are cloned instead \cw{Why should there be the need for more than one graph when compiling a method?}
2561
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
181 \end{itemize}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
182
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
183 \subsubsection{The Graph Data Structure}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
184 \begin{itemize}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
185 \item A graph deals out ids for new nodes and can be queried for the node corresponding to a given id.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
186 \item 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.
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
187 \item Graphs are
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
188 \end{itemize}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
189
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
190 \subsection{Frame States}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
191 Frame states capture the state of the program, in terms of the source representation (e.g., Java state: local variables, expressions, ...).
2576
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
192 Whenever a safepoint is reached or \cw{why is that an ``or'', both is basically the same} \ls{uncommon traps can be introduced at other points, e.g., at an if branch that isn't compiled} a deoptimization is needed a valid frame state needs to be available.
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
193 A frame state is valid as long as the program performs only actions that can safely be reexecuted (e.g., operations on local variables, loads, etc.).
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
194 Thus, frame states need only be generated for bytecodes that cannot be reexecuted:
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
195
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
196 \begin{itemize}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
197 \item Array stores: {\tt IASTORE, LASTORE, FASTORE, \\DASTORE, AASTORE, BASTORE, CASTORE, SASTORE}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
198 \item Field stores: {\tt PUTSTATIC, PUTFIELD}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
199 \item Method calls: {\tt INVOKEVIRTUAL, INVOKESPECIAL, \\INVOKESTATIC, INVOKEINTERFACE}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
200 \item Memory allocations: {\tt NEW, NEWARRAY, ANEWARRAY, \\MULTIANEWARRAY}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
201 \item Synchronization: {\tt MONITORENTER, MONITOREXIT}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
202 \end{itemize}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
203
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
204 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).
2561
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
205
2576
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
206 \begin{digraphenv}{scale=0.5}{fs1}
2577
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
207 \nodetrisplit{store1}{ArrayStore}
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
208 \nodebi{load1}{ArrayLoad}
2576
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
209 \controllabel{store1:succ1}{load1}
2577
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
210 \nodetrisplit{store2}{ArrayStore}
2576
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
211 \control{load1}{store2}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
212 end [shape=plaintext, label="...", width="2.0"]
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
213 store2:succ1:s -> end:n [color=red];
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
214 %
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
215 \nodeframestate{fs1}{FrameState}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
216 \controllabel{store1:succ2}{fs1}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
217 \nodeframestate{fs2}{FrameState}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
218 \controllabel{store2:succ2}{fs2}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
219 \end{digraphenv}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
220
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
221 FrameStates also have data dependencies on the contents of the state: the local variables and the expression stack.
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
222
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
223 \subsection{Deoptimization and Uncommon Traps}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
224 Uncommon trap nodes are not fixed to a certain frame state node, they can move around freely and will always use the correct frame state.
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
225 The node that is guarded by the deoptimization has a data dependency on the trap, and the trap in turn has a data dependency on the condition and on the most distant node that is postdominated by the guarded node.
2561
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
226
2576
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
227 \begin{digraphenv}{scale=0.5}{trap1}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
228 \nodesplit{if}{If}
2577
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
229 \node{split1}{Split}
2576
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
230 \controllabel{if:succ1}{split1}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
231 nop [shape=plaintext, label="..."]
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
232 \control{split1}{nop}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
233 %
2577
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
234 \node{split2}{Split}
2576
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
235 \controllabel{if:succ2}{split2}
2577
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
236 \nodebi{load1}{MemLoad}
2576
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
237 \control{split2}{load1}
2577
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
238 \nodebi{load2}{MemLoad}
2576
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
239 \control{load1}{load2}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
240 \control{load2}{merge}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
241 \node{merge}{Merge}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
242 \control{nop}{merge}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
243 %
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
244 \nodeconst{o1}{obj1}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
245 \nodeconst{o2}{obj2}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
246 \datalabel{load1:in2}{o1}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
247 \datalabel{load2:in2}{o2}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
248 \nodetrap{trap}{Trap}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
249 \node{cmpnull}{IsNull}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
250 \data{cmpnull}{o2}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
251 \datalabel{trap:in2}{cmpnull}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
252 \datalabel{load2:in1}{trap}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
253 \datalabel{trap:in1}{split2}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
254 \end{digraphenv}
2561
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
255
2577
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
256 \emph{\small In this example, the second load is guarded by an uncommon trap, because its receiver might be null (the receiver of the load is assumed to be non-null).
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
257 The trap is anchored to the control split, because as soon as this node is executed the second load must be executed as well.
2576
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
258 In the final scheduling the trap can be placed before or after the first load.}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
259
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
260 Another type of uncommon trap is a guard, which is used to remove branches that have a very low execution frequency from the compiled code.
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
261
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
262 \begin{digraphenv}{scale=0.5}{trap2}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
263 start [shape=plaintext, label="..."]
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
264 start2 [shape=plaintext, label=""]
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
265 start3 [shape=plaintext, label=""]
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
266 \control{start}{guard}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
267 \node{guard}{Guard}
2577
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
268 \nodebi{load1}{MemLoad}
2576
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
269 \control{guard}{load1}
2577
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
270 \control{load1}{nop}
2576
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
271 nop [shape=plaintext, label="..."]
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
272 %
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
273 \nodetrap{trap}{Trap}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
274 \datalabel{trap:in1}{start2}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
275 \datalabel{trap:in2}{start3}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
276 \data{guard}{trap}
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
277 \end{digraphenv}
2561
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
278
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
279
2576
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
280 \emph{\small In this example the If from the previous example was replaced by a guard and an uncommon trap.
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
281 The guard takes the place of the If in the control flow, and is connected to the trap node.
2577
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
282 The uncommon trap is now anchored to the most distant node of which the If was a postdominator.}
2576
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
283
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
284 At some point during the compilation, trap nodes need to be fixed, which means that appropriate data and control dependencies will be inserted so that they cannot move outside the scope of the associated frame state.
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
285 This will generate deoptimization-free zones that can be targeted by the most aggressive optimizations.
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
286 A simple algorithm for this removal of FrameStates would be to move all traps as far upwards as possible.
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
287
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
288
2577
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
289 Multiple Traps with the same condition and anchor can be merged:
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
290
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
291 \begin{digraphenv}{scale=0.5}{trap3}
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
292 \nodesplit{if}{If}
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
293 \node{split1}{Split}
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
294 \controllabel{if:succ1}{split1}
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
295 nop [shape=plaintext, label="..."]
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
296 \control{split1}{nop}
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
297 %
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
298 \node{split2}{Split}
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
299 \controllabel{if:succ2}{split2}
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
300 \nodebi{load1}{MemLoad}
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
301 \control{split2}{load1}
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
302 \nodebi{load2}{MemLoad}
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
303 \control{load1}{load2}
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
304 \control{load2}{merge}
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
305 \node{merge}{Merge}
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
306 \control{nop}{merge}
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
307 %
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
308 \nodeconst{o}{obj}
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
309 \datalabel{load1:in2}{o}
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
310 \datalabel{load2:in2}{o}
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
311 \nodetrap{trap}{Trap}
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
312 \node{cmpnull}{IsNull}
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
313 \data{cmpnull}{o}
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
314 \datalabel{trap:in2}{cmpnull}
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
315 \datalabel{load2:in1}{trap}
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
316 \datalabel{load1:in1}{trap}
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
317 \datalabel{trap:in1}{split2}
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
318 \end{digraphenv}
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
319
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
320 Also, if two Traps that are anchored to the true and false branch of the same If have the same condition, they can be merged, so that the resulting Trap is anchored at the most distant node of which the If is a postdominator.
ac2029d0898f doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents: 2576
diff changeset
321
2576
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
322 %Frame states should be represented using a delta-encoding.
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
323 %This will make them significantly smaller and will make inlining, etc. much easier.
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
324 %In later compilation phases unnecessary frame states might be removed, using a mark-and-merge algorithm.
2561
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
325
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
326 \subsection{Graph Building}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
327 \begin{itemize}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
328 \item The graph built by the initial parser (called \emph{GraphBuilder}) should be as close to the source representation (bytecode, ...) as possible.
2562
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
329 \item All nodes should be able to immediately lower themselves to a machine-level representation. \cw{What is that? You mean every node has x86 specific code that spits out machine code? Hope you are joking...} This allows for easier compiler development, and also leads to a compiler that is very flexible in the amount of optimizations it performs (e.g. recompilation of methods with more aggressive optimizations).
2561
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
330 \item
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
331 \end{itemize}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
332
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
333 \subsection{Graphical Representation}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
334 The graphs in this document use the following node layout:
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
335
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
336 \begin{digraphenv}{scale=0.5}{layout01}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
337 \node{node1}{nop}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
338 \nodebi{node2}{+}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
339 \nodetri{node3}{phi}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
340 \nodesplit{node4}{if}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
341 \end{digraphenv}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
342
2562
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
343 \cw{That doesn't compile with my latex. What do I have to do to get it working?}
2576
c59db1f02893 doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents: 2569
diff changeset
344 \ls{graphviz needs to be installed, and pdflatex needs to be started with -shell-escape}
2562
0023bd42eefe comments
christian.wimmer@oracle.com
parents: 2561
diff changeset
345
2561
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
346 Red arrows always represents control dependencies, while black arrows represent data dependencies:
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
347
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
348 \begin{digraphenv}{scale=0.5}{layout1}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
349 \node{a}{a}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
350 \node{b}{b}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
351 \nodesplit{if}{if}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
352 \node{nop}{nop}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
353 \nodebi{add}{+}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
354 \controllabel{if:succ1}{nop}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
355 \controllabel{if:succ2}{add}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
356 \datalabel{add:in1}{a}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
357 \datalabel{add:in2}{b}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
358 \end{digraphenv}
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
359
765dd54244a6 Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents: 2517
diff changeset
360
2517
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
361
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
362 \end{document}