Array dataflow analysis is a valuable tool for supercomputer
compilers. However, the worst-case time complexities for array
dataflow analysis techniques are either not well understood or
alarmingly high. For example, the constraint-based analysis used in
the Omega Test uses a subset of the 2^2^2^O(n) language of Presburger
Arithmetic for analysis of affine dependences, and its use of
uninterpreted function symbols for non-affine terms introduces
additional sources of complexity. Even traditional data dependence
analysis in this affine domain is equivalent to integer programming,
and is thus NP-complete. These worst-case complexities have raised
questions about the wisdom of using array dataflow analysis in a
production compiler, despite empirical data that show that various
tests runs quickly in practice.
In this paper, we demonstrate that a polynomial-time algorithm can
produce accurate information about the presence of loop-carried array
dataflow. We first identify a subdomain of Presburger Arithmetic that
can be manipulated (by the Omega Library) in polynomial time; we then
describe a modification to prevent exponential blowup of the Omega
Library's algorithm for manipulating function symbols. Restricting
the Omega Test to these polynomial cases can, in principle, reduce the
accuracy of the dataflow information produced by the Omega Test. We
therefore present an investigation of the effects of our restrictions
on the analysis of loop-carried array dataflow dependences in
benchmark codes. The restriction to polynomial-time algorithms blocks
parallelization of only three unimportant loops in the approximately
18000 lines of benchmark code we studied.
DIMACS Home Page