A practical data flow framework for array reference analysis and its use in optimizations
Evelyn Duesterwald, Rajiv Gupta, Mary Lou Soffa · Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation · 1993
Data flow analysis techniques have traditionally been restricted to the analysis of scalar variables. This retriction, however, imposes a limitation on the kinds of optimizations that can be performed in loops containing array references. We present a data flow framework for array reference analysis that provides the information needed in various optimizations targeted at sequential or fine-grained parallel architectures. The framework extends the traditional scalar framework by incorporating iteration distance values into the analysis to qualify the computed data flow solution during the fixed point iteration. Analyses phrased in this framework are capable of discovering recurrent access patterns among array references that evolve during the execution of a loop. Applications of our framework are discussed for register allocation, load/store optimizations, and controlled loop unrolling.
Cited by 71 works. doi:10.1145/155090.155097 Open-access PDF
Authors
References
- Compilers: Principles, Techniques, and Tools
- Abstract interpretation
- Register allocation & spilling via graph coloring
- Dependence graphs and compiler optimizations
- Optimizing supercompilers for supercomputers
- Register allocation & spilling via graph coloring
- Monotone data flow analysis frameworks
- Unrolling loops in fortran
- Improving register allocation for subscripted variables
- Dataflow analysis of array and scalar references