truffle: doc/design/graal_compiler.tex annotate

annotate doc/design/graal_compiler.tex @ 2574:d1ea2563836d

Merge.

author	Thomas Wuerthinger <thomas@wuerthinger.net>
date	Wed, 04 May 2011 16:36:09 +0200
parents	6d99b909696d 7aa67f5f3884
children	999407dbfe10

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}}
2573 6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	28 \newcommand\nodename[1]{\texttt{#1}}
2562 0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	29
0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	30
0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	31
2517 8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	32 \smartqed % flush right qed marks, e.g. at end of proof
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	33
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	34 \journalname{Graal Compiler Design}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	35 \def\makeheadbox{{%
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	36 \hbox to0pt{\vbox{\baselineskip=10dd\hrule\hbox
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	37 to\hsize{\vrule\kern3pt\vbox{\kern3pt
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	38 \hbox{\bfseries The Graal Compiler - Design and Strategy}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	39 \kern3pt}\hfil\kern3pt\vrule}\hrule}%
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	40 \hss}}}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	41
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	42 \begin{document}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	43
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	44 \author{Thomas W\"{u}rthinger \Sa, Lukas Stadler \Sc, Gilles Duboscq \Sa}
2517 8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	45 \institute{\Sa Oracle, \Sc Johannes Kepler University, Linz}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	46
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	47 \date{Created: \today}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	48
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	49 \title{The Graal Compiler}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	50 \subtitle{Design and Strategy \\ \textcolor{red}{work in progress}}
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	51
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	52 \maketitle
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	53
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	54 \abstract{
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	55 The Graal compiler aims at improving C1X, the Java port of the HotSpot client compiler, both in terms of modularity and peak performance.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	56 The compiler should work with the Maxine VM and the HotSpot VM.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	57 This document contains information about the proposed design and strategy for developing the Graal compiler.}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	58
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	59 \section{Context}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	60
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	61 In 2009, the Maxine team started with creating C1X, a Java port of the HotSpot client compiler, and integrate it into the Maxine VM.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	62 Part of this effort, was the development of a clear and clean compiler-runtime interface that allows the separation of the compiler and the VM that enables the use of one compiler for multiple VMs.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	63 In June 2010, we started integrating C1X into the HotSpot VM and we called the resulting system Graal~VM.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	64 Currently, the Graal~VM is fully functional and runs benchmarks (SciMark, DaCapo) at a similar speed to the HotSpot client compiler.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	65
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	66 \section{Goals}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	67 The Graal compiler effort aims at rewriting the high-level intermediate representation of C1X with two main goals:
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	68 \begin{description}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	69 \item[Modularity:] A modular design of the compiler should simplify the implementation of new languages, new back-ends, and new optimizations.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	70 \item[Peak Performance:] A more powerful intermediate representation should enable the implementation of heavy-weight optimizations that impact the peak performance of the resulting machine code.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	71 \end{description}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	72
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	73 \section{Design}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	74 For the implementation of the Graal compiler, we rely on the following design decisions:
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	75 \begin{description}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	76 \item[Graph Representation:]
2562 0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	77 The compiler's intermediate representation is modeled as a graph with nodes that are connected with directed edges.
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	78 There is only a single node base class and every node has an associated graph object that does not change during the node's lifetime.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	79 Every node is serializable and has an id that is unique within its graph.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	80 Every edge is classified as either a control flow edge (anti-dependency) or a data flow edge (dependency) and represented as a simple pointer from the source node to the target node.
2562 0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	81 There is no cycle in the graph that contains only control flow edges or only data flow edges. \cw{What does that sentence mean? I can certainly think of a loop that has a control-flow cycle, but no data-flow cycle.}
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	82 It is possible to replace a node with another node without traversing the full graph.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	83 \item[Extensibility:]
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	84 The compiler is extensible by adding new compiler phases and new node subclasses without modifying the compiler's sources.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	85 A node has an abstract way of expressing its effect and new compiler phases can ask compiler nodes for their properties and capabilities.
2562 0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	86 \cw{Add: We use the ``everything is an extension'' concept. Even standard compiler optimizations are internally modeled as extensions, to show that the extension mechanism exposes all necessary functionality.}
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	87 \item[Detailing:]
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	88 The compilation starts with a graph that contains nodes that represent the operations of the source language (e.g., one node for an array store to an object array).
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	89 During the compilation, the nodes are replaced with more detailed nodes (e.g., the array store node is split into a null check, a bounds check, a store check, and a memory access).
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	90 Compiler phases can choose whether they want to work on the earlier versions of the graph (e.g., escape analysis) or on later versions (e.g., null check elimination).
2562 0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	91 \cw{In general, I agree that the lowering should happen without changing the style of IR. However, I don't agree that optimizations such as null check elimination should work on a lower level graph. Isn't it bette to model ``needs null check'' as a capability of high-level instructions? Then the eliminator just sets a property that no null check is necessary. But that is a good discussion point: How much optimization do we want to do by augmenting a high-level IR, and how much do we want to do by rewriting a low-level IR.}
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	92 \item[Generality:]
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	93 The compiler does not require Java as its input.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	94 This is achieved by having a graph as the starting point of the compilation and not a Java bytecodes array.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	95 Building the graph from the Java bytecodes must happen before giving a method to the compiler.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	96 This enables front-ends for different languages (e.g., Ruby) to provide their own graph.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	97 Also, there is no dependency on a specific back-end, but the output of the compiler is a graph that can then be converted to a different representation in a final compiler phase.
2562 0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	98 \cw{Here we are getting into the nits of terminology. I think the term ``compiler'' should always refer to the whole system that goes from bytecodes to machine code. Yes, there will be additional parsers for different bytecode formats. But still, the compiler doesn't have graphs as input and outputs, but still bytecodes and machine code, respectively.}
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	99 \end{description}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	100
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	101 \section{Milestones}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	102 The Graal compiler is developed starting from the current C1X source code base.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	103 This helps us testing the compiler at every intermediate development step on a variety of Java benchmarks.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	104 We define the following development milestones and when they are considered achieved:
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	105 \begin{description}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	106 \item[M1:] We have a fully working Graal VM version with a stripped down C1X compiler that does not perform any optimizations.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	107 \item[M2:] We modified the high-level intermediate representation to be based on the Graal compiler graph data structure.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	108 \item[M3:] We have reimplemented and reenabled compiler optimizations in the Graal compiler that previously existed in C1X.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	109 \item[M4:] We have reintegrated the new Graal compiler into the Maxine VM and can use it as a Maxine VM bootstrapping compiler.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	110 \end{description}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	111
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	112 After those four milestones, we see three different possible further development directions that can be followed in parallel:
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	113 \begin{itemize}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	114 \item Removal of the XIR template mechanism and replacement with a snippet mechanism that works with the Graal compiler graph.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	115 \item Improvements for Graal peak performance (loop optimizations, escape analysis, bounds check elimination, processing additional interpreter runtime feedback).
2562 0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	116 \item Implementation of a prototype front-end for different languages, e.g., JavaScript.
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	117 \end{itemize}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	118
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	119 \section{Implementation}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	120
2573 6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	121 \subsection{Loops}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	122 Loops form a first-class construct in the IR that is expressed in specialized IR nodes during all optimization phases.
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	123 We only compile methods with a control flow where every loop has only one single entry point.
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	124 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	125 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	126 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	127 It goes from the beginning to the end in order to make the graph acyclic.
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	128 An algorithm that traverses the control flow has to explicitely decide whether it wants to incorporate backedges (i.e., special case the treatment of \nodename{LoopEnd}) or ignore them.
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	129 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	130
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	131 \begin{figure}[h]
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	132 \label{fig:loop1}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	133 \centering
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	134 \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	135 \textnode{BeforeLoop}{Loop entry}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	136 \textnode{Exit1}{First loop exit}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	137 \textnode{Exit2}{Second loop exit}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	138 \nodesplit{LoopBegin}{LoopBegin}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	139 \node{LoopEnd}{LoopEnd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	140 \nodesplit{If1}{If}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	141 \nodesplit{If2}{If}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	142 \controllabel{LoopBegin:succ1}{LoopEnd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	143 \controllabel{LoopBegin:succ2}{If1}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	144 \controllabel{If1:succ1}{If2}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	145 \controllabel{If2:succ1}{LoopEnd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	146 \controllabel{BeforeLoop}{LoopBegin}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	147 \controllabel{If1:succ2}{Exit1}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	148 \controllabel{If2:succ2}{Exit2}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	149 \end{digraphenv}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	150 \caption{A simple loop with two exits.}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	151 \end{figure}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	152
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	153 \subsection{Loop Phis}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	154 Data flow in loops is modelled with special phi nodes at the beginning and the end of the loop.
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	155 The \nodename{LoopEnd} node merges every value that is flows into the next loop iteration in associated \nodename{LoopEndPhi} nodes.
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	156 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	157 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	158
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	159 \begin{figure}[h]
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	160 \label{fig:loop2}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	161 \centering
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	162 \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	163 \textnode{BeforeLoop}{Loop entry}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	164 \textnode{Exit}{Loop exit}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	165 \textnode{n}{n}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	166 \textnode{Constant0}{0}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	167 \textnode{Constant1}{1}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	168 \nodesplit{LoopBegin}{LoopBegin}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	169 \node{LoopEnd}{LoopEnd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	170 \nodesplit{If1}{If}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	171 \controllabel{LoopBegin:succ1}{LoopEnd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	172 \controllabel{LoopBegin:succ2}{If1}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	173 \nodebi{Compare}{<}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	174 \nodebi{LoopBeginPhi}{LoopBeginPhi}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	175 \nodebi{Add}{+}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	176 \datalabel{Add:in1}{LoopBeginPhi}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	177 \datalabel{Add:in2}{Constant1}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	178 \nodebi{LoopEndPhi}{LoopEndPhi}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	179 \control{LoopBeginPhi}{LoopEndPhi}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	180 \data{LoopEndPhi:in1}{LoopEnd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	181 \data{LoopEndPhi:in2}{Add}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	182 \datalabel{LoopBeginPhi:in1}{LoopBegin}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	183 \datalabel{LoopBeginPhi:in2}{Constant0}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	184 \datalabel{Compare:in1}{LoopBeginPhi}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	185 \datalabel{Compare:in2}{n}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	186 \data{If1}{Compare}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	187 \controllabel{If1:succ1}{LoopEnd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	188 \controllabel{BeforeLoop}{LoopBegin}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	189 \controllabel{If1:succ2}{Exit}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	190 \end{digraphenv}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	191 \caption{Graal compiler graph for a loop counting from 0 to n-1.}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	192 \end{figure}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	193
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	194 \subsection{Loop Counters}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	195 The compiler is capable of recognizing variables that are only increased within a loop.
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	196 A potential overflow of such a variable is guarded with a trap before the loop.
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	197 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	198
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	199
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	200 \begin{figure}[h]
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	201 \label{fig:loop3}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	202 \centering
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	203 \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	204 \textnode{BeforeLoop}{Loop entry}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	205 \textnode{Exit}{Loop exit}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	206 \textnode{n}{n}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	207 \textnode{Constant0}{0}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	208 \textnode{Constant1}{1}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	209 \nodesplit{LoopBegin}{LoopBegin}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	210 \node{LoopEnd}{LoopEnd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	211 \nodesplit{If1}{If}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	212 \controllabel{LoopBegin:succ1}{LoopEnd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	213 \controllabel{LoopBegin:succ2}{If1}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	214 \nodebi{Compare}{<}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	215 \nodetri{LoopCounter}{LoopCounter}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	216 \datalabel{LoopCounter:in1}{LoopBegin}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	217 \datalabeltext{LoopCounter:in2}{Constant0}{init}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	218 \datalabeltext{LoopCounter:in3}{Constant1}{stride}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	219 \datalabel{Compare:in1}{LoopCounter}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	220 \datalabel{Compare:in2}{n}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	221 \data{If1}{Compare}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	222 \controllabel{If1:succ1}{LoopEnd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	223 \controllabel{BeforeLoop}{LoopBegin}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	224 \controllabel{If1:succ2}{Exit}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	225 \end{digraphenv}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	226 \caption{Graal compiler graph after loop counter transformation.}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	227 \end{figure}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	228
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	229 \subsection{Bounded Loops}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	230
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	231 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	232 The total number of iterations always denotes the number of full iterations of the loop with the control flowing from the loop begin to the loop end.
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	233 If the totel number of iterations is reached, the loop is exited directly from the loop header.
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	234 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	235 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	236
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	237 \begin{figure}[h]
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	238 \label{fig:loop4}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	239 \centering
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	240 \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	241 \textnode{BeforeLoop}{Loop entry}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	242 \textnode{Exit}{Loop exit}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	243 \textnode{n}{n}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	244 \textnode{Constant0}{0}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	245 \textnode{Constant1}{1}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	246 \nodesplittri{LoopBegin}{BoundedLoopBegin}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	247 \node{LoopEnd}{LoopEnd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	248 \controllabel{LoopBegin:succ1}{LoopEnd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	249 \controllabel{LoopBegin:succ2}{LoopEnd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	250 \controllabel{LoopBegin:succ3}{Exit}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	251 \nodetri{LoopCounter}{LoopCounter}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	252 \datalabel{LoopCounter:in1}{LoopBegin}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	253 \datalabeltext{LoopCounter:in2}{Constant0}{init}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	254 \datalabeltext{LoopCounter:in3}{Constant1}{stride}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	255 \data{LoopBegin}{n}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	256 \controllabel{BeforeLoop}{LoopBegin}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	257 \end{digraphenv}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	258 \caption{Graal compiler graph after bounded loop transformation.}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	259 \end{figure}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	260
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	261 \subsection{Vectorization}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	262
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	263 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	264 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	265 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	266 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	267 Figure \ref{fig:loop5} shows the compiler graph of the example loop after vectorization.
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	268 The vector nodes all work on an ordered list of integer values and are subject to canonicalization like any other node.
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	269
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	270
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	271 \begin{figure}[h]
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	272 \label{fig:loop5}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	273 \centering
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	274 \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	275 \textnode{Entry}{Entry}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	276 \textnode{Exit}{Exit}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	277 \textnode{n}{n}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	278 \textnode{Constant0}{0}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	279 \textnode{Constant1}{1}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	280 \node{Vector}{Vector}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	281 \nodebi{VectorAdd}{VectorAdd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	282 \nodebi{VectorMul}{VectorMul}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	283 \control{Entry}{Vector}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	284 \control{Vector}{Exit}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	285 \datalabel{VectorAdd:in1}{Vector}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	286 \datalabel{VectorAdd:in2}{Constant0}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	287 \datalabel{VectorMul:in1}{VectorAdd}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	288 \datalabel{VectorMul:in2}{Constant1}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	289 \data{Vector}{n}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	290 \end{digraphenv}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	291 \caption{Graal compiler graph after bounded loop transformation.}
6d99b909696d Documentation: More content and graphs on loops and vectorization. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2572 diff changeset	292 \end{figure}
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	293
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	294 \subsection{Project Source Structure}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	295 In order to have clear interfaces between the different parts of the compiler, the code will be divided into the following source code projects:
2562 0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	296 \cw{Use new naming scheme com.oracle.graal...}
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	297 \begin{description}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	298 \item[Graph] contains the abstract node implementation, the graph implementation and all the associated tools and auxiliary classes.
2562 0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	299 \item[Nodes] contains the node implementations, ranging from high-level to machine-level nodes. \cw{Can't we just stay with the name ``instruction'', which everyone understands, instead of ``Node''? I strongly vote for that.}
0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	300 \item[GraphBuilder] contains helpers for building graphs from Java bytecodes and other source representations.
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	301 \item[Assembler] contains the assembler classes that are used to generate the compiled code of methods and stubs.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	302 \item[Optimizations] contains all the optimizations, along with different optimization plans.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	303 \item[GraalCompiler] contains the compiler, including:
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	304 \begin{itemize}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	305 \item Handling of compilation phases.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	306 \item Compilation-related data structures.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	307 \item Implementation of the \emph{compiler interface} (CI).
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	308 \item Register allocation.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	309 \item Machine code creation, including debug info.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	310 \item Debug output and compilation observation.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	311 \item Compiler options management.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	312 \end{itemize}
2562 0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	313 \cw{So you want to keep the backend as part of the ``main compiler'' at first. Seems OK for me.}
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	314 \end{description}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	315
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	316 \subsection{Initial Steps}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	317 \begin{itemize}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	318 \item Restructuring of the project to include the compiler and the modified HotSpot code within one repository. The CRI project will remain in the Maxine repository, because it will remain mostly unchanged.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	319 \item Stripping optimizations from the existing compiler, they will be reimplemented later on using the new infrastructure.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	320 \item Creating Node and Graph classes, along with the necessary auxiliary classes.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	321 \item Writing documentation on the design of the compiler.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	322 \item Use the Node class as the superclass of the existing Value class.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	323 \item Identify (and later: remove) extended bytecodes.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	324 \item Implement the new frame state concept.
2562 0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	325 \item Remove LIR - in the long run there should only be one IR, which will be continually lowered until only nodes that can be translated into machine code remain. \cw{That cannot be an initial step, because you have nothing yet that could replace the LIR.}
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	326 \end{itemize}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	327
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	328 \subsection{Nodes and Graphs}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	329 The most important aspect of a compiler is the data structure that holds information about an executable piece of code, called \emph{intermediate representation}~(IR).
2562 0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	330 The IR used in the Graal Compiler (simply referred to as \emph{the compiler} in the rest of this document) was designed in such a way as to allow for extensive optimizations, easy traversal, compact storage and efficient processing.
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	331
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	332 \subsubsection{The Node Data Structure}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	333 \begin{itemize}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	334 \item Each node is always associated with a graph.
2562 0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	335 \item Each node has an immutable id which is unique within its associated graph. \cw{The server compiler supports ``renumbering'' of nodes to make the ids dense again after large graph manipulations that deleted many nodes.}
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	336 \item Nodes represent either operations on values or control flow operations.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	337 \item Nodes can have a data dependency, which means that one node requires the result of some other node as its input. The fact that the result of the first node needs to be computed before the second node can be executed introduces a partial order to the set of nodes.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	338 \item Nodes can have a control flow dependency, which means that the execution of one node depends on some other node. This includes conditional execution, memory access serialization and other reasons, and again introduces a partial order to the set of nodes.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	339 \item Nodes can only have data and control dependencies to nodes which belong to the same graph.
2562 0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	340 \item Control dependencies and data dependencies each represent a \emph{directed acyclic graph} (DAG) on the same set of nodes. This means that data dependencies always point upwards, and control dependencies always point downwards. Situations that are normally incur cycles (like loops) are represented by special nodes (like LoopEnd).
0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	341 \cw{I don't like that item. Cycles are a normal thing for control flow and for phi functions. I would phrase it as something like that: Nodes can only have data and control dependencies to nodes that are dominators. The only exception of that are control loop headers and phi functions}
0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	342 \item Ordering between nodes is specified only to the extent which is required to correctly express the semantics of a given program. Some compilers (notably the HotSpot client compiler \cw{Wrong: the client compiler only has a fixed order of pinned instructions, most instructions are not pinned and can be moved around freely}) always maintain a complete order for all nodes (called \emph{scheduling}), which impedes advanced optimizations. For algorithms that require a fixed ordering of nodes, a temporary schedule can always be generated.
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	343 \item Both data and control dependencies can be traversed in both directions, so that each node can be traversed in four directions:
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	344 \begin{itemize}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	345 \item \emph{inputs} are all nodes that this node has data dependencies on.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	346 \item \emph{usages} are all nodes that have data dependencies on this node, this is regarded as the inverse of inputs.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	347 \item \emph{successors} are all nodes that have a control dependency on this node.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	348 \item \emph{predecessors} are all nodes that this node has control dependencies on, this is regarded as the inverse of successors.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	349 \end{itemize}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	350 \item Only inputs and successors can be changed, and changes to them will update the usages and predecessors.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	351 \item The Node class needs to provide facilities for subclasses to perform actions upon cloning, dependency changes, etc.
2562 0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	352 \item Nodes cannot be reassigned to another graph, they are cloned instead \cw{Why should there be the need for more than one graph when compiling a method?}
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	353 \end{itemize}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	354
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	355 \subsubsection{The Graph Data Structure}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	356 \begin{itemize}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	357 \item A graph deals out ids for new nodes and can be queried for the node corresponding to a given id.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	358 \item Graphs can manage side data structures, which will be automatically invalidated and lazily recomputed whenever the graph changes. Examples for side data structures are dominator trees and temporary schedules. These side data structures will usually be understood by more than one optimization.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	359 \item Graphs are
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	360 \end{itemize}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	361
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	362 \subsection{Frame States}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	363 Frame states capture the state of the program, in terms of the source representation (e.g., Java state: local variables, expressions, ...).
2572 28a8b3c8b9b4 Small fix to documentation. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2562 diff changeset	364 Whenever a safepoint is reached or \cw{why is that an ``or'', both is basically the same} a deoptimization is needed a valid frame state needs to be available.
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	365 A frame state is valid as long as the program performs only actions that can safely be reexecuted (e.g., operations on local variables, etc.).
2562 0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	366 Thus, frame states need only be generated for bytecodes that cannot be reexecuted: putfield, astore, invoke, monitorenter/exit, ...
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	367
2562 0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	368 Within the node graph a frame state is represented as a node that is fixed between the node that caused it to be generated (data dependency) and the node that invalidates it (control dependency).
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	369
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	370 Deopmization nodes are not fixed to a certain frame state node, they can move around freely and will always use the correct frame state.
2562 0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	371 At some point during the compilation, deoptimization nodes need to be fixed, which means that appropriate data and control dependencies will be inserted so that it can not move outside the scope of the associated frame state.
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	372 This will generate deoptimization-free zones that can be targeted by the most aggressive optimizations.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	373
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	374 Frame states should be represented using a delta-encoding.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	375 This will make them significantly smaller and will make inlining, etc. much easier.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	376 In later compilation phases unnecessary frame states might be removed, using a mark-and-merge algorithm.
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	377
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	378
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	379
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	380 \subsection{Graph Building}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	381 \begin{itemize}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	382 \item The graph built by the initial parser (called \emph{GraphBuilder}) should be as close to the source representation (bytecode, ...) as possible.
2562 0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	383 \item All nodes should be able to immediately lower themselves to a machine-level representation. \cw{What is that? You mean every node has x86 specific code that spits out machine code? Hope you are joking...} This allows for easier compiler development, and also leads to a compiler that is very flexible in the amount of optimizations it performs (e.g. recompilation of methods with more aggressive optimizations).
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	384 \item
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	385 \end{itemize}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	386
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	387 \subsection{Graphical Representation}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	388 The graphs in this document use the following node layout:
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	389
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	390 \begin{digraphenv}{scale=0.5}{layout01}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	391 \node{node1}{nop}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	392 \nodebi{node2}{+}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	393 \nodetri{node3}{phi}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	394 \nodesplit{node4}{if}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	395 \end{digraphenv}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	396
2562 0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	397 \cw{That doesn't compile with my latex. What do I have to do to get it working?}
0023bd42eefe comments christian.wimmer@oracle.com parents: 2561 diff changeset	398
2561 765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	399 Red arrows always represents control dependencies, while black arrows represent data dependencies:
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	400
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	401 \begin{digraphenv}{scale=0.5}{layout1}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	402 \node{a}{a}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	403 \node{b}{b}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	404 \nodesplit{if}{if}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	405 \node{nop}{nop}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	406 \nodebi{add}{+}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	407 \controllabel{if:succ1}{nop}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	408 \controllabel{if:succ2}{add}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	409 \datalabel{add:in1}{a}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	410 \datalabel{add:in2}{b}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	411 \end{digraphenv}
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	412
765dd54244a6 Updated doc. Added Texclipse project. Thomas Wuerthinger <thomas@wuerthinger.net> parents: 2517 diff changeset	413
2517 8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	414
8c6e31c62fba added initial version of design docs, fixed .hgignore (regex, . -> \.) Lukas Stadler <lukas.stadler@jku.at> parents: diff changeset	415 \end{document}

Mercurial > hg > truffle

annotate doc/design/graal_compiler.tex @ 2574:d1ea2563836d