Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 12 / Issue 8

available in:   PDF (135 kB) PS (133 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-012-08-1007


Eliminating Redundant Join-Set Computations in Static Single Assignment

Angela French (University of Alberta, Canada)

José Nelson Amaral (University of Alberta, Canada)

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: SSA, compiler optimization

Categories: D.1.3, D.3.4, I.1.2