Pushpa Publishing House

Journal Menu

Content

Volume 17 (2018)

Volume 16 (2016)

Volume 15 (2015)

Volume 14 (2015)

Volume 13 (2014)

Volume 12 (2014)

Volume 11 (2013)

Volume 10 (2013)

Volume 9 (2012)

Volume 8 (2012)

Volume 7 (2011)

	Volume 7, Issue 2 Pg 99 - 168 (November 2011)
	Volume 7, Issue 1 Pg 1 - 97 (August 2011)

Volume 6 (2011)

Volume 5 (2010)

Volume 4 (2010)

Volume 3 (2009)

Volume 2 (2008)

Volume 1 (2007)

Advances in Computer Science and Engineering

Advances in Computer Science and Engineering
Volume 7, Issue 1, Pages 1 - 24 (August 2011)

A GENERALIZED METHOD FOR REALIZING PARTIAL REDUNDANCY ELIMINATION FOR NORMAL FORMS IN STATIC SINGLE ASSIGNMENT FORMS
Masataka Sassa, Takanori Imahashi and Yo Ito

Abstract:
Partial Redundancy Elimination (PRE) is an effective optimization for eliminating partially redundant expressions and includes the effects of common subexpression elimination and hoisting loop invariant expressions. There have been some previous attempts to realize PRE on the Static Single Assignment (SSA) form, which is a suitable intermediate form for optimization. However, such attempts are generally difficult because of the uniqueness of variable names in the SSA form. For example, a variable that is used in several contexts in the normal form may be assigned a new name for each context in the SSA form, so it is difficult to identify the same variables in the two forms. To handle such problems, previous methods performed complicated processing by using special data structures.

To deal with this problem, we pay attention to the so-called Conventional SSA (CSSA) form and phi congruence class (pcc). Using these concepts, we can identify the same variables in the normal form and the SSA form. We therefore propose a method for transforming PRE algorithms for the normal form to those for the SSA form. This transformation is a universal one, so, in principle, it can transform any PRE algorithm that has ordinary processes (selecting insertion points and inserting expressions, and replacing expressions) to the SSA form, without changing the framework of the original PRE algorithm, independently of the algorithm. Finally, as an experiment, we apply this method to Lazy Code Motion (LCM), which is a representative PRE algorithm. We confirmed that the transformed LCM in the SSA form performs PRE correctly and produces object code with the same efficiency as PRE in normal form.

Keywords and phrases: compiler optimization, static single assignment form, partial redundancy elimination.

Number of Downloads: 286 | Number of Views: 665