
\chapter{Middle End Data-Structures and Tools}

\section{Introduction}

This chapter and the following chapter discuss the middle end of the
Id compiler.  In theory, the middle end of the compiler encompasses a
machine independent data structure for representing Id programs and a
set of modules that transform one instance of the data structure into
another semantically equivalent (but hopefully more efficient)
instance.  However, one should always be wary of sweeping claims. As in
most optimizing compilers, our current implementations of semantics
preserving optimizations have not always been rigorously checked (not
of course, due to lack of desire, but these problems are still open
areas of research).  Making claims that certain machine independent
code transformations result in more efficient execution (in time or
space) on a particular machine is even harder to decide. Therefore, the
reader is encouraged to adopt a critical attitude for the next two
chapters and towards machine independent compiler optimizations in
general until the field reaches firmer ground.

Disclaimers aside, the overall philosphy of machine independent
optimizations seems appropriate. There are many well known program
transformations that work best when applied before the details of
specific machine implementations obscure the landscape of a program.
For the Id compiler these include: optimizing accesses to statically
known data (either through constant folding and propagation or fetch
elimination from static structures), simplifying algebraic
expressions, unrolling procedure calls and loops, and hoisting code
out of loops among others.

Also, over time, features that have more to do with specific machine
models than machine independent optimizations have crept into middle
end modules. Hence the middle end is an amalgam of modules that
perform general optimizations as well as add features that make 
programs easier to implement in the dataflow model or on a specific
machine.

Current wisdom dictates that graphs are the most appropriate data
structure for middle end transformations. The Id compiler has the
fortune to use very similar graph structures for both the middle {\it
and} the ETS back end (described in \cite{Hicks90}),
both program graphs (in the middle end) and ets machine graphs (in the
back end) are implemented on top of the same low level structure
provided by DFCS. Unfortunately, sometimes the underlying details of
the low-level data structure obscure the higher level abstraction used
by the middle end (largely for reasons of efficiency). In particular, it's
worthwhile to pay extra attention to the details of {\it surfaces } which
can confuse the novice.

\section{Program Graphs}

The Id compiler's middle end modules manipulate program graphs, a
graph data structure for representing Id programs. Program graphs are
a generalization of the dataflow graph data structure provided by
DFCS. Conceptually, progam graphs consist of instructions wired
together into a graph:

