Induction Variable Analysis Without Idiom Recognition: Beyond Monotonicity

International audienceTraditional induction variable (IV) analyses focus on computing the closed form expressions of variables. This paper presents anew IV analysis based on a property called distance interval. This property captures the value changes of a variable along a given control-flowpath of a program. Based on distance intervals, an efficient algorithmdetects 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. With the same computationalcomplexity, the new algorithm improves the monotonic evolution-basedanalysis in two aspects: more accurate dependence testing and the abilityto compute closed form expressions.The experimental results demonstrate that when dealing with induction variables, dependence tests based on distance intervals are bothefficient and effective compared to closed-form based dependence tests