Detection of redundant expressions: A precise, efficient, and pragmatic algorithm in SSA

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.