Loop Tree and Induction Variables

Induction variables refer to a wide class of inductive definitions, where the sequence of values taken by a variable follows a regular pattern. The typical case is that of a loop counter. More generally, induction variables are associated with affine, geometric, or otherwise statically predictable progressions in loops. The purpose of the induction variable analysis is to provide a characterization of such sequences. There are numerous applications, from the detection of parallel loops to optimizations such as loop-invariant code motion, strength reduction, eliminating dependencies, and evaluating the number of iterations of a while loop. This chapter focuses particularly on the analysis and classification of induction variables in the presence of complex, low-level control flow (gotos, multiple loop exits, etc.). It describes the algorithm underlying the analysis of “scalar evolutions” in the GCC and LLVM compilers.

1. 1.

   To simplify the discussion, we consider the original program to be free of side effect instructions.

2. 2.

   Note, however, that the computation of closed-form expressions is not required for dependence testing itself [309].

Authors and Affiliations

1. Amazon Web Services, Austin, Texas, USA

   Sebastian Pop

2. Google, Paris, France

   Albert Cohen

Corresponding author

Correspondence to Albert Cohen .

Editors and Affiliations

1. Inria, Grenoble, France

   Fabrice Rastello

2. University of Grenoble Alpes, Grenoble, France

   Florent Bouchez Tichadou

Reprints and permissions

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

Policies and ethics