source: proto/pabloj/trunk/docs/notes @ 2932

Last change on this file since 2932 was 2932, checked in by ksherdy, 6 years ago

Added notes.

File size: 8.6 KB
Line 
1State of PabloJ Compiler
2
3This document describes the state of the PabloJ compiler at Version 0.8.0.
4
5Version 0.8.0
6
7Implements basic carry macro support.
8Validates against XMLWF test suite.
9Validates against larger XML files.
10
11Modelled on Python/Pablo version 2615.
12
13-----
14
15Pablo vs. PabloJ Implementation Differences
16
17(1) Explicit local variable declarations with explicit types.
18
19e.g. bitblock s; s = simd::constant<1>(0);
20
21(2) Current PabloB grammar does not support boolean OR.
22
23Work around. Added PabloJCarryTest runtime check that returns a type BitBlock.
24Wrapped 'if' / 'while' conditions within bitblock::any() IDISA call.
25
26(3) TODO - Avoid carry object creation in Kernel w/o carries.
27
28(4) BitBlock EOF_mask --> const BitBlock mask
29
30(5) 
31
32PabloS - Design and implementation issues.
33
34(1) Grammar/Parser/Semantic Analyzer
35
36    The current Scatter grammar does not restrict many programs accepted by the parser.
37       
38        At this time the intention is that a semantic analysis phase will generate semantic errors.
39       
40    For example,
41   
42    (a) PabloS grammar permits top-level type declarations of all types.
43        However, the intention is to restrict to stream struct definitions.
44   
45    (b) PabloS grammar does not enforce def/use for stream structs prior to use in stream function defintions,
46        i.e. PabloS grammar does not prevent the definition of stream functions prior to stream structs.
47       
48    (c) PabloS grammar does not prevent the definition of new types within the body of
49        stream functions.   
50
51 (2) No semantic analysis, no type checking.
52       
53
54PabloB - Design and implementation issues.
55
56(1) 'static' initialization section vs. 'kernel' constructor
57
58(2) integer types uint8, uint16, uint32, uint64, uint128, uint256
59  - if integer types are restricted 'sections' of stream then no apparent need exists for signed integers
60
61C++ Code Generation Strategy
62
63(1) sythetic variable, scope, identifiers, tree compression, etc...
64
65PabloJ - Pablo language implementation.
66
67(1) Translates arbitrary length 2^k bit field width streams to an equivalent block-at-a-time target language implementation.
68(2) ...
69
70PabloJ Design Differences
71
721. Programmer defined stream function variable declaration. PabloJ does not gather local variables.
73
74PabloJ Implementation Differences
75
762. Split CarryIntro into separate passes:
77(i) Add carry macros to AST.
78
79Pablo 'if' - Note: The PabloJ translation of 'if' differs slightly from Pablo (Python).
80               
81E - Pablo Expression
82S - Pablo Statement     
83               
84Pablo --> C++/IDISA block-at-a-time target language implementation.
85   
86if ( E ) { S* } (else { S'* } )?
87           
88-->
89           
90if (bitblock::any(E | carryQ.any_carry(base,count)) { S* } else { carrrQ.enqueue_dequeue(base, count); }
91           
92Pablo 'while'
93           
94while ( E ) { S* }
95
96-->
97
98if (bitblock::any(E | carryQ.any_carry(base, count))
99{
100  S*
101  while(E)
102  {
103    S*
104  }
105}
106else
107{
108  carryQ.enqueue_dequeue(base, count);
109
110
111Pablo 'body'
112
113-->
114
115  body += carryQ.carryAdjust(base, count);
116       
117Missing Features
118
1191. Support for negative constant integers (-1).
120//2. Code indentation.   
121//3. Pablo '1' --> simd::constant<1>(0)
122//4. Add assert compiler.
123//5. Add SIMD register dump.
124//6. carryQ.CarryQ_Adjust
1257. Map substitutions.
126
127PabloJ Design Issues
128 
1291. Front-end / Back-end decoupling. Support for multiple target languages (C/C++).
130
131   TODO
132   
133   Replace all occurrences of X.getCPPCode() with a generic getCode call
134   that is configurable based on the target back-end. e.g. C macro syntax
135   versus C++ template syntax etc.
136 
137   Done.
138   
1392. Logical division of the compiler into phases to promote the decoupling of visitor passes.
140
141   (a) Analysis - Gather information and populate symbol table information.
142   
143   (b) AST modification
144   
145   (c) Target language instruction generation (unparsing).
146
147   Work in progress.
148   
1493. AST Visitor naming conventions.
150
151   Term non-AST modifying visitors XVisitor and AST modifying visitors XXFormers.
152   Done.
153     
154   Done.
155
1564. Verify function call expressions versus function call statements in C++ unparsing.
157   Review the the current scheme.
158         
159   Pending.     
160   
1615. Decision to analyze a list of AST nodes in the semantic analyzer.
162   Perhaps this should be skipped we should simply push processing up to the program node level.
163   This may reduce future code changes.
164   Plan to add a graph type to the compiler to organize the stream program generation.
165
1666. Decision to call AST transformer a 'semantic analyzer'.
167
1687. Add a symbol table and type checking to rid the compiler of the upper case naming
169   convention for stream function and stream structures.
170   
1718. Pass around a configuration object or have setters on the semantic analyzer object.     
172
1739. ApplicationConfigurationFactory generates an ApplicationConfiguration object. Not sure if this oject
174   should be a singleton.
175   
17610. Semantic analyzer. Add Scatter logging.   
177
17811. Clone AST or not. Clone.
179
18011. X2Lang design decision. enum/assert etc...
181
18212. do_block()/do_final_block() code generation implementation.
183
184        i.e. How do we represent/output both do_block and do_final_block function/code?
185
186        We attach nodes to the Pablo AST to produce do_block() versus do_final_block() code.
187
188        Case do_block()
189
190->
191
192        Case do_final_block()
193
194->
195       
196        Implementation options:
197       
198        (a) Parse source file twice to produce two separate AST.
199        (b) Clone complete AST. Apply AST transformation passes to both ASTs.
200        (c) Add both body and final block bodies to a single AST. We accomplish this through
201            the addition/introduce of both PabloS and PabloB grammars and translate
202            from PabloS to PabloB.
203       
204        An additional decision remains as to which point in Pablo AST transformation we clone ASTs.
205
206        Design choice taken (c): Translate from PabloS to PabloB.
207
20813. Carry mode (ci/co) and do_block/do_final_block are independent concepts.
209
210        In the current approach we restrict the carry mode dependent transformation of the AST to
211        the transformation to:
212       
213        Pablo while
214       
215->     
216       
217        Prior carry operations considered carry mode in the selection of carry dependent operations.
218        For example, final block carry producing operations are not 'strictly' required to write
219        carry out values.
220
22114. 3-Addr Form (SSA) AST permits the applications of simplification rules (local optimization)
222        of the AST.     
223
224Additional Notes
225
226Ci|Co
227-----
228F | F
229F | T
230T | F
231T | T
232       
233+ Carry Modes   
234
235Pablo language control structures.     
236
237Neither
238
239Ci (Carry In Only Mode)
240
241- While statements iteration i>1
242
243Co (Carry Out Only Mode)
244
245Ci/Co (Carry In / Carry Out Mode)
246
247- While statements (1st iteration)
248- If statements
249
250+ Potential Block Types
251
252Initial block(ScanToFirst)
253Intermediate block (Non-initial and Non-final block)
254Final block
255Initial/Final block
256
25715. Apply &~ EOF_mask to all pablo builtin operations.
258
259+ Final Block EOF_mask
260
261Builtins
262
263AdvanceThenScanThru(M,S)        --> AdvanceThenScanThru(M, (S &~ EOF_mask))
264AdvanceThenScanTo(M,S)          --> AdvanceThenScanThru(M,~(S &~ EOF_mask))
265
266inFile(E) --> S & EOF_mask  --> assert_0(inFile(E))
267
268i.e. look at only bits within the file extent
269
270i.e. tests only bits within the file the extent and then test none of this set of bits is marked
271
272atEOF(E)  --> S &~ EOF_mask --> assert_0(atEOF(E))
273
274i.e. look at only bits beyond the EOF
275 
276i.e. tests no bit beyond the file extents is marked
277
278Control Structures
279
280while (E) { S }
281
282-->
283
284if(bitblock::any( (E | carry_test(lower,count) &~ EOF_mask ) )
285{
286        S
287       
288        while (bitblock::any(simd_and(E, EOF_mask))
289        {
290                S
291        }
292}
293
294if (E) { S }
295
296-->
297
298if(bitblock::any( (E | carry_test(lower,count) &~ EOF_mask ) )
299{
300        S
301}
302
30316. PabloB grammar design issue (together with Carry InfoSet design)
304
305How do we add stream function level declaration / initialization code to the output?
306
307Options:
308
309(a) Add explicit carry info set information to the PabloB function definition representation.
310
311    No, this would burden the programmer at the PabloB level.
312    The idea is the we remove carry counting ... from the developer
313    but still we need carry count / advn carry count information
314    for code output.
315   
316(b) Hold carry info set information in a symbol table external
317        to both PabloB. Query this data structure during code generation.
318   
319(a) and (b) are similar in that both options remove explicit carry counting from the programmer.
320
321We currently translate PabloS to PabloB and PabloS code is used to populate the information
322contained in the symbol table used by PabloB.
323
324We could populate similar symbol table information based on PabloB code alone.
325
326More investigation is required here.
327
32817. Limitations of a macro driven carry handling approach.
329
330Fill in this section ...
331
33218. PabloB needs both bitwise OR as well as boolean OR.
333
33419. Translate to Dotty for AST diagrams.
335   
336
Note: See TracBrowser for help on using the repository browser.