  % -*- Mode:TeX -*-

\section{Dataflow Graphs}
\label{dfg}

When all parse tree manipulations are complete, the parse tree is converted to
a dataflow graph\index{dataflow graph}.  Initially, the dataflow graph has a
level of detail comparable to that of the original source program; this graph
is called the program graph\index{program graph}.  At some point toward the end
of compilation, the program graph, which may have undergone various
transformations, is converted to a graph containing more detail and which is
more specific to the particular target dataflow architecture; this graph is
called the machine graph\index{machine graph}.  After possibly further
manipulations, this graph is assembled into object code for the target machine.

A single abstraction suffices to represent both program graphs and machine
graphs; the distinction is merely one of restrictions imposed by the various
compiler modules.  As these restrictions depend on the language being compiled
and the target architecture, they will not be discussed in this section.
Instead, the abstractions for manipulating dataflow graphs, be they program
graphs or machine graphs, are described here.

\begin{fig}{DataflowGraphFragmentFigure}{(a) A Dataflow Graph Fragment; (b)
Its Internal Representation}
\illustration{csg261-3}
\end{fig}

Figure \ref{DataflowGraphFragmentFigure} shows a fragment of a dataflow graph
and its internal representation within the compiler.  The components of this
figure are explained in the sections that follow.

\subsection{Instructions}

A dataflow graph is simply a collection of {\it instructions}\index{instruction},
which are connected together by {\it arcs}\index{arc}.  Each instruction contains
an {\it opcode}, which identifies what operation the instruction performs, a
certain number of {\it inputs}, and a certain number of {\it outputs}.  Although
the compiler substrate assigns no semantics to instructions in dataflow graphs,
instruction inputs should be thought of as receiving data from other
instructions, and instruction outputs should be thought of as sending data to
other instructions.  Collectively, the inputs and outputs of an instruction are
referred to as its {\it ports}.\index{port}

A dataflow graph is constructed by wiring the outputs of some instructions to
the inputs of other instructions; it is not possible to wire outputs to outputs
or inputs to inputs.  An additional restriction is that while outputs may have
any number of arcs leading away from them, each input may have only one arc
leading to it.  The implications of this restriction are discussed below.
While arcs are thought of as being unidirectional, leading from outputs to
inputs, they are actually implemented as bidirectional links for easy
traversing of graph structure.

An instruction actually has eight slots: {\tt opcode}, {\tt parameter}, {\tt inputs},
{\tt input-map}, {\tt outputs}, {\tt output-map}, {\tt mark}, and {\tt other-slots}.
{\tt opcode} is a keyword symbol identifying the instruction, as described above.
The {\tt parameter} slot is intended for use when one opcode stands for a whole
family of instructions.  For example, there might be an instruction with opcode
{\sc constant} which emits a certain value upon the receipt of any input; the
{\tt parameter} slot could be used to indicate which constant is to be emitted
for particular {\sc constant} instruction.  The slots {\tt inputs} and {\tt outputs}
contain arrays which hold the inputs and outputs of the instruction.  The sizes
of these arrays are fixed at the time the instruction is created, and their
exact contents is discussed below.  The slots {\tt input-map} and {\tt output-map}
each contain a data structure called a {\it port map}\index{port map}, which
allows the inputs and outputs of an instruction to be referred to by symbolic
names.  Certain graph manipulation algorithms require the ability to mark nodes
of the graph as they are encountered (so that each node is processed only once,
for instance), and so a {\tt mark} slot is provided for this purpose.  Finally,
{\tt other-slots} holds a property list for additional slots defined by compiler
modules, analogous to the {\tt other-slots} slot of ptnodes (see Section
\ref{ParseTreeNodeSubsection}).

An instruction's inputs and outputs are each numbered consecutively from zero,
and can be referred to by number.  Usually, however, it is more convenient to
refer to a port by a symbolic name that suggests its function.  A symbolic name
for a port may be a simple name (a keyword symbol), or it may be a subscripted
name consisting of a keyword symbol and a non-negative integer.  Subscripted
names are particularly useful for complicated instructions like {\sc if} and
{\sc loop} used for Id, whose ports can be logically grouped into sets of
varying size.  The {\sc if} instruction, for example, has three sets of outputs:
a set of outputs feeding the graph for the ``then'' side, a set of outputs feeding the
``else'' side, and a set of outputs that is the result of the conditional itself.
Using symbolic port names, a compiler module can easily refer to the second
``else'' output, for example, even though the actual port number for that output
may depend on how many ``then'' outputs the instruction has.

