Abstract
Many compiler techniques require analysis of array subscripts to determine whether a transformation is legal. Traditional methods require the array subscript expressions to be expressed as closed-form expressions of loop indices. Most methods further require the subscript expressions to be linear. However, in sparse/ irregular programs, closed-form expressions of array subscripts are not available. More powerful methods to analyze array subscripts are needed. Array accesses with no closed-form expressions available are called irregular array accesses. In real programs, many irregular array accesses are single-indexed. In this paper, we present techniques to analyze irregular single-indexed array accesses. We show that single-indexed array accesses often have properties that are useful in compiler analysis. We discuss how to use these properties to enhance compiler optimizations. We also demonstrate the application of these techniques in three real-life programs to exploit more implicit parallelism.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley Publishing Company, 1986. 204, 210
John R. Allen and Ken Kennedy. Automatic loop interchange. In Proceedings of the SIGPLAN’ 84 Symposium on Compiler Construction, pages 233–246, New York, NY 10036, USA, 1984. ACM Press, ACM Press. 212
J. Barnes and P. Hut. A hierarchical o(nlogn) force calculation algorithm. Nature, 324(4):446–449, 1986. 215
Joshua E. Barnes. ftp://hubble.ifa.hawaii.edu/pub/barnes/treecode/. Technical report. 215
W. Blume and R. Eigenmann. An overview of symbolic analysis techniques needed for the effective parallelization of the perfect benchmarks. In K. C. Tai, editor, Proceedings of the 23rd International Conference on Parallel Processing. Volume 2: Software, pages 233–238, Boca Raton, FL, USA, August 1994. CRC Press. 209
Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark K. Wegman, and F. Kenneth Zadeck. An efficient method of computing static single assignment form. In Proceedings of 16th Annual ACM Symposium on Principles of Programming Languages, pages 25–35, 1989. 213
Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Efficiently computing static single assignment form and the control dependence graph. ACM Transaction on Programming Languages and Systems, 13(4):451–490, October 1991. 213
Mike Berry et.al. The perfect club benchmarks: Effective performance evaluation of supecomputers. International Journal of Supercomputer Applications, 3(3):5–40, Fall 1989. 214
P. Feautrier. Array expansion. In Proceedings of the Second International Conference on Supercomputing, St. Malo, France, July 1988. 202
Michael P. Gerlek, Eric Stoltz, and Michael Wolfe. Beyond induction variables: Detecting and classifying sequences using a demand-driven SSA form. ACM Transactions on Programming Languages and Systems, 17(1):85–122, January 1995. 213
Rajiv Gupta. Optimizing array bound checks using flow analysis. ACM Letters on Programming Languages and Systems, 2(1–4):135–150, March–December 1993. 212
Priyadarshan Kolte and Michael Wolfe. Elimination of redundant array subscript range checks. ACM SIGPLAN Notices PLDI 1995, 30(6):270–278, June 1995. 212
Z. Li. Array privatization for parallel execution of loops. In Proceedings of 1992 International Conference on Supercomputing, July 19–23, 1992, Washington, DC, pages 313–322, New York, NY 10036, USA, 1992. ACM Press. 202
Y. Lin and D. Padua. On the automatic parallelization of sparse and irregular fortran programs. In Proc. of 4th Workshop on Languages, Compilers, and Runtime Systems for Scalable Computers (LCR98), volume 1511 of Lecture Notes in Computer Science, pages 41–56. Springer-Verlag, Pittsburgh, PA, 1998. 207, 209
Y. Lin and D. Padua. Demand-driven interprocedural array property analysis. In Proceedings of the 12th International Workshop on Languages and Compilers for Parallel Computing, San Diego, CA, August 1999. 209
Victoria Markstein, John Cocke, and Peter Markstein. Optimization of range checking. In Proceedings of the SIGPLAN’ 82 Symposium on Compiler Construction, pages 114–119. ACM, ACM, 1982. 212
Dror E. Maydan, Saman P. Amarasinghe, and Monica S. Lam. Array-data flow analysis and its use in array privatization. In Proceedings of the Twentieth Annual ACM Symposium on Principles of Programming Languages, Charleston, South Carolina, January 10–13, 1993, pages 2–15, New York, NY, USA, 1993. ACM Press. 202
Madalene Spezialetti and Rajiv Gupta. Loop monotonic statements. IEEE Transactions on Software Engineering, 21(6):497–505, June 1995. 212, 213
Peng Tu and David Padua. Automatic array privatization. In Uptal Banerjee, David Gelernter, Alex Nicolau, and David Padua, editors, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, Lecture Notes in Computer Science, pages 500–521, Portland, Oregon, August 12–14, 1993. Intel Corp. and the Portland Group, Inc., Springer-Verlag. 202
M. J. Wolfe. Optimizing Supercompilers for Supercomputers. PhD thesis, Dept. of Computer Science, University of Illinois at Urbana-Champaign, October 1982. 212
Michael Wolfe. Beyond induction variables. In Proceedings of the Conference on Programming Language Design and Implementation (PLDI), volume 27, pages 162–174, New York, NY, July 1992. ACM Press. 213
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lin, Y., Padua, D. (2000). Analysis of Irregular Single-Indexed Array Accesses and Its Applications in Compiler Optimizations. In: Watt, D.A. (eds) Compiler Construction. CC 2000. Lecture Notes in Computer Science, vol 1781. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46423-9_14
Download citation
DOI: https://doi.org/10.1007/3-540-46423-9_14
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67263-0
Online ISBN: 978-3-540-46423-5
eBook Packages: Springer Book Archive