adjusted placement of figures and tables; minor edits in section 3
authorNorman Ramsey <nr@cs.tufts.edu>
Sat, 24 Jul 2010 00:00:46 +0000 (20:00 -0400)
committerNorman Ramsey <nr@cs.tufts.edu>
Sat, 24 Jul 2010 00:00:46 +0000 (20:00 -0400)
paper/dfopt.tex

index 6f41701..ec5d240 100644 (file)
@@ -848,9 +848,9 @@ if it is closed, it may have arbitrarily many successors---or none.
 
 \subsection{Nodes} \seclabel{nodes}
 
-The primitive constituents of a \ourlib{} control-flow graph are
+The primitive constituents of a control-flow graph are
 \emph{nodes}, which are defined by the client.
-Typically, a node might represent a machine instruction, such as an
+For example, a node might represent a machine instruction, such as an
 assignment, a call, or a conditional branch.  
 But \ourlib{}'s graph representation is \emph{polymorphic in the node type},
 so each client can define nodes as it likes.
@@ -882,7 +882,7 @@ Such a type parameter may be instantiated only with type @O@~(for
 open) or type~@C@ (for closed).
 
 As an example,
-\figref{cmm-node} shows a typical node type as it might be written by
+\figref{cmm-node} shows a typical node type as it might be defined by
 one of \ourlib's {clients}.
 The type parameters are written @e@ and @x@, for
 entry and exit respectively.  
@@ -921,6 +921,42 @@ basic block,
 we~often call them \emph{first}, \emph{middle}, and \emph{last} nodes
 respectively.
 
+
+\begin{figure}
+\begin{fuzzcode}{0.98pt}
+data `O   -- Open
+data `C   -- Closed
+
+data `Block n e x where
+ `BFirst  :: n C O                      -> Block n C O
+ `BMiddle :: n O O                      -> Block n O O
+ `BLast   :: n O C                      -> Block n O C
+ `BCat    :: Block n e O -> Block n O x -> Block n e x
+
+data `Graph n e x where
+  `GNil  :: Graph n O O
+  `GUnit :: Block n O O -> Graph n O O
+  `GMany :: MaybeO e (Block n O C) 
+        -> LabelMap (Block n C C)
+        -> MaybeO x (Block n C O)
+        -> Graph n e x
+
+data `MaybeO ^ex t where
+  `JustO    :: t -> MaybeO O t
+  `NothingO ::      MaybeO C t
+
+newtype `Label -- abstract type
+
+class `NonLocal n where
+  `entryLabel :: n C x -> Label
+  `successors :: n e C -> [Label]
+\end{fuzzcode}
+\caption{The block and graph types defined by \ourlib} 
+\figlabel{graph} \figlabel{edges}
+\end{figure}
+% omit MaybeC :: * -> * -> *
+
+
 \subsection{Blocks} \seclabel{blocks}
 
 \ourlib\ combines the client's nodes into
@@ -941,11 +977,9 @@ shape?
 Because by making the shape known statically, we simplify the
 implementation of analysis and transformation in 
 \secref{dfengine}. 
