BEYOND INDUCTION VARIABLES - DETECTING AND CLASSIFYING SEQUENCES USING A DEMAND-DRIVEN SSA FORM

Linear induction variable detection is usually associated with the str ength reduction optimization. For restructuring compilers, effective d ata dependence analysis requires that the compiler detect and accurate ly describe linear and nonlinear induction variables as well as more g eneral sequences. In this article we present a practical technique for detecting a broader class of linear induction variables than is usual ly recognized, as well as several other sequence forms, including peri odic, polynomial, geometric, monotonic, and wraparound variables. Our method is based on Factored Use-Def (FUD) chains, a demand-driven repr esentation of the popular Static Single Assignment (SSA) form. In this form, strongly connected components of the associated SSA graph corre spond to sequences in the source program: we describe a simple yet eff icient algorithm for detecting and classifying these sequences. We hav e implemented this algorithm in Nascent, our restructuring Fortran 90 compiler, and we present some results showing the effectiveness of ou r approach.