The rules for naming inputs or outputs are as follows:\index{port naming rules}
\begin{itemize}
\item An input or output may have at most one name.  (Arvind's principle)

\item No two inputs or two outputs of the same instruction may have the same name,
although an input and an output may have the same name (it is always possible
to tell whether an input or output is meant).

\item A name is either a keyword symbol (a simple name) or a cons whose car is a
keyword symbol and whose cdr is a non-negative integer (a subscripted name).

\item A simple name is an abbreviation for a subscripted name with a subscript of
zero.

\item If {\tt ({\it symbol\/} . {\it n\/})} is a name for an instruction's
port, then so is {\tt ({\it symbol\/} . {\it i\/})}, for all {\it i\/} from
zero through {\it n}.

\item Subscripted names with consecutive subscripts always map to ports with
consecutive numbers.
\end{itemize}
In other words, port names define a partition of an instruction's ports, with
the first port in a partition always having subscript zero.

There must be some way of translating symbolic names for ports to the
corresponding numbers, and so each instruction contains an {\it input
map\/}\index{input map} and an {\it output map\/}\index{output map} which give the
appropriate translations.  Maps can be created with the function
{\tt make-port-map}\lispindex{Name = "make-port-map"}, which takes a description
of the port names as input.  Since the configuration of ports for an
instruction cannot change, the maps for an instruction cannot change, and so a
map may be shared by several instructions that have the same configuration of
inputs or outputs.  In fact, such sharing is encouraged because it saves space.
One way to do this is to create maps for commonly used configurations and save
them in some variables or in a table.  The only function provided for
manipulating maps is {\tt make-port-map}; the user should not attempt to play
with the internal structure of maps.

\lispdoc make-instruction opcode input-map output-map \key :parameter [Function]
Creates and returns a new instruction, whose {\tt opcode},
{\tt input-map}, {\tt output-map}, and {\tt parameter} slots have
been initialized from the corresponding arguments.  The number of inputs and
outputs is inferred from the information in {\it input-map\/} and {\it output-map},
which must be port maps as created by {\tt make-port-map}\lispindex{Name =
"make-port-map"}.  {\it Opcode\/} must be a keyword symbol.

\lispdoc make-port-map map-description [Function]
Creates and returns a port map, based on a description of its contents.  The
description is a list of descriptors, each of which is either a keyword symbol
or a cons of a keyword symbol and a positive integer.  Each descriptor
specifies a given number of ports with the same symbol and subscripts running
consecutively from zero.  If a descriptor is just a symbol, it is the same as
the cons of that symbol and the number one.  The map created assigns port
numbers to the names in the descriptor from left to right.  Naturally, no
symbol may appear in the description twice.  Here's an example:
\begin{verbatim}
(make-port-map '((:structure . 1)
                 (:subscript . 3)
                 :value
                 (:trigger . 2)))
\end{verbatim}
returns a port map that describes the following mapping of port names to port
numbers:

$$\vbox{%
  \offinterlineskip
  \halign{%
      \hfil\strut#\quad&{\tt #}\hfil\hskip1in&\hfil#\quad&{\tt #}\hfil\cr
    Number&{\rm Name}&Number&{\rm Name}\cr
    \omit\hfil\centerstrut\hrulefill&\hrulefill&\hrulefill&\hrulefill\cr
    0&:STRUCTURE&4&:VALUE\cr
    1&(:SUBSCRIPT . 0)&5&(:TRIGGER . 0)\cr
    2&(:SUBSCRIPT . 1)&6&(:TRIGGER . 1)\cr
    3&(:SUBSCRIPT . 2)&&\cr}}$$

\lispdoc instruction-opcode instruction [Function]
Returns the contents of the {\tt opcode} slot of {\it instruction}.  May be used
with {\tt setf}, although this fact is of limited utility since the number of
inputs and outputs of an instruction cannot be altered after creation.

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

