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 | |
---|
15 | The following Pablo operations generate carry bits that |
---|
16 | must 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}) |
---|
20 | generates 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}) |
---|
23 | generates 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 |
---|
26 | bit 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 |
---|
29 | bits shifted out by the {\tt n}-position forward shift operation. |
---|
30 | \end{itemize} |
---|
31 | |
---|
32 | |
---|
33 | \subsection{Carry Enumeration} |
---|
34 | |
---|
35 | Carry enumeration is the process of assigning sequential {\em carry bit numbers} |
---|
36 | to each of the carry bits required in compiling a stream function. |
---|
37 | Carry enumeration is carried out by visiting all possibly carry-generating |
---|
38 | operations in the stream function body in a standard order called |
---|
39 | the {\em carry enumeration order}, typically |
---|
40 | depth-first and left-to-right. |
---|
41 | Note that for an ({\tt Advance(s, n)} operation, |
---|
42 | {\tt n} consecutive carry bit numbers are assigned. |
---|
43 | |
---|
44 | \subsection{Carry Information Set} |
---|
45 | |
---|
46 | The Carry Information Set ({\tt CarryInfoSet}) is a representation |
---|
47 | of the carry bit information required in compiling a stream function. |
---|
48 | |
---|
49 | The Carry Information Set identifies positions and counts of carry |
---|
50 | generating operations and carry-dependent structures. The position is |
---|
51 | identified as the position within carry enumeration order. That is, |
---|
52 | the position of an operation or structure corresponds to the number |
---|
53 | of carry bits that are enumerated prior to encountering the operation |
---|
54 | or structure in the standard carry enumeration order. The carry |
---|
55 | count of an item is the number of carry bits recursively encountered within it. |
---|
56 | |
---|
57 | The 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 |
---|
67 | following 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 |
---|
72 | in nonoptimizing implementations. In optimizing, it is the number of carry bits at the end of the loop body |
---|
73 | that 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 |
---|
77 | following 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 | |
---|
88 | When a carry value is represented in a register or field, |
---|
89 | we distinguish between two forms. The {\em carry-in} form is the form |
---|
90 | in which the carry bit is a single bit in the low (rightmost) position |
---|
91 | of a register or field, with all other bits being zero. |
---|
92 | In the carry-in form, the carry value is ready to be used |
---|
93 | directly in performing an add-with-carry operation. |
---|
94 | |
---|
95 | The {\em carry-out} form is the form in which the |
---|
96 | carry bit is in the high bit position of a register or field, |
---|
97 | and other bits have arbitrary values. |
---|
98 | Typically, the other bits will have values |
---|
99 | resulting from a carry calculation using bitwise logic; |
---|
100 | this calculation is ignored at all positions except the |
---|
101 | high (leftmost) position. |
---|
102 | |
---|
103 | As each block of data is processed, carries are generated |
---|
104 | in carry-out form. Prior to moving on to use these carries |
---|
105 | in processing the next block of data, each of the carries |
---|
106 | must be converted to carry-in form. |
---|
107 | |
---|
108 | |
---|
109 | |
---|
110 | |
---|
111 | \section{Implementation} |
---|
112 | |
---|
113 | \subsection{Carry Code Generation Objects} |
---|
114 | |
---|
115 | A Carry Code Generation Object (CCGO) is an object that encapsulates the information |
---|
116 | needed to handle all of the carry-processing requirements in compiling |
---|
117 | a stream function to block-by-block code. |
---|
118 | |
---|
119 | In general, a separate CCGO is created for |
---|
120 | each stream function based on a strategy that is chosen for that |
---|
121 | stream function. The CCGO provides a set of methods that may |
---|
122 | be called by the compiler to create code fragments that the compiler then |
---|
123 | inserts into compiled code. |
---|
124 | |
---|
125 | Each 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. |
---|
128 | These include variables for holding individual carries, packed groups of carries and/or carry-test variables depending on the code |
---|
129 | generation 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 |
---|
134 | by {\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 |
---|
136 | by {\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} |
---|
138 | and 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} |
---|
140 | and 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 |
---|
142 | in 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 |
---|
144 | in 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 |
---|
146 | 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.) |
---|
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 |
---|
149 | for finalizing the carry variable processing of the current block. This may include code to convert from carry-in form to carry-out form, |
---|
150 | if necessary. |
---|
151 | \end{itemize} |
---|
152 | |
---|
153 | \end{document} |
---|