JUCS - Journal of Universal Computer Science 12(8): 1007-1019, doi: 10.3217/jucs-012-08-1007
Eliminating Redundant Join-Set Computations in Static Single Assignment
expand article infoAngela French‡, Jose N. Amaral§
‡ University of Alberta, Canada§ Computing Science Dept., University of Alberta, Edmonton, Canada

Corresponding author: Angela French ( french@cs.ualberta.ca )

© Angela French, Jose Amaral.
This article is freely available under the J.UCS Open Content License.
Citation: French A, Amaral JN (2006) Eliminating Redundant Join-Set Computations in Static Single Assignment. JUCS - Journal of Universal Computer Science 12(8): 1007-1019. https://doi.org/10.3217/jucs-012-08-1007
Open Access
Abstract
The seminal algorithm developed by Ron Cytron, Jeanne Ferrante and colleagues in 1989 for the placement of φ-nodes in a control flow graph is still widely used in commercial compilers. Placing φ-nodes is necessary when converting a program representation to Static Single Assignment (SSA) form. This paper shows that if a variable x is defined in a set of basic blocks A(x), then the iterated join set of A(x) can be decomposed into the computation of the iterated join set of a disjoint collection of subsets of A(x). We use this result to show that some join set computations are redundant. We measured the number of redundant computations in the Open Research Compiler (ORC) in a selection of SPEC 2000 benchmarks.
Keywords
compiler optimization, SSA