\lispdoc define-instruction-slot selector-name [Macro]
Defines a new ``slot'' for instructions, analogous to
{\tt define-ptnode-slot}\lispindex{Name = "define-ptnode-slot", Type = "Macro"}.
{\it Selector-name\/} must be a symbol whose print name begins with
{\tt instruction-}, and may not be any of the symbols {\tt instruction-opcode},
{\tt instruction-parameter}, {\tt instruction-input-map},
{\tt instruction-output-map}, {\tt instruction-inputs}, {\tt instruction-outputs},
{\tt instruction-mark}, or {\tt instruction-other-slots}.

\lispdoc instruction-n-inputs instruction [Function]
Returns the number of input ports that {\it instruction\/} has.

\lispdoc instruction-n-outputs instruction [Function]
Returns the number of output ports that {\it instruction\/} has.

\lispdoc instruction-input-name-to-number instruction input-name [Function]
Returns the input number corresponding to the input of {\it instruction\/} named
{\it input-name}, or {\tt nil} if that input name does not exist.

\lispdoc instruction-output-name-to-number instruction output-name [Function]
Returns the output number corresponding to the output of {\it instruction\/} named
{\it output-name}, or {\tt nil} if that output name does not exist.

\lispdoc instruction-input-number-to-name instruction input-number [Function]
Returns the input name corresponding to the input of {\it instruction\/} with
number {\it input-number}, or {\tt nil} if there is no input with that number.
Always returns a subscripted name.

\lispdoc instruction-output-number-to-name instruction output-number [Function]
Returns the output name corresponding to the output of {\it instruction\/} with
number {\it output-number}, or {\tt nil} if there is no output with that number.
Always returns a subscripted name.

\lispdoc wire-instruction-to-instruction
         instruction-1 output instruction-2 input \optional annotation
         [Function]
Wires {\it instruction-1\/}'s output {\it output\/} to {\it instruction-2\/}'s input
{\it input}.  {\it Output\/} and {\it input\/} may be either port numbers or port names.
The argument {\it annotation\/} is discussed in Section \ref{ArcSubSection}.

\subsection{Instruction Sources and Sinks}

The only primitive provided thus far for wiring instructions together is
{\tt wire-instruction-to-instruction}\lispindex{Name =
"wire-instruction-to-instruction"}, which takes the instructions and port
names/numbers as separate arguments.  Often, however, it is convenient to pass
around an object that refers to a particular input or output of a particular
instruction.  Two additional primitive types are provided for this:
{\it instruction sinks}\index{instruction sink}\index{sink}, and {\it instruction
sources}\index{instruction source}\index{source}.  The terminology is that a
sink is anything to which an instruction's output may be wired, and a source is
anything to which an instruction's input may be wired.  Putting it another way,
a sink is something that can absorb a dataflow token, while a source is
something that can emit a dataflow token.  An instruction sink, therefore,
describes a particular input of a particular instruction, while an instruction
source describes a particular output of a particular instruction.  As will be
seen in a later section, there are other kinds of sinks and sources as well.

\lispdoc make-instruction-sink instruction input \optional annotation [Function]
Creates and returns an instruction sink referring to input {\it input\/} of
instruction {\it instruction}.  {\it Input\/} may be either an input name or an input
number.   The {\it annotation\/} argument is discussed in Section \ref{ArcSubSection}.

\lispdoc make-instruction-source instruction output \optional annotation [Function]
Creates and returns an instruction source referring to output {\it output\/} of
instruction {\it instruction}.  {\it Output\/} may be either an output name or an output
number.   The {\it annotation\/} argument is discussed in Section \ref{ArcSubSection}.

\lispdoc wire-source-to-sink source sink \optional annotation [Function]
         Wires the source {\it source\/} to the source {\it sink}.  If {\it
source\/} and {\it sink\/} are instruction sources and sinks, respectively,
then this is equivalent to {\tt wire-instruction-to-instruction}\lispindex{Name
= "wire-instruction-to-instruction"}.  Other kinds of sources and sinks are
discussed in Section \ref{FrameSubSection}.  The {\it annotation\/} argument is
discussed in Section \ref{ArcSubSection}.

\lispdoc wire-source-to-instruction source instruction input \optional
annotation [Function]
Equivalent to calling {\tt wire-source-to-sink} with a call to
{\tt make-instruction-sink} as the second argument.

\lispdoc wire-instruction-to-sink instruction output sink \optional annotation [Function]
Equivalent to calling {\tt wire-source-to-sink} with a call to
{\tt make-instruction-source} as the first argument.

