Eliminating Redundant Join-Set Computations in Static Single Assignment
Дата
Авторы
French,Angela
Amaral,Jose
Journal Title
Journal ISSN
Volume Title
Издатель
Journal of Universal Computer Science
Аннотация
Описание
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.
Ключевые слова
compiler optimization , SSA