An Efficient SSABased Algorithm for Complete Glob

Authors: JiuTao Nie Xu Cheng

Publish Date: 2007/11/29

Volume: , Issue: , Pages: 319-334

PDF Link

Abstract

Global value numbering GVN is an important static analysis technique both for optimizing compilers and program verification tools Existing complete GVN algorithms discovering all Herbrand equivalences are all inefficient One reason of this is the intrinsic exponential complexity of the problem but in practice since the exponential case is quite rare the more important reason is the huge data structures annotated to every program point and slow abstract evaluations on them site by site In this paper we present an SSAbased algorithm for complete GVN which uses just one global graph to represent all equivalences at different program points and performs fast abstract evaluations on it This can be achieved because in SSA form interferences among equivalence relations at different program points can be entirely resolved with dominance information We implement the new algorithm in GCC The average proportion of execution time of the new algorithm in the total compilation time is only 036 To the best of our knowledge this is the first practical complete GVN algorithm

Keywords: