Search Word(s) in Title, Keywords, Authors, and Abstract: Equivalent Expression

An Improved Algorithm for Redundancy Detection Using Global Value Numbering
Nabizath Saleena and Vineeth Paleri
Page: 214~225, Vol. 12, No.2, 2016
10.3745/JIPS.02.0014

Keywords: Equivalent Expression, Global Value Numbering, Herbrand Equivalence, Strong Equivalence Dag
Show / Hide 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