JCSE, vol. 2, no. 3, pp.301-320, 2008

DOI:

A Practical Improvement to the Partial Redundancy Elimination in SSA Form

Jongsoo Park Jaejin Lee
Department of Electrical Engineering, Stanford University, Stanford, CA|School of Computer Science and Engineering, Seoul National University, Seoul, Korea

Abstract: Partial redundancy elimination (PRE) is an interesting compiler optimization because of itseffectiveness and generality. Among many PRE algorithms, the one in static single assignmentform (SSAPRE) has benefits over other bit-vector-based PRE algorithms. It preserves theproperties of the SSA form after PRE and exploits the sparsity of the SSA form, resulting inreduced analysis and optimization time. This paper presents a practical improvement of theSSAPRE algorithm that further reduces the analysis and optimization time. The underlyingidea is removing unnecessary Φ’s during the Φ-Insertion phase that is the first step of SSAPRE.We classify the expressions into three categories: confined expressions, local expressions, andthe others. We show that unnecessary Φ’s for confined and local expressions can be easilydetected and removed. We implement our locality-based SSAPRE algorithm in a C compilerand evaluate its effectiveness with 20 applications from SPEC benchmark suites. In ourmeasurements, on avera

Keyword: No keyword

Full Paper:   381 Downloads, 3792 View