Flow-sensitive loop-variant variable classification in linear time

Abstract. This paper presents an efficient algorithm for classifying gen-eralized induction variables and more complicated flow-sensitive loop-variant variables that have arbitrary conditional update patterns along multiple paths in a loop nest. Variables are recognized and translated into closed-form functions, such as linear, polynomial, geometric, wrap-around, periodic, and mixer functions. The remaining flow-sensitive vari-ables (those that have no closed forms) are bounded by tight bounding functions on their value sequences by bounds derived from our exten-sions of the Chains of Recurrences (CR#) algebra. The classification algorithm has a linear worst-case execution time in the size of the SSA region of a loop nest. Classification coverage and performance results for the SPEC2000 benchmarks are given and compared to other methods. 1 Introduction and Related Work Induction variables (IVs) [1, 9, 11–13, 23] are an important class of loop-variant variables whose value progressions form linear, polynomial, or geometric se