Sources and sinks make it easy to write procedures such as the following:
\begin{verbatim}
(defun compile-binding (lhs rhs)
  (let ((lhs-sink (compile-lhs lhs))
        (rhs-source (compile-expression rhs)))
     (wire-source-to-sink rhs-source lhs-sink)))
\end{verbatim}
where {\tt compile-lhs} and {\tt compile-rhs} return a sink and a source,
respectively.

\subsection{Arcs}
\label{ArcSubSection}

Instruction sources and sinks serve an additional role beyond being passed
around by modules of a compiler:  they are actually stored in the {\tt inputs}
and {\tt outputs} slots of instructions themselves.  The {\tt inputs} slot of an
instruction contains an array with as many elements as there are inputs, each
element containing either an instruction source, if the input is wired, or
{\tt nil}, if it is not.  The instruction source points to the instruction output
to which the input is wired.  Similarly, the {\tt outputs} slot of an instruction
contains an array with as many elements as there are outputs, and the elements
of the array contain instruction sinks.  Because an output may feed several
inputs, however, each element of the array contains not a single instruction
sink but a list of instruction sinks.  The order in which sinks appear in these
lists is unimportant.

\lispdoc instruction-inputs instruction [Function]
Returns the array containing the inputs of {\it instruction}, as described above.
May {\it not\/} be used with {\tt setf}.

\lispdoc instruction-outputs instruction [Function]
Returns the array containing the outputs of {\it instruction}, as described above.
May {\it not\/} be used with {\tt setf}.

\lispdoc instruction-input instruction input [Function]
Returns the contents of input {\it input\/} of instruction {\it instruction}.
{\it Input\/} may be either an input number or an input name.  The value returned
is either an instruction source, if the input is wired, or {\tt nil}, if it is
not.  May be used with {\tt setf}, although the wiring functions are the
preferred way of altering instruction inputs.

\lispdoc instruction-output instruction output [Function]
Returns the contents of output {\it output\/} of instruction {\it instruction}.
{\it Output\/} may be either an output number or an output name.  The value
returned is a (possibly empty) list of instruction sinks.  The order of sinks
in this list is unimportant.  May be used with {\tt setf}, although the wiring
functions are the preferred way of altering instruction outputs.

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

\lispdoc instruction-sink-input instruction-sink [Function]
Returns the input number referred to by {\it instruction-sink}.  Note that the
value returned is always a number, as {\tt make-instruction-sink}\lispindex{Name
= "make-instruction-sink"} converts input
names to input numbers.  May {\it not\/} be used with {\tt setf}.

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

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

\lispdoc instruction-source-output instruction-source [Function]
Returns the output number referred to by {\it instruction-source}.  Note that the
value returned is always a number, as
{\tt make-instruction-source}\lispindex{Name = "make-instruction-source"}
converts output names to output numbers.  May {\it not\/} be used with {\tt setf}.

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

As can be seen from the above definitions, sources and sinks are immutable
objects; the way an instruction's inputs and outputs are changed is by storing
new sources and sinks, not by modifying the existing ones.  Hence, there is no
danger in sharing sources and sinks.  Note too that instruction sources and
sinks always carry port numbers instead of port names, as this minimizes the
number of name-to-number translations that have to be performed.

When an instruction output is wired to an instruction input, the resulting
connection is called an arc\index{arc}.  In the graph, the arc is represented
by a source and a sink: a sink pointing to the second instruction is stored in
the appropriate output if the first instruction, and a source pointing to the
first instruction is stored in the appropriate input of the second instruction.
There is a certain amount of redundancy here, but having both the source and
the sink available makes it easy to traverse a graph in any direction.

\lispdoc remove-arc instruction-1 output instruction-2 input [Function]
If there is an arc from output {\it output\/} of instruction {\it instruction-1\/} to
input {\it input\/} of instruction {\it instruction-2}, {\tt remove-arc} removes it by
removing the sink from {\it instruction-1\/}'s output and removing the source from
{\it instruction-2\/}'s input.  Returns either {\tt t} or {\tt nil}, depending on
whether the arc actually existed or not, respectively.

