Cited By
View all- Belevantsev AGaisaryan SIvannikov V(2008)Construction of speculative optimization algorithmsProgramming and Computing Software10.1134/S036176880803002X34:3(138-153)Online publication date: 1-May-2008
Recovery code generation for general speculative optimizations
Pages 67 - 89
Abstract
A general framework that integrates both control and data speculation using alias profiling and/or compiler heuristic rules has shown to improve CPU2000 performance on Itanium systems. However, speculative optimizations require check instructions and recovery code to ensure correct execution when speculation fails at runtime. How to generate check instructions and their associated recovery code efficiently and effectively is an issue yet to be well studied. It is also, very important that the recovery code generated in the earlier phases integrate gracefully in the later optimization phases. At the very least, it should not hinder later optimizations, thus, ensuring overall performance improvement. This paper proposes a framework that uses an if-block structure to facilitate check instructions and recovery code generation for general speculative optimizations. It allows speculative instructions and their recovery code generated in the early compiler optimization phases to be integrated effectively with the subsequent optimization phases. It also allows multilevel speculation for multilevel pointers and multilevel expression trees to be handled with no additional complexity. The proposed recovery code generation framework has been implemented and evaluated in the Open Research Compiler (ORC).
References
[1]
Bharadwaj, J., Menezes, K., and McKinsey, C. 1999. Wavefront scheduling: Path based data representation and scheduling of subgraphs, MICRO'32, (Dec.).
[2]
Bringmann, R. A., Mahlke, S. A., Hank, R. E., Gyllenhaal, J. C., and Hwu, W. W. 1993. Speculative execution exception recovery using write-back Suppression. MICRO'26.
[3]
Chen, T., Lin, J., Hsu, W., and Yew, P. C. 2002. An empirical study on the granularity of pointer analysis in C Programs. In 15th Workshop on Languages and Compilers for Parallel Computing. 151--160.
[4]
Chen, T., Lin, J., Hsu, W., and Yew, P. C. 2004. Data dependence profiling for speculative optimization. In Proceedings of the 14th International Conference on Compiler Construction. 57--62.
[5]
Chow, F., Chan, S., Liu, S., Lo, R., and Streich, M. 1996. Effective representation of aliases and indirect memory operations in SSA form. In Proceedings of the Sixth International Conference on Compiler Construction. 253--267.
[6]
Chow, F., Chan, S., Kennedy, R., Liu, S., Lo, R., and Tu, P. 1997. A new algorithm for partial redundancy elimination based on SSA form. In Proceedings of the ACM SICPLAN Conference on Programming Language Design and Implementation. 273--286.
[7]
Cytron, R., Ferrante, J., Rosen, B., Wegman, M., and Zadeck, K. 1991. Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems, 13, 4, 451--490.
[8]
Ishizaki, K., Inagaki, T., Komatsu, H., and Nakatani, T. 2002. Eliminating exception constraints of Java programs for IA-64. In Proceedings of International Conference on Parallel Architecture and Compiler Technology. 259--268.
[9]
Ju, R. D.-C., Nomura, K., Mahadevan, U., and Wu, L.-C. 2000. A unified compiler framework for control and data speculation. In Proceedings of the International Conference on Parallel Architectures and Compilation Techniques. 157--168.
[10]
Ju, R. D.-C., Chan, S., and Wu, C. 2001. Open Research Compiler (ORC) for the Itanium Processor Family. Tutorial. MICRO 34.
[11]
Heggy, B. and Soffa, M. L. 1990. Architectural support for register allocation in the presence of aliasing. In Proceeding of Supercomputing 1990.
[12]
Kawahito, M., Komatsu, H., and Nakatani, T. 2000. Effective null pointer check elimination utilizing hardware trap. In Proceeding of the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems.
[13]
Kennedy, R., Chow, F., Dahl, P., Liu, S.-M., Lo, R., and Streich, M. 1998. Strength reduction via SSAPRE. In Proceedings of the Seventh International Conference on Compiler Construction. 144--158.
[14]
Kennedy, R., Chan, S., Liu, S., Lo, R., Tu, P., and Chow, F. 1999. Partial redundancy elimination in SSA Form. ACM Trans. on Programming Languages and Systems, 21, 3, 627--676.
[15]
Knoop, J., Ruthing, O., and Steffen, B. 1992. Lazy code motion. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. 224--234 .
[16]
Lin, J., Chen, T., Hsu, W. C., Yew, P. C., Ju, R. D.-C., Ngai, T. F., and Chan, S. 2003. A compiler framework for speculative analysis and optimizations. In Proceedings of ACM SIGPLAN on Programming Language Design and Implementation. 289--299.
[17]
Lin, J., Hsu, W. C., Yew, P. C., Ju, R. D.-C., Ngai, T. F., and Chan, S. 2004. A compiler framework for recovery code generation in general speculative optimizations. In Proceedings of the International Conference on Parallel Architectures and Compilation Techniques. 17--28.
[18]
Lo, R., Chow, F., Kennedy, R., Liu, S., and Tu, P. 1998. Register promotion by sparse partial redundancy elimination of loads and stores. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. 26--37.
[19]
Mahadevan, U., Nomura, K., Ju, R. D.-C., and Hank, R. 2000. Applying data speculation in modulo scheduled loops. In Proceedings of the International Conference on Parallel Architectures and Compilation Techniques. 169--176.
[20]
Mahlke, S. A., Chen, W. Y., Bringmann, R. A, Hank, R. E., Hwu, W.-M., Rau, B. R., and Schlansker, M. S. 1993. Sentinel scheduling: a model for compiler-controlled speculative executions. ACM Trans. Comput. Syst., 11, 4, 276--408.
[21]
Pfmon 2003. ftp://ftp.hpl.hp.com/pub/linux-ia64/pfmon-1.1-0.ia64.rpm.
[22]
Postiff, M., Greene, D., and Mudge, T. 2000. The store-load address table and speculative register promotion. In Proceedings of International Symposium on Micro Architecture. 235--244.
[23]
Wu, Y. and Larus, J. R. 1994. Static branch frequency and program profile analysis. In Proceedings of the 27th Annual IEEE/ACM International Symposium on Micro Architecture. 1--11.
Index Terms
- Recovery code generation for general speculative optimizations
Recommendations
A Compiler Framework for Recovery Code Generation in General Speculative Optimizations
PACT '04: Proceedings of the 13th International Conference on Parallel Architectures and Compilation TechniquesA general framework that integrates both control and data speculation using alias profiling and/or compiler heuristic rules has shown to improve SPEC2000 performance on Itanium systems. However, speculative optimizations require check instructions and ...
A compiler framework for speculative optimizations
Speculative execution, such as control speculation or data speculation, is an effective way to improve program performance. Using edge/path profile information or simple heuristic rules, existing compiler frameworks can adequately incorporate and exploit ...
A compiler framework for speculative analysis and optimizations
PLDI '03: Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementationSpeculative execution, such as control speculation and data speculation, is an effective way to improve program performance. Using edge/path profile information or simple heuristic rules, existing compiler frameworks can adequately incorporate and ...
Comments
Information & Contributors
Information
Published In
Copyright © 2006 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 March 2006
Published in TACO Volume 3, Issue 1
Check for updates
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 771Total Downloads
- Downloads (Last 12 months)82
- Downloads (Last 6 weeks)5
Reflects downloads up to 01 Mar 2025
Other Metrics
Citations
Cited By
View all- Belevantsev AGaisaryan SIvannikov V(2008)Construction of speculative optimization algorithmsProgramming and Computing Software10.1134/S036176880803002X34:3(138-153)Online publication date: 1-May-2008
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in