Re: aycock's algorithm for ssa

Hi N


it happens that i have taught the Aycock-Horspool SSA construction
algorithm during this last three years at a Greek university. It is a
minimal SSA construction algorithm, using similar but not identical
variable numbering and phi insertion stages to a variation based on
Appel's really-crude approach. I have some indicative results that
Appel's method has lower program complexity.


I have implemented both algorithms in C for a typed-assembly language
of mine called NAC (N-Address Code). Right now, i can direct you to my
description of Aycock-Horspool here:
http://www.nkavvadias.co.cc/compilers2-course.html


Also, check out this PDF:
http://www.nkavvadias.co.cc/courses/compilers2/compilers2_lecture_02.pdf


See the running example through slides 25--34 of this presentation.


NAC EBNF is as follows:


anum = (letter | "_") {letter | digit}.
integer = digit {digit}.
fxpnum = [integer] "." integer.
numeric = (integer | fxpnum).
id = anum | ["-"] numeric.
nac_top = globalvar_list procedure_list.
globalvar_list = {globalvar_def}.
procedure_list = {procedure_def}.
globalvar_def = "globalvar" anum decl_item_list ";".
procedure_def = "procedure" [anum] "(" [arg_list] ")"
"{" [localvar_list] [stmt_list] "}".
stmt_list = {stmt}.
stmt = nac | pcall | id ":".
nac = [id_list "<="] anum [id_list] ";".
pcall = ["(" id_list ")" "<="] anum ["(" id_list ")"] ";".
id_list = id {"," id}.
anum_list = anum {"," anum}.
decl_item_list = decl_item {"," decl_item}.
decl_item = (anum | uninitializedarray | initializedarray).
arg_list = arg_decl {"," arg_decl}.
arg_decl = ("in" | "out") anum (anum | uninitializedarray).
localvar_list = {localvar_decl}.
localvar_decl = "localvar" anum decl_item_list ";".
initializedarray = anum "[" id "]" "=" "{" numeric {"," numeric} "}".
uninitializedarray = anum "[" [id] "]".




This is a quick description of NAC, i use it as my intermediate
representation for my new compilation projects.


NAC (N-Address Code) is the name of a typed assembly language suitable
for use as an executable/interpretable intermediate representation for
compilation frameworks. NAC provides arbitrary m-to-n mappings, a
single construct for all operations, and bit-accurate data types. It
supports scalar, single-dimensional array and streamed I/O procedure
arguments. NAC statements are labels, n-address instructions or
procedure calls.
All declared objects (global variables, local variables, input and
output procedure arguments) have a type specification. NAC uses the
notions of globalvar (a global scalar or single-dimensional array
variable), localvar (a local scalar or single-dimensional array
variable), in (an input argument to the given procedure), and
out (an output argument to the given procedure).


Hope this helps
Nikolaos Kavvadias

Return to the comp.compilers page.
Search the comp.compilers archives again.