Nonlinear Array Dependence Analysis
Abstract
Standard array data dependence techniques can only reason about linear
constraints. There has also been work on analyzing some dependences
involving polynomial constraints. Analyzing array data dependences in
real-world programs requires handling many ``unanalyzable'' terms:
subscript arrays, run-time tests, function calls.
The standard approach to analyzing such programs has been to omit and
ignore any constraints that cannot be reasoned about. This is unsound
when reasoning about value-based dependences and whether privatization
is legal. Also, this prevents us from determining the conditions that
must be true to disprove the dependence. These conditions could be
checked by a run-time test or verified by a programmer or aggressive,
demand-driven interprocedural analysis.
We describe a solution to these problems. Our solution makes our
system sound and more accurate for analyzing value-based dependences
and derives conditions that can be used to disprove dependences. We
also give some preliminary results from applying our techniques to
programs from the Perfect benchmark suite.
(Also cross-referenced as UMIACS-TR-94-123)