

\chapter{Middle End Modules}

\section{Introduction}

The program graph structure is extremely flexible and expressive.
Constraining middle end modules to work on program graphs is hardly a
restraint since the number of different types of instructions in a
program graph is indefinitely extendable. In retrospect, the design of
the Id compiler is complicated by an intermediate language that is
{\it too} flexible (though extensions to the core of the intermediate
language are easier to express, if not implement). Without a more
restrictive notion of an intermediate language, adding new program
graph instructions can impinge on every module in the middle end. For
ease of development, it's probably best, to define several
intermediate languages, each a small perturbation of the other, which
have modules that work exclusively on them.  Other, more general
modules can be defined to work with every perturbation. In actuality,
the Id compiler implements this scheme, but its boundaries are hard to
define without close examination of the compiler's code.

\section{Ordering the Modules}	

The middle end modules can be divided into two categories: {\it
tranformation} and {\it optimization}. Optimization modules perform machine
independent optimizations within a given intermediate language. They can be
used in any order, any number of times (including not at all).
Transformation modules, convert one intermediate language to another.
Usually they perform a small perturbation of the intermediate language by
either excising opcodes, adding opcodes or enforcing some machine dependent
constraint on the graph.  They {\it must} be used exactly once in a
sensible order.

\begin{itemize}

\item The following modules transform the program graph:

\begin{tabular}{llr}
{\tt generate-program-graph }	& Creates a program graph from a parse tree. \\
{\tt manager-synchronization}	& Connects {\tt release} instructions. \\
{\tt call-substitution}		& Stores inlinable functions in the Exsym table. \\
{\tt synchronize-release}		& Translates the {\tt synch} instruction. \\
{\tt thunk-splitting}		& Translates the {\tt thunk} instruction. \\
{\tt  inlineable-definitions}		& Inlines functions. \\
{\tt loop-constant-propagation}	& Inserts loop-constant instructions. \\
{\tt code-blocks}			& Splits loop's into seperate code blocks. \\
{\tt loop-analysis} 			& Determine's when a while loop can be used as a for loop. \\
{\tt unroll-loops}			& Unroll and unfold loops. \\
{\tt signals-and-triggers}		& Insert signals and triggers into the graph.\\
\end{tabular}

The above ordering of transformation modules gives a middle end with a minimum number of modules.

\item The following modules optimize the program graph:

\begin{tabular}{llr}
{\tt fetch-elimination}		& Remove fetch's when a corresponding store found. \\
{\tt simple-fetch-elimination}	& Remove fetch's from functional data-structures. \\
{\tt dead-code-elimination}		& Remove dead code. \\
{\tt constant-propagation}		& Propagate constants through encapsulators and bodies.\\
{\tt cse-and-hoisting} 		& Common subexpression eilmination and hoisting out of loops.\\
{\tt partial-evaluation}		& Simplify some algebraic identities. \\
{\tt circulate-structures}		& Hoist allocate's and deallocate's out of loops. \\
\end{tabular}


Note, a minimal middle end won't necessarily compile quickly
since some optimizations shrink the the program graph's size considerably.

\end{itemize}

\section{The Modules}

Each module description briefly describes some high-level characteristic of the module,
including:

\begin{description}
\item[Module:] The {\tt defcompiler} module definition.
\item[Options:] A description of the module's options.
\item[Description:] A declarative description of the module's effect on the program graph.
\item[Strategy:] The module's method of traversing the graph.
\item[Author:]  Primary person responsible for coding.
\item[Caveats:] Known limitations, warnings, points of interest etc.
\end{description}

Each module in the middle end of the compiler reads or modifies a number of global
data structures in addition to its explicit program graph argument and result.
The following entries, for each module, provide information about its usage of global
data structures:

\begin{description}
\item[Exsym Properties:] External symbol properties.
\item[Graph Properties:] Dataflow graph properties.
\item[Instruction Properties:] Program graph instruction properties.
\item[Instruction Slots:] Program graph instruction slots.
\end{description}

Not each module has all the entries filled in. If a module is the
first to define an entry in a global structure or is the exclusive
user of an entry then the entry's name is in {\bf boldface} followed
by a description. Otherwise, just the name is listed.

\subsection{Generate Program Graph}

%\paragraph{Exsym Properties:}

%\paragraph{Instruction Properties:}

%\paragraph{Instruction Slots:}

\paragraph{Module:}
\begin{verbatim}
(defcompiler-module generate-program-graph id-compiler
  (:input parse-tree procedure)
  (:output program-graph procedure)
  (:options check-bounds)
  (:function gpg-definition))
\end{verbatim}

