truffle: graal/com.oracle.max.graal.doc.initial/graal

annotate graal/com.oracle.max.graal.doc.initial/graal_compiler.tex @ 2977:f01de7799e05

Updated hgignore.

author	Thomas Wuerthinger <thomas@wuerthinger.net>
date	Wed, 15 Jun 2011 17:54:31 +0200
parents	4db4e8cb6bd6
children

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

Mercurial > hg > truffle

annotate graal/com.oracle.max.graal.doc.initial/graal_compiler.tex @ 2977:f01de7799e05