\begin{defn} A {\bf Program graph} contains
\begin{enumerate}
\item A set of {\bf instructions}, each with the following components:
\begin{enumerate}
\item An {\bf opcode}, represented by a keyword symbol.
\item An {\bf external surface} with a set of {\bf input and output ports}.
The name of the external surface is the keyword symbol {\tt :exterior}.
\item Zero or more {\bf internal surfaces}, each with their own
sets of input and output ports. The name of each internal surface is
represented by a keyword symbol.
\item Various other fields for characterizing an instruction's properties
and keeping bookkeeping information.
\end{enumerate}
\item A set of {\bf directed arcs} connecting instruction output ports
to instruction input ports:
\begin{itemize}
\item No input ports may have more than one incoming arc.
\item Output ports have no limitation on the number of outgoing arcs.
\end{itemize}
\item An (implicit) notion of the {\bf graph's inputs and outputs}:
\begin{itemize}
\item A graph's inputs are the set of its unconnected instruction inputs.
\item A graph's outputs are the set of its unconnected instruction outputs.
\end{itemize}
\end{enumerate}
\end{defn}

In the dataflow model, where arcs carry tokens from outputs to inputs, 
every dataflow instruction produces a complete set of output tokens when
presented with a complete set of input tokens. Program graph instructions
have dataflow instruction behavior. Dataflow behavior can be generalized
to graphs of instructions as well. 

\begin{defn} A {\bf Basic Block} (or just a block) is a program graph where if
a token arrives at every input:
\begin{enumerate}
\item Every output emits a token.
\item Every instruction in the graph executes exactly once.
\end{enumerate}
\end{defn}

Its useful to classify program graph instructions based on the number of internal
surfaces they have:

\begin{defn} 
{\bf Simple instructions} have no internal surfaces.
\end{defn}

Simple instructions represent primitive Id operators (like {\tt +} or {\tt i-store}).
A simple instruction's input ports represent arguments to the operator and its 
outputs represent the results returned by the operator. Some simple instructions can
be classified by their use of input and output ports:
\begin{itemize}
\item {\bf Purely functional instructions} (like {\tt +}) depend only on their inputs and have
no observable effects outside the results they return.
\item {\bf Purely side-effecting instructions} (like {\tt i-store}) have no outputs.
\item {\bf Constant instructions} have no inputs.
\end{itemize}

\begin{defn}
{\bf Encapsulating instructions} (called encapsulators) have at least one internal surface.
\end{defn}

Each internal surface of an encapsulator connects to different,
disjoint basic blocks.  Encapsulators are used to represent Id
operators with complex translations from parse trees to blocks of
machine graph instructions (called translation schemas). The opcode of
the encapsulating instruction represents the invariant part of the
schema and the blocks connected to each internal surface of the
instruction correspond to the variant subgraphs of the schema.

Alternatively, encapsulators can be thought of as simple instructions
whose semantics are completely determined by their opcode and internal
blocks. They represent black boxes, hiding internal surfaces from the
outside. Like simple instructions, they produce a full set of output
tokens on their external outputs when presented with a full set of
tokens on their external inputs.

For example, the Id {\tt if} expression is represented by an {\tt if} encapsulator with the
following components:
\begin{enumerate}
\item An external input taking the output of the predicate expression.
\item n external inputs for the arguments (free variables) of the {\tt then} and
{\tt else} expressions.
\item m external outputs.
\item Two internal surfaces named {\tt :then} and {\tt :else} which connect to
blocks of n inputs and m outputs.
\end{enumerate}

Note, after being presented with a full set of input tokens, the {\tt if} encapsulator
produces a full set of output tokens, though only one of its internal blocks executes.


\section{Port Names}

The input and output ports on each surface of an instruction can be
referred to either by number or symbolic name. If a surface has n
input ports then each input port can be referred to as a number in the range
$\{0,\dots,n-1\}$ (similarly for output ports). Alternatively, ports can
be referred to by symbolic names (which map onto port numbers)
using the following conventions:

\begin{itemize}
\item A {\bf Symbolic Name} is either
\begin{enumerate}
\item A keyword symbol (a simple name).
\item {\tt (keyword . i)} (a subscripted name), where $i$ is a non-negative integer.
\end{enumerate}
\item An input or output port may have at most one symbolic name.
\item No two input ports or output ports of the same instruction may have the
same symbolic name although an input port and an output port may have the same name.
\item If {\tt (keyword . n)} is a port name then so is {\tt (keyword . i)} for all i
from zero through n.
\item Subscripted names with consecutive subscripts always map to
consecutive port numbers.
\end{itemize}

The following functions translate between port names and numbers:
\begin{lispdocs}
\lispdoc instruction-input-name-to-number instruction input-name [Function]
\lispdoc instruction-output-name-to-number instruction output-name [Function]
\lispdoc instruction-input-number-to-name instruction input-number [Function]
\lispdoc instruction-output-number-to-name instruction output-number [Function]
\end{lispdocs}
These functions return nil if the name or number is ill-defined for the given
{\it instruction}. The names returned are always subscripted. 


\section{Arcs, Sources and Sinks}

\begin{defn} {\bf Sources} and {\bf sinks} allow the programmer to specify a specific output or input
port of an instruction:
\begin{itemize}
\item A {\bf source} points to an instruction's output port.
\item A {\bf sink} points to an instruction's input port.
\end{itemize}
\end{defn}


\begin{defn}
An {\bf Arc} is a source-sink pair.
\end{defn}

Arcs are implemented as pairs of sources and sinks. The source of the pair 
points to the output port attached to the arc's tail. The sink of the
pair points to the input port attached to the arc's head.

Notice that instructions never point directly to other instructions.
Instead, sources and sinks provide a doubly linked list corresponding
to arcs.  For example, if instruction A points to instruction B then A
points to a sink pointing to an input of B and B points to a source
pointing to an output of A.

Sources, sinks and arcs can also carry {\bf annotations} which are either
nil or a pointer to some data-structure.


\subsubsection{Constructors}

\begin{lispdocs}
\lispdoc make-instruction-sink instruction port \optional annotation [Function]
\lispdoc make-instruction-source instruction port \optional annotation [Function]
\end{lispdocs}
Creates and returns an instruction source or sink referring to an
input or output {\it port\/} of {\it instruction}.
{\it Port\/} may be either a symbolic name or a port number.

\subsubsection{Selectors} 

\begin{lispdocs}
\lispdoc instruction-sink-instruction instruction-sink [Function]
\lispdoc instruction-source-instruction instruction-source [Function]
\end{lispdocs}
Returns the instruction referred to by {\it instruction-sink} or {\it
instruction-source}.  May {\it not\/} be used with {\tt setf}.

\begin{lispdocs}
\lispdoc instruction-sink-input instruction-sink [Function]
\lispdoc instruction-source-output instruction-source [Function]
\end{lispdocs}
Returns the port number referred to by {\it instruction-sink} or {\it
instruction-source}.  Note that the value returned is always a number.
These functions are discussed further in section~\ref{sec-use-pginst}.
May {\it not\/} be used with {\tt setf}.

\begin{lispdocs}
\lispdoc instruction-sink-annotation instruction-sink [Function]
\lispdoc instruction-source-annotation instruction-source [Function]
\end{lispdocs}
Returns the {\tt annotation} slot of {\it instruction-sink} or {\it
instruction-source}.  May {\it not\/} be used with {\tt setf}.

\section{Parameters, Slots and Properties}

\subsubsection{Instruction Parameters}
Instruction  parameters are used when one opcode stands for a
family of instructions.  For example, there might be an instruction
with opcode {\tt :constant} which emits a certain value upon the
receipt of any input. The {\tt :constant} instruction's parameter
determines what constant it emits.

\subsubsection{Instruction Slots}
It's possible to define extra slots for program graph instructions.
These extra slots can store additional information about a given
instruction. Also, slots can be added and removed without the
entire compiler being recompiled.  Section~\ref{sec-instruction-slots}
describes slots used in the compiler's current implementation.

\subsubsection{Instruction Properties}
Read-only slots called {\tt properties} can be set up
that store information for all instructions with a particular
opcode. See section~\ref{sec-define-pg-inst} and the explanation
of the {\tt define-program-graph-instruction} macro for the details
of defining instruction properties. Section~\ref{sec-instruction-properties}
describes properties used in the compiler's current implementation.

\section{Using Program Graph Instructions} \label{sec-use-pg-inst}

Now that the basic components of program graph instructions have been defined,
we can describe the Lisp functions operate on instructions.

\subsubsection{Selectors} 
\lispdoc instruction-opcode instruction [Function]
Returns the contents of the {\tt opcode} slot of {\it instruction}. 

\lispdoc instruction-parameter instruction [Function]
Returns the {\tt parameter} value of {\it instruction}.  May be used
with {\tt setf}.

\lispdoc instruction-encapsulator-p instruction [Function]
Returns true if the instruction contains internal surfaces.

\lispdoc instruction-block-names instruction [Function]
Returns a list of the names of {\it instruction}'s surfaces.

\lispdoc instruction-\angleb{{\it property-name}} instruction [Function]
Returns the value of the property for {\it instruction}. May not
be used with {\tt setf}.

\lispdoc define-program-graph-instruction-slot selector-name \key{copyable-p} [Macro]
Sets up a new instruction slot with name {\it selector-name}.

\lispdoc instruction-\angleb{{\it slot-name}} instruction [Function]
Returns the value of the slot for {\it instruction}. May be used
with {\tt setf}.

\begin{lispdocs}
\lispdoc instruction-n-exterior-inputs instruction [Function]
\lispdoc instruction-n-exterior-outputs instruction [Function]
\end{lispdocs}
Returns the number of exterior inputs or outputs for {\it instruction}.

\subsection{Surface Related Functions}

For historical and efficiency reasons, an encapsulator's internal
surfaces are manipulated with the same functions used for manipulating
a simple instruction's external surface. In actuality, input and
output ports are assigned to different surfaces only by convention.
For simple instructions, an instruction's input and output ports are
the same as the ports for its exterior surface.  For encapsulators,
functions are provided to map between the absolute ports of the
instruction (considering all ports to be on the {\tt :exterior}
surface) and the ports for each surface.

\begin{fact} 
A {\bf simple instructions} input and output ports 
are the same as the ports on its exterior surface.
\end{fact} 
\lispdoc instruction-inputs instruction [Function]
Returns an array containing the inputs of {\it instruction}.
Each element of the array is an instruction source and each element's index
is its port number.
May {\it not\/} be used with {\tt setf}.

\lispdoc instruction-outputs instruction [Function]
Returns an array containing the outputs of {\it instruction}.
Each element of the array is a {\it list} of instruction sinks and
each elements index is its port number.
May {\it not\/} be used with {\tt setf}.

\begin{fact}
An {\bf encapsulating instruction} has an indirect mapping between
the ports of its surfaces and its absolute ports referenced by {\tt
instruction-inputs} and {\tt instruction-outputs}.

There is an indirect mapping between: (\angleb{surface-name}, \angleb{surface-port-num}) and \angleb{absolute-port-num}
\end{fact}

\subsubsection{Mapping from Surface to Absolute Ports} 

The following functions implement the mapping from 
(\angleb{surface-name}, \angleb{surface-port-num}) to \angleb{absolute-port-num}.

\begin{lispdocs}
\lispdoc instruction-surface-lowest-input instruction surface [Function]
\lispdoc instruction-surface-lowest-output instruction surface [Function]
\lispdoc instruction-surface-highest-input instruction surface [Function]
\lispdoc instruction-surface-highest-output instruction surface [Function]
\end{lispdocs}

These functions return the number of the lowest (or highest) numbered port belonging to a given
surface, or {\tt nil} if there is no such surface.  Note that a number is
returned in the case where a surface exists but has no ports.

Note: \angleb{absolute-port-num} = \angleb{lowest-surface-absolute-port-num} + \angleb{surface-port-num}.

\subsubsection{Mapping from Absolute to Surface Ports} 

The following functions implement the mapping from 
\angleb{absolute-port-num} to (\angleb{surface-name}, 
\angleb{surface-port-num}).

\begin{lispdocs}
\lispdoc  instruction-input-surface instruction port [Function]
\lispdoc  instruction-output-surface instruction port [Function]
\end{lispdocs}

These return the surface on which a given port of {\it instruction} lies,
or {\tt nil} if the instruction has no such port.

\subsection{Using Internal Surfaces}
The definition of interior surfaces, as implemented above, usually
confuses novice users. Though program graph instructions make no distinction
between internal and external ports, a user's mental picture of an instruction
does! In the diagrams we draw to represent an encapsulating instruction (see figure~\ref{fig-encaps-inst}),
external inputs connect to the ``top'' of the instruction and outputs extend
from its ``bottom.'' However, for internal blocks, outputs hang off the ``top''
of the internal block and inputs enter from the ``bottom'' of the internal block.
It's vital to keep in mind that the {\it outputs} from an interior surface feed
the inputs of an internal block (and vice versa for the {\it inputs} of an interior surface).

\subsubsection{An Example}

Here are some Lisp functions using instruction surfaces:

\begin{verbatim}
;;;-------------------------------------------------------------------------
;;; multiple value giving number of lowest & highest port for given surface

(defun instruction-surface-input-numbers (instruction surface)
  (values (instruction-surface-lowest-input instruction surface)
	  (instruction-surface-highest-input instruction surface)))

(defun instruction-surface-output-numbers (instruction surface)
  (values (instruction-surface-lowest-output instruction surface)
	  (instruction-surface-highest-output instruction surface)))
	 
;;;-------------------------------------------------------------------------
;;; Return sequence that corresponds to the subsequence of the port array
;;; for a given surface

(defun instruction-surface-inputs (instruction surface)
  (multiple-value-bind (l h)
      (instruction-surface-input-numbers instruction surface)
    (and l h (coerce (safe-subseq (instruction-inputs instruction) l h) 'list))))

(defun instruction-surface-outputs (instruction surface)
  (multiple-value-bind (l h)
      (instruction-surface-output-numbers instruction surface)
    (and l h (coerce (safe-subseq (instruction-outputs instruction) l h) 'list))))
\end{verbatim}

\section{Defining Program Graph Instructions} \label{sec-define-pg-inst}

 The {\tt define-program-graph-instruction} macro provides a
convenient way of declaring program graph instructions.  It sets up a
blueprint that defines all instructions of a given opcode.  It
declares a parameterized constructor function to create instances of
the instruction having the specified opcode. It defines the symbolic
names of input and output ports, interior surface names,
and what ports are associated with what surfaces. It also defines
properties associated with any instructions created by the constructor.

The syntax is as follows:
\lispdoc define-program-graph-instruction opcode \list{arg1 arg2 \dots} \clauses
    \group{\list{{\tt :inputs} \repeat{input-name input-expr}}}
   \group{\list{{\tt :outputs} \repeat{output-name output-expr}}}
   \optgroup{\list{{\tt :constructor-name} constructor-name}}
   \optgroup{\list{{\tt :blocks} 
		     \repeat{block-name input-names output-names}}}
   \optgroup{\list{{\tt :properties} \repeat{indicator value}}}
   [Macro]

\begin{inden}
\item \identype{input-expr}{integer}
\item \identype{output-expr}{integer}
\item \dscat{input-names}{(\bscat{keyword}*)}
\item \dscat{output-names}{(\bscat{keyword}*)}
\end{inden}


\begin{itemize}
\item  The {\tt :inputs} and {\tt :outputs} clauses are required; all others are
optional.  

\item The numbers of inputs and outputs are determined by evaluating 
the expression for each port name, where these expressions may refer
to the arguments.

\item The {\tt :blocks} clause may be used to declare that certain inputs and outputs 
belong to interior subgraphs; there is always a surface named {\tt :exterior} to which all ports not
mentioned in the {\tt :blocks} clause belong.  If the {\tt :blocks} clause is
omitted entirely, then the only surface is the {\tt :exterior}.  

\item Ports within a surface are always assigned consecutive numbers.  The lowest
numbers are assigned to the {\tt :exterior} surface, and the remaining
numbers are assigned to surfaces in the order in which they appear in
the {\tt :blocks} clause.  Within each surface, the ports are ordered as
they appear in the {\tt :inputs} or {\tt :outputs} clause.  

\item The {\tt :properties} clause can be used to associate properties to
all instructions of a given opcode; Note that the properties are really
assigned to opcodes, rather than individual instructions.
\end{itemize}

Evaluating the macro defines the lisp constructor:

\lispdoc make-\angleb{opcode}-instruction \repeat{arg} [Function]
The constructor function for the instruction. The name may be overridden by the
{\tt constructor-name} clause. The argument values may be used to
parameterize the numbers of inputs and outputs.

\lispdoc \angleb{opcode}-instruction-arg\angleb{i} instruction [Function]
Returns the ith argument to the constructor creating the instruction

\subsubsection{Examples} 
Here's an example defining a simple instruction.

\begin{verbatim}
(define-program-graph-instruction make-tuple ()
  (:constructor-name make-make-tuple-instruction-internal)
  (:inputs :trigger 1 :anchor 1)
  (:outputs :output 1 :signal (if *resource-manager-signal-p* 1 0))
  (:properties :generate-ets-function 'g-ets-make-functional-tuple-instruction
	       :side-effecting-p t
	       :create-like-p t
	       :k-allocator :make_k_tuples
	       :k-deallocator :free_k_tuples))

;;;
;;; Constructor for make-tuple instruction. Notice make-...-internal is used
;;; to construct a tuple instruction with no parameter. The parameter of
;;; resulting instruction is set to be size. Parameters should be definable
;;; with define-program-graph-instruction, but apparently they must be
;;; set by hand!
;;;
(defun make-make-tuple-instruction (size)
  (let ((make-tuple-instruction (make-make-tuple-instruction-internal)))
    (setf (instruction-parameter make-tuple-instruction) size)
    make-tuple-instruction))

;;;
;;; Selector for the size of the tuple the instruction creates
;;;
(defun make-tuple-instruction-size (make-tuple-instruction)
  (instruction-parameter make-tuple-instruction))

\end{verbatim}

Here's an example defining an encapsulating instruction:

\begin{verbatim}
 (define-program-graph-instruction loop (n-variables n-constants)
   (:inputs :predicate 1
            :loop-constant n-constants
            :predicate-output n-variables
            :loop-input n-variables
            :body-output n-variables)
   (:outputs :predicate-input n-variables
             :body-input n-variables
             :loop-output n-variables)
   (:blocks :predicate (:predicate-output :predicate) (:predicate-input)
            :body (:body-output) (:body-input))
   (:properties :iterator-p t))
\end{verbatim}

The example above defines the following functions:

\begin{verbatim}
      (make-loop-instruction n-variables n-constants)
      (loop-instruction-n-variables loop-instruction)
      (loop-instruction-n-constants loop-instruction)
      (instruction-iterator-p instruction)
\end{verbatim}

\section{ @!-opcode program graph instructions}

To be filled in.

%% [Motivation]
%% 
%% Instructions available through the @!opcode pragma.  These
%% instructions may have zero, one, or two inputs named :INPUT, and zero
%% or one outputs named :OUTPUT.  In addition, they may have a :TRIGGER
%%input and a :SIGNAL output.  They may not be parameterized.  To
%% facilitate this abstraction, the DEFINE-@!OPCODE-INSTRUCTION macro is
%% provided, having the following form:
%% 
%% GET LISPDOC TO WORK HERE
%% %%%\lispdoc DEFINE-\@\!OPCODE-INSTRUCTION name \list{ n-inputs n-outputs \:TRIGGER-P bool \:SIGNAL-P bool} properties-clause [Macro]
%% 
%% The TRIGGER-P and SIGNAL-P keyword args may be omitted; their default
%% is NIL.  This is extended to any program graph instruction that has a
%% constant number of inputs and outputs, no matter what name the inputs
%% and outputs have.
%% 
%% Here's an example:
%% 
%% [example]


\section{Wiring Instructions Together}

For now see the DFCS manual for a description of how to wire
together dataflow graphs.

%% \subsection{Wiring together Program Graphs}
%% [To be added]
%% \subsection{Frames}
%% [To be added]

\section{Traversing Program Graphs}

\subsubsection{Instruction Marks and Numbers} 

When traversing program graphs it's often useful to mark instructions
as they are processed, to avoid following loops in the graph. Instructions may
also be numbered with non-negative integers. Algorithms which traverse
program graphs cannot mark some instructions and number others since
marks and numbers are stored in the same location within an instruction structure.

The functions below control marking a program graph:

\begin{lispdocs}
\lispdoc reset-all-instruction-marks [Function]
\lispdoc mark-instruction instruction [Function]
\lispdoc instruction-marked-p instruction [Function]
\lispdoc unmark-instruction instruction [Function]
\end{lispdocs}

The functions below control numbering a program graph:

\begin{lispdocs}
\lispdoc reset-all-instruction-numbers [Function]
\lispdoc number-instruction instruction number [Function]
\lispdoc instruction-number instruction [Function]
\lispdoc unnumber-instruction instruction [Function]
\end{lispdocs}


\subsubsection{Iterating Over Blocks} 

The {\tt with-basic-block-array} macro provides an efficient way to
point to every instruction in a basic block.  The macro stores the
simple and encapsulating instructions of a block in two arrays (in no
particular order). Iterating over the arrays provides access to every
instruction in the block.

\lispdoc with-basic-block-array \list{bb-array encaps-array encapsulator bb-name} body [Macro]

\begin{inden}
\item \dscat{bb-array}{\bscat{symbol}}
\item \dscat{encaps-array}{\bscat{symbol}}
\item \dscat{encapsulator}{\scat{lisp form evaluating to an encapsulator instruction}}
\item \dscat{bb-name}{\scat{keyword denoting a basic block in encapsulator}}
\end{inden}

\begin{itemize}
\item  {\it bb-array} is bound to an array whose
elements are the instructions comprising the block named {\it bb-name} in
the encapsulator. 
\item {\it encaps-array} is bound to an array containing all
instructions in {it bb-array} which are themselves encapsulators. 
\item The original encapsulator is not included in either array. 
\item Any values returned by the body are returned as the result of the entire macro.
\item {\tt with-basic-block-array} changes instruction marks.
\end{itemize}

{\tt With-basic-block-array} is a macro because it recycles the arrays
after executing the body.  Therefore, {\bf no pointers to the arrays must
exist when the body exits!}  If necessary, the body can make copies of
these arrays.

\subsubsection{An Example}
Here's a code fragment lifted from the {\tt circulate-structures}
module. {\tt Circ-basic-block} traverses a basic block within an
encapsulator from the bottom-up, applying {\tt circ-loop-instruction}
to every {\tt loop} encapsulator in the block.

\begin{verbatim}
(defun circ-basic-block (encapsulator surface)
  (with-basic-block-array (instruction-array encapsulator-array encapsulator surface)
    instruction-array
    (map nil #'circ-encapsulator encapsulator-array)))

(defun circ-encapsulator (encapsulator)
  (loop for block in (instruction-block-names encapsulator) do
	(circ-basic-block encapsulator block))
  (when (eq (instruction-opcode encapsulator) :loop)
    (circ-loop-instruction encapsulator)))
\end{verbatim}

\subsubsection{Iterating Without Blocks} 
The {\tt with-instruction-array} stores all instructions in a program
graph into an array, not separating encapsulators from simple
instructions and not heeding block boundaries.

\lispdoc with-instruction-array \list{instruction-array dfgraph} body [Macro]

\begin{inden}
\item \dscat{instruction-array}{\bscat{symbol}}
\item \dscat{dfgraph}{\scat{lisp form evaluating to a dataflow graph}}
\end{inden}

{\it Instruction-array} is bound to an array whose elements are all
the instructions in the {\it dfgraph}. {\it Instruction-array}
contains a pointer to every instruction in the graph, including those
hidden by encapsulators.  The restrictions for array reuse in {\tt
with-basic-block} apply to {\tt with-instruction-array}. Note, that
when dealing with program graphs, {\tt with-basic-block} is preferred.

\section{Anchors, Signals and Triggers}

Though program graph's are machine independent, they are also
the preferred site for adding some machine dependent features.
The fact that these transformations occur in the machine-independent
``middle-end'' is just a matter of semantics. In fact, it's
more correct to view the middle-end as a mixture of machine
independent optimizations and some machine dependent transformations.
I describe these concepts here because the modules that implement
them work on program graphs as defined above.

\subsection{Signals and Triggers}

The abstract model of dataflow graph execution, though useful for
reasoning about graph transformations, has flaws that make it hard to
realize directly in executable machine instructions. The requirement
that every instruction in a basic block execute exactly once, when all
inputs are presented, needs clarification. In a block, reachable
instructions with inputs fire after inputs are presented to the basic
block since tokens will travel to every reachable instruction.
However, constant instructions with no inputs, are not reachable from
the block's inputs and have no local method of determining when to
fire. Similarly, it's often necessary to know when every instruction
in a block has executed since the resources required by the graph's
execution can be deallocated.  But again, instructions with no outputs
don't contribute to the outputs of the block making a simplistic check
of the outputs insufficient. 

In order to solve the above problems and make dataflow graph
evaluation easier to implement, two new software abstractions are
added to our model of program graphs: signals and triggers. In
essence, adding signals and triggers to the program graph gives every
instruction at least one input and one output, making the question of
when an instruction fires simple to determine.  As a first
approximation, trigger inputs are added to instructions with no other
inputs and signal outputs are added to instructions with no other
outputs:

\begin{defn}
A {\bf Trigger} is an additional input to an instruction which must
receives a token whenever a set of inputs arrive (the trigger may
itself be the only input).
\end{defn}

\begin{defn}
A {\bf Signal} is an additional output of an instruction which emits a
token whenever the instruction fires and a set of outputs appear (the
signal may itself be the only output).
\end{defn}

With these definitions in hand, we can define triggers and signals
for basic blocks:

\begin{defn}
A {\bf Block Trigger} is an additional input to a basic block that receives a
``trigger token'' whenever inputs arrive at the block. One token
is received for every complete set of inputs that arrive.
\end{defn}

\begin{defn}
A {\bf Block Signal} is an additional output from a basic block that must
emit a ``signal token'' after every instruction with a signal output fires.
\end{defn}

Note, a block signal indicates only that instructions with signal outputs
have fired. {\bf All} instructions in a block have fired {\it only} after all outputs
from the block (including the block signal) emit tokens. 

\begin{defn}
A {\bf Signal Tree} is a graph of instructions with n-inputs and one output
that fires after receiving all it's inputs.
\end{defn}

A block signal is normally computed by connecting it to the output of a 
signal tree whose inputs are connected to all the signal outputs in the block.
Though the addition of signals and triggers is closely related to 
a particular machine implementation, it's easier to add them at the
program graph level 

\subsection{Anchors}

Signals and triggers make the semantics of basic blocks explicit by
providing paths from a block's inputs to all its instructions and from
all its instructions to its outputs. However, signals and triggers
also complicate the graph considerably and are usually added just
before leaving the middle end. Before their addition, blocks can
contain subgraphs with no paths to the block's inputs or outputs (for
example, constant instructions connected to purely side-effecting
instructions).  During optimizations it's easier to work with fully
connected graphs, so extra inputs are provided to ``anchor'' all
instructions with either no inputs or outputs.

\begin{defn}
An {\bf Anchor} is an additional input to an instruction with either no input's
or output's that serves to keep blocks connected.
\end{defn}

\begin{defn}
A {\bf Block Anchor} is an additional input to a basic block that
connects to every instruction in the block with no inputs or outputs
\end{defn}

Semantically, anchors are superfluous. They are merely a convenience
to the programmer, providing a simple way to keep blocks connected.

\section{Program Graph Properties} \label{sec-instruction-properties}

What follows is a list of some currently used program graph properties:
\begin{inden}

\item \bfidentype{constant-p}{boolean} True for constant instructions and loop constants.
\item propagatable-constant-p
\item \bfidentype{strict-p}{boolean} True for instructions which are strict in all their arguments.
\item \bfidentype{folding-function}{ $\ctype{value}^n$ $->$ $\ctype{value}^m$} Function which
``executes'' an instruction, taking n inputs and returning m outputs.
\item \bfidentype{side-effecting-p}{\btype{boolean}} True for instructions that are non-functional. Includes those that allocate
unfilled storage for aggregate structures as well as explicit store instructions.
\item \bfidentype{apply-like-p}{boolean} True for any instruction that matches the type signature of the
{\tt apply} instruction. {\bf Apply-like} instructions are used to
apply a function whose arity won't be satisfied by the given arguments.
\item encapsulator-propagation-alist 

\item \bfidentype{create-like-p}{\btype{boolean}} True for instructions that return a pointer to an aggregate structure that can be fetched 
from or stored into

\item \bfidentype{store-like-p}{(list \ctype{Input-port} \ctype{Output-port} \ctype{fe-Match-p})} 
Instructions that store into part of an aggregate data structure. All
store-like instructions are side-effecting.

\item \bfidentype{fetch-like-p}{(list \ctype{Input-port} \ctype{Output-port} \ctype{fe-Match-p} \ctype{sfe-Match})} 
Instructions that retrieve part of an aggregate DS created by a
create-like instruction.

Where: \\
\dtype{fe-Match-p}{(\ctype{store-inst} x \ctype{fetch-inst} $->$ \btype{boolean})} \\
is the type of a function which returns true if the fetch
instruction retrieves the same item put in by the store instruction
(ie storing and fetching on the same index).
\\
\dtype{sfe-Match}{(\ctype{make-inst} x \ctype{fetch-inst} $->$ \ctype{input-Port})} \\
is the type of a function which returns the \ctype{make-inst}'s 
input port name that corresponds to the object the fetch instruction is fetching.\\
For example, 
if (\identype{match}{\ctype{sfe-match}}),(\identype{cons}{\ctype{make-inst}}) and (\identype{head}{\ctype{fetch-inst}})
then {\tt (match cons head)} returns {\tt `(:input . 0)}.
%\item \bfidentype{legal-unconnected-inputs}{}
%\item \bfidentype{legal-unconnected-outputs}{}
\item \bfidentype{associative-p}{boolean} True for associative instructions.
%\item inhibit-constant-propagation
%\item \bfidentype{k-allocator}{}
%\item \bfidentype{k-deallocator}{}
%\item \bfidentype{opcode-machine-translation}{}
\item \bfidentype{generate-ets-function}{\ctype{pg-inst} $->$ \ctype{ets-machine-graph}} Generates an ets machine graph
for a given program graph instruction.
\item \bfidentype{sr-before-function}{}

\end{inden}

\section{Program Graph Slots}

What follows is a list of currently used program graph slots:

\begin{inden}
\item {\bf instruction-unfold-count} :copyable-p t
\item {\bf instruction-peel-count} :copyable-p t
\item {\bf instruction-loop-type} :copyable-p t
\end{inden}
