--- a/doc/design/graal_compiler.tex	Fri Apr 29 16:51:33 2011 +0200
+++ b/doc/design/graal_compiler.tex	Fri Apr 29 11:14:05 2011 -0700
@@ -17,6 +17,17 @@
 \newcommand{\Sb}{{\Large$^\dag$}}
 \newcommand{\Sc}{{\Large$^\S$}}
 
+
+\newcommand{\mynote}[2]{
+\textcolor{red}{\fbox{\bfseries\sffamily\scriptsize#1}
+  {\small\textsf{\emph{#2}}}
+\fbox{\bfseries\sffamily\scriptsize }}}
+
+\newcommand\TODO[1]{\mynote{TODO}{#1}}
+\newcommand\cw[1]{\mynote{CW}{#1}}
+
+
+
 \smartqed  % flush right qed marks, e.g. at end of proof
 
 \journalname{Graal Compiler Design}
@@ -62,25 +73,28 @@
 For the implementation of the Graal compiler, we rely on the following design decisions:
 \begin{description}
 \item[Graph Representation:]
-The compiler's intermediate representation is modelled as a graph with nodes that are connected with directed edges.
+The compiler's intermediate representation is modeled as a graph with nodes that are connected with directed edges.
 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.
 Every node is serializable and has an id that is unique within its graph.
 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.
-There is no cycle in the graph that contains only control flow edges or only data flow edges.
+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.}
 It is possible to replace a node with another node without traversing the full graph.
 \item[Extensibility:]
 The compiler is extensible by adding new compiler phases and new node subclasses without modifying the compiler's sources.
 A node has an abstract way of expressing its effect and new compiler phases can ask compiler nodes for their properties and capabilities.
+\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.}
 \item[Detailing:]
 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).
 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).
 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).
+\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.}
 \item[Generality:]
 The compiler does not require Java as its input.
 This is achieved by having a graph as the starting point of the compilation and not a Java bytecodes array.
 Building the graph from the Java bytecodes must happen before giving a method to the compiler.
 This enables front-ends for different languages (e.g., Ruby) to provide their own graph.
 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.
+\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.}
 \end{description}
 
 \section{Milestones}
@@ -94,11 +108,15 @@
 \item[M4:] We have reintegrated the new Graal compiler into the Maxine VM and can use it as a Maxine VM bootstrapping compiler.
 \end{description}
 
+\cw{That's a very coarse (not to say useless) listing, sound a bit like the generic ``define problem - think hard about it - publish it''...}
+
+\cw{Mario wants a timeline.  You better think about that carefully, so that you can keep the timeline.  Mario doesn't want to repeat the C1X experience where at first it should take only 2 months, but it finally takes 2 years.  Take that as a confidential hint from me...}
+
 After those four milestones, we see three different possible further development directions that can be followed in parallel:
 \begin{itemize}
   \item Removal of the XIR template mechanism and replacement with a snippet mechanism that works with the Graal compiler graph.
   \item Improvements for Graal peak performance (loop optimizations, escape analysis, bounds check elimination, processing additional interpreter runtime feedback).
-  \item Implementation of a prototype front-end for a scripting language (e.g., Ruby).
+  \item Implementation of a prototype front-end for different languages, e.g., JavaScript.
 \end{itemize}
 
 \section{Implementation}
@@ -106,10 +124,11 @@
 
 \subsection{Project Source Structure}
 In order to have clear interfaces between the different parts of the compiler, the code will be divided into the following source code projects:
+\cw{Use new naming scheme com.oracle.graal...}
 \begin{description}
     \item[Graph] contains the abstract node implementation, the graph implementation and all the associated tools and auxiliary classes.
-    \item[Nodes] contains the node implementations, ranging from high-level to machine-level nodes.
-    \item[GraphBuilder] contains helpers for building graphs from java bytecodes and other source representations.
+    \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.}
+    \item[GraphBuilder] contains helpers for building graphs from Java bytecodes and other source representations.
     \item[Assembler] contains the assembler classes that are used to generate the compiled code of methods and stubs.
     \item[Optimizations] contains all the optimizations, along with different optimization plans.
     \item[GraalCompiler] contains the compiler, including:
@@ -122,6 +141,7 @@
             \item Debug output and compilation observation.
             \item Compiler options management.
         \end{itemize}
+		\cw{So you want to keep the backend as part of the ``main compiler'' at first.  Seems OK for me.}
 \end{description}
 
 \subsection{Initial Steps}
@@ -133,23 +153,24 @@
     \item Use the Node class as the superclass of the existing Value class.
     \item Identify (and later: remove) extended bytecodes.
     \item Implement the new frame state concept.
-    \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.
+    \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.}
 \end{itemize}
 
 \subsection{Nodes and Graphs}
 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).
-The IR used in the Graal Compiler (simply refered 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.
+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.
 
 \subsubsection{The Node Data Structure}
 \begin{itemize}
     \item Each node is always associated with a graph.
-    \item Each node has an immutable id which is unique within its associated graph.
+    \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.}
     \item Nodes represent either operations on values or control flow operations.
     \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.
     \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.
     \item Nodes can only have data and control dependencies to nodes which belong to the same graph.
-    \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 incurr cycles (like loops) are represented by special nodes (like LoopEnd).
-    \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) 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.
+    \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).
+		\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}
+    \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.
     \item Both data and control dependencies can be traversed in both directions, so that each node can be traversed in four directions:
     \begin{itemize}
         \item \emph{inputs} are all nodes that this node has data dependencies on.
@@ -159,7 +180,7 @@
     \end{itemize}
     \item Only inputs and successors can be changed, and changes to them will update the usages and predecessors.
     \item The Node class needs to provide facilities for subclasses to perform actions upon cloning, dependency changes, etc.
-    \item Nodes cannot be reassigned to another graph, they are cloned instead
+    \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?}
 \end{itemize}
 
 \subsubsection{The Graph Data Structure}
@@ -171,14 +192,14 @@
 
 \subsection{Frame States}
 Frame states capture the state of the program, in terms of the source representation (e.g., Java state: local variables, expressions, ...).
-Whenever a safepoint is reached or the a deoptimization is needed a valid frame state needs to be available.
+Whenever a safepoint is reached or \cwi{why is that an ``or'', both is basically the same} a deoptimization is needed a valid frame state needs to be available.
 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.).
-Thus, frame states need only be generated for bytecodes that can not be reexecuted: putfield, astore, invoke, monitorenter/exit, ...
+Thus, frame states need only be generated for bytecodes that cannot be reexecuted: putfield, astore, invoke, monitorenter/exit, ...
 
-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 will invalidate it (control dependency).
+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).
 
 Deopmization nodes are not fixed to a certain frame state node, they can move around freely and will always use the correct frame state.
-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.
+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.
 This will generate deoptimization-free zones that can be targeted by the most aggressive optimizations.
 
 Frame states should be represented using a delta-encoding.
@@ -190,7 +211,7 @@
 \subsection{Graph Building}
 \begin{itemize}
     \item The graph built by the initial parser (called \emph{GraphBuilder}) should be as close to the source representation (bytecode, ...) as possible.
-    \item All nodes should be able to immediately lower themselves to a machine-level representation. 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).
+    \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).
     \item 
 \end{itemize}
 
@@ -204,6 +225,8 @@
 \nodesplit{node4}{if}
 \end{digraphenv}
 
+\cw{That doesn't compile with my latex.  What do I have to do to get it working?}
+
 Red arrows always represents control dependencies, while black arrows represent data dependencies:
 
 \begin{digraphenv}{scale=0.5}{layout1}