Abstract
In this paper we present techniques to detect three common patterns of parallelism in C programs that use recursive data structures. These patterns include, function calls that access disjoint sub-pieces of tree-like data structures, pointer-chasing loops that traverse list-like data structures, and array-based loops which operate on an array of pointers pointing to disjoint data structures. We design dependence tests using a family of three existing pointer analyses, namely points-to, connection and shape analyses, with special emphasis on shape analysis. To identify loop parallelism, we introduce special tests for detecting loop-carried dependences in the context of recursive data structures. We have implemented the tests in the framework of our McCAT C compiler, and we present some preliminary experimental results.
This research supported in part by NSERC and FCAR.
Chapter PDF
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
Maryam Emami, Rakesh Ghiya, and Laurie J. Hendren. Context-sensitive interprocedural points-to analysis in the presence of function pointers. In Proceedings of the ACM SIGPLAN '94 Conference on Programming Language Design and Implementation, pages 242–256, Orlando, Florida, June 1994.
Rakesh Ghiya and Laurie J. Hendren. Connection Analysis: A practical interprocedural heap analysis for C. International Journal of Parallel Programming, 24(6), pages 547–578, 1996.
Rakesh Ghiya and Laurie J. Hendren. Is it a tree, a DAG, or a cyclic graph? a shape analysis for heap-directed pointers in C. In Conference Record of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 1–15, St. Petersburg, Florida, January 1996.
Rakesh Ghiya and Laurie J. Hendren.Putting Pointer Analysis to Work. In Conference Record of the 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, San Diego, California, January 1998.
Rakesh Ghiya. Putting Pointer Analysis to Work. PhD Thesis, School of Computer Science, McGill University, Montreal, Canada. February 1998. Expected.
Vincent A. Guarna, Jr. A technique for analyzing pointer and structure references in parallel restructuring compilers. In Proceedings of the 1988 International Conference on Parallel Processing, volume II, pages 212–220, August 1988.
Joseph Hummel, Laurie J. Hendren, and Alexandru Nicolau. A general data dependence test for dynamic, pointer-based data structures. In Proceedings of the ACM SIGPLAN '94 Conference on Programming Language Design and Implementation, pages 218–229, Orlando, Florida, June 1994.
Laurie J. Hendren and Alexandru Nicolau. Parallelizing programs with recursive data structures. IEEE Transactions on Parallel and Distributed Systems, 1(1):3547, January 1990.
Susan Horwitz, Phil Pfeiffer, and Thomas Reps. Dependence analysis for pointer variables. In Proceedings of the SIGPLAN '89 Conference on Programming Language Design and Implementation, pages 28–40, Portland, Oregon, June 1989.
Laurie J. Hendren, Xinan Tang, Yingchun Zhu, Guang R. Gao, Xun Xue, Haiying Cai, and Pierre Ouellet. Compiling C for the EARTH multithreaded architecture. In Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques (PACT '96), pages 12–23, Boston, Massachusetts, October 1996.
Justiani. An array dependence testing framework for the McCAT compiler. Master's thesis, McGill University, Montréal, Québec, December 1994.
Christopher Lapkowski. A practical symbolic array dependence analysis framework for C. Master's thesis, McGill University, Montréal, Québec, April 1997.
James R. Larus and Paul N. Hilfinger. Detecting conflicts between structure accesses. In Proceedings of the SIGPLAN '88 Conference on Programming Language Design and Implementation, pages 21–34, Atlanta, Georgia, June 1988.
Bhama Sridharan. An analysis framework for the McCAT compiler. Master's thesis, McGill University, Montréal, Québec, September 1992.
Xinan Tang, Rakesh Ghiya, L. J. Hendren, and G. R. Gao. Heap analysis and optimizations for threaded programs. In Proceedings of the 1997 Conference on Parallel Architectures and Compilation Techniques, San Franc., Calif, Nov. 1997.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ghiya, R., Hendren, L.J., Zhu, Y. (1998). Detecting parallelism in C programs with recursive data structures. In: Koskimies, K. (eds) Compiler Construction. CC 1998. Lecture Notes in Computer Science, vol 1383. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0026429
Download citation
DOI: https://doi.org/10.1007/BFb0026429
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64304-3
Online ISBN: 978-3-540-69724-4
eBook Packages: Springer Book Archive