Eliminating False Data Dependences using the Omega Test
Eliminating False Data Dependences using the Omega Test
Loading...
Files
Publication or External Link
Date
1998-10-15
Authors
Pugh, William
Wonnacott, David
Advisor
Citation
DRUM DOI
Abstract
Array data dependence analysis methods currently in use generate
false dependences that can prevent useful program transformations.
These false dependences arise because the questions asked are
conservative approximations to the questions we really should be
asking. Unfortunately, the questions we really should be asking
go beyond integer programming and require decision procedures for
a subclass of Presburger formulas. In this paper, we describe how
to extend the Omega test so that it can answer these queries and
allow us to eliminate these false data dependences. We have
implemented the techniques described here and believe they are
suitable for use in production compilers.
(An earlier version of this paper appeared at the
ACM SIGPLAN PLDI'92 conference).
(Also cross-referenced as UMIACS-TR-93-132)