Title :
Loop induction variable canonicalization in parallelizing compilers
Author :
Liu, Shin-Ming ; Lo, Raymond ; Chow, Fred
Author_Institution :
Silicon Graphics Comput. Syst., Mountain View, CA, USA
Abstract :
Loop induction variable canonicalization transforms a loop to use a single primary induction variable that is incremented by one at the end of each iteration. In this process, other induction variables in the loop, called secondary induction variables, are removed from the loop, with their original references expressed in terms of the primary induction variable, and their loop exit values assigned to them after the loop exit. This paper presents a simple and powerful approach to loop induction variable canonicalization in which the problem is broken up into a sequence of steps. The whole canonicalization process is integrated into a global optimizer that builds an SSA representation of the program, performs global optimizations and hands the optimized code on to other components in the compiler that perform loop and instruction level parallelization. By taking advantage of optimizations that will be performed later each step in the canonicalization process can be made small and efficient. By letting generic parts of the optimizer share in the work, the approach infuses generality into the solution and provides automatic coverage of a wide variety of forms of induction variable occurrences. A number of examples are given to show the effectiveness of the approach. We also provide a set of measurements that shows that the additional compile-time cost incurred due to implementing our approach is small
Keywords :
parallel programming; parallelising compilers; compile-time cost; copy propagation; dead store elimination; global optimizer; induction variable expansion; induction variable recognition; induction variable substitution; instruction level parallelization; loop induction; loop induction variable canonicalization; loop normalization; parallelizing compilers; static single assignment form; symbolic interpretation; variable canonicalization; Computer graphics; Costs; Optimizing compilers; Performance analysis; Performance evaluation; Pipeline processing; Program processors; Silicon; Testing;
Conference_Titel :
Parallel Architectures and Compilation Techniques, 1996., Proceedings of the 1996 Conference on
Conference_Location :
Boston, MA
Print_ISBN :
0-8186-7633-7
DOI :
10.1109/PACT.1996.554033