Nonlinear Array Dependence Analysis
Nonlinear Array Dependence Analysis
Files
Publication or External Link
Date
1998-10-15
Authors
Pugh, William
Wonnacott, David
Advisor
Citation
DRUM DOI
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)