truffle: doc/design/graal_compiler.tex annotate

annotate doc/design/graal_compiler.tex @ 2619:1586b1b56f0c

Fixed typo.

author	Thomas Wuerthinger <thomas@wuerthinger.net>
date	Mon, 09 May 2011 19:12:45 +0200
parents	15774da89658
children	b9b0a0aa7ee8

rev	line source
2517 8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	1 \documentclass[twocolumn]{svjour3}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	2 \usepackage[pdftex]{graphicx}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	3 \usepackage{environ}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	4 \usepackage{amsmath}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	5 \usepackage{amsfonts}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	6 \usepackage[english]{babel}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	7 \usepackage[utf8]{inputenc}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	8 \usepackage{lmodern}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	9 \usepackage[T1]{fontenc}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	10 \usepackage{color}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	11
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	12 \input{graphdrawing}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	13
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	14 \renewcommand*\descriptionlabel[1]{\hspace\labelsep\normalfont\bf #1}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	15
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	16 \newcommand{\Sa}{{\Large$^*$}}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	17 \newcommand{\Sb}{{\Large$^\dag$}}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	18 \newcommand{\Sc}{{\Large$^\S$}}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	19
2562 0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	20
0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	21 \newcommand{\mynote}[2]{
0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	22 \textcolor{red}{\fbox{\bfseries\sffamily\scriptsize#1}
0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	23 {\small\textsf{\emph{#2}}}
0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	24 \fbox{\bfseries\sffamily\scriptsize }}}
0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	25
0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	26 \newcommand\TODO[1]{\mynote{TODO}{#1}}
0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	27 \newcommand\cw[1]{\mynote{CW}{#1}}
2576 c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	28 \newcommand\ls[1]{\mynote{LS}{#1}}
2573 6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	29 \newcommand\nodename[1]{\texttt{#1}}
2562 0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	30
0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	31
0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	32
2517 8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	33 \smartqed % flush right qed marks, e.g. at end of proof
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	34
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	35 \journalname{Graal Compiler Design}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	36 \def\makeheadbox{{%
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	37 \hbox to0pt{\vbox{\baselineskip=10dd\hrule\hbox
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	38 to\hsize{\vrule\kern3pt\vbox{\kern3pt
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	39 \hbox{\bfseries The Graal Compiler - Design and Strategy}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	40 \kern3pt}\hfil\kern3pt\vrule}\hrule}%
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	41 \hss}}}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	42
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	43 \begin{document}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	44
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	45 \author{Thomas W\"{u}rthinger \Sa, Lukas Stadler \Sc, Gilles Duboscq \Sa}
2517 8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	46 \institute{\Sa Oracle, \Sc Johannes Kepler University, Linz}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	47
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	48 \date{Created: \today}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	49
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	50 \title{The Graal Compiler}
2604 c9b17ac5c06b Doc fixes. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2598 diff changeset	51 \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	52
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	53 \maketitle
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	54
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	55 \abstract{
2589 795df30f979d Refer to "Graal compiler" as "the compiler" in the design document. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2588 diff changeset	56 The Graal compiler (simply referred to as \emph{the compiler} in the rest of this document) aims at improving C1X, the Java port of the HotSpot client compiler, both in terms of modularity and peak performance.
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	57 The compiler should work with the Maxine VM and the HotSpot VM.
2589 795df30f979d Refer to "Graal compiler" as "the compiler" in the design document. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2588 diff changeset	58 This document contains information about the proposed design and strategy for developing the compiler.}
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	59
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	60 \section{Context}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	61
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	62 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	63 Part of this effort was the development of a clear and clean compiler-runtime interface that allows the separation of the compiler and the VM.
c9b17ac5c06b Doc fixes. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2598 diff changeset	64 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	65 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	66 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	67
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	68 \section{Goals}
2589 795df30f979d Refer to "Graal compiler" as "the compiler" in the design document. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2588 diff changeset	69 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	70 \begin{description}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	71 \item[Modularity:] A modular design of the compiler should simplify the implementation of new languages, new back-ends, and new optimizations.
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	72 \item[Peak Performance:] A more powerful intermediate representation should enable the implementation of aggressive optimizations that impact the peak performance of the resulting machine code.
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	73 \end{description}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	74
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	75 \section{Design}
2589 795df30f979d Refer to "Graal compiler" as "the compiler" in the design document. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2588 diff changeset	76 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	77 \begin{description}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	78 \item[Graph Representation:]
2562 0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	79 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	80 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	81 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	82 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	83 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	84 The graph does not allow data flow edge cycles or control flow edge cycles.
26ecba0ead6d Update on doc. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2578 diff changeset	85 We achieve this by explicitely modelling loops (see Section~\ref{sec:loops}).
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	86 \item[Extensibility:]
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	87 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	88 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	89 We use the ``everything is an extension'' concept.
26ecba0ead6d Update on doc. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2578 diff changeset	90 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	91 \item[Detailing:]
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	92 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	93 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	94 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	95 \item[Generality:]
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	96 The compiler does not require Java as its input.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	97 This is achieved by having a graph as the starting point of the compilation and not a Java bytecodes array.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	98 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	99 This enables front-ends for different languages (e.g., Ruby or JavaScript) to provide their own graph.
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	100 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	101 \end{description}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	102
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	103 \section{Milestones}
2597 08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	104 \label{sec:mile}
2589 795df30f979d Refer to "Graal compiler" as "the compiler" in the design document. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2588 diff changeset	105 The compiler is developed starting from the current C1X source code base.
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	106 This helps us testing the compiler at every intermediate development step on a variety of Java benchmarks.
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	107 We define the following development milestones and when they are considered to be achieved (see Section~\ref{sec:conclusions} for planned dates):
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	108 \begin{description}
2589 795df30f979d Refer to "Graal compiler" as "the compiler" in the design document. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2588 diff changeset	109 \item[M1:] We have a fully working Graal~VM version with a stripped down C1X compiler that does not perform any optimizations.
795df30f979d Refer to "Graal compiler" as "the compiler" in the design document. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2588 diff changeset	110 \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	111 \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	112 \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	113 \end{description}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	114
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	115 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	116 \begin{itemize}
2589 795df30f979d Refer to "Graal compiler" as "the compiler" in the design document. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2588 diff changeset	117 \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	118 \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	119 \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	120 \end{itemize}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	121
2597 08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	122 \section{Graph}
2589 795df30f979d Refer to "Graal compiler" as "the compiler" in the design document. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2588 diff changeset	123
2597 08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	124 The \emph{intermediate representation}~(IR) of the compiler is designed as a directed graph.
2604 c9b17ac5c06b Doc fixes. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2598 diff changeset	125 The graph deals out 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.
2597 08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	126 Graphs can manage side data structures, which will be automatically invalidated and lazily recomputed whenever the graph changes. Examples for side data structures are dominator trees and temporary schedules. These side data structures will usually be understood by more than one optimization.
2589 795df30f979d Refer to "Graal compiler" as "the compiler" in the design document. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2588 diff changeset	127
2597 08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	128 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	129 \begin{itemize}
2597 08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	130 \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	131 \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	132 \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	133 \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	134 \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	135 \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	136 \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	137 \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	138 \begin{itemize}
795df30f979d Refer to "Graal compiler" as "the compiler" in the design document. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2588 diff changeset	139 \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	140 \item \emph{usages} are all nodes whose inputs contain this node.
c9b17ac5c06b Doc fixes. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2598 diff changeset	141 \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	142 \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	143 \end{itemize}
795df30f979d Refer to "Graal compiler" as "the compiler" in the design document. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2588 diff changeset	144 \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	145 \item Every node must be able to support cloning and serialization.
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	146 \item Inlining should always be performed as embedding one graph into another graph.
2590 d559fac49699 More work on doc. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2589 diff changeset	147 \item Nodes cannot be reassigned to another graph, they are cloned instead.
2597 08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	148 \item The edges of a node also define \textit{happens-before} and \textit{happens-after} relationships as shown in 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	149 \end{itemize}
795df30f979d Refer to "Graal compiler" as "the compiler" in the design document. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2588 diff changeset	150
2597 08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	151 \begin{figure}[h]
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	152 \centering
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	153 \begin{digraphenv}{scale=0.5}{graphdirections}
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	154 \node{node1}{Node}
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	155 \textnode{inputs}{inputs}
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	156 \textnode{usages}{usages}
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	157 \textnode{successors}{successors}
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	158 \textnode{predecessors}{predecessors}
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	159 \data{node1}{inputs}
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	160 \control{node1}{successors}
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	161 \data{usages}{node1}
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	162 \control{predecessors}{node1}
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	163 \node{node2}{Node}
2604 c9b17ac5c06b Doc fixes. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2598 diff changeset	164 \textnode{before}{happens-before}
c9b17ac5c06b Doc fixes. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2598 diff changeset	165 \textnode{after}{happens-after}
2597 08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	166 \data{node2}{before}
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	167 \control{node2}{after}
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	168 \data{after}{node2}
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	169 \control{before}{node2}
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	170 \end{digraphenv}
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	171 \caption{A node and its edges.}
2604 c9b17ac5c06b Doc fixes. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2598 diff changeset	172 \label{fig:directions}
2597 08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	173 \end{figure}
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	174
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	175 \subsection{Project Source Structure}
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	176 In order to support the goal of a modular compiler, the code will be divided into the following source code projects (as subprojects of \textbf{com.oracle.graal}).
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	177
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	178 \begin{description}
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	179 \item[graph] contains the abstract node implementation, the graph implementation and all the associated tools and auxiliary classes.
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	180 \item[nodes] contains the implementation of known basic nodes (e.g., phi nodes, control flow nodes, \ldots).
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	181 Additional node classes should go into separate projects and be specializations of the known basic nodes.
2597 08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	182 \item[java] contains code for building graphs from Java bytecodes and Java-specific nodes.
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	183 \item[opt] contains optimizations such as global value numbering or conditional constant propagation.
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	184 \item[compiler] contains the compiler, including:
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	185 \begin{itemize}
2604 c9b17ac5c06b Doc fixes. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2598 diff changeset	186 \item Scheduling of the compilation phases.
2597 08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	187 \item Implementation of the \emph{compiler interface} (CI).
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	188 \item Implementation of the final compilation phase that produces the low-level representation.
2597 08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	189 \item Machine code creation, including debug info.
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	190 \end{itemize}
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	191 \end{description}
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	192
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	193 \section{Loops}
2588 26ecba0ead6d Update on doc. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2578 diff changeset	194 \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	195 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	196 We only compile methods with a control flow where every loop has a single entry point.
2573 6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	197 This entry point is a \nodename{LoopBegin} node.
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	198 This node is connected to a \nodename{LoopEnd} node that merges all control flow paths that do not exit the loop.
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	199 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	200 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	201 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	202 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	203
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	204 \begin{figure}[h]
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	205 \centering
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	206 \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	207 \textnode{BeforeLoop}{Loop entry}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	208 \textnode{Exit1}{First loop exit}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	209 \textnode{Exit2}{Second loop exit}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	210 \nodesplit{LoopBegin}{LoopBegin}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	211 \node{LoopEnd}{LoopEnd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	212 \nodesplit{If1}{If}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	213 \nodesplit{If2}{If}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	214 \controllabel{LoopBegin:succ1}{LoopEnd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	215 \controllabel{LoopBegin:succ2}{If1}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	216 \controllabel{If1:succ1}{If2}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	217 \controllabel{If2:succ1}{LoopEnd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	218 \controllabel{BeforeLoop}{LoopBegin}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	219 \controllabel{If1:succ2}{Exit1}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	220 \controllabel{If2:succ2}{Exit2}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	221 \end{digraphenv}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	222 \caption{A simple loop with two exits.}
2604 c9b17ac5c06b Doc fixes. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2598 diff changeset	223 \label{fig:loop1}
2573 6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	224 \end{figure}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	225
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	226 \subsection{Loop Phis}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	227 Data flow in loops is modelled with special phi nodes at the beginning and the end of the loop.
2590 d559fac49699 More work on doc. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2589 diff changeset	228 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	229 A corresponding \nodename{LoopBeginPhi} node that is associated with the loop header has a control flow dependency on the \nodename{LoopEndPhi} node.
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	230 Figure \ref{fig:loop2} shows how a simple counting loop is modelled in the graph.
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	231
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	232 \begin{figure}[h]
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	233 \centering
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	234 \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	235 \textnode{BeforeLoop}{Loop entry}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	236 \textnode{Exit}{Loop exit}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	237 \textnode{n}{n}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	238 \textnode{Constant0}{0}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	239 \textnode{Constant1}{1}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	240 \nodesplit{LoopBegin}{LoopBegin}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	241 \node{LoopEnd}{LoopEnd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	242 \nodesplit{If1}{If}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	243 \controllabel{LoopBegin:succ1}{LoopEnd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	244 \controllabel{LoopBegin:succ2}{If1}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	245 \nodebi{Compare}{<}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	246 \nodebi{LoopBeginPhi}{LoopBeginPhi}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	247 \nodebi{Add}{+}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	248 \datalabel{Add:in1}{LoopBeginPhi}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	249 \datalabel{Add:in2}{Constant1}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	250 \nodebi{LoopEndPhi}{LoopEndPhi}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	251 \control{LoopBeginPhi}{LoopEndPhi}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	252 \data{LoopEndPhi:in1}{LoopEnd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	253 \data{LoopEndPhi:in2}{Add}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	254 \datalabel{LoopBeginPhi:in1}{LoopBegin}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	255 \datalabel{LoopBeginPhi:in2}{Constant0}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	256 \datalabel{Compare:in1}{LoopBeginPhi}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	257 \datalabel{Compare:in2}{n}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	258 \data{If1}{Compare}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	259 \controllabel{If1:succ1}{LoopEnd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	260 \controllabel{BeforeLoop}{LoopBegin}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	261 \controllabel{If1:succ2}{Exit}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	262 \end{digraphenv}
2589 795df30f979d Refer to "Graal compiler" as "the compiler" in the design document. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2588 diff changeset	263 \caption{Graph for a loop counting from 0 to n-1.}
2604 c9b17ac5c06b Doc fixes. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2598 diff changeset	264 \label{fig:loop2}
2573 6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	265 \end{figure}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	266
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	267 \subsection{Loop Counters}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	268 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	269 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	270 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	271
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	272
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	273 \begin{figure}[h]
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	274 \centering
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	275 \begin{digraphenv}{scale=0.5}{layout3}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	276 \textnode{BeforeLoop}{Loop entry}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	277 \textnode{Exit}{Loop exit}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	278 \textnode{n}{n}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	279 \textnode{Constant0}{0}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	280 \textnode{Constant1}{1}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	281 \nodesplit{LoopBegin}{LoopBegin}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	282 \node{LoopEnd}{LoopEnd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	283 \nodesplit{If1}{If}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	284 \controllabel{LoopBegin:succ1}{LoopEnd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	285 \controllabel{LoopBegin:succ2}{If1}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	286 \nodebi{Compare}{<}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	287 \nodetri{LoopCounter}{LoopCounter}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	288 \datalabel{LoopCounter:in1}{LoopBegin}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	289 \datalabeltext{LoopCounter:in2}{Constant0}{init}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	290 \datalabeltext{LoopCounter:in3}{Constant1}{stride}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	291 \datalabel{Compare:in1}{LoopCounter}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	292 \datalabel{Compare:in2}{n}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	293 \data{If1}{Compare}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	294 \controllabel{If1:succ1}{LoopEnd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	295 \controllabel{BeforeLoop}{LoopBegin}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	296 \controllabel{If1:succ2}{Exit}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	297 \end{digraphenv}
2589 795df30f979d Refer to "Graal compiler" as "the compiler" in the design document. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2588 diff changeset	298 \caption{Graph after loop counter transformation.}
2604 c9b17ac5c06b Doc fixes. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2598 diff changeset	299 \label{fig:loop3}
2573 6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	300 \end{figure}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	301
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	302 \subsection{Bounded Loops}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	303
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	304 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	305 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	306 If the total number of iterations is reached, the loop is exited directly from the loop header.
2573 6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	307 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	308 Figure \ref{fig:loop4} shows the compiler graph of the example loop after the bounded loop transformation.
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	309
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	310 \begin{figure}[h]
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	311 \centering
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	312 \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	313 \textnode{BeforeLoop}{Loop entry}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	314 \textnode{Exit}{Loop exit}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	315 \textnode{n}{n}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	316 \textnode{Constant0}{0}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	317 \textnode{Constant1}{1}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	318 \nodesplittri{LoopBegin}{BoundedLoopBegin}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	319 \node{LoopEnd}{LoopEnd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	320 \controllabel{LoopBegin:succ1}{LoopEnd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	321 \controllabel{LoopBegin:succ2}{LoopEnd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	322 \controllabel{LoopBegin:succ3}{Exit}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	323 \nodetri{LoopCounter}{LoopCounter}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	324 \datalabel{LoopCounter:in1}{LoopBegin}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	325 \datalabeltext{LoopCounter:in2}{Constant0}{init}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	326 \datalabeltext{LoopCounter:in3}{Constant1}{stride}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	327 \data{LoopBegin}{n}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	328 \controllabel{BeforeLoop}{LoopBegin}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	329 \end{digraphenv}
2589 795df30f979d Refer to "Graal compiler" as "the compiler" in the design document. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2588 diff changeset	330 \caption{Graph after bounded loop transformation.}
2604 c9b17ac5c06b Doc fixes. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2598 diff changeset	331 \label{fig:loop4}
2573 6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	332 \end{figure}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	333
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	334 \subsection{Vectorization}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	335
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	336 If we have now a bounded loop with no additional loop exit and no associated phi nodes (only associated loop counters), we can vectorize the loop.
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	337 We replace the loop header with a normal instruction that produces a vector of values from 0 to the number of loop iterations minus 1.
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	338 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	339 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	340 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	341 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	342
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	343
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	344 \begin{figure}[h]
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	345 \centering
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	346 \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	347 \textnode{Entry}{Entry}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	348 \textnode{Exit}{Exit}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	349 \textnode{n}{n}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	350 \textnode{Constant0}{0}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	351 \textnode{Constant1}{1}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	352 \node{Vector}{Vector}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	353 \nodebi{VectorAdd}{VectorAdd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	354 \nodebi{VectorMul}{VectorMul}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	355 \control{Entry}{Vector}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	356 \control{Vector}{Exit}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	357 \datalabel{VectorAdd:in1}{Vector}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	358 \datalabel{VectorAdd:in2}{Constant0}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	359 \datalabel{VectorMul:in1}{VectorAdd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	360 \datalabel{VectorMul:in2}{Constant1}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	361 \data{Vector}{n}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	362 \end{digraphenv}
2598 e4395464810e Made graphs smaller. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2597 diff changeset	363 \caption{Graph after vectorization.}
2604 c9b17ac5c06b Doc fixes. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2598 diff changeset	364 \label{fig:loop5}
2573 6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	365 \end{figure}
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	366
2588 26ecba0ead6d Update on doc. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2578 diff changeset	367
2597 08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	368 \section{Frame States}
2590 d559fac49699 More work on doc. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2589 diff changeset	369 A frame state captures the state of the program in terms of the Java bytecode specification (i.e., the values of the local variables, the operand stack, and the locked monitors).
d559fac49699 More work on doc. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2589 diff changeset	370 Every deoptimization point needs a valid frame state.
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	371 A frame state stays valid as long as the subsequent instructions perform only actions that can safely be reexecuted.
2604 c9b17ac5c06b Doc fixes. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2598 diff changeset	372 Thus, frame states need only be generated for the states after bytecodes that cannot be reexecuted:
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	373
2576 c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	374 \begin{itemize}
c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	375 \item Array stores: {\tt IASTORE, LASTORE, FASTORE, \\DASTORE, AASTORE, BASTORE, CASTORE, SASTORE}
c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	376 \item Field stores: {\tt PUTSTATIC, PUTFIELD}
c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	377 \item Method calls: {\tt INVOKEVIRTUAL, INVOKESPECIAL, \\INVOKESTATIC, INVOKEINTERFACE}
c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	378 \item Synchronization: {\tt MONITORENTER, MONITOREXIT}
c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	379 \end{itemize}
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	380
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	381 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	382 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	383
2604 c9b17ac5c06b Doc fixes. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2598 diff changeset	384 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.
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	385 We save the frame state at control flow merges if there is at least one frame state on any control flow path after the immediate dominator.
2604 c9b17ac5c06b Doc fixes. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2598 diff changeset	386
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	387
2578 999407dbfe10 merge Lukas Stadler <lukas.stadler@jku.at> parents: 2577 2574 diff changeset	388 \begin{figure}[h]
999407dbfe10 merge Lukas Stadler <lukas.stadler@jku.at> parents: 2577 2574 diff changeset	389 \centering
2576 c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	390 \begin{digraphenv}{scale=0.5}{fs1}
2577 ac2029d0898f doc: framestate and deopt changes Lukas Stadler <lukas.stadler@jku.at> parents: 2576 diff changeset	391 \nodetrisplit{store1}{ArrayStore}
ac2029d0898f doc: framestate and deopt changes Lukas Stadler <lukas.stadler@jku.at> parents: 2576 diff changeset	392 \nodebi{load1}{ArrayLoad}
2576 c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	393 \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	394 \nodetrisplit{store2}{FieldStore}
2576 c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	395 \control{load1}{store2}
c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	396 end [shape=plaintext, label="...", width="2.0"]
c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	397 store2:succ1:s -> end:n [color=red];
c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	398 %
c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	399 \nodeframestate{fs1}{FrameState}
c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	400 \controllabel{store1:succ2}{fs1}
c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	401 \nodeframestate{fs2}{FrameState}
c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	402 \controllabel{store2:succ2}{fs2}
c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	403 \end{digraphenv}
2578 999407dbfe10 merge Lukas Stadler <lukas.stadler@jku.at> parents: 2577 2574 diff changeset	404 \caption{Simple example using two frame states.}
2604 c9b17ac5c06b Doc fixes. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2598 diff changeset	405 \label{fig:fs1}
2578 999407dbfe10 merge Lukas Stadler <lukas.stadler@jku.at> parents: 2577 2574 diff changeset	406 \end{figure}
2576 c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	407
c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	408
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	409 \subsection{Guards}
15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	410 A guard node is a node that deoptimizes based on a conditional expression.
15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	411 Guard nodes are not attached to a certain frame state node, 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).
15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	412 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 and on the most distant node that is postdominated by the guarded node.
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	413
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	414 In the example of Figure~\ref{fig:guard1}, the second load is guarded by a guard, because its receiver might be null (the receiver of the first load is assumed to be non-null).
15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	415 The guard is anchored to the control split, because as soon as this node is executed, the second load must be executed as well.
15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	416 In the final schedule, the guard can be placed before or after the first load.
2598 e4395464810e Made graphs smaller. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2597 diff changeset	417
2578 999407dbfe10 merge Lukas Stadler <lukas.stadler@jku.at> parents: 2577 2574 diff changeset	418 \begin{figure}[h]
999407dbfe10 merge Lukas Stadler <lukas.stadler@jku.at> parents: 2577 2574 diff changeset	419 \centering
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	420 \begin{digraphenv}{scale=0.5}{guard1}
2576 c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	421 \nodesplit{if}{If}
c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	422 nop [shape=plaintext, label="..."]
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	423 \controllabel{if:succ1}{nop}
2576 c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	424 %
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	425 \node{split2}{Anchor}
2576 c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	426 \controllabel{if:succ2}{split2}
2577 ac2029d0898f doc: framestate and deopt changes Lukas Stadler <lukas.stadler@jku.at> parents: 2576 diff changeset	427 \nodebi{load1}{MemLoad}
2576 c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	428 \control{split2}{load1}
2577 ac2029d0898f doc: framestate and deopt changes Lukas Stadler <lukas.stadler@jku.at> parents: 2576 diff changeset	429 \nodebi{load2}{MemLoad}
2576 c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	430 \control{load1}{load2}
c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	431 \control{load2}{merge}
c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	432 \node{merge}{Merge}
c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	433 \control{nop}{merge}
c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	434 %
c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	435 \nodeconst{o1}{obj1}
c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	436 \nodeconst{o2}{obj2}
c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	437 \datalabel{load1:in2}{o1}
c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	438 \datalabel{load2:in2}{o2}
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	439 \nodeguard{guard}{Guard}
2576 c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	440 \node{cmpnull}{IsNull}
c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	441 \data{cmpnull}{o2}
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	442 \datalabel{guard:in2}{cmpnull}
15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	443 \datalabel{load2:in1}{guard}
15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	444 \datalabel{guard:in1}{split2}
2576 c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	445 \end{digraphenv}
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	446 \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	447 \label{fig:guard1}
2578 999407dbfe10 merge Lukas Stadler <lukas.stadler@jku.at> parents: 2577 2574 diff changeset	448 \end{figure}
2576 c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	449
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	450 A guard can be used to remove branches that have a very low execution frequency and replace them with a conditional jump to deoptimization.
2576 c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	451
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	452 In the example of Figure~\ref{fig:guard2}, an \texttt{If} node was replaced by an anchor and a guard.
15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	453 The anchor takes the place of the \texttt{If} node in the control flow, and is connected to the guard node.
15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	454 The guard is now anchored to the most distant node of which the \texttt{If} node was a postdominator.
2598 e4395464810e Made graphs smaller. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2597 diff changeset	455
2578 999407dbfe10 merge Lukas Stadler <lukas.stadler@jku.at> parents: 2577 2574 diff changeset	456 \begin{figure}[h]
999407dbfe10 merge Lukas Stadler <lukas.stadler@jku.at> parents: 2577 2574 diff changeset	457 \centering
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	458 \begin{digraphenv}{scale=0.5}{guard2}
2576 c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	459 start [shape=plaintext, label="..."]
c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	460 start2 [shape=plaintext, label=""]
c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	461 start3 [shape=plaintext, label=""]
c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	462 \control{start}{guard}
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	463 \node{anchor}{Anchor}
2577 ac2029d0898f doc: framestate and deopt changes Lukas Stadler <lukas.stadler@jku.at> parents: 2576 diff changeset	464 \nodebi{load1}{MemLoad}
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	465 \control{anchor}{load1}
2577 ac2029d0898f doc: framestate and deopt changes Lukas Stadler <lukas.stadler@jku.at> parents: 2576 diff changeset	466 \control{load1}{nop}
2576 c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	467 nop [shape=plaintext, label="..."]
c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	468 %
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	469 \nodeguard{guard}{Guard}
15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	470 \datalabel{guard:in1}{start2}
15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	471 \datalabel{guard:in2}{start3}
15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	472 \data{anchor}{guard}
2576 c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	473 \end{digraphenv}
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	474 \caption{A guard that is fixed to the control flow using an anchor instruction.}
15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	475 \label{fig:guard2}
2578 999407dbfe10 merge Lukas Stadler <lukas.stadler@jku.at> parents: 2577 2574 diff changeset	476 \end{figure}
2576 c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	477
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	478 At some point during the compilation, guard nodes need to be fixed, which means that appropriate data and control dependencies will be inserted so that they cannot move outside the scope of the associated frame state.
2576 c59db1f02893 doc: expanded framestate section Lukas Stadler <lukas.stadler@jku.at> parents: 2569 diff changeset	479 This will generate deoptimization-free zones that can be targeted by the most aggressive optimizations.
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	480 A simple algorithm for this removal of frame states would be to move all guards as far upwards as possible.
15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	481 Multiple guards with the same condition and anchor can be merged (see Figure~\ref{fig:guard3}).
2577 ac2029d0898f doc: framestate and deopt changes Lukas Stadler <lukas.stadler@jku.at> parents: 2576 diff changeset	482
2578 999407dbfe10 merge Lukas Stadler <lukas.stadler@jku.at> parents: 2577 2574 diff changeset	483 \begin{figure}[h]
999407dbfe10 merge Lukas Stadler <lukas.stadler@jku.at> parents: 2577 2574 diff changeset	484 \centering
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	485 \begin{digraphenv}{scale=0.5}{guard3}
2577 ac2029d0898f doc: framestate and deopt changes Lukas Stadler <lukas.stadler@jku.at> parents: 2576 diff changeset	486 \nodesplit{if}{If}
ac2029d0898f doc: framestate and deopt changes Lukas Stadler <lukas.stadler@jku.at> parents: 2576 diff changeset	487 nop [shape=plaintext, label="..."]
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	488 \controllabel{if:succ1}{nop}
2577 ac2029d0898f doc: framestate and deopt changes Lukas Stadler <lukas.stadler@jku.at> parents: 2576 diff changeset	489 %
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	490 \node{split2}{Anchor}
2577 ac2029d0898f doc: framestate and deopt changes Lukas Stadler <lukas.stadler@jku.at> parents: 2576 diff changeset	491 \controllabel{if:succ2}{split2}
ac2029d0898f doc: framestate and deopt changes Lukas Stadler <lukas.stadler@jku.at> parents: 2576 diff changeset	492 \nodebi{load1}{MemLoad}
ac2029d0898f doc: framestate and deopt changes Lukas Stadler <lukas.stadler@jku.at> parents: 2576 diff changeset	493 \control{split2}{load1}
ac2029d0898f doc: framestate and deopt changes Lukas Stadler <lukas.stadler@jku.at> parents: 2576 diff changeset	494 \nodebi{load2}{MemLoad}
ac2029d0898f doc: framestate and deopt changes Lukas Stadler <lukas.stadler@jku.at> parents: 2576 diff changeset	495 \control{load1}{load2}
ac2029d0898f doc: framestate and deopt changes Lukas Stadler <lukas.stadler@jku.at> parents: 2576 diff changeset	496 \control{load2}{merge}
ac2029d0898f doc: framestate and deopt changes Lukas Stadler <lukas.stadler@jku.at> parents: 2576 diff changeset	497 \node{merge}{Merge}
ac2029d0898f doc: framestate and deopt changes Lukas Stadler <lukas.stadler@jku.at> parents: 2576 diff changeset	498 \control{nop}{merge}
ac2029d0898f doc: framestate and deopt changes Lukas Stadler <lukas.stadler@jku.at> parents: 2576 diff changeset	499 %
ac2029d0898f doc: framestate and deopt changes Lukas Stadler <lukas.stadler@jku.at> parents: 2576 diff changeset	500 \nodeconst{o}{obj}
ac2029d0898f doc: framestate and deopt changes Lukas Stadler <lukas.stadler@jku.at> parents: 2576 diff changeset	501 \datalabel{load1:in2}{o}
ac2029d0898f doc: framestate and deopt changes Lukas Stadler <lukas.stadler@jku.at> parents: 2576 diff changeset	502 \datalabel{load2:in2}{o}
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	503 \nodeguard{guard}{Guard}
2577 ac2029d0898f doc: framestate and deopt changes Lukas Stadler <lukas.stadler@jku.at> parents: 2576 diff changeset	504 \node{cmpnull}{IsNull}
ac2029d0898f doc: framestate and deopt changes Lukas Stadler <lukas.stadler@jku.at> parents: 2576 diff changeset	505 \data{cmpnull}{o}
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	506 \datalabel{guard:in2}{cmpnull}
15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	507 \datalabel{load2:in1}{guard}
15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	508 \datalabel{load1:in1}{guard}
15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	509 \datalabel{guard:in1}{split2}
2577 ac2029d0898f doc: framestate and deopt changes Lukas Stadler <lukas.stadler@jku.at> parents: 2576 diff changeset	510 \end{digraphenv}
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	511 \caption{Two loads using the same guard.}
15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	512 \label{fig:guard3}
2578 999407dbfe10 merge Lukas Stadler <lukas.stadler@jku.at> parents: 2577 2574 diff changeset	513 \end{figure}
2577 ac2029d0898f doc: framestate and deopt changes Lukas Stadler <lukas.stadler@jku.at> parents: 2576 diff changeset	514
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	515 Also, 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.
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	516
2597 08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	517 \section{Conclusions}
2618 15774da89658 Incorporated comments from Peter. Renamings trap=>guard and guard/split=>anchor. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2604 diff changeset	518 \label{sec:conclusions}
2597 08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	519 This document sketched the strategy for the Graph compiler.
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	520 We already reached M1 (as defined in Section~\ref{sec:mile}) and have the following plans for M2 to M4:
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	521 \begin{description}
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	522 \item[M2:] June 30th, 2011
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	523 \item[M3:] August 15th, 2011
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	524 \item[M4:] September 30th, 2011
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	525 \end{description}
08cda6637103 More doc + conclusion. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2591 diff changeset	526 After we reached 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	527
2517 8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	528 \end{document}

Mercurial > hg > truffle

annotate doc/design/graal_compiler.tex @ 2619:1586b1b56f0c