\lispdoc remove-any-arc instruction input [Function]
 If there is any arc to input {\it input\/} of instruction {\it instruction\/},
{\tt remove-any-arc} removes it by removing the sink from the source
instruction's output and removing the source from {\it instruction\/}'s input.
Returns either {\tt t} or {\tt nil}, depending on whether the arc actually
existed or not, respectively.

\lispdoc remove-all-arcs instruction output [Function]
 If there are arcs from output {\it output\/} of instruction {\it
instruction\/}, {\tt remove-all-arc} removes them by removing all the sinks
from {\it instruction\/}'s output and removing the sources from each of the
destination instruction's inputs.

\lispdoc move-any-arc-destination old-instruction old-input new-instruction new-input [Function]
 If there is any arc to input {\it input\/} of instruction {\it instruction\/},
{\tt move-any-arc-destination} moves it by modifying the sink in the source
instruction's output and moving the source from {\it old-instruction\/}'s input
to {\it new-instruction\/}'s input {\it new-input\/}.

\lispdoc move-all-arc-origins old-instruction old-output new-instruction new-output [Function]
 If there are arcs from output {\it output\/} of instruction {\it
instruction\/}, {\tt move-all-arc-origins} moves them by moving all the sinks
from {\it old-instruction\/}'s output to {\it new-instruction\/}'s output {\it
new-output}, and modifying the sources in each of the destination instructions'
inputs.

Associated with every arc is an annotation, which may be used to describe the
data flowing on the arc.  This annotation might be, for example, an indication
of a variable name from the source program.  Once an arc is put in place, both
the source and the sink comprising that arc carry a pointer to the annotation,
for convenience (only one of them really needs to carry it).  Sources and sinks
can also carry annotations even when they are not part of an arc, and these
annotations are used in determining what the final annotation for an arc will
be.  When two instructions are wired together, the following rules for
determining the annotation are applied in the order given:\index{arc annotation
rules}

\begin{enumerate}
\label{simplearcrules}
\item If the call to the wiring function includes the optional
{\it annotation\/} argument, then the value of that argument becomes the
annotation.

\item If the wiring function takes a sink as an argument, and that sink carries an
annotation, then that annotation becomes the annotation for the arc.

\item If the wiring function takes a source as an argument, and that source carries
an annotation, then that annotation becomes the annotation for the arc.

\item Otherwise, the arc has no annotation.
\end{enumerate}

\begin{aside}
{\bf Design Note:}  It was decided that sinks should take priority over sources in
determining arc annotations because each source may be wired to many sinks, but
not {\it vice versa}.  Thus, in some sense, sinks carry more specific
information.  More complicated schemes, such as retaining {\it both\/} the sink's
and source's annotation if they exist, were rejected as needlessly complex.
The annotation policy is subject to revision.
\end{aside}

A sink or source has no annotation if the {\tt annotation} slot contains {\tt nil},
and so {\tt nil} can never be used as an annotation.  Unlike the {\tt other-slots}
slots of ptnodes and instructions, the {\tt annotation} slot of sources and sinks
are not constrained to be property lists, and there is no ``define slot'' feature
for arc annotations.

\lispdoc arc-annotation instruction-1 output instruction-2 input [Function]
Returns the annotation of the arc connecting output {\it output\/} of instruction
{\it instruction-1\/} with input {\it input\/} of instruction {\it instruction-2}.  May
be used with {\tt setf}.

\subsection{Frames}
\label{FrameSubSection}

\index{frame}A situation that commonly arises during compilation to dataflow
graphs is that you want to wire something to an instruction, but you don't know
what that something is.  For example, consider the expression {\tt a + b}.  To
compile this, you must create a {\tt +} instruction, and then wire {\tt a} and
{\tt b} to its inputs.  Depending on when you encountered {\tt a + b}, however, you
may or may not yet have generated the graphs that produce {\tt a} and {\tt b}.  To
deal with this situation, the compiler substrate includes a facility called
{\it frames}.

\begin{fig}{FrameFigure}{A Typical Frame}
\illustration{csg261-4}
\end{fig}

