Re: aycock's algorithm for ssa

From comp.compilers

Related articles
aycock's algorithm for ssa n.oje.bar@gmail.com (nojb) (2011-03-15)
| List of all articles for this month |

 From: Nikolaos Kavvadias Newsgroups: comp.compilers Date: Thu, 17 Mar 2011 05:51:06 -0700 (PDT) Organization: Compilers Central References: 11-03-042 Keywords: analysis Posted-Date: 18 Mar 2011 23:39:35 EDT

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:

Also, check out this 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