Mercurial > hg > graal-compiler
annotate doc/design/graal_compiler.tex @ 2589:795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
author | Thomas Wuerthinger <thomas@wuerthinger.net> |
---|---|
date | Thu, 05 May 2011 14:03:49 +0200 |
parents | 26ecba0ead6d |
children | d559fac49699 |
rev | line source |
---|---|
2517
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
1 \documentclass[twocolumn]{svjour3} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
2 \usepackage[pdftex]{graphicx} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
3 \usepackage{environ} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
4 \usepackage{amsmath} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
5 \usepackage{amsfonts} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
6 \usepackage[english]{babel} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
7 \usepackage[utf8]{inputenc} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
8 \usepackage{lmodern} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
9 \usepackage[T1]{fontenc} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
10 \usepackage{color} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
11 |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
12 \input{graphdrawing} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
13 |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
14 \renewcommand*\descriptionlabel[1]{\hspace\labelsep\normalfont\bf #1} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
15 |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
16 \newcommand{\Sa}{{\Large$^*$}} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
17 \newcommand{\Sb}{{\Large$^\dag$}} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
18 \newcommand{\Sc}{{\Large$^\S$}} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
19 |
2562 | 20 |
21 \newcommand{\mynote}[2]{ | |
22 \textcolor{red}{\fbox{\bfseries\sffamily\scriptsize#1} | |
23 {\small\textsf{\emph{#2}}} | |
24 \fbox{\bfseries\sffamily\scriptsize }}} | |
25 | |
26 \newcommand\TODO[1]{\mynote{TODO}{#1}} | |
27 \newcommand\cw[1]{\mynote{CW}{#1}} | |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
28 \newcommand\ls[1]{\mynote{LS}{#1}} |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
29 \newcommand\nodename[1]{\texttt{#1}} |
2562 | 30 |
31 | |
32 | |
2517
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
33 \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
|
34 |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
35 \journalname{Graal Compiler Design} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
36 \def\makeheadbox{{% |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
37 \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
|
38 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
|
39 \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
|
40 \kern3pt}\hfil\kern3pt\vrule}\hrule}% |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
41 \hss}}} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
42 |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
43 \begin{document} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
44 |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
45 \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
|
46 \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
|
47 |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
48 \date{Created: \today} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
49 |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
50 \title{The Graal Compiler} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
51 \subtitle{Design and Strategy \\ \textcolor{red}{work in progress}} |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
52 |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
53 \maketitle |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
54 |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
55 \abstract{ |
2589
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
56 The Graal compiler (simply referred to as \emph{the compiler} in the rest of this document) aims at improving C1X, the Java port of the HotSpot client compiler, both in terms of modularity and peak performance. |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
57 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
|
58 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
|
59 |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
60 \section{Context} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
61 |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
62 In 2009, the Maxine team started with creating C1X, a Java port of the HotSpot client compiler, and integrate it into the Maxine VM. |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
63 Part of this effort, was the development of a clear and clean compiler-runtime interface that allows the separation of the compiler and the VM that enables the use of one compiler for multiple VMs. |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
64 In June 2010, we started integrating C1X into the HotSpot VM and we called the resulting system Graal~VM. |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
65 Currently, the Graal~VM is fully functional and runs benchmarks (SciMark, DaCapo) at a similar speed to the HotSpot client compiler. |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
66 |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
67 \section{Goals} |
2589
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
68 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
|
69 \begin{description} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
70 \item[Modularity:] A modular design of the compiler should simplify the implementation of new languages, new back-ends, and new optimizations. |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
71 \item[Peak Performance:] A more powerful intermediate representation should enable the implementation of heavy-weight optimizations that impact the peak performance of the resulting machine code. |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
72 \end{description} |
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{Design} |
2589
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
75 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
|
76 \begin{description} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
77 \item[Graph Representation:] |
2562 | 78 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
|
79 There is only a single node base class and every node has an associated graph object that does not change during the node's lifetime. |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
80 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
|
81 Every edge is classified as either a control flow edge (anti-dependency) or a data flow edge (dependency) and represented as a simple pointer from the source node to the target node. |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
82 It is possible to replace a node with another node without traversing the full graph. |
2588
26ecba0ead6d
Update on doc.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2578
diff
changeset
|
83 The graph does not allow data flow edge cycles or control flow edge cycles. |
26ecba0ead6d
Update on doc.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2578
diff
changeset
|
84 We achieve this by explicitely modelling loops (see Section~\ref{sec:loops}). |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
85 \item[Extensibility:] |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
86 The compiler is extensible by adding new compiler phases and new node subclasses without modifying the compiler's sources. |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
87 A node has an abstract way of expressing its effect 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
|
88 We use the ``everything is an extension'' concept. |
26ecba0ead6d
Update on doc.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2578
diff
changeset
|
89 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
|
90 \item[Detailing:] |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
91 The compilation starts with a graph that contains nodes that represent the operations of the source language (e.g., one node for an array store to an object array). |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
92 During the compilation, the nodes are replaced with more detailed nodes (e.g., the array store node is split into a null check, a bounds check, a store check, and a memory access). |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
93 Compiler phases can choose whether they want to work on the earlier versions of the graph (e.g., escape analysis) or on later versions (e.g., null check elimination). |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
94 \item[Generality:] |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
95 The compiler does not require Java as its input. |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
96 This is achieved by having a graph as the starting point of the compilation and not a Java bytecodes array. |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
97 Building the graph from the Java bytecodes must happen before giving a method to the compiler. |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
98 This enables front-ends for different languages (e.g., Ruby) to provide their own graph. |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
99 Also, there is no dependency on a specific back-end, but the output of the compiler is a graph that can then be converted to a different representation in a final compiler phase. |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
100 \end{description} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
101 |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
102 \section{Milestones} |
2589
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
103 The compiler is developed starting from the current C1X source code base. |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
104 This helps us testing the compiler at every intermediate development step on a variety of Java benchmarks. |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
105 We define the following development milestones and when they are considered achieved: |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
106 \begin{description} |
2589
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
107 \item[M1:] We have a fully working Graal~VM version with a stripped down C1X compiler that does not perform any optimizations. |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
108 \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
|
109 \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
|
110 \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
|
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 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
|
114 \begin{itemize} |
2589
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
115 \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
|
116 \item Improvements for peak performance (loop optimizations, escape analysis, bounds check elimination, processing additional interpreter runtime feedback). |
2562 | 117 \item Implementation of a prototype front-end for different languages, e.g., JavaScript. |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
118 \end{itemize} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
119 |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
120 \section{Implementation} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
121 |
2589
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
122 \subsection{Nodes and Graphs} |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
123 The most important aspect of a compiler is the data structure that holds information about an executable piece of code, called \emph{intermediate representation}~(IR). |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
124 The IR used in the compiler was designed in such a way as to allow for extensive optimizations, easy traversal, compact storage and efficient processing. |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
125 |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
126 \subsubsection{The Graph Data Structure} |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
127 \begin{itemize} |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
128 \item A graph deals out ids for new nodes and can be queried for the node corresponding to a given id. |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
129 \item Graphs can manage side data structures, which will be automatically invalidated and lazily recomputed whenever the graph changes. Examples for side data structures are dominator trees and temporary schedules. These side data structures will usually be understood by more than one optimization. |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
130 \end{itemize} |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
131 |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
132 \subsubsection{The Node Data Structure} |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
133 \begin{itemize} |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
134 \item Each node is always associated with a graph. |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
135 \item Each node has an immutable id which is unique within its associated graph. \cw{The server compiler supports ``renumbering'' of nodes to make the ids dense again after large graph manipulations that deleted many nodes.} |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
136 \item Nodes represent either operations on values or control flow operations. |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
137 \item Nodes can have a data dependency, which means that one node requires the result of some other node as its input. The fact that the result of the first node needs to be computed before the second node can be executed introduces a partial order to the set of nodes. |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
138 \item Nodes can have a control flow dependency, which means that the execution of one node depends on some other node. This includes conditional execution, memory access serialization and other reasons, and again introduces a partial order to the set of nodes. |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
139 \item Nodes can only have data and control dependencies to nodes which belong to the same graph. |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
140 \item Control dependencies and data dependencies each represent a \emph{directed acyclic graph} (DAG) on the same set of nodes. This means that data dependencies always point upwards, and control dependencies always point downwards. Situations that are normally incur cycles (like loops) are represented by special nodes (like LoopEnd). |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
141 \cw{I don't like that item. Cycles are a normal thing for control flow and for phi functions. I would phrase it as something like that: Nodes can only have data and control dependencies to nodes that are dominators. The only exception of that are control loop headers and phi functions} |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
142 \item Ordering between nodes is specified only to the extent which is required to correctly express the semantics of a given program. Some compilers (notably the HotSpot client compiler \cw{Wrong: the client compiler only has a fixed order of pinned instructions, most instructions are not pinned and can be moved around freely}) always maintain a complete order for all nodes (called \emph{scheduling}), which impedes advanced optimizations. For algorithms that require a fixed ordering of nodes, a temporary schedule can always be generated. |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
143 \item Both data and control dependencies can be traversed in both directions, so that each node can be traversed in four directions: |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
144 \begin{itemize} |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
145 \item \emph{inputs} are all nodes that this node has data dependencies on. |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
146 \item \emph{usages} are all nodes that have data dependencies on this node, this is regarded as the inverse of inputs. |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
147 \item \emph{successors} are all nodes that have a control dependency on this node. |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
148 \item \emph{predecessors} are all nodes that this node has control dependencies on, this is regarded as the inverse of successors. |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
149 \end{itemize} |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
150 \item Only inputs and successors can be changed, and changes to them will update the usages and predecessors. |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
151 \item The Node class needs to provide facilities for subclasses to perform actions upon cloning, dependency changes, etc. |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
152 \item Nodes cannot be reassigned to another graph, they are cloned instead \cw{Why should there be the need for more than one graph when compiling a method?} |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
153 \end{itemize} |
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
154 |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
155 \subsection{Loops} |
2588
26ecba0ead6d
Update on doc.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2578
diff
changeset
|
156 \label{sec:loops} |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
157 Loops form a first-class construct in the IR that is expressed in specialized IR nodes during all optimization phases. |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
158 We only compile methods with a control flow where every loop has only one single entry point. |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
159 This entry point is a \nodename{LoopBegin} node. |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
160 This node is connected to a \nodename{LoopEnd} node that merges all control flow paths that do not exit the loop. |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
161 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
|
162 It goes from the beginning to the end in order to make the graph acyclic. |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
163 An algorithm that traverses the control flow has to explicitely decide whether it wants to incorporate backedges (i.e., special case the treatment of \nodename{LoopEnd}) or ignore them. |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
164 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
|
165 |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
166 \begin{figure}[h] |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
167 \label{fig:loop1} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
168 \centering |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
169 \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
|
170 \textnode{BeforeLoop}{Loop entry} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
171 \textnode{Exit1}{First loop exit} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
172 \textnode{Exit2}{Second loop exit} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
173 \nodesplit{LoopBegin}{LoopBegin} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
174 \node{LoopEnd}{LoopEnd} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
175 \nodesplit{If1}{If} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
176 \nodesplit{If2}{If} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
177 \controllabel{LoopBegin:succ1}{LoopEnd} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
178 \controllabel{LoopBegin:succ2}{If1} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
179 \controllabel{If1:succ1}{If2} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
180 \controllabel{If2:succ1}{LoopEnd} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
181 \controllabel{BeforeLoop}{LoopBegin} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
182 \controllabel{If1:succ2}{Exit1} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
183 \controllabel{If2:succ2}{Exit2} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
184 \end{digraphenv} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
185 \caption{A simple loop with two exits.} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
186 \end{figure} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
187 |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
188 \subsection{Loop Phis} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
189 Data flow in loops is modelled with special phi nodes at the beginning and the end of the loop. |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
190 The \nodename{LoopEnd} node merges every value that is flows into the next loop iteration in associated \nodename{LoopEndPhi} nodes. |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
191 A corresponding \nodename{LoopBeginPhi} node that is associated with the loop header has a control flow dependency on the \nodename{LoopEndPhi} node. |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
192 Figure \ref{fig:loop2} shows how a simple counting loop is modelled in the graph. |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
193 |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
194 \begin{figure}[h] |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
195 \label{fig:loop2} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
196 \centering |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
197 \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
|
198 \textnode{BeforeLoop}{Loop entry} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
199 \textnode{Exit}{Loop exit} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
200 \textnode{n}{n} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
201 \textnode{Constant0}{0} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
202 \textnode{Constant1}{1} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
203 \nodesplit{LoopBegin}{LoopBegin} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
204 \node{LoopEnd}{LoopEnd} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
205 \nodesplit{If1}{If} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
206 \controllabel{LoopBegin:succ1}{LoopEnd} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
207 \controllabel{LoopBegin:succ2}{If1} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
208 \nodebi{Compare}{<} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
209 \nodebi{LoopBeginPhi}{LoopBeginPhi} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
210 \nodebi{Add}{+} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
211 \datalabel{Add:in1}{LoopBeginPhi} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
212 \datalabel{Add:in2}{Constant1} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
213 \nodebi{LoopEndPhi}{LoopEndPhi} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
214 \control{LoopBeginPhi}{LoopEndPhi} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
215 \data{LoopEndPhi:in1}{LoopEnd} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
216 \data{LoopEndPhi:in2}{Add} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
217 \datalabel{LoopBeginPhi:in1}{LoopBegin} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
218 \datalabel{LoopBeginPhi:in2}{Constant0} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
219 \datalabel{Compare:in1}{LoopBeginPhi} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
220 \datalabel{Compare:in2}{n} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
221 \data{If1}{Compare} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
222 \controllabel{If1:succ1}{LoopEnd} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
223 \controllabel{BeforeLoop}{LoopBegin} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
224 \controllabel{If1:succ2}{Exit} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
225 \end{digraphenv} |
2589
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
226 \caption{Graph for a loop counting from 0 to n-1.} |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
227 \end{figure} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
228 |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
229 \subsection{Loop Counters} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
230 The compiler is capable of recognizing variables that are only increased within a loop. |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
231 A potential overflow of such a variable is guarded with a trap before the loop. |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
232 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
|
233 |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
234 |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
235 \begin{figure}[h] |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
236 \label{fig:loop3} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
237 \centering |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
238 \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
|
239 \textnode{BeforeLoop}{Loop entry} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
240 \textnode{Exit}{Loop exit} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
241 \textnode{n}{n} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
242 \textnode{Constant0}{0} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
243 \textnode{Constant1}{1} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
244 \nodesplit{LoopBegin}{LoopBegin} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
245 \node{LoopEnd}{LoopEnd} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
246 \nodesplit{If1}{If} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
247 \controllabel{LoopBegin:succ1}{LoopEnd} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
248 \controllabel{LoopBegin:succ2}{If1} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
249 \nodebi{Compare}{<} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
250 \nodetri{LoopCounter}{LoopCounter} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
251 \datalabel{LoopCounter:in1}{LoopBegin} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
252 \datalabeltext{LoopCounter:in2}{Constant0}{init} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
253 \datalabeltext{LoopCounter:in3}{Constant1}{stride} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
254 \datalabel{Compare:in1}{LoopCounter} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
255 \datalabel{Compare:in2}{n} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
256 \data{If1}{Compare} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
257 \controllabel{If1:succ1}{LoopEnd} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
258 \controllabel{BeforeLoop}{LoopBegin} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
259 \controllabel{If1:succ2}{Exit} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
260 \end{digraphenv} |
2589
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
261 \caption{Graph after loop counter transformation.} |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
262 \end{figure} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
263 |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
264 \subsection{Bounded Loops} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
265 |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
266 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
|
267 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. |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
268 If the totel number of iterations is reached, the loop is exited directly from the loop header. |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
269 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
|
270 Figure \ref{fig:loop4} shows the compiler graph of the example loop after the bounded loop transformation. |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
271 |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
272 \begin{figure}[h] |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
273 \label{fig:loop4} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
274 \centering |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
275 \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
|
276 \textnode{BeforeLoop}{Loop entry} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
277 \textnode{Exit}{Loop exit} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
278 \textnode{n}{n} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
279 \textnode{Constant0}{0} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
280 \textnode{Constant1}{1} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
281 \nodesplittri{LoopBegin}{BoundedLoopBegin} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
282 \node{LoopEnd}{LoopEnd} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
283 \controllabel{LoopBegin:succ1}{LoopEnd} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
284 \controllabel{LoopBegin:succ2}{LoopEnd} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
285 \controllabel{LoopBegin:succ3}{Exit} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
286 \nodetri{LoopCounter}{LoopCounter} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
287 \datalabel{LoopCounter:in1}{LoopBegin} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
288 \datalabeltext{LoopCounter:in2}{Constant0}{init} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
289 \datalabeltext{LoopCounter:in3}{Constant1}{stride} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
290 \data{LoopBegin}{n} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
291 \controllabel{BeforeLoop}{LoopBegin} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
292 \end{digraphenv} |
2589
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
293 \caption{Graph after bounded loop transformation.} |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
294 \end{figure} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
295 |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
296 \subsection{Vectorization} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
297 |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
298 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. |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
299 We replace the loop header with a normal instruction that produces a vector of values from 0 to the number of loop iterations minus 1. |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
300 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
|
301 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
|
302 Figure \ref{fig:loop5} shows the compiler graph of the example loop after vectorization. |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
303 The vector nodes all work on an ordered list of integer values and are subject to canonicalization like any other node. |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
304 |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
305 |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
306 \begin{figure}[h] |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
307 \label{fig:loop5} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
308 \centering |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
309 \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
|
310 \textnode{Entry}{Entry} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
311 \textnode{Exit}{Exit} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
312 \textnode{n}{n} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
313 \textnode{Constant0}{0} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
314 \textnode{Constant1}{1} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
315 \node{Vector}{Vector} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
316 \nodebi{VectorAdd}{VectorAdd} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
317 \nodebi{VectorMul}{VectorMul} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
318 \control{Entry}{Vector} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
319 \control{Vector}{Exit} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
320 \datalabel{VectorAdd:in1}{Vector} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
321 \datalabel{VectorAdd:in2}{Constant0} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
322 \datalabel{VectorMul:in1}{VectorAdd} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
323 \datalabel{VectorMul:in2}{Constant1} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
324 \data{Vector}{n} |
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
325 \end{digraphenv} |
2589
795df30f979d
Refer to "Graal compiler" as "the compiler" in the design document.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2588
diff
changeset
|
326 \caption{Graph after bounded loop transformation.} |
2573
6d99b909696d
Documentation: More content and graphs on loops and vectorization.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2572
diff
changeset
|
327 \end{figure} |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
328 |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
329 \subsection{Project Source Structure} |
2588
26ecba0ead6d
Update on doc.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2578
diff
changeset
|
330 In order to support the goal of a modular compiler, the code will be divided into the following source code projects (as subprojects of \textbf{com.oracle.graal}). |
26ecba0ead6d
Update on doc.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2578
diff
changeset
|
331 |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
332 \begin{description} |
2588
26ecba0ead6d
Update on doc.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2578
diff
changeset
|
333 \item[graph] contains the abstract node implementation, the graph implementation and all the associated tools and auxiliary classes. |
26ecba0ead6d
Update on doc.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2578
diff
changeset
|
334 \item[nodes] contains the implementation of known basic nodes (e.g., phi nodes, control flow nodes, \ldots). |
26ecba0ead6d
Update on doc.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2578
diff
changeset
|
335 Additional node classes should go into seperate projects and be specializations of the known basic nodes.] |
26ecba0ead6d
Update on doc.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2578
diff
changeset
|
336 \item[java] contains code for building graphs from Java bytecodes and Java-specific nodes. |
26ecba0ead6d
Update on doc.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2578
diff
changeset
|
337 \item[opt] contains optimizations such as global value numbering or conditional constant propagation. |
26ecba0ead6d
Update on doc.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2578
diff
changeset
|
338 \item[compiler] contains the compiler, including: |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
339 \begin{itemize} |
2588
26ecba0ead6d
Update on doc.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2578
diff
changeset
|
340 \item Schedules the compilation phases. |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
341 \item Implementation of the \emph{compiler interface} (CI). |
2588
26ecba0ead6d
Update on doc.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2578
diff
changeset
|
342 \item Implements the final compilation phase that produces the low-level representation. |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
343 \item Machine code creation, including debug info. |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
344 \end{itemize} |
2562 | 345 \cw{So you want to keep the backend as part of the ``main compiler'' at first. Seems OK for me.} |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
346 \end{description} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
347 |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
348 |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
349 \subsection{Frame States} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
350 Frame states capture the state of the program, in terms of the source representation (e.g., Java state: local variables, expressions, ...). |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
351 Whenever a safepoint is reached or \cw{why is that an ``or'', both is basically the same} \ls{uncommon traps can be introduced at other points, e.g., at an if branch that isn't compiled} a deoptimization is needed a valid frame state needs to be available. |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
352 A frame state is valid as long as the program performs only actions that can safely be reexecuted (e.g., operations on local variables, loads, etc.). |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
353 Thus, frame states need only be generated for bytecodes that cannot be reexecuted: |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
354 |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
355 \begin{itemize} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
356 \item Array stores: {\tt IASTORE, LASTORE, FASTORE, \\DASTORE, AASTORE, BASTORE, CASTORE, SASTORE} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
357 \item Field stores: {\tt PUTSTATIC, PUTFIELD} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
358 \item Method calls: {\tt INVOKEVIRTUAL, INVOKESPECIAL, \\INVOKESTATIC, INVOKEINTERFACE} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
359 \item Synchronization: {\tt MONITORENTER, MONITOREXIT} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
360 \end{itemize} |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
361 |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
362 Within the node graph a frame state is represented as a node that is fixed to the node that caused it to be generated (control dependency). |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
363 |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
364 |
2578 | 365 \begin{figure}[h] |
366 \label{fig:fs1} | |
367 \centering | |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
368 \begin{digraphenv}{scale=0.5}{fs1} |
2577
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
369 \nodetrisplit{store1}{ArrayStore} |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
370 \nodebi{load1}{ArrayLoad} |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
371 \controllabel{store1:succ1}{load1} |
2577
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
372 \nodetrisplit{store2}{ArrayStore} |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
373 \control{load1}{store2} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
374 end [shape=plaintext, label="...", width="2.0"] |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
375 store2:succ1:s -> end:n [color=red]; |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
376 % |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
377 \nodeframestate{fs1}{FrameState} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
378 \controllabel{store1:succ2}{fs1} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
379 \nodeframestate{fs2}{FrameState} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
380 \controllabel{store2:succ2}{fs2} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
381 \end{digraphenv} |
2578 | 382 \caption{Simple example using two frame states.} |
383 \end{figure} | |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
384 |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
385 FrameStates also have data dependencies on the contents of the state: the local variables and the expression stack. |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
386 |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
387 \subsection{Deoptimization and Uncommon Traps} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
388 Uncommon trap nodes are not fixed to a certain frame state node, they can move around freely and will always use the correct frame state. |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
389 The node that is guarded by the deoptimization has a data dependency on the trap, and the trap in turn has a data dependency on the condition and on the most distant node that is postdominated by the guarded node. |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
390 |
2578 | 391 \begin{figure}[h] |
392 \label{fig:trap1} | |
393 \centering | |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
394 \begin{digraphenv}{scale=0.5}{trap1} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
395 \nodesplit{if}{If} |
2577
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
396 \node{split1}{Split} |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
397 \controllabel{if:succ1}{split1} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
398 nop [shape=plaintext, label="..."] |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
399 \control{split1}{nop} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
400 % |
2577
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
401 \node{split2}{Split} |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
402 \controllabel{if:succ2}{split2} |
2577
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
403 \nodebi{load1}{MemLoad} |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
404 \control{split2}{load1} |
2577
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
405 \nodebi{load2}{MemLoad} |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
406 \control{load1}{load2} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
407 \control{load2}{merge} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
408 \node{merge}{Merge} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
409 \control{nop}{merge} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
410 % |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
411 \nodeconst{o1}{obj1} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
412 \nodeconst{o2}{obj2} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
413 \datalabel{load1:in2}{o1} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
414 \datalabel{load2:in2}{o2} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
415 \nodetrap{trap}{Trap} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
416 \node{cmpnull}{IsNull} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
417 \data{cmpnull}{o2} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
418 \datalabel{trap:in2}{cmpnull} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
419 \datalabel{load2:in1}{trap} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
420 \datalabel{trap:in1}{split2} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
421 \end{digraphenv} |
2578 | 422 \caption{In this example, the second load is guarded by an uncommon trap, because its receiver might be null (the receiver of the load is assumed to be non-null). |
2577
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
423 The trap is anchored to the control split, because as soon as this node is executed the second load must be executed as well. |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
424 In the final scheduling the trap can be placed before or after the first load.} |
2578 | 425 \end{figure} |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
426 |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
427 Another type of uncommon trap is a guard, which is used to remove branches that have a very low execution frequency from the compiled code. |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
428 |
2578 | 429 \begin{figure}[h] |
430 \label{fig:trap2} | |
431 \centering | |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
432 \begin{digraphenv}{scale=0.5}{trap2} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
433 start [shape=plaintext, label="..."] |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
434 start2 [shape=plaintext, label=""] |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
435 start3 [shape=plaintext, label=""] |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
436 \control{start}{guard} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
437 \node{guard}{Guard} |
2577
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
438 \nodebi{load1}{MemLoad} |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
439 \control{guard}{load1} |
2577
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
440 \control{load1}{nop} |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
441 nop [shape=plaintext, label="..."] |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
442 % |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
443 \nodetrap{trap}{Trap} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
444 \datalabel{trap:in1}{start2} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
445 \datalabel{trap:in2}{start3} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
446 \data{guard}{trap} |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
447 \end{digraphenv} |
2578 | 448 \caption{In this example the If from the previous example was replaced by a guard and an uncommon trap. |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
449 The guard takes the place of the If in the control flow, and is connected to the trap node. |
2577
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
450 The uncommon trap is now anchored to the most distant node of which the If was a postdominator.} |
2578 | 451 \end{figure} |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
452 |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
453 At some point during the compilation, trap nodes need to be fixed, which means that appropriate data and control dependencies will be inserted so that they cannot move outside the scope of the associated frame state. |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
454 This will generate deoptimization-free zones that can be targeted by the most aggressive optimizations. |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
455 A simple algorithm for this removal of FrameStates would be to move all traps as far upwards as possible. |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
456 |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
457 |
2577
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
458 Multiple Traps with the same condition and anchor can be merged: |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
459 |
2578 | 460 \begin{figure}[h] |
461 \label{fig:trap3} | |
462 \centering | |
2577
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
463 \begin{digraphenv}{scale=0.5}{trap3} |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
464 \nodesplit{if}{If} |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
465 \node{split1}{Split} |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
466 \controllabel{if:succ1}{split1} |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
467 nop [shape=plaintext, label="..."] |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
468 \control{split1}{nop} |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
469 % |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
470 \node{split2}{Split} |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
471 \controllabel{if:succ2}{split2} |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
472 \nodebi{load1}{MemLoad} |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
473 \control{split2}{load1} |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
474 \nodebi{load2}{MemLoad} |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
475 \control{load1}{load2} |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
476 \control{load2}{merge} |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
477 \node{merge}{Merge} |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
478 \control{nop}{merge} |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
479 % |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
480 \nodeconst{o}{obj} |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
481 \datalabel{load1:in2}{o} |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
482 \datalabel{load2:in2}{o} |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
483 \nodetrap{trap}{Trap} |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
484 \node{cmpnull}{IsNull} |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
485 \data{cmpnull}{o} |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
486 \datalabel{trap:in2}{cmpnull} |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
487 \datalabel{load2:in1}{trap} |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
488 \datalabel{load1:in1}{trap} |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
489 \datalabel{trap:in1}{split2} |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
490 \end{digraphenv} |
2578 | 491 \caption{Two loads guarded by the same Trap.} |
492 \end{figure} | |
2577
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
493 |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
494 Also, if two Traps that are anchored to the true and false branch of the same If have the same condition, they can be merged, so that the resulting Trap is anchored at the most distant node of which the If is a postdominator. |
ac2029d0898f
doc: framestate and deopt changes
Lukas Stadler <lukas.stadler@jku.at>
parents:
2576
diff
changeset
|
495 |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
496 %Frame states should be represented using a delta-encoding. |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
497 %This will make them significantly smaller and will make inlining, etc. much easier. |
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
498 %In later compilation phases unnecessary frame states might be removed, using a mark-and-merge algorithm. |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
499 |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
500 \subsection{Graph Building} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
501 \begin{itemize} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
502 \item The graph built by the initial parser (called \emph{GraphBuilder}) should be as close to the source representation (bytecode, ...) as possible. |
2562 | 503 \item All nodes should be able to immediately lower themselves to a machine-level representation. \cw{What is that? You mean every node has x86 specific code that spits out machine code? Hope you are joking...} This allows for easier compiler development, and also leads to a compiler that is very flexible in the amount of optimizations it performs (e.g. recompilation of methods with more aggressive optimizations). |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
504 \end{itemize} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
505 |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
506 \subsection{Graphical Representation} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
507 The graphs in this document use the following node layout: |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
508 |
2578 | 509 \begin{digraphenv}{scale=0.5}{graphrep1} |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
510 \node{node1}{nop} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
511 \nodebi{node2}{+} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
512 \nodetri{node3}{phi} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
513 \nodesplit{node4}{if} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
514 \end{digraphenv} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
515 |
2562 | 516 \cw{That doesn't compile with my latex. What do I have to do to get it working?} |
2576
c59db1f02893
doc: expanded framestate section
Lukas Stadler <lukas.stadler@jku.at>
parents:
2569
diff
changeset
|
517 \ls{graphviz needs to be installed, and pdflatex needs to be started with -shell-escape} |
2562 | 518 |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
519 Red arrows always represents control dependencies, while black arrows represent data dependencies: |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
520 |
2578 | 521 \begin{digraphenv}{scale=0.5}{graphrep2} |
2561
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
522 \node{a}{a} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
523 \node{b}{b} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
524 \nodesplit{if}{if} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
525 \node{nop}{nop} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
526 \nodebi{add}{+} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
527 \controllabel{if:succ1}{nop} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
528 \controllabel{if:succ2}{add} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
529 \datalabel{add:in1}{a} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
530 \datalabel{add:in2}{b} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
531 \end{digraphenv} |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
532 |
765dd54244a6
Updated doc. Added Texclipse project.
Thomas Wuerthinger <thomas@wuerthinger.net>
parents:
2517
diff
changeset
|
533 |
2517
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
534 |
8c6e31c62fba
added initial version of design docs, fixed .hgignore (regex, . -> \.)
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
535 \end{document} |