An Improved Algorithm for Redundancy Detection Using Global Value Numbering

Nabizath Saleena and Vineeth Paleri
Volume: 12, No: 2, Page: 214 ~ 225, Year: 2016
10.3745/JIPS.02.0014
Keywords: Equivalent Expression, Global Value Numbering, Herbrand Equivalence, Strong Equivalence Dag
Full Text:

Abstract
Global value numbering (GVN) is a method for detecting equivalent expressions in programs. Most of the GVN algorithms concentrate on detecting equalities among variables and hence, are limited in their ability to identify value-based redundancies. In this paper, we suggest improvements by which the efficient GVN algo- rithm by Gulwani and Necula (2007) can be made to detect expression equivalences that are required for identifying value based redundancies. The basic idea for doing so is to use an anticipability-based Join algo- rithm to compute more precise equivalence information at join points. We provide a proof of correctness of the improved algorithm and show that its running time is a polynomial in the number of expressions in the program

Article Statistics
Multiple requests among the same broswer session are counted as one view (or download).
If you mouse over a chart, a box will show the data point's value.


Cite this article
IEEE Style
Nabizath Saleena and Vineeth Paleri, "An Improved Algorithm for Redundancy Detection Using Global Value Numbering," Journal of Information Processing Systems, vol. 12, no. 2, pp. 214~225, 2016. DOI: 10.3745/JIPS.02.0014.

ACM Style
Nabizath Saleena and Vineeth Paleri, "An Improved Algorithm for Redundancy Detection Using Global Value Numbering," Journal of Information Processing Systems, 12, 2, (2016), 214~225. DOI: 10.3745/JIPS.02.0014.