Figure \ref{FrameFigure} depicts a typical frame.  As the figure shows, the
name ``frame'' was chosen by analogy to a picture frame---in this case, the
frame encloses a dataflow graph.  A frame consists of a number of {\it frame
inputs}\index{frame input} and a number of {\it frame outputs\/}\index{frame
output};  collectively, a frame's inputs and outputs are known as its
{\it points}\index{point}\index{frame point}.  Each point serves as a wiring
point, to which one source and any number of sinks may be connected.  If the
source and sinks are an instruction source and instruction sinks, the net
effect is to cause the source to be wired to each of the sinks.  For example,
in Figure \ref{FrameFigure}, if the output of an instruction were to be
wired to frame input {\tt :A}, then that output would be automatically wired to
the inputs of the {\tt +} and {\tt APPLY} instructions shown.

As the figure shows, each frame input and frame output has a name associated
with it.  Frame point names are like instruction port names, and the rules for
naming frame inputs and outputs are exactly the same.  Unlike instruction
ports, however, frame points can only be referred to by name; there is no
number corresponding to a frame input or output.  Another difference is that
while the number of ports of an instruction is fixed when the instruction is
created, frames are always created with no points at all, and additional inputs
and outputs may be added to a frame at any time, although they can never be
removed.

It should be noted that there is really no difference between a frame input and
a frame output, since each can have one source and any number of sinks wired to
it.  But frames are most commonly used to ``enclose'' a subgraph, and so it is
useful to separate the frame's points into those that lead to the enclosed
subgraph (the frame inputs) and those that lead away from the enclosed subgraph
(the frame outputs).  Having separate frame inputs and outputs allows a frame
to have both an input and an output with the same name.

Here is how frame points work.  A frame point is created by adding an input or
output to some frame.  Any number of sinks may then be wired to the point, and
they will be recorded in the frame.  When a source is wired to that point, the
system automatically wires the source to each of the sinks recorded for that
point, and then records the source in the frame.  Each time a sink is wired to
the point thereafter, the sink is automatically wired to the point's source.
Any attempt to wire another source to the point is an error.

Any kind of sink or source may be wired to a frame point, including sinks or
sources referring to other frame points.  This allows the creation of chains of
interconnected frame points, with the system taking care of proper propagation
of information.  Since a frame point may have only one source but several
sinks, interconnected frame points actually form a tree structure.  When an
instruction source is wired to the root of such a tree, that instruction output
is wired to all instruction sinks at the leaves of the tree, and to any
additional sinks that are later wired to the leaves.  The system will detect
any attempt to create a circular interconnection of frame points, and will
signal an error.

There is an important difference between wiring instructions to instructions
and wiring instructions to frame points.  When an instruction is wired to
another instruction, an arc is created consisting of a source/sink pair
recorded in the output and input of the instructions involved.  Thus, if
instruction A is wired to instruction B, a pointer to instruction B is stored
within instruction A and a pointer to instruction A is stored within
instruction B.  When an instruction is wired to a frame point, however, that
fact is recorded only in the frame, and not in the instruction.  For example,
if an output of instruction C is wired to frame point D, an instruction source
is recorded within D's frame, but no sink is recorded in instruction C's
output.  Similarly, if an input of instruction E is wired to frame point F, an
instruction sink is recorded in F's frame, but no source is stored in E's
input.  The arcs between instructions and frame points and between pairs of
frame points are called {\it virtual arcs}\index{virtual arc}, to contrast them
with true arcs between instructions.

This fact is significant because it means you cannot tell if an instruction is
wired to a frame point by examining the instruction.  Consider the following
situation: instruction input A is wired to frame point B, and then that same
input is wired to instruction output C.  One might expect the latter wiring to
cause an error, since it will be the second time instruction input A is wired.
Because wiring the input A to the frame point did not affect A's instruction,
however, the wiring of A to instruction output C does not cause an error, and
an arc between A and C is placed normally.  An error {\it does\/} occur if an
instruction output is later wired to frame point B, since the system will then
attempt to wire that output to instruction input A, and A is already
wired.

\begin{aside}
{\bf Design Note:} The behavior of frame points as described in the preceding
paragraph was chosen to make the implementation of frames more efficient, even
though it results in anomalous situations as described.  The alternative was to
record virtual arcs in the same manner as real arcs, which means that virtual
arcs would have to be replaced whenever a chain of interconnected frame points
was extended, or finally connected to instructions.  The scheme adopted allows
frames to be used heavily with little overhead, but the behavior of frame
points may be revised if the anomalous situations described become a problem.
\end{aside}