-\finalremark{SLPJ: Do we intend that clients
-can see the representation of blocks?
-Answer: At present the representation is partially exposed, and we
-have no principled answer to the question.  ---NR
-OK; but what do we tell our readers?
+\finalremark{We have no principled answer to the question of what
+parts of the representation of blocks are exposed.
+Do we tell our readers or just ignore the question?
 }
 
 The @BCat@ constructor concatenates blocks in sequence. 
@@ -979,46 +1013,11 @@ to a middle node or a last node.
 an~explicit edge originates in a last node and flows to a (labelled)
 first node. 
 \hoopl\ discovers explicit edges by using the @successors@ and
-@entryLabel@ functions of the @NonLocal@ class.
+@entryLabel@ functions of the @NonLocal@ class (\figref{graph}).
 Any~edge, whether implicit or explicit, is considered a program point,
 and an analysis written using \hoopl\ computes a dataflow fact at each
 such point.
 
-\begin{figure}
-\begin{fuzzcode}{0.98pt}
-data `O   -- Open
-data `C   -- Closed
-
-data `Block n e x where
- `BFirst  :: n C O                      -> Block n C O
- `BMiddle :: n O O                      -> Block n O O
- `BLast   :: n O C                      -> Block n O C
- `BCat    :: Block n e O -> Block n O x -> Block n e x
-
-data `Graph n e x where
-  `GNil  :: Graph n O O
-  `GUnit :: Block n O O -> Graph n O O
-  `GMany :: MaybeO e (Block n O C) 
-        -> LabelMap (Block n C C)
-        -> MaybeO x (Block n C O)
-        -> Graph n e x
-
-data `MaybeO ^ex t where
-  `JustO    :: t -> MaybeO O t
-  `NothingO ::      MaybeO C t
-
-newtype `Label -- abstract type
-
-class `NonLocal n where
-  `entryLabel :: n C x -> Label
-  `successors :: n e C -> [Label]
-\end{fuzzcode}
-\caption{The block and graph types defined by \ourlib} 
-\figlabel{graph} \figlabel{edges}
-\end{figure}
-% omit MaybeC :: * -> * -> *
-
-
 \subsection{Graphs} \seclabel{graphs}
 
 \ourlib{} composes blocks into graphs, which are also defined 
@@ -1105,10 +1104,7 @@ The representation of @Graph@s is exposed to \hoopl's clients.
 \finalremark{This \P\ is a candidate to be cut.}
 We~have carefully crafted the types so that if @BCat@ 
 is considered as an associative operator, 
-every graph has a unique representation.\finalremark{So what? (Doumont)
-Need some words about how this is part of making the API simple for
-the client---I've added something to the end of the paragraph, but I'm
-not particularly thrilled.}
+every graph has a unique representation.
 %%  \simon{Well, you were the one who was so keen on a unique representation!
 %%  And since we have one, I think tis useful to say so. Lastly, the representation of
 %%  singleton blocks is not entirely obvious.}
@@ -1206,32 +1202,6 @@ if a @Graph@ is closed on entry, it need not have a unique entry label.
 
 
 
-\begin{table}
-\centerline{%
-\begin{tabular}{@{}>{\raggedright\arraybackslash}p{1.03in}>{\scshape}c>{\scshape
-}
-      c>{\raggedright\arraybackslash}p{1.29in}@{}}
-&\multicolumn1{r}{\llap{\emph{Specified}}\hspace*{-0.3em}}&
-\multicolumn1{l}{\hspace*{-0.4em}\rlap{\emph{Implemented}}}&\\
-\multicolumn1{c}{\emph{Part of optimizer}}
-&\multicolumn1{c}{\emph{by}}&
-\multicolumn1{c}{\emph{by}}&
-\multicolumn1{c}{\emph{How many}}%
-\\[5pt]
-Control-flow graphs& Us & Us & One \\
-Nodes in a control-flow graph & You & You & One type per intermediate language \\[3pt]
-Dataflow fact~$F$    & You & You & One type per logic \\
-Lattice operations & Us & You & One set per logic \\[3pt]
-Transfer functions & Us & You & One per analysis \\
-Rewrite functions & Us & You & One per \rlap{transformation} \\[3pt]
-Solve-and-rewrite functions & Us & Us & Two (forward, backward) \\
-\end{tabular}%
-}
-\ifpagetuning\vspace*{0.5\baselineskip}\fi
-\caption{Parts of an optimizer built with \ourlib}
-\tablabel{parts}
-\end{table}
-
 
 
 \section {Using \ourlib{} to analyze and transform graphs} \seclabel{using-hoopl}
@@ -1271,6 +1241,33 @@ These requirements are summarized in \tabref{parts}.
 Because facts, transfer functions, and rewrite functions work together,
 we~combine them in a single record of type @FwdPass@ (\figref{api-types}).
 
+\begin{table}
+\centerline{%
+\begin{tabular}{@{}>{\raggedright\arraybackslash}p{1.03in}>{\scshape}c>{\scshape
+}
+      c>{\raggedright\arraybackslash}p{1.29in}@{}}
+&\multicolumn1{r}{\llap{\emph{Specified}}\hspace*{-0.3em}}&
+\multicolumn1{l}{\hspace*{-0.4em}\rlap{\emph{Implemented}}}&\\
+\multicolumn1{c}{\emph{Part of optimizer}}
+&\multicolumn1{c}{\emph{by}}&
+\multicolumn1{c}{\emph{by}}&
+\multicolumn1{c}{\emph{How many}}%
+\\[5pt]
+Control-flow graphs& Us & Us & One \\
+Nodes in a control-flow graph & You & You & One type per intermediate language \\[3pt]
+Dataflow fact~$F$    & You & You & One type per logic \\
+Lattice operations & Us & You & One set per logic \\[3pt]
+Transfer functions & Us & You & One per analysis \\
+Rewrite functions & Us & You & One per \rlap{transformation} \\[3pt]
+Analyze-and-rewrite functions & Us & Us & Two (forward, backward) \\
+\end{tabular}%
+}
+\ifpagetuning\vspace*{0.5\baselineskip}\fi
+\caption{Parts of an optimizer built with \ourlib}
+\tablabel{parts}
+\end{table}
+
+
 
 
 Given a node type~@n@ and a @FwdPass@,