next up previous contents
Next: Construct Interactions Up: Implementation Previous: Compiler Selection

Parsing Constructs

SUIF's C front end is based on the lcc front-end, heavily modified to produce SUIF output. The first pass, snoot, performs initial parsing and lexing and outputs a SUIF file with possibly non-conformant data structures. A second pass, porky, eliminates such artifacts, rendering the output of snoot into standard SUIF.

Modifying snoot to accept the new keywords and constructs was fairly straight-forward, since the syntax for these constructs had been deliberately chosen to resemble existing C syntax forms. Specifically:

(At the current time, qvar variable definitions are not implemented. Instead, upon first use of a quasistatic variable in a qif statement, the symbol name is looked up and if it is not found, is then entered into the symbol table as a constant integer annotatedgif as a quasistatic variable. This should be easily fixable.)
qif and qelse
statements are parsed as if the tokens encountered were really if and else respectively. Annotations are used to flag the resulting intermediate format nodes as quasistatic constructs.
parameters are entered as constant integers into the global symbol table (as a declaration) and the file symbol table (as a definition); annotations are used to flag the global declarations as quasistatic parameters, and to store the range of possible values.
statements are parsed as if they were simply a scope-introducing block, and a dummy variable is inserted into the symbol table of the new scope to ensure that the new scope will not be prematurely optimized away. An annotation is used to flag the block as having originated from a qinfluence construct.

Figures gif and gif illustrate what the modified snoot transforms quasistatic constructs into --- for brevity of presentation, I have approximated the SUIF-format annotations in the s2c output by using C-style comments. By making both quasistatic variables and quasistatic parameters explicitly const, the programmer cannot accidentally mutate their values. Although it would be desirable to prevent the programmer from referencing a quasistatic variable as an integer value, I saw no easy way to prevent such mis-usage. Note also how a qif-qelse chain is parsed into nested if statements in Figure gif. This would be a matter of concern for run-time efficiency except that gcc with the -O option is known to do constant-propagation and dead-code-elimination, and does disambiguating such nested if statements to a single clause, leaving no residual run-time selection overhead.

Figure: Modified snoot pass example input.

Figure: Quasistatic constructs rendered into SUIF by modified snoot.

next up previous contents
Next: Construct Interactions Up: Implementation Previous: Compiler Selection

Reinventing Computing, MIT AI Lab. Author: (Ping Huang)