Induction variable analysis without idiom recognition: Beyond monotonicity

Peng Wu, Albert Cohen, David Padua

Research output: Contribution to journalArticle


Traditional induction variable (IV) analyses focus on computing the closed form expressions of variables. This paper presents a new IV analysis based on a property called distance interval. This property captures the value changes of a variable along a given control-flow path of a program. Based on distance intervals, an efficient algorithm detects dependences for array accesses that involve induction variables. This paper describes how to compute distance intervals and how to compute closed form expressions and test dependences based on distance intervals. This work is an extension of the previous induction variable analyses based on monotonic evolution [11]. With the same computational complexity, the new algorithm improves the monotonic evolution-based analysis in two aspects: more accurate dependence testing and the ability to compute closed form expressions. The experimental results demonstrate that when dealing with induction variables, dependence tests based on distance intervals are both efficient and effective compared to closed-form based dependence tests.

Original languageEnglish (US)
Pages (from-to)427-441
Number of pages15
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
StatePublished - Dec 1 2003

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Induction variable analysis without idiom recognition: Beyond monotonicity'. Together they form a unique fingerprint.

  • Cite this