Global Value Propagation Through Value Flow Graph and Its Use in
Dependence Analysis
Global Value Propagation Through Value Flow Graph and Its Use in
Dependence Analysis
Files
Publication or External Link
Date
1998-10-15
Authors
Maslov, Vadim
Advisor
Citation
DRUM DOI
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)