%\paragraph{Options:}
%\begin{defn}
% \item \bfidentype{check-bounds}{\btype{boolean}} determines whether bounds-checking code is
%inserted for array references.  The default is {\tt nil}, so
%bounds-checking is usually not done. 
% \end{defn}

\paragraph{Description:}

The primary function of this module is to transform the parse-tree
into a program graph. Pattern matching is also compiled out at this
stage, although it should probably be done at an earlier module.

\footnote{
Nikhil and Arvind figured out the algorithm for doing pattern matching
regardless of the order of the patterns.  The algorithm for this is
described in the file: {\tt /jj/nikhil/haskell/pattern-matching.text}
Unfortunately, this file has not been published -- perhaps it should
be turned into a CSG memo.  Other pattern matching algorithms can be
found in Simon Peyton Jones's book \cite{PJ87}.  }

\paragraph{Strategy:}

The information obtained from the {\tt scope-analysis} module is used to
wire together instructions, given the parse-tree.

\paragraph{Author:} Ken Traub, October 1986.  

\paragraph{Caveats:} Pattern matching should logically being in the 
desugaring module in the front end.  At this point, it would probably be
too difficult to change move this code there.

\subsection{Fetch Elimination}

\paragraph{Instruction Properties:} store-like-p, fetch-like-p
%\paragraph{Instruction Slots:} 

\paragraph{Module:}
\begin{verbatim}
(defcompiler-module fetch-elimination id-compiler
  (:input program-graph code-block)
  (:output program-graph code-block)
  (:options fetch-elimination)
  (:function fe-code-block))
\end{verbatim}

\paragraph{Description:}
Fetch elimination traverses the program graph searching for instructions
storing values into data aggregates. When a ``store-like'' instruction is
found it looks back from it's inputs for the create instruction allocating
the aggregate. If found it follows the aggregate's other uses looking for
other fetch instructions retrieving information placed in the aggregate by
the store. These fetches can be eliminated by rewiring from the store
instruction's input.

\paragraph{Strategy:}
Uses {\tt with-instruction-array} to traverse every instruction in the
graph, hence it doesn't do fetch elimination across encapsulator
boundaries\footnote{To {\tt with-instruction-array} an encapsulator's
subgraphs are disjoint from the graph containing the encapsulator.
Logical connections between the two are determined by the semantics of
the encapsulator and are captured, for simple cases by an encapsulator's {\tt
encapsulator-propagating-alist} property}. Fetch elimination is defined for
i-structures, tuples, sums and cons.

\paragraph{Caveats:} Fetch elimination doesn't look across encapsulator
boundaries.

\subsection{Simple Fetch Elimination}

\paragraph{Instruction Properties:} fetch-like-p
%\paragraph{Instruction Slots:} 

\paragraph{Module:}
\begin{verbatim}
(defcompiler-module simple-fetch-elimination id-compiler
  (:input program-graph code-block)
  (:output program-graph code-block)
  (:options fetch-elimination)
  (:function sfe-code-block))
\end{verbatim}

\paragraph{Description:}
Traverse the program graph searching for instructions fetching from a data
aggregate. When the fetch is from an aggregate allocated by a functional
create instruction (determined by the result of sfe-match) then the fetch
instruction can eliminated by wiring directly from the create instruction's
input.

\paragraph{}The following pairs of functional \angleb{constructor, selector} 
instructions can be ``short-circuited'' (ie.  an input of the constructor
instruction can be wired around the selector function. The, no longer connected,
selector function can be removed. \\
\\
\angleb{{\tt make-functional-tuple, tuple-fetch}}\\
\angleb{{\tt make-functional-sum, sum-fetch}}\\
\angleb{{\tt make-functional-sum, disjunct-number}}\\

\paragraph{Strategy:}
Uses {\tt with-instruction-array} to traverse every instruction in the
graph, hence it doesn't look across encapsulator boundaries.

\paragraph{Author:} Jonathan Young, September 1988.

\paragraph{Caveats:} Simple fetch elimination doesn't look
across encapsulator boundaries.

\subsection{Dead Code Elimination}

\paragraph{Instruction Properties:} 
side-effecting-p, create-like-p
%\paragraph{Instruction Slots:} 

\paragraph{Module:}
\begin{verbatim}
(defcompiler-module dead-code-elimination id-compiler
  (:input program-graph code-block)
  (:output program-graph code-block)
  (:options dead-code-elimination)
  (:function dce-code-block))
\end{verbatim}

\paragraph{Description:}
There are three types of dead code elimination:
\begin{enumerate}

\item Remove non-encapsulating, non-side-effecting instructions with unused outputs.

\item Remove arcs from encapsulators.

	\begin{enumerate}
	\item If there is an {\tt if} output not used, then disconnect the corresponding arcs
	feeding the interior {\tt then-output} and {\tt else-output}.

	\item If there is an {\tt if} input or {\tt loop} constant not used within any interior blocks,
	disconnect the corresponding arc feeding the exterior.
	\end{enumerate}

\item Find structure creating instructions that only feed structure storing
instructions. Remove both the creating and storing instructions.

\end{enumerate}

\paragraph{Strategy:}
Traverse the program graph doing 2a on the way down for each level. On the
way up do 1 for all non-SE instruction in the basic-block (searching out
the largest subgraphs with unused outputs) and 3 for all create-like
instructions. Finish each level by doing 2b.

\paragraph{Author:} Ken Traub, June, 1987

\paragraph{Caveats:}
Step 2 should be generalized to other encapsulators.  Neither entire
encapsulators, useless circulating variables from loops, or dead but cyclic
portions of the graph are eliminated.  Not all the dead code is caught in
one pass.


\subsection{Constant and Loop Constant Propagation}

The constant propagation module and the loop constant propagation module
use the same internal functions and differ only in the way they handle
propagation of loop constants.

\paragraph{Instruction Properties:} folding-function, inhibit-constant-propagation.
% \paragraph{Instruction Slots:} 

\paragraph{Module:}
\begin{verbatim}
(defcompiler-module constant-propagation id-compiler
  (:input program-graph code-block)
  (:output program-graph code-block)
  (:function cp-dataflow-graph)
  (:options constant-folding constant-propagation)
\end{verbatim}

\paragraph{Options:}
\begin{inden}
\item \bfidentype{constant-folding}{\btype{boolean}} Whether to evaluate constant expressions at compile time.
\item \bfidentype{constant-propagation}{\btype{boolean}} Whether to propagate constants through encapsulators at compile time.
\end{inden}

\paragraph{Description:} Constant propagation,
\begin{enumerate}
\item Evaluates expressions involving only constants.
\item Pushes constants through encapsulators.
\item Removes encapsulators that choose which internal block to execute based on a constant expression
by unencapsulating the appropriate block.
\end{enumerate}

\paragraph{Strategy:}
Traverse the program graph top-down. At each level identify constant
instructions and either evaluate (fold) them (creating a new constant
instruction) or, depending on where on an encapsulator they are connected,
push them in or use them to unencapsulate a block. If any blocks are
unencapsulated then iterate the process again at the same level. Otherwise,
recurse on the next lower level of the graph.

\paragraph{Module:}
\begin{verbatim}
(defcompiler-module loop-constant-propagation id-compiler
  (:input program-graph code-block)
  (:output program-graph code-block)
  (:function lcp-dataflow-graph)
  (:options constant-folding constant-propagation 
\end{verbatim}

\paragraph{Description:}
The loop constant propagation module, uses the same code as the constant
propagation module except it performs an extra transformation on loop
encapsulators. In addition to the constant propagation optimizations, it
removes constant arcs from the predicate and body blocks of loop
encapsulators and makes them the first variable arcs, splitting each arc
with a loop-constant instruction. Only constants actually used within the
body or predicate are retained.

\paragraph{Caveats:}
The loop-constant conversion is a machine specific optimization. It
turns free-variables occurring inside loops into constants that must
be evaluated before any of the loop's iterations begin. Conceptually,
it belongs in the back end.


\subsection{Code Block Partitioning}

\paragraph{Graph Properties:}
\begin{inden}
\item \bfidentype{code-block-summary}{} See below.
\item \bfidentype{n-loops}{}
\item \bfidentype{constant-area-size}{}
\end{inden}

\paragraph{Program Graph Instructions:}
\begin{inden}
\item The {\tt \bf fastcall-apply} instruction applies a code-block to n args and get m results.
\item The {\tt \bf fastcall-def} instruction defines a code block taking n args and returning m results.
\end{inden}

\paragraph{Instruction Properties:} 
side-effecting-p

% \paragraph{Instruction Slots:}

\paragraph{Module:}
\begin{verbatim}
(defcompiler-module code-blocks id-compiler
  (:input program-graph procedure)
  (:output program-graph procedure)
  (:function cb-procedure))
\end{verbatim}

\paragraph{Description:}
The code block partitioning module takes a procedure's program graph and
splits off each of the graph's loop encapsulators into their own code
block. These code blocks are contained inside {\tt fastcall-def}
encapsulators and linked into from the existing code blocks with {\tt
fastcall-apply}. For efficiency, both the loop encapsulator and any of its
constant inputs are lifted into the {\tt fastcall-def}.  As configured, the
module limits every code block (including the top-level {\tt def}) to at
most one loop.

\paragraph{Naming Conventions:}
If the top level procedure is named {\tt F} and has n code-blocks lifted
out then their names are {\tt F-0}, {\tt F-1}, \dots, {\tt F-(n-1)}.
Similarly, if F-i has n code blocks lifted out then their names are {\tt
F-i-0}, {\tt F-i-1}, \dots, {\tt F-i-(n-1)}, etc.

\begin{enumerate}
\item Each code block has the same {\tt :procedure-name} property as the outer
code block. 
\item The outer code block has a {\tt :code-block-summary} property describing
the names of code blocks lifted out and their hierarchy: {\tt (F (F-0) (F-1 (F-1-0)))}
says {\tt F} has three code blocks lifted out, two from the body of F and one from
the body of {\tt F-1}.
\end{enumerate}

\paragraph{Strategy:}
Code block partitioning proceeds top-down, splitting off all loop
instructions at a given level before proceeding into the next level of
encapsulators. It differentiates between loops at the top-most level and
ones nested inside other loops. The first top-level loop is kept in the
original code block and all others are split out. When a loop instruction
is found and split out, all the constants attached to the loop's inputs are
taken along with the loop.

This module should be called immediately prior to signal and trigger
generation.

\paragraph{Author:} Ken Traub, May, 1986.

\paragraph{Caveats:} The module's name should say something about loops!
Also, it uses a hack to find the constant instructions connected to a
loop's inputs which doesn't always give the best results.
The coding style might benefit from some graph cut and paste abstractions.

\subsection{Inlinable Definitions}

\paragraph{Exsym Properties:}
\begin{inden}
\item \bfidentype{:inlinable-definition}{(\ctype{string $\rightarrow$ dfgraph})}  maps procedure name to copy of dataflow-graph
\end{inden}

\paragraph{Graph Properties:} :inlinablep, :procedure-name

\paragraph{Module:}
\begin{verbatim}
(defcompiler-module inlinable-definitions id-compiler
  (:input program-graph procedure)
  (:output program-graph procedure)
  (:function ild-procedure))
\end{verbatim}

\paragraph{Description:}
For every code-block with the {\bf :inlinablep} property true, make an
entry in the current exsym table associating the procedure name of the
code-block with a copy of the code-block.

\paragraph{Caveats:} Inlinable definitions must come before call substitution.

\subsection{Call Substitution}

\paragraph{Exsym Properties:} :arity, :inlinable-definition, :recursive-set.

\paragraph{Instructions:}
\begin{inden}
\item \bfidentype{:direct-apply}{\ctype{instruction}} Known arity application (is not apply-like and is side-effecting).
\item \bfidentype{:apply-unsatisfied}{\ctype{instruction}} Unfulfilled arity application (is apply-like and not side-effecting).
\end{inden}

\paragraph{Instruction Properties:}side-effecting-p, apply-like-p.
\begin{inden}
\item \bfidentype{apply-like-p}{\btype{boolean}} True for apply or apply-unsatisfied instructions
\item \bfidentype{propagating-input-p}{(\ctype{encapsulator x input $\rightarrow$ \btype{boolean}})}
True if input of encapsulator propagates to each block.
\end{inden}

\paragraph{Instruction Slots:}
\begin{inden}
\item \bfidentype{instruction-cs-forwarding}{?} forwarding pointer from instruction which has all its connections
moved to another instruction.
\end{inden}


\paragraph{Module:}
\begin{verbatim}
(defcompiler-module call-substitution id-compiler
  (:input program-graph code-block)
  (:output program-graph code-block)
  (:options call-substitution)
  (:function cs-code-block))
\end{verbatim}


\paragraph{Description:}
\begin{enumerate}
\item Replaces a chain of applications of correct arity with :direct-apply 
(works across encapsulator boundaries) taking a :code-block literal
(as the function) and n arguments.
\item Replaces applications of incorrect arity with :apply-unsatisfied
\item Performs inlining for identifiers having the :inlinable-definition property
\begin{enumerate}
\item If the identifier is a constant then plug in its definition
\item If the identifier defines a function, then replace a :direct-apply by the code-block for the
function (if it's not in the :recursive set of the top-level definition, to avoid infinite
unwinding). Only full arity applications will be inlined.
\end{enumerate}
\end{enumerate}

\paragraph{Strategy:}
Traverse the program graph top-down. For each encapsulator, attach a source
to the encapsulator's anchor output. For every block in the encapsulator,
first traverse every simple instruction, searching for identifier literals.
Inline inlinable constant identifiers. For every non-constant identifier,
follow its application chain (perhaps into an encapsulator) and convert it
to either a direct-apply on a code-block literal or a chain of
apply-unsatisfieds. For every inlinable code-block literal, inline the
function body (subject to the recursive constraint) and recursively do call
substitution on its body. Finally, do call-substitution for every
encapsulator in the current block.

% \paragraph{Author:}

\paragraph{Caveats:} The code for cs-inline-function could use some
abstractions. A function application can only be inlined if the function's arity
is satisfied by its arguments. It seems like there may be a cleaner and
more efficient way of handling this optimization. 

% Why do you need complication of going across encaps boundaries? Can't
% we pull call chains out first or something... You're doing a lot of
% stuff with anchors in here that's not commented at all!  Can only
% inline functions with all their arguments known. Why not collapse ALL
% apply chains, satisfied or not worry about how you do the call in the
% machine graph?

\subsection{Common Subexpression Elimination and Code Hoisting}

% \paragraph{Exsym Properties:}

% \paragraph{Graph Properties:}

\paragraph{Instruction Properties:} 
side-effecting-p,
associative-p.

% \paragraph{Instruction Slots:}

\paragraph{Options:}
\begin{inden}
\item \bfidentype{cse}{\btype{boolean}}   Whether to eliminate common subexpressions
\item \bfidentype{hoist}{\btype{boolean}} Whether to hoist invariant subexpressions from loops
\end{inden}

\paragraph{Module:}
\begin{verbatim}
(defcompiler-module cse-and-hoisting id-compiler
  (:input program-graph code-block)
  (:output program-graph code-block)
  (:function csech-dataflow-graph)
  (:options cse hoist))
\end{verbatim}

\paragraph{Description:}
This module combines two interrelated but conceptually independent
optimizations, Common Subexpression Elimination (CSE) and Code Hoisting (CH)

\begin{description}

\item[CSE]   Common Subexpression Elimination (CSE) merges
duplicated expressions that compute the same function on the same inputs.
CSE is done only within a given code block and only for purely functional
expressions composed entirely of simple instructions (see caveats). There
is no attempt to detect and eliminate equivalent encapsulators (the
rationale being that this case won't occur often).


\item[Combine Equivalent Inputs to Encapsulators] CSE may make some inputs
of a loop or seq encapsulator redundant and they should be eliminated
before CH or else code may be duplicated when lifted out through the
encapsulator inputs.

\item[CH] Code hoisting (CH), lifts invariant computations out of 
{\tt loop} and {\tt seq} encapsulators:

\begin{description}
\item[{\tt \bf seq}] Non-constant (ie having at most one input), pure functional
instructions connected to the {\tt seq} inputs and their successors are hoisted
out of the encapsulator ``through their inputs.''

\item[{\tt \bf loop}] Loop expressions are reassociated and hoisted from both
the predicate and body:

\begin{enumerate}

\item Find loop invariant expressions (called loop ``constants'' in the code),
pure instructions (and their successors) connected
to ``constant inputs'' or literal values.

\item Find loop variant expressions, instructions that have any input from the loop
variable inputs or any non-functional instruction.

\item Chains of n associative instructions with the same opcode 
are re-associated to form a tree of log(n) depth with invariant and
variant inputs partitioning the leaves from left to right.

\item Hoist loop invariant expressions outside the encapsulator.
\end{enumerate}

\end{description}
\end{description}


\paragraph{Strategy:} CSE and CH occurs bottom-up:
\begin{enumerate}
\item Recursively CSE-CH all the encapsulators (hoisting out invariants, which must be simple and functional).
\item CSE all the simple, functional instructions in the basic block.
\item Combine equivalent inputs for all encapsulating instructions in the block.
\end{enumerate}

\paragraph{Author:} Ian Lance Taylor, May '87


\paragraph{Caveats:} 
\begin{enumerate}
\item Application is assumed to always be side-effecting.
\item Encapsulators are assumed to always be side-effecting.  
\item Reassociation is a general notion that should be applied everywhere, not just in
loops. 
\item Invariants aren't hoisted out of {\tt if} encapsulators.
\end{enumerate}

There should be a general abstraction to make lifting instructions out
or pushing them into an encapsulator easy.

\subsection{Loop Analysis}
% \paragraph{Exsym Properties:}

% \paragraph{Graph Properties:}

\paragraph{Instruction Slots:}
\begin{inden}
\item \bfidentype{loop-parameters}{(\btype{keyword} \ctype{init-source} \ctype{upper-source} \ctype{step-source})} 
Identifies the type of loop and sources for its bounds (see below).
\end{inden}

\paragraph{Module:}
\begin{verbatim}
(defcompiler-module loop-analysis id-compiler
  (:input program-graph code-block)
  (:output program-graph code-block)
  (:function la-dataflow-graph))
\end{verbatim}

\paragraph{Description:} For every loop instruction, {\tt Loop-analysis}
examines the predicate and body to determine if the loop is equivalent
to a simple {\tt for} construct.  If so, the module builds a piece of
graph which computes the number of iterations and wires it into the loop as
a new loop constant. Also, set up the loop-parameter slot to hold the sources
for the loop's initial value, upper-limit and increment.

\paragraph{Strategy:} Proceed top-down, analyzing loop instructions.

\subsection{Loop Unfolding and Unrolling}

% \paragraph{Exsym Properties:}

% \paragraph{Graph Properties:}

% \paragraph{Instruction Properties:}

\paragraph{Instruction Slots:}
\begin{inden}
\item \bfidentype{peel-count}{integer} - number of times to peel loop
\item \bfidentype{unfold-count}{integer} - number of times to unfold loop
\item \bfidentype{sequential-loop-p}{boolean} - set true if loop is sequentialized
\end{inden}

\paragraph{Module:}
\begin{verbatim}
(defcompiler-module unroll-loops id-compiler
  (:input program-graph code-block)
  (:output program-graph code-block)
  (:function ul-dataflow-graph))
\end{verbatim}

\paragraph{Description:}
Performs loop unfolding and unrolling. An unrolled loop executes k
copies of the loop's body (ie k copies of the program graph
corresponding to the loop's body wired in series) before entering the
loop itself. Inother words, it unroll's k iterations from the start of the loop.
Loop unfolding executes k copies of the loop's body for every
iteration of the loop.  Of course, care must be taken that termination
during an unfolded or unrolled body exits the loop correctly
(which is accomplished by analyzing the loop's behavior or by inserting checks
of the loop's predicate around every body).

\paragraph{Strategy:}
Proceed bottom up, replacing loop instructions with their unrolled or
unfolded equivalents when the unroll-count or unfold-count is non-nil.
{\tt While}loops use the most general unfolding strategy, nesting
additional conditionals around every new body graph. {\tt For} loops are
compiled without this additional overhead by changing the loop's
predicate and adding a series of (k-1) nested conditionals.

\paragraph{Author:} Jamey Hicks, September 1989

\paragraph{Caveats:} 
The terms unpeeling and unrolling are used interchangeably.


\subsection{Circulate Structures}

\paragraph{Instruction Properties:} 
side-effecting-p, 
create-like-p,
k-allocator,
k-deallocator

\paragraph{Module:}
\begin{verbatim}
(defcompiler-module circulate-structures id-compiler
  (:input program-graph code-block)
  (:output program-graph code-block)
  (:options circulate-structures)
  (:function circ-code-block))
\end{verbatim}

\paragraph{Description:} 
Attempts to find structures that are allocated and deallocated within a
given loop body. If a structure with these properties exists, its
allocation and deallocation code is lifted out of the loop. [A k-bounded
loop will have k copies of the structure allocated before starting?]

\paragraph{Strategy:} Circulate structures proceeds bottom-up through the graph
hoisting allocation and deallocation code out of loop encapsulators at each
level on the way up.

\paragraph{Author:} Jamey Hicks

%\paragraph{Caveats:}
% This code needs to commented by its author. Exactly what it does and how is
% very difficult to figure out.

\subsection{Algebraic Identities (misnamed partial-evaluation)}

% \paragraph{Exsym Properties:}

% \paragraph{Graph Properties:}

% \paragraph{Instruction Properties:}

% \paragraph{Instruction Slots:}

\paragraph{Module:}
\begin{verbatim}
(defcompiler-module partial-evaluation id-compiler
  (:input program-graph code-block)
  (:output program-graph code-block)
  \#+DEBUG (:before-function program initialize-partial-evaluation)
  (:function pe-dataflow-graph)
  \#+DEBUG (:after-function program print-partial-evaluation-statistics)
  (:options partial-evaluation))
\end{verbatim}

\paragraph{Description:} The algebraic identities module defines a set of
rewriting rules for program graph fragments. A program graph fragment is some
subgraph of the program graph all of whose instructions can be reached from a single
instruction. A pattern is a parenthesized expression that can match a graph fragment:

\begin{inden}
\item \dscat{pattern}{(\scat{opcode} \set{\scat{input}* \vbar \scat{every-input}} \scat{output}* [\scat{triggers}] )}
\item \dscat{simple-pattern}{\bscat{variable} \vbar \bscat{constant} \vbar \scat{pattern}}
\item \dscat{opcode} { \bscat{opcode} [\$parameter \scat{sexp}]}
\item \dscat{input}{{\tt :input} \scat{simple-pattern}}
\item \dscat{every-input}{(\$every \scat{sexp})}
\item \dscat{output}{\scat{simple-pattern}}
\item \dscat{triggers}{{\tt :triggered-by} \scat{pattern}*}
\end{inden}

\begin{inden}
\item For example,
\item {\tt (:intimes :input 1 :input x)}
represents an integer multiply instruction with two inputs.
\item {\tt (:make-functional-tuple (\$every :component i) (:tuple-fetch \$parameter i :tuple x))}
represents a tuple creating instruction connected to a tuple fetch instruction.
\end{inden}

The module compiles a set of rewrite rules which describe how to rewrite existing patterns
into new patterns. Sets of rewrite rules are defined by the {\tt defevaluator} macro:

\lispdoc defevaluator name input-pattern output-pattern \repeat{constraint} [Macro]

\begin{inden}
\item \dscat{name}{\bscat{symbol}}
\item \dscat{input-pattern}{(\$or \scat{pattern}*) \vbar \scat{pattern}}
\item \dscat{output-pattern}{\scat{pattern}}
\item \dscat{constraint}{\scat{lisp form}}
\end{inden}

The module searches for instructions matching the applicable rewrite rules. If any instruction
matches against the input pattern of a {\tt defevaluator} then that graph fragment is replaced
by the output pattern if all the constraints evaluate to true.

For example, a {\tt defevaluator} for additive integer identity might look like:
\begin{verbatim}
(defevaluator plus-zero
  ($or (:intplus :input 0 :input x)
       (:intplus :input x :input 0))
   x)
\end{verbatim}
Notice that repeated variable names refer to the same instruction in the scope of
one {\tt defevaluator}. Currently, there are {\tt defevaluator}s to do:

\begin{enumerate}
\item Algebraic simplification for integers and floats:
\begin{inden}
\item $x + 0 = 0 + x \rightarrow x$ 
\item $x * 0 = 0 * x \rightarrow 0$ 
\item $x * 1 = 1 * x \rightarrow x$
\end{inden}

\item Reduction in strength for exponentiation
\begin{inden}
\item $x ^ 2 \rightarrow x * x$
\item $x ^ 3 \rightarrow x * x * x$
\end{inden}

\item Algebraic simplification for booleans:
\begin{inden}
\item $x \andl x \rightarrow x$
\item $\truel \andl x = x \andl \truel \rightarrow x$
\item $\falsel \andl x = x \andl \falsel \rightarrow \falsel$
\item $x \orl x \rightarrow x$
\item $\truel \orl x = x \orl \truel \rightarrow \truel$
\end{inden}

\item Fetch elimination for functional data-structures

\item Removal of gates controlled by constants

\item Swapping of {\tt form-address} with {\tt set-ip} instructions

\begin{inden}
\item {\tt (:set-ip :input (:form-addr :input x :input offset) :input ip)} $\rightarrow$
\item {\tt (:form-addr :input (:set-ip :input x :input ip) :input offset)}
\end{inden}

\item Composition of {\tt form-address} instructions

\begin{inden}
\item {\tt (:form-addr :input (:form-addr :input x :input offset1) :input offset2)} $\rightarrow$
\item {\tt (:form-addr :input x :input (:intplus :input offset1 :input offset2))}
\end{inden}
\end{enumerate}
	
\paragraph{Strategy:}
The algebraic identities module proceeds top down, trying first to rewrite graph fragments
in the current basic block, before proceeding to basic blocks within encapsulators.
New instructions created by the rewrite rules are added to the list of instructions to traverse
within the block.

\paragraph{Author:} Ken Traub

\paragraph{Caveats:} The module searches the rewriting rules in order of their definition.
This may not be the best strategy. Pathological rewrite rules might cause the compiler
to enter an infinite loop.


\subsection{Thunk Splitting}

\paragraph{Graph Properties:} Adds new code blocks to the current graph.

\paragraph{Module:}
\begin{verbatim}
(defcompiler-module thunk-splitting id-compiler
  (:input program-graph procedure)
  (:output program-graph procedure)
  (:function ts-proc))
\end{verbatim}

\paragraph{Description:}
Delay encapsulators take arguments to a delayed expression and an address
to store the result of the expression when evaluated.  Thunk-splitting
implements the delay abstraction by removing delay encapsulators and
replacing them with lower level instructions.  In detail, thunk-splitting
implements the following: it encapsulates the delayed expression in a
defthunk encapsulator and places it in its own code-block with the name
``~i-THUNK-~.'' It replaces the delay encapsulator with a pair of
make-thunk/store-thunk instructions which take the arguments to the delayed
expression, the address to store the delayed value in (when it's lazily
computed) and the name of the thunk'd expressions code-block.

\paragraph{Strategy:} 
Proceed bottom-up, transforming delay encapsulators into
make-thunk/store-thunk pairs and add one defthunk code-block, for the
delayed expression, to the current set of code-blocks.

\paragraph{Author:} Jamey Hicks and ?

\paragraph{Caveats:}
Thunk splitting is very implementation dependent and should be 
considered part of the back end.

\subsection{Synchronize Release}

%\paragraph{Exsym Properties:}

%\paragraph{Graph Properties:}

\paragraph{Instruction Properties:} encapsulator-propagation-alist
\begin{inden}
\item \bfidentype{sr-before-function}{?} Only defined for loop instructions. Function that
given a loop instruction, seems to peel it once if it contains a
loop-release and hasn't been unrolled already. Jamey
says that this has something to do with releasing nextified variables that
are garbage after at least one iteration.
\end{inden}

\paragraph{Instruction Slots:}
\begin{inden}
\item \bfidentype{instruction-unrolled-p}{\btype{boolean}} Set for an unrolled loop instruction by sr-before-function
\end{inden}

\paragraph{Module:}
\begin{verbatim}
(defcompiler-module synchronize-release id-compiler
  (:input program-graph code-block)
  (:output program-graph code-block)
  (:function sr-dataflow-graph))
\end{verbatim}

\paragraph{Description:} Synchronize-release implements the {\tt synch} 
instruction in terms of the {\tt seq} encapsulator and other simple
instructions. Basic blocks containing {\tt synch}s are wrapped in {\tt seq}
encapsulators.  Conceptually, {\tt synch} instructions and the instructions
that depend on their outputs are moved outside the seq and {\tt synchs} are
turned into gates controlled by the {\tt seq}'s completion signal.  
% I'm not sure if this violates the encapsulator boundary or not....

\paragraph{Strategy:} Synchronize-release proceeds bottom-up, (partially) 
wrapping every basic block containing a {\tt synch} instruction with a {\tt
seq} encapsulator.  It finds all the outputs of the block that don't depend
on synch instructions and wires them as the body outputs of the {\tt seq}.
All {\tt synch} instructions and their successors are moved outside the
encapsulator and replaced by gates controlled by the {\tt seq}'s
termination signal.

\paragraph{Author:} Jamey Hicks

% \paragraph{Caveats:} 
%Needs many more comments...

\subsection{Manager Synchronization}

%\paragraph{Exsym Properties:}

%\paragraph{Graph Properties:}

%\paragraph{Instruction Properties:}

%\paragraph{Instruction Slots:}

\paragraph{Description:}
{\tt Manager-synchronization} implements finer grain control over
mutable structures than is possible using only block signals. Using Id's
{\it enter} construct, mutable data-structures can be atomically read
and modified using a locking mechanism. {\tt Manager-synchronization}
makes the ``unlocking'' of the structure occur after all its uses within
the {\it enter} block, but before the block itself terminates.

\paragraph{Strategy:}
Generate-program-graph creates {\tt enter} and {\tt release} instructions that delimit
the scope of Id's {\it enter} construct. The arc corrsponding to the
imperative data-structure named in the {\it enter} statement is wired
to the input of the {\tt enter} instruction by {\tt
generate-program-graph}. Also, {\tt enter} instruction's outputs are
wired to every use of the data-structure. In {\tt
manager-synchronization}, the {\tt release} instruction (wired to the
block's signal by gpg), receives a signal tree taking its
inputs from all the uses of the data-structure.

\paragraph{Author:} Paul Barth

\paragraph{Caveats:} This could (and probably should) be done by desugaring.

\subsection{Signals and Triggers}

\paragraph{Module:}
\begin{verbatim}
(defcompiler-module signals-and-triggers id-compiler
  (:input program-graph code-block)
  (:output program-graph code-block)
  (:function st-dataflow-graph))
\end{verbatim}

%\paragraph{Exsym Properties:}

%\paragraph{Graph Properties:}

\paragraph{Instruction Properties:}strict-p,legal-unconnected-inputs,legal-unconnected-outputs
%\paragraph{Instruction Slots:}

\paragraph{Description:} Adds signals and triggers to the program graph, as described in the
previous chapter.

\paragraph{Strategy:} {\tt Signals-and-triggers} proceeds top-down, adding block signals and
triggers to every block in every encapsulator, then wiring them to the
appropriate instruction signals and triggers.

\paragraph{Author:} Ken Traub

\paragraph{Caveats:} I'm not sure how much optimization goes on here, but there should be
ample opportunities.










