Detection of redundant expressions: A precise, efficient, and pragmatic algorithm in SSA. (November 2016)

• Record Type: Journal Article
• Authors: Pai, Rekha R.
• Is Part Of: Computer languages, systems & structures. Volume 46(2016)
• Page Start: 167
• Page End: 181
• Publication Date: 2016-11
• Subjects: Global Value Numbering -- Redundancy detection -- Equivalence detection -- Value ϕ-function; Programming languages (Electronic computers) -- Periodicals; Computer networks -- Periodicals; Computer architecture -- Periodicals; Computer systems -- Periodicals; Langage de programmation; Réseau d'ordinateurs; Architecture d'ordinateur; Périodique électronique (Descripteur de forme); Ressource Internet (Descripteur de forme); 005.13
• DOI: 10.1016/j.cl.2016.07.006
• Languages: English
• ISSNs: 1477-8424

Abstract

Abstract: Detection of redundant expressions in a program based on values is a well researched problem done with a view to eliminate redundancies so as to improve run-time efficiency of the program. The problem entails detection of equivalent expressions in a program. An iterative data-flow analysis algorithm is presented to detect equivalent expressions in SSA for the purpose of detection of redundancies. The challenge is detection of equivalence of expressions at join points, in polynomial time, that enable detection of later redundancies. This is achieved by the use of value ϕ-function . The proposed algorithm is as precise as Kildall׳s in detection of redundant expressions and takes only polynomial time. The algorithm is implemented in LLVM. An experimental analysis demonstrates that the algorithm is as precise as Kildall׳s and outperforms some existing algorithms in terms of run-time efficiency indicating its practical significance. Highlights: A precise and polynomial-time algorithm to detect equivalences in SSA programs. The algorithm uses value φ-function, an abstraction of set of equivalent φ-functions. Experimental comparison with popular algorithms shows our's is precise as Kildall's. An experimental comparison shows the algorithm is efficient in practice.