source: proto/Compiler/carrycodegen.tex

Last change on this file was 2573, checked in by cameron, 7 years ago

Carry Code Generation Document - initial version.

File size: 7.9 KB
Line 
1\documentclass{article}
2\usepackage{fullpage}
3
4\begin{document}
5\title{Carry Processing in Pablo}
6\author{Kenneth S. Herdy and Robert D. Cameron}
7\date{\today}
8
9\maketitle
10
11
12\section{Concepts}
13\subsection{Carry Generating Operations}
14
15The following Pablo operations generate carry bits that
16must be considered in block-by-block processing.
17
18\begin{itemize}
19\item Each scan operation ({\tt ScanThru}, {\tt ScanTo}, {\tt AdvanceThenScanThru}, {\tt AdvanceThenScanTo}, {\tt ScanToFirst})
20generates a single carry bit based on the underlying addition used in its implementation.
21
22\item Each span operation ({\tt SpanUpTo}, {\tt InclusiveSpan}, {\tt ExclusiveSpan})
23generates a single carry bit (actually a ``borrow'') based on the underlying subtraction used in its implementation.
24
25\item Each ({\tt Advance(s)} operation generates a single carry bit corresponding to the single
26bit shifted out by a single position forward shift operation.
27
28\item Each ({\tt Advance(s, n)} operation generates {\tt n} carry bits corresponding to the
29bits shifted out by the {\tt n}-position forward shift operation. 
30\end{itemize}
31
32
33\subsection{Carry Enumeration}
34
35Carry enumeration is the process of assigning sequential {\em carry bit numbers}
36to each of the carry bits required in compiling a stream function.
37Carry enumeration is carried out by visiting all possibly carry-generating
38operations in the stream function body in a standard order called
39the {\em carry enumeration order}, typically
40depth-first and left-to-right. 
41Note that for an ({\tt Advance(s, n)} operation,
42{\tt n} consecutive carry bit numbers are assigned.
43
44\subsection{Carry Information Set}
45
46The Carry Information Set ({\tt CarryInfoSet}) is a representation
47of the carry bit information required in compiling a stream function.
48
49The Carry Information Set identifies positions and counts of carry
50generating operations and carry-dependent structures.   The position is
51identified as the position within carry enumeration order.   That is,
52the position of an operation or structure corresponds to the number
53of carry bits that are enumerated prior to encountering the operation
54or structure in the standard carry enumeration order.   The carry
55count of an item is the number of carry bits recursively encountered within it.
56
57The Carry Information Set consists of the following items.
58\begin{itemize}
59\item {\tt CarryCount}: the total number of carry bits for all carry-generating functions in the stream function.
60\item Advance Information: a list of the following information for each Advance operation.
61\begin{itemize}
62\item The position of the {\tt Advance} statement.
63\item The number of carry bits required corresponding to {\tt n} in {\tt Advance(s, n)}.
64\end{itemize}
65
66\item While Loop Information: a list of While Loop information items for each while loop in the stream function, comprising the
67following items.
68\begin{itemize}
69\item The position of the while loop.
70\item The while loop carry count.
71\item The while loop prologue overlap count.  This is a count related to optimization and may be set to 0
72in nonoptimizing implementations.   In optimizing, it is the number of carry bits at the end of the loop body
73that may be subsumed by equivalent carry bits in statements immediately preceding the loop body.
74\end{itemize}
75
76\item If Statement Information: a list of information items for each if statement in the stream function, comprising the
77following items.
78\begin{itemize}
79\item The position of the if statement.
80\item The if statement carry count.
81\end{itemize}
82\end{itemize}
83
84
85
86\subsection{Carry-In Form vs. Carry-Out Form}
87
88When a carry value is represented in a register or field,
89we distinguish between two forms.   The {\em carry-in} form is the form
90in which the carry bit is a single bit in the low (rightmost) position
91of a register or field, with all other bits being zero.
92In the carry-in form, the carry value is ready to be used
93directly in performing an add-with-carry operation.
94
95The {\em carry-out} form is the form in which the
96carry bit is in the high bit position of a register or field,
97and other bits have arbitrary values. 
98Typically, the other bits will have values
99resulting from a carry calculation using bitwise logic;
100this calculation is ignored at all positions except the
101high (leftmost) position.
102
103As each block of data is processed, carries are generated
104in carry-out form.  Prior to moving on to use these carries
105in processing the next block of data, each of the carries
106must be converted to carry-in form.
107
108
109
110
111\section{Implementation}
112
113\subsection{Carry Code Generation Objects}
114
115A Carry Code Generation Object (CCGO) is an object that encapsulates the information
116needed to handle all of the carry-processing requirements in compiling
117a stream function to block-by-block code.
118
119In general, a separate CCGO is created for
120each stream function based on a strategy that is chosen for that
121stream function.   The CCGO provides a set of methods that may
122be called by the compiler to create code fragments that the compiler then
123inserts into compiled code.
124
125Each CCGO provides the following methods.
126\begin{itemize}
127\item {\tt GenerateCarryVariables()}: return a list of strings naming the carry variables that are required for block-to-block communication of carry information.
128These include variables for holding individual carries, packed groups of carries and/or carry-test variables depending on the code
129generation strategy.
130\item {\tt GenerateCarryVariableTypes()}:  return a list of strings naming the types of the carry variables generated by {\tt GenerateCarryVariables}.
131\item {\tt GenerateCarryVariableInits()}:  return a list of initialization statements for each of the carry variables generated by {\tt GenerateCarryVariables}.
132\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}.
133\item {\tt GenerateCarryTempTypes(while\_index)}: return a list of strings naming the types of the local carry temporary variables generated
134by {\tt GenerateCarryTemps(while\_index)}.
135\item {\tt GenerateCarryTempInits(while\_index)}: return a list of initialization statements for each of the local carry temporary variables generated
136by {\tt GenerateCarryTemps(while\_index)}.
137\item {\tt GenerateCarryWhileTest(while\_index, exprNode):}  return the test expression for the while loop whose position is given by {\tt while\_index}
138and whose original expression node is {\tt exprNode}.
139\item {\tt GenerateCarryIfTest(if\_index, exprNode):}  return the test expression for the if statement whose position is given by {\tt if\_index}
140and whose original expression node is {\tt exprNode}.
141\item {\tt GenerateCarryInAccess(carry\_index):}  return the expression that retrieves and/or unpacks the value of the carry variable whose number
142in the enumeration order is {\tt carry\_index}.
143\item {\tt GenerateCarryOutReference(carry\_index):}  return the statement that appropriately stores and/or packs the value of the carry variable whose number
144in the enumeration order is {\tt carry\_index}.
145\item {\tt GenerateCarryWhileFinalization(while\_index):}  return the statements to be inserted at the end of each iteration of the
146while 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.)
147\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.
148\item {\tt GenerateStreamFunctionFinalization():} return the statements to be inserted at the end of the body of the stream function
149for finalizing the carry variable processing of the current block.  This may include code to convert from carry-in form to carry-out form,
150if necessary.
151\end{itemize}
152
153\end{document}
Note: See TracBrowser for help on using the repository browser.