Abstract
Compilers typically treat source-level and instruction-level issues as independent phases of compilation so that much of the information that might be available to source-level systems of transformations about the semantics of the high-level language and its implementation, as well as the algorithm in some cases, is generally “lost in the translation”, making it unavailable to instruction-level systems of transformations. While this separation of concerns reduces the complexity of the compiler and facilitates porting the compiler to different source/target combinations, it also forces the costly recomputation at the instruction-level of much of the information that was already available to the higher level, and in many cases introduces spurious dependencies that can not be eliminated by instruction-level analysis alone.
In this paper we present a simple mechanism for retaining algorithm and source language semantics information for use in instruction-level disambiguation, while retaining the ease of porting the compiler to different source/target combinations, and without noticeably increasing the complexity of the compiler. Simulation results show that our mechanism provides a significant increase in both performance, resulting from more accurate higher level data dependence information, and efficiency, as instruction-level dependence analysis no longer needs to recompute information that was already available at the higher level.
This work was supported in part by ONR grant N00014-93-1-1348.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
A. Aho, R. Sethi, and J.D. Ullman. Compilers: Principles, Techniques and Tools. Addison-Wesley, Reading, MA, 1986.
R. Allen and K. Kennedy. Automatic translation of FORTRAN programs to vector form. TOPLAS, 9(4), 1987.
U. Banerjee. Dependence analysis for supercomputing. Kluwer Academic Press, Boston, MA, 1988.
D. Culler, A. Dusseau, S. Goldstein, A. Krishnamurthy, S. Lumetta, T. von Eicken, and K. Yelick. Parallel programming in split-c. In Proceedings of Supercomputing 1993, 1993.
J. Dongarra, J.R. Bunch, C.B. Moler, and G.W. Stewart. LINPACK Users's Guide. Society for Industrial and Applied Mathematics, Philadelphia, PA, 1978.
M. Emami, R. Ghiya, and L. Hendren. Context-sensitive interprocedural points-to analysis in the presence of function pointers. In PLDI, 1994.
R. Ghiya. Disambiguating heap references. Technical Report Masters Thesis, School of Computer Science, McGill University, October 1994.
M. Girkar and C.D. Polychronopoulos. A general framework for program optimization and scheduling. TOPLAS, 1995. Preprint.
M. Haghighat and C. Polychronopoulos. Symbolic program analysis and optimization for parallelizing compilers. In Lang. and Compilers for Par. Comp., volume 757 of LNCS Series. Springer-Verlag, 1992.
D. Hearn and M. Pauline Baker. Computer Graphics. Prentice-Hall, 1986.
L. Hendren, J. Hummel, and A. Nicolau. Abstractions for recursive pointer data structures: Improving the analysis and transformation of imperative programs. In PLDI, 1992.
L. Hendren and A. Nicolau. Parallelizing programs with recursive data structures. IEEE Trans. on Parallel and Distributed Computing, 1(1), 1990.
J. Hummel, L. Hendren, and A. Nicolau. A language for conveying the aliasing properties of dynamic, pointer-based data structures. In IPPS, 1994.
D. Kuck, R. Kuhn, B. Leasure, and M. Wolfe. The structure of an advanced vectorizer for pipelined processors. In Fourth International Computer Software and Applications Conference, 1980.
K. Kundert. Sparse matrix techniques. In A. Ruehli, editor, Circuit Analysis, Simulation and Design. Elsevier Science Publishers B.V. (North-Holland), 1986.
W. Landi and B. Ryder. A safe approximation algorithm for interprocedural pointer aliasing. In PLDI, 1992.
J. M. Lucassen. Types and Effects: Towards the Integration of Functional and Imperative Programming. PhD thesis, MIT, 1987.
F.H. McMahon. The livermore fortran kernels: A computer test of the numerical performance range. Technical Report UCRL-53745, Lawrence Livermore National Laboratory, 1986.
S. Novack and A. Nicolau. An efficient global resource constrained technique for exploiting instruction level parallelism. In ICPP, St. Charles, IL, August 1992.
S. Novack and A. Nicolau. Vista: The visual interface for scheduling transformations and analysis. In Lang. and Compilers for Par. Comp., volume 768 of LNCS Series. Springer-Verlag, 1993.
S. Novack and A. Nicolau. Mutation scheduling: A unified approach to compiling for finegrain parallelism. In Lang. and Compilers for Par. Comp., volume 892 of LNCS Series. Springer-Verlag, 1994.
S. Novack and A. Nicolau. A hierarchical approach to instruction-level parallelization. International Journal of Parallel Programming, 23(1), February 1995.
D. Padua and M. Wolfe. Advanced compiler optimization for supercomputers. CACM, 29(12), December 1986.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Novack, S., Hummel, J., Nicolau, A. (1996). A simple mechanism for improving the accuracy and efficiency of instruction-level disambiguation. In: Huang, CH., Sadayappan, P., Banerjee, U., Gelernter, D., Nicolau, A., Padua, D. (eds) Languages and Compilers for Parallel Computing. LCPC 1995. Lecture Notes in Computer Science, vol 1033. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0014206
Download citation
DOI: https://doi.org/10.1007/BFb0014206
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60765-6
Online ISBN: 978-3-540-49446-1
eBook Packages: Springer Book Archive