Premium
Structured dataflow analysis for arrays and its use in an optimizing compiler
Author(s) -
Gross Thomas,
Steenkiste Peter
Publication year - 1990
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.4380200203
Subject(s) - compiler , dataflow , computer science , parallel computing , optimizing compiler , data flow analysis , control flow graph , interprocedural optimization , compiler correctness , code generation , compiler construction , dead code elimination , programming language , register allocation , generator (circuit theory) , loop optimization , control flow , data flow diagram , operating system , object code , power (physics) , physics , quantum mechanics , database , key (lock)
We extend the well‐known interval analysis method so that it can be used to gather global flow information for individual array elements. Data dependences between all array accesses in different basic blocks, different iterations of the same loop, and across different loops are computed and represented as labelled arcs in a program flow graph. This approach results in a uniform treatment of scalars and arrays in the compiler and builds a systematic basis from which the compiler can perform numerous global optimizations. This global dataflow analysis is performed as a separate phase in the compiler. This phase only gathers the global relationships between different accesses to a variable, yet the use of this information is left to the code generator. This organization substantially simplifies the engineering of an optimizing compiler and separates the back end of the compiler (e.g. code generator and register allocator) from the flow analysis part. The global dataflow analysis algorithm described in this paper has been implemented and used in an optimizing compiler for a processor with deep pipelines. This paper describes the algorithm and its compact implementation and evaluates it, both with respect to the accuracy of the information and to the compile‐time cost of obtaining and using it.