Mercurial > hg > truffle
annotate graal/com.oracle.max.graal.doc.initial/graal_compiler.tex @ 3186:0baa318b28f5
Merge
author | Josef Haider <josef.haider@khg.jku.at> |
---|---|
date | Thu, 07 Jul 2011 18:31:25 +0200 |
parents | 4db4e8cb6bd6 |
children |
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} |
2678
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
2 \usepackage{listings} |
2517
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
3 \usepackage[pdftex]{graphicx} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
4 \usepackage{environ} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
5 \usepackage{amsmath} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
6 \usepackage{amsfonts} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
7 \usepackage[english]{babel} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
8 \usepackage[utf8]{inputenc} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
9 \usepackage{lmodern} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
10 \usepackage[T1]{fontenc} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
11 \usepackage{color} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
12 |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
13 \input{graphdrawing} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
14 |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
15 \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
|
16 |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
17 \newcommand{\Sa}{{\Large$^*$}} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
18 \newcommand{\Sb}{{\Large$^\dag$}} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
19 \newcommand{\Sc}{{\Large$^\S$}} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
20 |
2562 | 21 |
22 \newcommand{\mynote}[2]{ | |
23 \textcolor{red}{\fbox{\bfseries\sffamily\scriptsize#1} | |
24 {\small\textsf{\emph{#2}}} | |
25 \fbox{\bfseries\sffamily\scriptsize }}} | |
26 | |
27 \newcommand\TODO[1]{\mynote{TODO}{#1}} | |
28 \newcommand\cw[1]{\mynote{CW}{#1}} | |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
29 \newcommand\ls[1]{\mynote{LS}{#1}} |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
30 \newcommand\nodename[1]{\texttt{#1}} |
2562 | 31 |
2896
5d4aa5672d3d
Small fix to design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2892
diff
changeset
|
32 \hyphenpenalty=0 |
5d4aa5672d3d
Small fix to design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2892
diff
changeset
|
33 \doublehyphendemerits=0 |
5d4aa5672d3d
Small fix to design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2892
diff
changeset
|
34 \finalhyphendemerits=0 |
5d4aa5672d3d
Small fix to design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2892
diff
changeset
|
35 \clubpenalty10000 |
5d4aa5672d3d
Small fix to design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2892
diff
changeset
|
36 \widowpenalty10000 |
2562 | 37 |
38 | |
2517
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
39 \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
|
40 |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
41 \journalname{Graal Compiler Design} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
42 \def\makeheadbox{{% |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
43 \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
|
44 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
|
45 \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
|
46 \kern3pt}\hfil\kern3pt\vrule}\hrule}% |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
47 \hss}}} |
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 \begin{document} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
50 |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
51 \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
|
52 \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
|
53 |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
54 \date{Created: \today} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
55 |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
56 \title{The Graal Compiler} |
2604 | 57 \subtitle{Design and Strategy \\ \textcolor{red}{work in progress (Oracle internal)}} |
2517
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
58 |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
59 \maketitle |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
60 |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
61 \abstract{ |
2688
3396862d4cee
Minor design doc edits.
Doug Simon <doug.simon@oracle.com>
parents:
2687
diff
changeset
|
62 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. |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
63 The compiler should work with the Maxine VM and the HotSpot VM. |
2589
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
64 This document contains information about the proposed design and strategy for developing the compiler.} |
2561
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{Context} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
67 |
2618
15774da89658
Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2604
diff
changeset
|
68 In 2009, the Maxine team started with creating C1X, a Java port of the HotSpot client compiler, and integrated it into the Maxine VM. |
2604 | 69 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. |
70 This compiler-runtime interface enables the use of one compiler for multiple VMs. | |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
71 In June 2010, we started integrating C1X into the HotSpot VM and we called the resulting system Graal~VM. |
2618
15774da89658
Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2604
diff
changeset
|
72 Currently, the Graal~VM is fully functional and runs benchmarks (SciMark, DaCapo) at a similar speed as the HotSpot client compiler. |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
73 |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
74 \section{Goals} |
2589
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
75 The compiler effort aims at rewriting the high-level intermediate representation of C1X with two main goals: |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
76 \begin{description} |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
77 \item[Modularity:] |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
78 A modular design of the compiler should simplify the implementation of new languages, new back-ends, and new optimizations. |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
79 \item[Peak Performance:] |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
80 A more powerful intermediate representation should enable the implementation of aggressive optimizations that impact the peak performance of the resulting machine code. |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
81 In terms of startup performance, we want to orientate ourselves to the HotSpot server compiler configuration. |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
82 \end{description} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
83 |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
84 \section{Design} |
2589
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
85 For the implementation of the compiler, we rely on the following design decisions: |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
86 \begin{description} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
87 \item[Graph Representation:] |
2562 | 88 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
|
89 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
|
90 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
|
91 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. |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
92 It is possible to replace a node with another node without traversing the full graph. |
2588
26ecba0ead6d
Update on doc.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2578
diff
changeset
|
93 The graph does not allow data flow edge cycles or control flow edge cycles. |
2688
3396862d4cee
Minor design doc edits.
Doug Simon <doug.simon@oracle.com>
parents:
2687
diff
changeset
|
94 We achieve this by explicitly modeling loops (see Section~\ref{sec:loops}). |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
95 \item[Extensibility:] |
2618
15774da89658
Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2604
diff
changeset
|
96 The compiler is extensible by allowing developers to add new compiler phases and new node subclasses without modifying the compiler's sources. |
15774da89658
Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2604
diff
changeset
|
97 A node has an abstract way of expressing its semantics and new compiler phases can ask compiler nodes for their properties and capabilities. |
2588
26ecba0ead6d
Update on doc.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2578
diff
changeset
|
98 We use the ``everything is an extension'' concept. |
26ecba0ead6d
Update on doc.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2578
diff
changeset
|
99 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
|
100 \item[Detailing:] |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
101 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
|
102 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
|
103 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). |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
104 \item[Generality:] |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
105 The compiler does not require Java as its input. |
2688
3396862d4cee
Minor design doc edits.
Doug Simon <doug.simon@oracle.com>
parents:
2687
diff
changeset
|
106 This is achieved by having a graph as the starting point of the compilation and not a Java bytecode array. |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
107 Building the graph from the Java bytecodes must happen before giving a method to the compiler. |
2618
15774da89658
Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2604
diff
changeset
|
108 This enables front-ends for different languages (e.g., Ruby or JavaScript) to provide their own graph. |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
109 The support for different languages is constrained by the following two conditions: We only support structured control flow, and the dynamic type system of the language must be expressible using the RiType class. |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
110 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. |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
111 \end{description} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
112 |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
113 \section{Milestones} |
2597
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
114 \label{sec:mile} |
2688
3396862d4cee
Minor design doc edits.
Doug Simon <doug.simon@oracle.com>
parents:
2687
diff
changeset
|
115 The compiler is being developed starting from the current C1X source code base. |
3396862d4cee
Minor design doc edits.
Doug Simon <doug.simon@oracle.com>
parents:
2687
diff
changeset
|
116 This helps us test the compiler at every intermediate development step on a variety of Java benchmarks. |
3396862d4cee
Minor design doc edits.
Doug Simon <doug.simon@oracle.com>
parents:
2687
diff
changeset
|
117 We define the following development milestones (see Section~\ref{sec:conclusions} for planned dates): |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
118 \begin{description} |
2688
3396862d4cee
Minor design doc edits.
Doug Simon <doug.simon@oracle.com>
parents:
2687
diff
changeset
|
119 \item[M1:] We have a fully working Graal~VM version with a stripped down C1X compiler that does not perform any optimization. |
2589
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
120 \item[M2:] We modified the high-level intermediate representation to be based on the compiler graph data structure. |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
121 \item[M3:] We have reimplemented and reenabled compiler optimizations in the compiler that previously existed in C1X. |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
122 \item[M4:] We have reintegrated the new compiler into the Maxine VM and can use it as a Maxine VM bootstrapping compiler. |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
123 \end{description} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
124 |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
125 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
|
126 \begin{itemize} |
2589
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
127 \item Removal of the XIR template mechanism and replacement with a snippet mechanism that works with the compiler graph. |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
128 \item Improvements for peak performance (loop optimizations, escape analysis, bounds check elimination, processing additional interpreter runtime feedback). |
2604 | 129 \item Implementation of a prototype front-end for a different language, e.g., JavaScript. |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
130 \end{itemize} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
131 |
2678
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
132 \section{Project Source Structure} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
133 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.max.graal}). |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
134 |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
135 \begin{description} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
136 \item[graph] contains the abstract node implementation, the graph implementation and all the associated tools and auxiliary classes. |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
137 \item[nodes] contains the implementation of known basic nodes (e.g., phi nodes, control flow nodes, \ldots). |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
138 Additional node classes should go into separate projects and be specializations of the known basic nodes. |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
139 \item[java] contains code for building graphs from Java bytecodes and Java-specific nodes. |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
140 \item[opt] contains optimizations such as global value numbering or conditional constant propagation. |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
141 \item[compiler] contains the compiler, including: |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
142 \begin{itemize} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
143 \item Scheduling of the compilation phases. |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
144 \item Implementation of the \emph{compiler interface} (CI). |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
145 \item Implementation of the final compilation phase that produces the low-level representation. |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
146 \item Machine code creation, including debug info. |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
147 \end{itemize} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
148 \end{description} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
149 |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
150 |
2597
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
151 \section{Graph} |
2589
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
152 |
2597
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
153 The \emph{intermediate representation}~(IR) of the compiler is designed as a directed graph. |
2688
3396862d4cee
Minor design doc edits.
Doug Simon <doug.simon@oracle.com>
parents:
2687
diff
changeset
|
154 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. |
3396862d4cee
Minor design doc edits.
Doug Simon <doug.simon@oracle.com>
parents:
2687
diff
changeset
|
155 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. |
2589
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
156 |
2597
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
157 The nodes of the graph have the following properties: |
2589
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
158 \begin{itemize} |
2597
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
159 \item Each node is always associated with a single graph and this association is immutable. |
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
160 \item Each node has an immutable id that is unique within its associated graph. |
2604 | 161 \item Nodes can have a data dependency, which means that one node requires the result of another 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. |
2597
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
162 \item Nodes can have a control flow dependency, which means that the execution of one node will be followed by the execution of another node. This includes conditional execution, memory access serialization and other reasons, and again introduces a partial order to the set of nodes. |
2589
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
163 \item Nodes can only have data and control dependencies to nodes which belong to the same graph. |
2618
15774da89658
Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2604
diff
changeset
|
164 \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 in a drawing of the graph. Situations that normally incur cycles (like loops) are represented by special nodes (see Section~\ref{sec:loops}). |
2619 | 165 \item Ordering between nodes is specified only to the extent which is required to correctly express the semantics of a given program. This gives the compiler flexibility for the possible scheduling of a node and therefore wiggle room for optimizations. For algorithms that require a fixed ordering of nodes, a temporary schedule can always be generated. |
2597
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
166 \item Both data and control dependencies can be traversed in both directions, so that each node can be traversed in four directions (see Figure~\ref{fig:directions}): |
2589
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
167 \begin{itemize} |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
168 \item \emph{inputs} are all nodes that this node has data dependencies on. |
2604 | 169 \item \emph{usages} are all nodes whose inputs contain this node. |
170 \item \emph{successors} are all nodes that have to be after this node in control flow. | |
171 \item \emph{predecessors} are all nodes whose successors contain this node. | |
2589
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
172 \end{itemize} |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
173 \item Only inputs and successors can be changed, and changes to them will update the usages and predecessors. |
2597
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
174 \item Every node must be able to support cloning and serialization. |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
175 \item The edges of a node also define \textit{emitted-before} and \textit{emitted-after} relationships as shown in Figure~\ref{fig:directions}. |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
176 They mean that the machine code for one node is emitted before or after the machine code of another node. |
2589
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
177 \end{itemize} |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
178 |
2896
5d4aa5672d3d
Small fix to design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2892
diff
changeset
|
179 \begin{figure}[ht] |
2597
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
180 \centering |
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
181 \begin{digraphenv}{scale=0.5}{graphdirections} |
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
182 \node{node1}{Node} |
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
183 \textnode{inputs}{inputs} |
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
184 \textnode{usages}{usages} |
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
185 \textnode{successors}{successors} |
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
186 \textnode{predecessors}{predecessors} |
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
187 \data{node1}{inputs} |
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
188 \control{node1}{successors} |
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
189 \data{usages}{node1} |
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
190 \control{predecessors}{node1} |
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
191 \node{node2}{Node} |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
192 \textnode{before}{emitted-before} |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
193 \textnode{after}{emitted-after} |
2597
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
194 \data{node2}{before} |
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
195 \control{node2}{after} |
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
196 \data{after}{node2} |
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
197 \control{before}{node2} |
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
198 \end{digraphenv} |
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
199 \caption{A node and its edges.} |
2604 | 200 \label{fig:directions} |
2597
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
201 \end{figure} |
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
202 |
2687
77e106760633
Additional subsection on inlining.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2685
diff
changeset
|
203 \subsection{Inlining} |
77e106760633
Additional subsection on inlining.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2685
diff
changeset
|
204 Inlining is always performed by embedding one graph into another graph. |
77e106760633
Additional subsection on inlining.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2685
diff
changeset
|
205 Nodes cannot be reassigned to another graph, they are cloned instead. |
77e106760633
Additional subsection on inlining.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2685
diff
changeset
|
206 Therefore, inlining is performed by copying and rewiring the nodes of the inlined method into the graph of the outer method. |
77e106760633
Additional subsection on inlining.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2685
diff
changeset
|
207 While the copying will decrease compilation performance, it enables us to cache the graph for the inlined method, optimize it independently from the outer method, and use the optimized graph for subsequent inlinings. |
77e106760633
Additional subsection on inlining.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2685
diff
changeset
|
208 We do not expect a significant negative impact on overall compilation performance. |
77e106760633
Additional subsection on inlining.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2685
diff
changeset
|
209 |
77e106760633
Additional subsection on inlining.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2685
diff
changeset
|
210 We are able to perform the inlining at any point during the compilation of a method and can therefore selectively expand the inlining if a certain optimization turns out to depend on the inlining of a method. |
77e106760633
Additional subsection on inlining.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2685
diff
changeset
|
211 An example for this would be when the escape analysis finds out that a certain object only escapes because of one method call and this method call is not inlined, because the penalty was to high. |
77e106760633
Additional subsection on inlining.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2685
diff
changeset
|
212 In this case, we can chose to nevertheless inline the method in order to increase the chances for finding out that the object does not escape. |
77e106760633
Additional subsection on inlining.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2685
diff
changeset
|
213 |
2678
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
214 \section{Control Flow} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
215 |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
216 Control flow is managed in a way where the predecessor node contains direct pointers to its successor nodes. |
2678
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
217 This is opposite to the approach taken in the server compiler, where control flow and data flow edges point in the same direction. |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
218 The advantage that we see in our approach is that there is no need for projection nodes in case of control flow splits. |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
219 An \texttt{If} node can directly point to its true and false successors without any intermediate nodes. |
2678
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
220 This makes the graph more compact and simplifies graph traversal. |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
221 We distinguish between \textit{fixed nodes} that are directly embedded in the control flow and \textit{floating nodes} whose position in the control flow may vary. |
2678
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
222 |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
223 Listing~\ref{lst:cfg2} shows an example Java program with an if statement where both paths do not contain any node with side effects. |
2896
5d4aa5672d3d
Small fix to design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2892
diff
changeset
|
224 Figure~\ref{fig:loopexits} shows the corresponding compiler graph. |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
225 The \texttt{If} node can directly point its true and false successors to a \texttt{Merge} node. |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
226 A \texttt{Phi} node that selects the appropriate value is appended to the \texttt{Merge} node. |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
227 The \texttt{Return} node then has a data dependency on the \texttt{Phi} node. |
2678
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
228 |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
229 \begin{lstlisting}[label=lst:cfg2, caption=Control flow in the graph., captionpos=b] |
2678
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
230 if (condition) { return 0; } |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
231 else { return 1; } |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
232 \end{lstlisting} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
233 |
2896
5d4aa5672d3d
Small fix to design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2892
diff
changeset
|
234 \begin{figure}[ht] |
2678
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
235 \centering |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
236 \begin{digraphenv}{scale=0.5}{cfg2} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
237 \textnode{entry}{Entry} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
238 \textnode{condition}{condition} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
239 \textnode{const0}{0} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
240 \textnode{const1}{1} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
241 \nodesplit{if}{If} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
242 \control{entry}{if} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
243 \controllabel{if:succ1}{merge} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
244 \controllabel{if:succ2}{merge} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
245 \data{if}{condition} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
246 \node{merge}{Merge} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
247 \node{return}{Return} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
248 \nodetri{phi}{Phi} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
249 \datalabel{phi:in1}{merge} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
250 \datalabel{phi:in2}{const0} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
251 \datalabel{phi:in3}{const1} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
252 \data{return}{phi} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
253 \control{merge}{return} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
254 \end{digraphenv} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
255 \caption{A simple loop with two exits.} |
2896
5d4aa5672d3d
Small fix to design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2892
diff
changeset
|
256 \label{fig:loopexits} |
2678
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
257 \end{figure} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
258 |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
259 \section{Exceptions} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
260 \label{sec:Exceptions} |
2597
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
261 |
2896
5d4aa5672d3d
Small fix to design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2892
diff
changeset
|
262 We do not throw runtime exceptions (e.g., \texttt{IndexOutOf\-BoundsException}, \texttt{Null\-Pointer\-Exception}, or \texttt{Out\-Of\-Memory\-Exception}), but deoptimize instead. |
2678
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
263 This reduces the places in the compiled code where an exact bytecode location and debug information must be known. |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
264 Additionally, this greatly reduces the number of exception handler edges in the compiled code. |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
265 The main advantage of this technique is however, that we are free in moving around bounds checks, memory allocation, memory accesses with implicit null checks, etc. |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
266 |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
267 There are only two kinds of nodes that need explicit exception edges, because they are the only nodes that can throw exceptions in compiled code: \texttt{Throw} nodes and \texttt{Invoke} nodes. |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
268 They are modelled as nodes with an additional control flow continuation that points to an \texttt{ExceptionDispatch} node. |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
269 The exception dispatch node decides based on the type of the exception object whether the control should flow to the catch handler or to another exception dispatch. |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
270 If there is no catch handler in the currently compiled method, then the control flows into the \texttt{Unwind} node that handles the exception by forwarding it to the caller. |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
271 Listing~\ref{lst:exc1} shows an example Java program with nested try blocks and Figure \ref{fig:exc1} shows the corresponding compiler graph. |
2678
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
272 |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
273 \begin{lstlisting}[label=lst:exc1, caption=Exception dispatch in the compiler graph., captionpos=b] |
2678
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
274 try { m1(); |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
275 try { m2(); |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
276 } catch(ExtendedException e) { ... } |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
277 m3(); |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
278 throw exception; |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
279 } catch(Exception e) { ... } |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
280 \end{lstlisting} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
281 |
2896
5d4aa5672d3d
Small fix to design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2892
diff
changeset
|
282 \begin{figure}[ht] |
2678
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
283 \centering |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
284 \begin{digraphenv}{scale=0.5}{exc1} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
285 \textnode{entry}{Entry} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
286 \textnode{catch1}{catch1} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
287 \textnode{catch2}{catch2} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
288 \nodesplit{m1}{Invoke m1} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
289 \nodesplit{m2}{Invoke m2} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
290 \nodesplit{m3}{Invoke m3} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
291 \nodesplit{dispatch1}{ExceptionDispatch} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
292 \nodesplit{dispatch2}{ExceptionDispatch} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
293 \node{throw}{Throw} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
294 \node{unwind}{Unwind} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
295 \control{entry}{m1} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
296 \controllabel{m1:succ1}{m2} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
297 \controllabel{m1:succ2}{dispatch2} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
298 \controllabel{m2:succ1}{m3} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
299 \controllabel{m2:succ2}{dispatch1} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
300 \controllabel{m3:succ1}{throw} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
301 \controllabel{m3:succ2}{dispatch2} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
302 \control{throw}{dispatch2} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
303 \controllabel{dispatch1:succ2}{catch1} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
304 \controllabel{dispatch1:succ1}{dispatch2} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
305 \controllabel{dispatch2:succ2}{catch2} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
306 \controllabel{dispatch2:succ1}{unwind} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
307 \end{digraphenv} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
308 \caption{A simple loop with two exits.} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
309 \label{fig:exc1} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
310 \end{figure} |
2597
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
311 |
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
312 \section{Loops} |
2588
26ecba0ead6d
Update on doc.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2578
diff
changeset
|
313 \label{sec:loops} |
2618
15774da89658
Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2604
diff
changeset
|
314 Loops form a first-class construct in the IR that is expressed by specialized IR nodes during all optimization phases. |
15774da89658
Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2604
diff
changeset
|
315 We only compile methods with a control flow where every loop has a single entry point. |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
316 This entry point is a \nodename{LoopBegin} node. |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
317 This node is connected to a \nodename{LoopEnd} node that merges all control flow paths that do not exit the loop. |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
318 The edge between the \nodename{LoopBegin} and the \nodename{LoopEnd} is the backedge of the loop. |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
319 It goes from the beginning to the end in order to make the graph acyclic. |
2618
15774da89658
Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2604
diff
changeset
|
320 An algorithm that traverses the control flow has to explicitely decide whether it wants to incorporate backedges (i.e., special case of the treatment of \nodename{LoopEnd}) or ignore them. |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
321 Figure \ref{fig:loop1} shows a simple example with a loop with a single entry and two exits. |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
322 |
2896
5d4aa5672d3d
Small fix to design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2892
diff
changeset
|
323 \begin{figure}[ht] |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
324 \centering |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
325 \begin{digraphenv}{scale=0.5}{layout1} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
326 \textnode{BeforeLoop}{Loop entry} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
327 \textnode{Exit1}{First loop exit} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
328 \textnode{Exit2}{Second loop exit} |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
329 \node{LoopBegin}{LoopBegin} |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
330 \node{LoopEnd}{LoopEnd} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
331 \nodesplit{If1}{If} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
332 \nodesplit{If2}{If} |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
333 \data{LoopEnd}{LoopBegin} |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
334 \control{LoopBegin}{If1} |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
335 \controllabel{If1:succ1}{If2} |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
336 \controllabel{If2:succ1}{LoopBody} |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
337 \textnode{LoopBody}{Loop body} |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
338 \control{LoopBody}{LoopEnd} |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
339 \controllabel{BeforeLoop}{LoopBegin} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
340 \controllabel{If1:succ2}{Exit1} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
341 \controllabel{If2:succ2}{Exit2} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
342 \end{digraphenv} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
343 \caption{A simple loop with two exits.} |
2604 | 344 \label{fig:loop1} |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
345 \end{figure} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
346 |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
347 \subsection{Loop Phis} |
2688
3396862d4cee
Minor design doc edits.
Doug Simon <doug.simon@oracle.com>
parents:
2687
diff
changeset
|
348 Data flow in loops is modeled with special phi nodes at the beginning and the end of the loop. |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
349 The \nodename{LoopEnd} node merges every value that flows into the next loop iteration in associated \nodename{LoopEndPhi} nodes. |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
350 A corresponding \nodename{LoopBeginPhi} node that is associated with the loop header has a control flow dependency on the \nodename{LoopEndPhi} node. |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
351 Listing~\ref{lst:loop} shows a simple counting loop that is used as an example in the rest of this section. |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
352 Figure~\ref{fig:loop2} shows how the loop is modelled immediately after building the graph. |
2678
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
353 |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
354 \begin{lstlisting}[label=lst:loop, caption=Loop example that counts from 0 to n-1., captionpos=b] |
2678
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
355 for(int i=0; i<n; ++i) { } |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
356 \end{lstlisting} |
b9b0a0aa7ee8
Added addition sections on control flow and exceptions.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2619
diff
changeset
|
357 |
2896
5d4aa5672d3d
Small fix to design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2892
diff
changeset
|
358 \begin{figure}[ht] |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
359 \centering |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
360 \begin{digraphenv}{scale=0.5}{layout2} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
361 \textnode{BeforeLoop}{Loop entry} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
362 \textnode{Exit}{Loop exit} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
363 \textnode{n}{n} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
364 \textnode{Constant0}{0} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
365 \textnode{Constant1}{1} |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
366 \node{LoopBegin}{LoopBegin} |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
367 \node{LoopEnd}{LoopEnd} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
368 \nodesplit{If1}{If} |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
369 \data{LoopEnd}{LoopBegin} |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
370 \control{LoopBegin}{If1} |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
371 \nodebi{Compare}{<} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
372 \nodebi{LoopBeginPhi}{LoopBeginPhi} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
373 \nodebi{Add}{+} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
374 \datalabel{Add:in1}{LoopBeginPhi} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
375 \datalabel{Add:in2}{Constant1} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
376 \nodebi{LoopEndPhi}{LoopEndPhi} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
377 \control{LoopBeginPhi}{LoopEndPhi} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
378 \data{LoopEndPhi:in1}{LoopEnd} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
379 \data{LoopEndPhi:in2}{Add} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
380 \datalabel{LoopBeginPhi:in1}{LoopBegin} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
381 \datalabel{LoopBeginPhi:in2}{Constant0} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
382 \datalabel{Compare:in1}{LoopBeginPhi} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
383 \datalabel{Compare:in2}{n} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
384 \data{If1}{Compare} |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
385 \controllabel{If1:succ1}{LoopBody} |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
386 \textnode{LoopBody}{Loop body} |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
387 \control{LoopBody}{LoopEnd} |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
388 \controllabel{BeforeLoop}{LoopBegin} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
389 \controllabel{If1:succ2}{Exit} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
390 \end{digraphenv} |
2589
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
391 \caption{Graph for a loop counting from 0 to n-1.} |
2604 | 392 \label{fig:loop2} |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
393 \end{figure} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
394 |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
395 \subsection{Loop Counters} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
396 The compiler is capable of recognizing variables that are only increased within a loop. |
2618
15774da89658
Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2604
diff
changeset
|
397 A potential overflow of such a variable is prohibited with a guard before the loop (this is not necessary in this example, because the loop variable cannot overflow). |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
398 Figure \ref{fig:loop3} shows the compiler graph of the example loop after the loop counter transformation. |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
399 |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
400 |
2896
5d4aa5672d3d
Small fix to design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2892
diff
changeset
|
401 \begin{figure}[ht] |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
402 \centering |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
403 \begin{digraphenv}{scale=0.5}{layout3} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
404 \textnode{BeforeLoop}{Loop entry} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
405 \textnode{Exit}{Loop exit} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
406 \textnode{n}{n} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
407 \textnode{Constant0}{0} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
408 \textnode{Constant1}{1} |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
409 \node{LoopBegin}{LoopBegin} |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
410 \node{LoopEnd}{LoopEnd} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
411 \nodesplit{If1}{If} |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
412 \data{LoopEnd}{LoopBegin} |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
413 \control{LoopBegin}{If1} |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
414 \nodebi{Compare}{<} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
415 \nodetri{LoopCounter}{LoopCounter} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
416 \datalabel{LoopCounter:in1}{LoopBegin} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
417 \datalabeltext{LoopCounter:in2}{Constant0}{init} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
418 \datalabeltext{LoopCounter:in3}{Constant1}{stride} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
419 \datalabel{Compare:in1}{LoopCounter} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
420 \datalabel{Compare:in2}{n} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
421 \data{If1}{Compare} |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
422 \controllabel{If1:succ1}{LoopBody} |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
423 \textnode{LoopBody}{Loop body} |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
424 \control{LoopBody}{LoopEnd} |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
425 \controllabel{BeforeLoop}{LoopBegin} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
426 \controllabel{If1:succ2}{Exit} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
427 \end{digraphenv} |
2589
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
428 \caption{Graph after loop counter transformation.} |
2604 | 429 \label{fig:loop3} |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
430 \end{figure} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
431 |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
432 \subsection{Bounded Loops} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
433 |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
434 If the total maximum number of iterations of a loop is fixed, then the loop is converted into a bounded loop. |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
435 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. |
2604 | 436 If the total number of iterations is reached, the loop is exited directly from the loop header. |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
437 The representation of the bounded loop in the graph should support reasoning about the loop, but does not specify how the loop will later be converted to machine code. |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
438 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. |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
439 Figure \ref{fig:loop4} shows the compiler graph of the example loop after the bounded loop transformation. |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
440 If there are no other exits out of the loop, then the number of iterations specified as the input to the bounded loop node is also the exact number of loop iterations. |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
441 Loops with the same number of iterations can be merged into a single loop. |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
442 We also want to support loop splitting in order to find simple loops that are candidates for vectorization. |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
443 |
2896
5d4aa5672d3d
Small fix to design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2892
diff
changeset
|
444 \begin{figure}[ht] |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
445 \centering |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
446 \begin{digraphenv}{scale=0.5}{layout4} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
447 \textnode{BeforeLoop}{Loop entry} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
448 \textnode{Exit}{Loop exit} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
449 \textnode{n}{n} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
450 \textnode{Constant0}{0} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
451 \textnode{Constant1}{1} |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
452 \nodesplit{LoopBegin}{BoundedLoopBegin} |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
453 \node{LoopEnd}{LoopEnd} |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
454 \data{LoopEnd}{LoopBegin} |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
455 \controllabel{LoopBegin:succ1}{LoopBody} |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
456 \textnode{LoopBody}{Loop body} |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
457 \control{LoopBody}{LoopEnd} |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
458 \controllabel{LoopBegin:succ2}{Exit} |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
459 \nodetri{LoopCounter}{LoopCounter} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
460 \datalabel{LoopCounter:in1}{LoopBegin} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
461 \datalabeltext{LoopCounter:in2}{Constant0}{init} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
462 \datalabeltext{LoopCounter:in3}{Constant1}{stride} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
463 \data{LoopBegin}{n} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
464 \controllabel{BeforeLoop}{LoopBegin} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
465 \end{digraphenv} |
2589
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
466 \caption{Graph after bounded loop transformation.} |
2604 | 467 \label{fig:loop4} |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
468 \end{figure} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
469 |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
470 \subsection{Vectorization} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
471 |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
472 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. |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
473 We replace the loop header with a normal node that produces a vector of values from 0 to the number of loop iterations minus 1. |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
474 The loop counters are replaced with \texttt{VectorAdd} and \texttt{VectorMul} nodes. |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
475 The vectorization is only possible if every node of the loop can be replaced with a corresponding vector node. |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
476 Figure \ref{fig:loop5} shows the compiler graph of the example loop after vectorization. |
2604 | 477 The vector nodes all work on an ordered list of integer values and are subject to canonicalization and global value numbering like any other node. |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
478 |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
479 |
2896
5d4aa5672d3d
Small fix to design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2892
diff
changeset
|
480 \begin{figure}[ht] |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
481 \centering |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
482 \begin{digraphenv}{scale=0.5}{layout5} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
483 \textnode{Entry}{Entry} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
484 \textnode{Exit}{Exit} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
485 \textnode{n}{n} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
486 \textnode{Constant0}{0} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
487 \textnode{Constant1}{1} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
488 \node{Vector}{Vector} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
489 \nodebi{VectorAdd}{VectorAdd} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
490 \nodebi{VectorMul}{VectorMul} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
491 \control{Entry}{Vector} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
492 \control{Vector}{Exit} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
493 \datalabel{VectorAdd:in1}{Vector} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
494 \datalabel{VectorAdd:in2}{Constant0} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
495 \datalabel{VectorMul:in1}{VectorAdd} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
496 \datalabel{VectorMul:in2}{Constant1} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
497 \data{Vector}{n} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
498 \end{digraphenv} |
2598
e4395464810e
Made graphs smaller.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2597
diff
changeset
|
499 \caption{Graph after vectorization.} |
2604 | 500 \label{fig:loop5} |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
501 \end{figure} |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
502 |
2588
26ecba0ead6d
Update on doc.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2578
diff
changeset
|
503 |
2597
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
504 \section{Frame States} |
2679
07aa0a31fffb
Rewrote frame state to be not-so-Java-specific. Clarified and reduced the usage of the term "node".
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2678
diff
changeset
|
505 A frame state captures the state of the program like it is seen in by an interpreter of the program. |
07aa0a31fffb
Rewrote frame state to be not-so-Java-specific. Clarified and reduced the usage of the term "node".
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2678
diff
changeset
|
506 The frame state contains the information that is local to the current activation and will therefore disappear during SSA-form constructions or other compiler optimizations. |
07aa0a31fffb
Rewrote frame state to be not-so-Java-specific. Clarified and reduced the usage of the term "node".
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2678
diff
changeset
|
507 For Java, the frame state is defined in terms of the Java bytecode specification (i.e., the values of the local variables, the operand stack, and the locked monitors). |
07aa0a31fffb
Rewrote frame state to be not-so-Java-specific. Clarified and reduced the usage of the term "node".
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2678
diff
changeset
|
508 However, a frame state is not a concept specific to Java (e.g., the Crankshaft JavaScript engine uses frame states in their optimizing compiler to model the values of the AST interpreter). |
07aa0a31fffb
Rewrote frame state to be not-so-Java-specific. Clarified and reduced the usage of the term "node".
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2678
diff
changeset
|
509 |
07aa0a31fffb
Rewrote frame state to be not-so-Java-specific. Clarified and reduced the usage of the term "node".
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2678
diff
changeset
|
510 Frame states are necessary to support the deoptimization of the program, which is the precondition for performing aggressive optimizations that use optimistic assumptions. |
07aa0a31fffb
Rewrote frame state to be not-so-Java-specific. Clarified and reduced the usage of the term "node".
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2678
diff
changeset
|
511 Therefore every point in the optimizing compiler that may revert execution back to the interpreter needs a valid frame state. |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
512 However, the point where the interpreter continues execution need not correspond exactly to the execution position of the compiled code, because many Java bytecode nodes can be safely reexecuted. |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
513 Thus, frame states need only be generated for the states after nodes that cannot be reexecuted, because they modify the state of the program. |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
514 Examples for such nodes are: |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
515 |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
516 \begin{itemize} |
2679
07aa0a31fffb
Rewrote frame state to be not-so-Java-specific. Clarified and reduced the usage of the term "node".
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2678
diff
changeset
|
517 \item Array stores (in Java bytecodes {\tt IASTORE, LASTORE, FASTORE, \\DASTORE, AASTORE, BASTORE, CASTORE, SASTORE}) |
07aa0a31fffb
Rewrote frame state to be not-so-Java-specific. Clarified and reduced the usage of the term "node".
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2678
diff
changeset
|
518 \item Field stores (in Java bytecodes {\tt PUTSTATIC, PUTFIELD}) |
07aa0a31fffb
Rewrote frame state to be not-so-Java-specific. Clarified and reduced the usage of the term "node".
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2678
diff
changeset
|
519 \item Method calls (in Java bytecodes {\tt INVOKEVIRTUAL, INVOKESPECIAL, \\INVOKESTATIC, INVOKEINTERFACE}) |
07aa0a31fffb
Rewrote frame state to be not-so-Java-specific. Clarified and reduced the usage of the term "node".
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2678
diff
changeset
|
520 \item Synchronization (in Java bytecodes {\tt MONITORENTER, MONITOREXIT}) |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
521 \end{itemize} |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
522 |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
523 Within the graph a frame state is represented as a node that is attached to the node that caused it to be generated using a control dependency (see Figure~\ref{fig:fs1}). |
2598
e4395464810e
Made graphs smaller.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2597
diff
changeset
|
524 Frame states also have data dependencies on the contents of the state: the local variables and the expression stack. |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
525 |
2604 | 526 The frame state at the method beginning does not have to be explicitely in the graph, because it can always be reconstructed at a later stage. |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
527 We save the frame state at control flow merges if there is at least one frame state on any control flow path between a node and its immediate dominator. |
2604 | 528 |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
529 |
2896
5d4aa5672d3d
Small fix to design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2892
diff
changeset
|
530 \begin{figure}[ht] |
2578 | 531 \centering |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
532 \begin{digraphenv}{scale=0.5}{fs1} |
2577
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
533 \nodetrisplit{store1}{ArrayStore} |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
534 \nodebi{load1}{ArrayLoad} |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
535 \controllabel{store1:succ1}{load1} |
2618
15774da89658
Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2604
diff
changeset
|
536 \nodetrisplit{store2}{FieldStore} |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
537 \control{load1}{store2} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
538 end [shape=plaintext, label="...", width="2.0"] |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
539 store2:succ1:s -> end:n [color=red]; |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
540 % |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
541 \nodeframestate{fs1}{FrameState} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
542 \controllabel{store1:succ2}{fs1} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
543 \nodeframestate{fs2}{FrameState} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
544 \controllabel{store2:succ2}{fs2} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
545 \end{digraphenv} |
2578 | 546 \caption{Simple example using two frame states.} |
2604 | 547 \label{fig:fs1} |
2578 | 548 \end{figure} |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
549 |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
550 |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
551 A deoptimization node needs a valid frame state that specifies the location and state where the interpreter should continue. |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
552 The algorithm for constructing frame states makes sure that every possible location in the graph has a well-defined frame state that can be used by a deoptimization node. |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
553 Therefore, there are no direct links between the deoptimization node and its frame state thus allowing the deoptimization nodes to move freely around. |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
554 |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
555 \subsection{Partial Escape Analysis} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
556 |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
557 A partial escape analysis can help to further reduce the number of frame states. |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
558 A field or array store does not create a new frame state, when the object that is modified did not have a chance to escape between its creation and the store. |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
559 |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
560 Listing~\ref{lst:escape1} shows an example of a method that creates two \texttt{Point} objects, connects them, and returns them. |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
561 The object allocation of the first \texttt{Point} object does not need a frame state. |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
562 We can always reexecute the \texttt{NEW} bytecode again in the interpreter. |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
563 The \texttt{Point} object allocated by the compiler will then simply disappear after the next garbage collection. |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
564 The following field store is a thread-local memory store, because the \texttt{Point} object did not have any chance to escape. |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
565 Same applies to the assignment of the \texttt{next} field and the third field assignment. |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
566 Therefore, the whole method \texttt{getPoint} does not need an explicit frame state, because at any time during execution of this method, we can deoptimize and continue execution in the interpreter at the first bytecode of the method. |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
567 |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
568 \begin{lstlisting}[label=lst:escape1, caption=Example method that needs no frame state., captionpos=b] |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
569 void getPoint() { |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
570 Point p = new Point(); |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
571 p.x = 1; |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
572 p.next = new Point(); |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
573 p.next.x = 2; |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
574 return p; |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
575 } |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
576 \end{lstlisting} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
577 |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
578 The reduction of frame states makes it easier for the compiler to perform memory optimizations like memory access coalescing. |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
579 We believe that this reduction on frame states is the key to effective vectorization and other compiler optimizations where compilers of compilers of unmanaged languages have advantages. |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
580 |
2618
15774da89658
Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2604
diff
changeset
|
581 \subsection{Guards} |
2679
07aa0a31fffb
Rewrote frame state to be not-so-Java-specific. Clarified and reduced the usage of the term "node".
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2678
diff
changeset
|
582 A guard is a node that deoptimizes based on a conditional expression. |
07aa0a31fffb
Rewrote frame state to be not-so-Java-specific. Clarified and reduced the usage of the term "node".
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2678
diff
changeset
|
583 Guards are not attached to a certain frame state, they can move around freely and will always use the correct frame state when the nodes are scheduled (i.e., the last emitted frame state). |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
584 The node that is guarded by the deoptimization has a data dependency on the guard and the guard in turn has a data dependency on the condition. |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
585 A guard may only be executed if it is guaranteed that the guarded node is executed too (if no exceptions are thrown). |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
586 Therefore, we use \texttt{Anchor} nodes after a control flow split and a data dependency from the guard to this anchor. |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
587 The anchor is the most distant node that is postdominated by the guarded node and the guard can be scheduled anywhere between those two nodes. |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
588 This ensures maximum flexibility for the guard node and guarantees that we only deoptimize if the control flow would have reached the guarded node (without taking exceptions into account). |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
589 |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
590 To illustrate the strengths of this approach, we show the graph for the Java code snippet shown in \ref{lst:guard1}. |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
591 The example looks artificial, but in case of method inlining, this is a pattern that is not unlikely to be present in a normal Java program. |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
592 Figure \ref{fig:guard0} shows the compiler graph for the example method after graph building. |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
593 The field stores are both represented by a single node and the null check that is implicitely incorporated in the field store. |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
594 |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
595 \begin{lstlisting}[label=lst:guard1, caption=Example method that demonstrates the strengths of modelling the guards explicitely., captionpos=b] |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
596 void init(Point p) { |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
597 if (p != null) { |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
598 p.x = 0; |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
599 } |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
600 p.y = 0; |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
601 } |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
602 \end{lstlisting} |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
603 |
2896
5d4aa5672d3d
Small fix to design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2892
diff
changeset
|
604 \begin{figure}[ht] |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
605 \centering |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
606 \begin{digraphenv}{scale=0.5}{guard0} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
607 \textnode{entry}{Entry} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
608 \nodesplit{if}{If} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
609 \node{merge}{Merge} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
610 \node{return}{Return} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
611 \node{cmpnull}{NonNull} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
612 \textnode{p}{p} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
613 \textnode{const0}{0} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
614 \nodebisplit{store1}{FieldStore x} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
615 \nodebisplit{store2}{FieldStore y} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
616 \nodeframestate{fs1}{FrameState} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
617 \nodeframestate{fs2}{FrameState} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
618 \datalabel{store1:in1}{p} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
619 \datalabel{store2:in1}{p} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
620 \datalabel{store1:in2}{const0} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
621 \datalabel{store2:in2}{const0} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
622 \control{entry}{if} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
623 \data{if}{cmpnull} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
624 \controllabel{if:succ1}{merge} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
625 \controllabel{if:succ2}{store1} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
626 \controllabel{store1:succ1}{merge} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
627 \controllabel{store1:succ2}{fs1} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
628 \control{merge}{store2} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
629 \controllabel{store2:succ1}{return} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
630 \controllabel{store2:succ2}{fs2} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
631 \data{cmpnull}{p} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
632 \end{digraphenv} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
633 \caption{Initial graph with the two field stores.} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
634 \label{fig:guard0} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
635 \end{figure} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
636 |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
637 Figure~\ref{fig:guard1} shows the example graph at a later compilation phase when the field store nodes are lowered to memory store nodes and explicitely modelled null check guards. |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
638 The guards are attached to anchor nodes that delimit their possible schedule. |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
639 The first guard must not be moved outside the \texttt{if} block; the second guard may be moved before the \texttt{If} node, because at this point it is already guaranteed that the second store is executed. |
2598
e4395464810e
Made graphs smaller.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2597
diff
changeset
|
640 |
2896
5d4aa5672d3d
Small fix to design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2892
diff
changeset
|
641 \begin{figure}[ht] |
2578 | 642 \centering |
2618
15774da89658
Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2604
diff
changeset
|
643 \begin{digraphenv}{scale=0.5}{guard1} |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
644 \textnode{entry}{Entry} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
645 \node{anchor1}{Anchor} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
646 \node{anchor2}{Anchor} |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
647 \nodesplit{if}{If} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
648 \node{merge}{Merge} |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
649 \node{return}{Return} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
650 \node{cmpnull}{NonNull} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
651 \textnode{p}{p} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
652 \textnode{const0}{0} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
653 \nodeguard{guard1}{Guard} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
654 \nodeguard{guard2}{Guard} |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
655 \nodetrisplit{store1}{MemStore 16 (4 bytes)} |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
656 \nodetrisplit{store2}{MemStore 20 (4 bytes)} |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
657 \nodeframestate{fs1}{FrameState} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
658 \nodeframestate{fs2}{FrameState} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
659 \data{store1:in1}{p} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
660 \data{store2:in1}{p} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
661 \data{store1:in2}{const0} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
662 \data{store2:in2}{const0} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
663 \data{store1:in3}{guard1} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
664 \data{store2:in3}{guard2} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
665 \data{guard1:in1}{anchor2} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
666 \data{guard2:in1}{anchor1} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
667 \data{guard1:in2}{cmpnull} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
668 \data{guard2:in2}{cmpnull} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
669 \control{entry}{anchor1} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
670 \control{anchor1}{if} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
671 \data{if}{cmpnull} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
672 \controllabel{if:succ1}{merge} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
673 \controllabel{if:succ2}{anchor2} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
674 \control{anchor2}{store1} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
675 \controllabel{store1:succ1}{merge} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
676 \controllabel{store1:succ2}{fs1} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
677 \control{merge}{store2} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
678 \controllabel{store2:succ1}{return} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
679 \controllabel{store2:succ2}{fs2} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
680 \data{cmpnull}{p} |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
681 \end{digraphenv} |
2618
15774da89658
Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2604
diff
changeset
|
682 \caption{A load guarded by a null check guard.} |
15774da89658
Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2604
diff
changeset
|
683 \label{fig:guard1} |
2578 | 684 \end{figure} |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
685 |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
686 The first guard can be easily removed, because it is guarded by an \texttt{If} node that checks the same condition. |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
687 Therefore we can remove the guard and the anchor from the graph and this gives us the graph shown in Figure \ref{fig:guard2}. |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
688 |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
689 There is another optimization for guard nodes: If two guards that are anchored to the true and false branch of the same \texttt{If} node have the same condition, they can be merged, so that the resulting guard is anchored at the most distant node of which the \texttt{If} node is a postdominator. |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
690 |
2598
e4395464810e
Made graphs smaller.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2597
diff
changeset
|
691 |
2896
5d4aa5672d3d
Small fix to design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2892
diff
changeset
|
692 \begin{figure}[ht] |
2578 | 693 \centering |
2618
15774da89658
Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2604
diff
changeset
|
694 \begin{digraphenv}{scale=0.5}{guard2} |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
695 \textnode{entry}{Entry} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
696 \node{anchor1}{Anchor} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
697 \nodesplit{if}{If} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
698 \node{merge}{Merge} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
699 \node{return}{Return} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
700 \node{cmpnull}{NonNull} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
701 \textnode{p}{p} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
702 \textnode{const0}{0} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
703 \nodeguard{guard2}{Guard} |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
704 \nodetrisplit{store1}{MemStore 16 (4 bytes)} |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
705 \nodetrisplit{store2}{MemStore 20 (4 bytes)} |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
706 \nodeframestate{fs1}{FrameState} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
707 \nodeframestate{fs2}{FrameState} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
708 \data{store1:in1}{p} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
709 \data{store2:in1}{p} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
710 \data{store1:in2}{const0} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
711 \data{store2:in2}{const0} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
712 \data{store2:in3}{guard2} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
713 \data{guard2:in1}{anchor1} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
714 \data{guard2:in2}{cmpnull} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
715 \control{entry}{anchor1} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
716 \control{anchor1}{if} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
717 \data{if}{cmpnull} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
718 \controllabel{if:succ1}{merge} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
719 \controllabel{if:succ2}{store1} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
720 \controllabel{store1:succ1}{merge} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
721 \controllabel{store1:succ2}{fs1} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
722 \control{merge}{store2} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
723 \controllabel{store2:succ1}{return} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
724 \controllabel{store2:succ2}{fs2} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
725 \data{cmpnull}{p} |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
726 \end{digraphenv} |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
727 \caption{After removing redundant guards.} |
2618
15774da89658
Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2604
diff
changeset
|
728 \label{fig:guard2} |
2578 | 729 \end{figure} |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
730 |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
731 The remaining guard can now be moved above the \texttt{If} condition and be used to eliminate the need for the \texttt{If} node. |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
732 From this point on, the guard can however no longer be moved below the first memory store. |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
733 We use a control dependency from the guard to the field store to express this condition. |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
734 The link between the second store and the guard and the control flow merge node is no longer necessary. |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
735 |
2896
5d4aa5672d3d
Small fix to design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2892
diff
changeset
|
736 \begin{figure}[ht] |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
737 \centering |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
738 \begin{digraphenv}{scale=0.5}{guard3} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
739 \textnode{entry}{Entry} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
740 \node{anchor1}{Anchor} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
741 \node{return}{Return} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
742 \node{cmpnull}{NonNull} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
743 \textnode{p}{p} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
744 \textnode{const0}{0} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
745 \nodeguard{guard2}{Guard} |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
746 \nodetrisplit{store1}{MemStore 16 (4 bytes)} |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
747 \nodetrisplit{store2}{MemStore 20 (4 bytes)} |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
748 \nodeframestate{fs1}{FrameState} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
749 \nodeframestate{fs2}{FrameState} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
750 \data{store1:in1}{p} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
751 \data{store2:in1}{p} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
752 \data{store1:in2}{const0} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
753 \data{store2:in2}{const0} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
754 \data{store2:in3}{guard2} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
755 \data{guard2:in1}{anchor1} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
756 \data{guard2:in2}{cmpnull} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
757 \control{guard2}{store1} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
758 \control{entry}{anchor1} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
759 \control{anchor1}{store1} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
760 \controllabel{store1:succ2}{fs1} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
761 \control{store1}{store2} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
762 \controllabel{store2:succ1}{return} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
763 \controllabel{store2:succ2}{fs2} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
764 \data{cmpnull}{p} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
765 \end{digraphenv} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
766 \caption{After eliminating an if with a guard.} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
767 \label{fig:guard3} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
768 \end{figure} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
769 |
2679
07aa0a31fffb
Rewrote frame state to be not-so-Java-specific. Clarified and reduced the usage of the term "node".
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2678
diff
changeset
|
770 At some point during the compilation, guards 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. |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
771 This will generate deoptimization-free zones that can be targeted by the most aggressive optimizations. |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
772 A simple algorithm for this removal of frame states would be to move all guards as far upwards as possible and then the guards are fixed using anchor nodes. |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
773 In our example, the guard is already fixed, so there is no deoptimization point that uses any of the memory store frame states. |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
774 Therefore we can delete the frame states from the graph (see Figure \ref{fig:guard4}). |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
775 |
2896
5d4aa5672d3d
Small fix to design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2892
diff
changeset
|
776 \begin{figure}[ht] |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
777 \centering |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
778 \begin{digraphenv}{scale=0.5}{guard4} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
779 \textnode{entry}{Entry} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
780 \node{anchor1}{Anchor} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
781 \node{return}{Return} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
782 \node{cmpnull}{NonNull} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
783 \textnode{p}{p} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
784 \textnode{const0}{0} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
785 \nodeguard{guard2}{Guard} |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
786 \nodetrisplit{store1}{MemStore 16 (4 bytes)} |
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
787 \nodetrisplit{store2}{MemStore 20 (4 bytes)} |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
788 \data{store1:in1}{p} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
789 \data{store2:in1}{p} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
790 \data{store1:in2}{const0} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
791 \data{store2:in2}{const0} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
792 \data{store2:in3}{guard2} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
793 \data{guard2:in1}{anchor1} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
794 \data{guard2:in2}{cmpnull} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
795 \control{guard2}{store1} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
796 \control{entry}{anchor1} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
797 \control{anchor1}{store1} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
798 \control{store1}{store2} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
799 \controllabel{store2:succ1}{return} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
800 \data{cmpnull}{p} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
801 \end{digraphenv} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
802 \caption{After removing the frame states.} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
803 \label{fig:guard4} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
804 \end{figure} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
805 |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
806 Now we can use memory coalescing to combine the two stores without frame state to adjacent locations in the same object. |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
807 This is only possible if the first store does not have a frame state. |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
808 Figure \ref{fig:guard5} shows the resulting graph. |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
809 |
2577
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
810 |
2896
5d4aa5672d3d
Small fix to design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2892
diff
changeset
|
811 \begin{figure}[ht] |
2578 | 812 \centering |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
813 \begin{digraphenv}{scale=0.5}{guard5} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
814 \textnode{entry}{Entry} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
815 \node{anchor1}{Anchor} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
816 \node{return}{Return} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
817 \node{cmpnull}{NonNull} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
818 \textnode{p}{p} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
819 \textnode{const0}{0} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
820 \nodeguard{guard2}{Guard} |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
821 \nodetrisplit{store1}{MemStore 16 (8 bytes)} |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
822 \data{store1:in1}{p} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
823 \data{store1:in2}{const0} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
824 \data{guard2:in1}{anchor1} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
825 \data{guard2:in2}{cmpnull} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
826 \control{guard2}{store1} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
827 \control{entry}{anchor1} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
828 \control{anchor1}{store1} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
829 \controllabel{store1:succ1}{return} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
830 \data{cmpnull}{p} |
2577
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
831 \end{digraphenv} |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
832 \caption{After coalescing the two memory stores.} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
833 \label{fig:guard5} |
2578 | 834 \end{figure} |
2577
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
835 |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
836 A memory store that immediately follows a null check guard node on the same object, can be combined into a store with an implicit null check (that deoptimizes instead of throwing the exception). |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
837 Therefore, we can remove the guard again and also the anchor is no longer necessary. |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
838 Figure~\ref{fig:guard6} shows now that fully optimized graph that is generated for Listing~\ref{lst:guard1}. |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
839 |
2896
5d4aa5672d3d
Small fix to design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2892
diff
changeset
|
840 \begin{figure}[ht] |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
841 \centering |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
842 \begin{digraphenv}{scale=0.5}{guard6} |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
843 \textnode{entry}{Entry} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
844 \node{return}{Return} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
845 \textnode{p}{p} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
846 \textnode{const0}{0} |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
847 \nodetrisplit{store1}{DeoptimizingMemStore 16 (8 bytes)} |
2682
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
848 \data{store1:in1}{p} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
849 \data{store1:in2}{const0} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
850 \control{entry}{store1} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
851 \controllabel{store1:succ1}{return} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
852 \end{digraphenv} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
853 \caption{Fully optimized method.} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
854 \label{fig:guard6} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
855 \end{figure} |
c5739b99762a
New field store / guard / frame state example.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2679
diff
changeset
|
856 |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
857 |
2597
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
858 \section{Conclusions} |
2618
15774da89658
Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2604
diff
changeset
|
859 \label{sec:conclusions} |
2597
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
860 This document sketched the strategy for the Graph compiler. |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
861 We have the following plans for M1 to M4: |
2597
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
862 \begin{description} |
2949
4db4e8cb6bd6
Updated design document (incorporated comments from Peter Kessler).
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2896
diff
changeset
|
863 \item[M1:] May 15th, 2011 |
2597
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
864 \item[M2:] June 30th, 2011 |
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
865 \item[M3:] August 15th, 2011 |
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
866 \item[M4:] September 30th, 2011 |
08cda6637103
More doc + conclusion.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2591
diff
changeset
|
867 \end{description} |
2685 | 868 After we reach M4, we want to create a new project road map that further improves the Graal compiler with respect to its two main goals: Modularity and peak performance. |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
869 |
2517
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
870 \end{document} |