Technical Report (TR04-01) Cover Page

Title:

Partial Value Number Redundancy Elimination

Authors:

Rei Odaira and Kei Hiraki

Key words and phrases:

partial redundancy elimination, global value numbering, optimizing compiler, just-in-time compiler, runtime compiler, Java virtual machine

Abstract:

When developing a redundancy elimination algorithm for a runtime optimizing compiler, not only its optimizing power but also its analysis speed must be considered.
We propose a fast and efficient algorithm called Partial Value Number Redundancy Elimination (PVNRE), which completely fuses Partial Redundancy Elimination (PRE) and Global Value Numbering (GVN). Using value numbers in the data-flow analyses, PVNRE can deal with data-dependent redundancy, and can quickly remove path-dependent partial redundancy by converting value numbers at join nodes on demand during the data-flow analyses.
Compared with the naive combination of GVN, PRE, and copy propagation, PVNRE has a maximum 45% faster analyses speed, but the same optimizing power on SPECjvm98.

Report date:

June 9, 2004

Written language:

English

Total number of pages:

22

Number of references:

19

Any other identifying information of this report:

Distribution statement:

Supplementary notes: