Monotonic evolution: An alternative to induction variable substitution for dependence analysis

P. Wu, A. Cohen, J. Hoeflinger, David A Padua

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We present a new approach to dependence testing in the presence of induction variables. Instead of looking for closed form expressions, our method computes monotonic evolution which captures the direction in which the value of a variable changes. This information is then used in the dependence test to help determine whether array references are dependence-free. Under this scheme, closed form computation and induction variable substitution can be delayed until after the dependence test and be performed on-demand. To improve computative efficiency, we also propose an optimized (non-iterative) data-flow algorithm to compute evolution. Experimental results show that dependence tests based on evolution information matches the accuracy of that based on closed-form computation (implemented in Polaris), and when no closed form expressions can be calculated, our method is more accurate than that of Polaris.

Original languageEnglish (US)
Title of host publicationProceedings of the International Conference on Supercomputing
Number of pages14
StatePublished - 2001
Event2001 International Conference on Supercomputing - Sorento, Italy
Duration: Jun 17 2001Jun 21 2001


Other2001 International Conference on Supercomputing

ASJC Scopus subject areas

  • Computer Science(all)


Dive into the research topics of 'Monotonic evolution: An alternative to induction variable substitution for dependence analysis'. Together they form a unique fingerprint.

Cite this