DEPENDENCE ANALYSIS FOR SUBSCRIPTED VARIABLES AND ITS APPLICATION TO PROGRAM TRANSFORMATIONS

Abstract

The order in which the statements of a program are executed can affect the execution time of the program. Optimizing compilers have made use of this fact by reordering code to improve its performance on a machine. Some statement orderings are essential to a program's results, however; these orderings form the basis of a dependence relation among the statements of a program. Dependences can arise in two separate ways within a program: from data considerations, and from control considerations. However, since all control dependences can be converted to data dependences by guarding statements with precise conditions that control their execution, data dependence is the more general concept. Data dependences within loops can arise from two separate effects. The position of statements within the loops may cause a dependence, or iteration of a specific loop may cause a dependence. Characterizing dependence in this manner provides the foundation of extremely effective algorithms for reordering transformations. One very important reordering transformation which is made possible by dependence is vectorization. Vectorization of a program can often be enchanced by loop interchange. Dependence plays an important role in determining when loops should be interchanged. Interchange preventing dependences inhibit a particular interchange; interchange sensitive dependences may make an interchange less profitable in terms of increased vectorization. Dependence for symbolic subscripts is an extremely difficult problem. Nevertheless, some cases can be handled by techniques based on standard dependence tests. One last reordering transformation which is of extreme importance on vector machines is sectioning, or devectorization. Dependence not only determines when a statement can be correctly sectioned but it also can be used to improve the register performance of a sectioned statement.