Hello,

I'm trying to understand Aycock's algorithm for computing SSA form
("Simple Generation of Static Single Assignment Form"). Googling
hasn't turned up anything useful.

He proceeds in two steps, first he adds every possible phi-function
(i.e. one for every function in the control flow graph, in every basic
block) and then he eliminates many of these by iterating two steps:

1. remove phi-functions of the form v_i = phi(v_i,...,v_i) (his
notation)
2. remove phi-functions of the form v_i = phi(v_i,...,v_i, v_j) and
replace allt he ocurrences
of v_i with v_j. (idem for all the permutations of the operands of
phi).

My first problem is with step 1. I don't understand what he means by
v_i = phi(v_i, ...,v_i). Does he mean that all the phi operands are
the same? Then that would be a strange notation indeed...

Same question for 2.

Thanks!
N

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