Global Value Propagation Through Value Flow Graph and Its Use in Dependence Analysis

Abstract

As recent studies show, state-of-the-art parallelizing compilers produce no noticeable speedup for 9 out of 12 PERFECT benchmark codes, while the speedup that was reached by manually applying certain automatable techniques ranges from 10 to 50. In this paper we introduce the {\em Global Value Propagation} algorithm that unifies several of these techniques. Global propagation is performed using program abstraction called Value Flow Graph (VFG). VFG is an acyclic graph in which vertices and arcs are parametrically specified using F-relations. The distinctive features of our propagation algorithm are: (1) It propagates not only values carried by scalar variables, but also values carried by individual array elements. (2) We do not have to transform a program in order to use propagation results in program analysis. In this paper we focus on use of the VFG and global value propagation in array dataflow analysis. F-relations are used to represent values produced by uninterpreted function symbols that appear in dependence problems for non-affine program fragments. Global value propagation helps us to discover that some of these functions are in fact affine. (Also cross-referenced as UMIACS-TR-94-80)