Frames are an intermediate data structure only; they cannot be passed from
compiler module to compiler module.

\lispdoc make-frame [Function]
Creates and returns a new frame with no points.

\begin{lispdocs}
\lispdoc add-input-to-frame frame name [Function]
\lispdoc add-output-to-frame frame name [Function]
\end{lispdocs}
Adds a frame input (output) named {\it name\/} to frame {\it frame}.  It is an error
if an input (output) with that name already exists.  {\it Name\/} may be either a
keyword symbol or the cons of a keyword symbol and a non-negative integer;
specifying just a symbol is equivalent to specifying the cons of that symbol
and zero.  If {\it name\/} is a subscripted name, then inputs (outputs) are created
for all names with the same symbol and subscripts running from zero to the
given subscript, if any of those names do not already exist.

\lispdoc add-next-input-to-frame frame name [Function]
\lispdoc add-next-output-to-frame frame name [Function]
{\it Name\/} must be a keyword symbol.  If {\it frame\/} has no input (output) named
{\it name}, an input (output) named {\tt ({\it name\/} . 0)} is added to {\it frame}.
Otherwise, an input (output) named {\tt ({\it name\/} . $n+1$)} is added to
{\it frame}, where {\it n\/} is the subscript of the input (output) of {\it frame\/} that
has symbol {\it name\/} and the largest subscript.  Returns the name of the input
(output) that was actually created.

\begin{lispdocs}
\lispdoc frame-input-names frame \optional symbols-only? [Function]
\lispdoc frame-output-names frame \optional symbols-only? [Function]
\end{lispdocs}
If {\it symbols-only?\/} is {\tt nil} or unspecified, returns a list of frame input
(output) names for {\it frame}, where each element of the list is the
(subscripted) name of the input (output) with the highest subscript of all
names bearing that name's symbol.  Otherwise, just returns a list of symbols,
one for each frame input (output) with a different symbol.

\begin{lispdocs}
\lispdoc frame-input-exists? frame name [Function]
\lispdoc frame-output-exists? frame name [Function]
\end{lispdocs}
Returns {\tt t} if {\it frame\/} has a frame input (output) with name {\it name},
{\tt nil} otherwise.

\begin{lispdocs}
\lispdoc frame-number-of-inputs-with-symbol frame symbol [Function]
\lispdoc frame-number-of-outputs-with-symbol frame symbol [Function]
\end{lispdocs}
Returns the number of frame inputs (outputs) of frame {\it frame\/} whose symbol is
{\it symbol}.  This number is one greater than the subscript of the name with the
highest subscript, or zero if there are no inputs (outputs) with that symbol.

\begin{lispdocs}
\lispdoc make-frame-input-source frame name \optional annotation [Function]
\lispdoc make-frame-output-source frame name \optional annotation [Function]
\end{lispdocs}
Creates and returns a source referring to the frame input (output) named
{\it name\/} of frame {\it frame}.  This source may then be wired to an instruction
input, or to another frame input or output.  {\it Annotation\/} is discussed below.

\begin{lispdocs}
\lispdoc make-frame-input-sink frame name \optional annotation [Function]
\lispdoc make-frame-output-sink frame name \optional annotation [Function]
\end{lispdocs}
Creates and returns a sink referring to the frame input (output) named
{\it name\/} of frame {\it frame}.  This sink may then be wired to an instruction
output, or to another frame input or output.  {\it Annotation\/} is discussed below.

The function {\tt wire-source-to-sink}\lispindex{Name = "wire-source-to-sink"}
works for any combination of instruction, frame input, or frame output sources
and sinks.  In addition, the following functions are provided in case one of
the arguments to {\tt wire-source-to-sink} would be a call to one of the
{\tt make-?-sink} or {\tt make-?-source} functions.
\begin{lispdocs}
\lispdoc wire-frame-output-to-frame-output 
         frame-1 output-1 frame-2 output-2 \optional annotation
         [Function]
\lispdoc wire-frame-output-to-frame-input 
         frame-1 output frame-2 input \optional annotation
         [Function]
\lispdoc wire-frame-output-to-instruction
         frame output instruction input \optional annotation
         [Function]
\lispdoc wire-frame-output-to-sink frame output sink \optional annotation [Function]
\lispdoc wire-frame-input-to-frame-output
         frame-1 input frame-2 output \optional annotation
         [Function]
\lispdoc wire-frame-input-to-frame-input 
         frame-1 input-1 frame-2 input-2 \optional annotation
         [Function]
\lispdoc wire-frame-input-to-instruction
         frame input instruction input \optional annotation
         [Function]
\lispdoc wire-frame-input-to-sink frame input sink \optional annotation [Function]
\lispdoc wire-instruction-to-frame-output
         instruction output-1 frame output-2 \optional annotation
         [Function]
\lispdoc wire-instruction-to-frame-input
         instruction output frame input \optional annotation
         [Function]
\lispdoc wire-source-to-frame-output source frame output \optional annotation [Function]
\lispdoc wire-source-to-frame-input source frame input \optional annotation [Function]
\end{lispdocs}

The rules for annotating an arc are necessarily complicated by the presence of
frame points.  Here are the rules when frame points are involved:\index{arc
annotation rules}
\begin{itemize}
\item When a frame point is wired to an instruction or another frame point, a
virtual arc\index{virtual arc} is created and recorded in the frame (see above).  The
annotation for this virtual arc is derived from the rules on page
\pageref{simplearcrules}:  annotations given in call to the wiring function
take priority, followed by annotations on the sink involved, followed by
annotations on the source.

\item When a chain is completed, the annotation that will be included in the actual
arc from instruction output to instruction input is determined by starting at the
virtual arc leading to the instruction input and tracing up the chain until
an annotation is found.  If no annotation is found, the actual arc will have no
annotation.
\end{itemize}
Although the rules for arc annotation may seem horribly complex, they are
designed to the following simple principle:  the system should automatically
choose the annotation that best describes the arc.  By using {\tt setf} with
{\tt arc-annotation}\lispindex{Name = "arc-annotation"}, the compiler writer can
always override an annotation chosen by the system.

\subsection{Dataflow Graphs}
\label{DataflowGraphSubSection}

When passing a complete dataflow graph from module to module, it is often necessary
to pass along some additional information, such as the compiler version,
{\it etc}.  The {\tt dataflow-graph} abstraction is provided for this purpose.
Like the {\tt parse-tree} abstraction, the {\tt dataflow-graph} abstraction
packages up a graph along with a property list carrying additional information.
Unlike a parse tree, however, a dataflow graph is not necessarily connected,
and so it does not suffice to include a single instruction in the
{\tt dataflow-graph} structure.  Instead, it carries a {\it root set}, which is a
list containing one or more instructions of the graph.  Any instruction
reachable from one of the instructions in the root set is considered part of
the graph.  The root set must therefore contain at least one instruction from
each connected component of the graph; it does not matter if more than one
instruction from each component is included.

\lispdoc make-dataflow-graph root-set \optional plist [Function]
Creates and returns a new dataflow graph, whose root set is {\it root-set}, and
with property list {\it plist}.  The default for {\it plist\/} is an empty property
list. 

\lispdoc dataflow-graph-root-set dataflow-graph [Function]
Returns the root set of dataflow graph {\it dataflow-graph}.  May be used with
{\tt setf}.

\lispdoc dataflow-graph-plist dataflow-graph [Function]
Returns the property list of dataflow graph {\it dataflow-graph}.  May be used with
{\tt setf}.  The following function is probably more useful.

\lispdoc dataflow-graph-get dataflow-graph indicator \optional default [Function]
Returns the {\it indicator\/} property of {\it dataflow-graph\/}'s plist, or {\it default\/} if
that property does not exist.  In other words, {\tt dataflow-graph-get} combines
{\tt dataflow-graph-plist} with {\tt getf}.  May be used with {\tt setf}.

\lispdoc with-instruction-array \list{var dataflow-graph \optional number-p}
                                \body body [Macro]

 Within the body of the {\tt with-instruction-array} form, the variable
{\em var\/} will be bound to an array containing all of the instructions of
{\em dataflow-graph\/}.  If {\em number-p\/} is true, then the instructions
will be numbered such that the {\tt instruction-number} of the $i$th
element of the instruction-array will be $i$.  When control leaves the body
of the {\tt with-instruction-array} form in any way, the instruction-array
will be deallocated.  Therefore, the instruction array may not be passed
outside the dynamic scope of the {\tt with-instruction-array}.

