An Improved Algorithm for Redundancy Detection Using Global Value Numbering


Nabizath Saleena, Vineeth Paleri, Journal of Information Processing Systems Vol. 12, No. 2, pp. 214-225, Jun. 2016  

https://doi.org/10.3745/JIPS.02.0014
Keywords: Equivalent Expression, Global Value Numbering, Herbrand Equivalence, Strong Equivalence Dag
Fulltext:

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


Statistics
Show / Hide Statistics

Statistics (Past 3 Years)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.




Cite this article
[APA Style]
Saleena, N. & Paleri, V. (2016). An Improved Algorithm for Redundancy Detection Using Global Value Numbering. Journal of Information Processing Systems, 12(2), 214-225. DOI: 10.3745/JIPS.02.0014.

[IEEE Style]
N. Saleena and V. 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. 2016. 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.