\documentclass{article}
\usepackage{fullpage}
\begin{document}
\title{Carry Processing in Pablo}
\author{Kenneth S. Herdy and Robert D. Cameron}
\date{\today}
\maketitle
\section{Concepts}
\subsection{Carry Generating Operations}
The following Pablo operations generate carry bits that
must be considered in block-by-block processing.
\begin{itemize}
\item Each scan operation ({\tt ScanThru}, {\tt ScanTo}, {\tt AdvanceThenScanThru}, {\tt AdvanceThenScanTo}, {\tt ScanToFirst})
generates a single carry bit based on the underlying addition used in its implementation.
\item Each span operation ({\tt SpanUpTo}, {\tt InclusiveSpan}, {\tt ExclusiveSpan})
generates a single carry bit (actually a ``borrow'') based on the underlying subtraction used in its implementation.
\item Each ({\tt Advance(s)} operation generates a single carry bit corresponding to the single
bit shifted out by a single position forward shift operation.
\item Each ({\tt Advance(s, n)} operation generates {\tt n} carry bits corresponding to the
bits shifted out by the {\tt n}-position forward shift operation.
\end{itemize}
\subsection{Carry Enumeration}
Carry enumeration is the process of assigning sequential {\em carry bit numbers}
to each of the carry bits required in compiling a stream function.
Carry enumeration is carried out by visiting all possibly carry-generating
operations in the stream function body in a standard order called
the {\em carry enumeration order}, typically
depth-first and left-to-right.
Note that for an ({\tt Advance(s, n)} operation,
{\tt n} consecutive carry bit numbers are assigned.
\subsection{Carry Information Set}
The Carry Information Set ({\tt CarryInfoSet}) is a representation
of the carry bit information required in compiling a stream function.
The Carry Information Set identifies positions and counts of carry
generating operations and carry-dependent structures. The position is
identified as the position within carry enumeration order. That is,
the position of an operation or structure corresponds to the number
of carry bits that are enumerated prior to encountering the operation
or structure in the standard carry enumeration order. The carry
count of an item is the number of carry bits recursively encountered within it.
The Carry Information Set consists of the following items.
\begin{itemize}
\item {\tt CarryCount}: the total number of carry bits for all carry-generating functions in the stream function.
\item Advance Information: a list of the following information for each Advance operation.
\begin{itemize}
\item The position of the {\tt Advance} statement.
\item The number of carry bits required corresponding to {\tt n} in {\tt Advance(s, n)}.
\end{itemize}
\item While Loop Information: a list of While Loop information items for each while loop in the stream function, comprising the
following items.
\begin{itemize}
\item The position of the while loop.
\item The while loop carry count.
\item The while loop prologue overlap count. This is a count related to optimization and may be set to 0
in nonoptimizing implementations. In optimizing, it is the number of carry bits at the end of the loop body
that may be subsumed by equivalent carry bits in statements immediately preceding the loop body.
\end{itemize}
\item If Statement Information: a list of information items for each if statement in the stream function, comprising the
following items.
\begin{itemize}
\item The position of the if statement.
\item The if statement carry count.
\end{itemize}
\end{itemize}
\subsection{Carry-In Form vs. Carry-Out Form}
When a carry value is represented in a register or field,
we distinguish between two forms. The {\em carry-in} form is the form
in which the carry bit is a single bit in the low (rightmost) position
of a register or field, with all other bits being zero.
In the carry-in form, the carry value is ready to be used
directly in performing an add-with-carry operation.
The {\em carry-out} form is the form in which the
carry bit is in the high bit position of a register or field,
and other bits have arbitrary values.
Typically, the other bits will have values
resulting from a carry calculation using bitwise logic;
this calculation is ignored at all positions except the
high (leftmost) position.
As each block of data is processed, carries are generated
in carry-out form. Prior to moving on to use these carries
in processing the next block of data, each of the carries
must be converted to carry-in form.
\section{Implementation}
\subsection{Carry Code Generation Objects}
A Carry Code Generation Object (CCGO) is an object that encapsulates the information
needed to handle all of the carry-processing requirements in compiling
a stream function to block-by-block code.
In general, a separate CCGO is created for
each stream function based on a strategy that is chosen for that
stream function. The CCGO provides a set of methods that may
be called by the compiler to create code fragments that the compiler then
inserts into compiled code.
Each CCGO provides the following methods.
\begin{itemize}
\item {\tt GenerateCarryVariables()}: return a list of strings naming the carry variables that are required for block-to-block communication of carry information.
These include variables for holding individual carries, packed groups of carries and/or carry-test variables depending on the code
generation strategy.
\item {\tt GenerateCarryVariableTypes()}: return a list of strings naming the types of the carry variables generated by {\tt GenerateCarryVariables}.
\item {\tt GenerateCarryVariableInits()}: return a list of initialization statements for each of the carry variables generated by {\tt GenerateCarryVariables}.
\item {\tt GenerateCarryTemps(while\_index)}: return a list of strings naming the local carry temporary variables that are used for processing the while loop whose position is given by {\tt while\_index}.
\item {\tt GenerateCarryTempTypes(while\_index)}: return a list of strings naming the types of the local carry temporary variables generated
by {\tt GenerateCarryTemps(while\_index)}.
\item {\tt GenerateCarryTempInits(while\_index)}: return a list of initialization statements for each of the local carry temporary variables generated
by {\tt GenerateCarryTemps(while\_index)}.
\item {\tt GenerateCarryWhileTest(while\_index, exprNode):} return the test expression for the while loop whose position is given by {\tt while\_index}
and whose original expression node is {\tt exprNode}.
\item {\tt GenerateCarryIfTest(if\_index, exprNode):} return the test expression for the if statement whose position is given by {\tt if\_index}
and whose original expression node is {\tt exprNode}.
\item {\tt GenerateCarryInAccess(carry\_index):} return the expression that retrieves and/or unpacks the value of the carry variable whose number
in the enumeration order is {\tt carry\_index}.
\item {\tt GenerateCarryOutReference(carry\_index):} return the statement that appropriately stores and/or packs the value of the carry variable whose number
in the enumeration order is {\tt carry\_index}.
\item {\tt GenerateCarryWhileFinalization(while\_index):} return the statements to be inserted at the end of each iteration of the
while loop whose index is {\tt while\_index}. This will include the statements to combine the carry variables of successive iterations (CarryCombine). (But note that this may change for nested iteration with indexed stream variables.)
\item {\tt GenerateCarryIfFinalization(if\_index):} return the statements to be inserted at the end of the body of the if statement (then-part) whose index is {\tt if\_index}. This may include the statements to store the value of the if-test variable, depending on the strategy.
\item {\tt GenerateStreamFunctionFinalization():} return the statements to be inserted at the end of the body of the stream function
for finalizing the carry variable processing of the current block. This may include code to convert from carry-in form to carry-out form,
if necessary.
\end{itemize}
\end{document}