Keith D. Cooper
Mary W. Hall
Abstract
The structure of a program can encode implicit information that changes both the shape and speed of the generated code. Interprocedural transformations like inlining often discard such information; using interprocedural data-flow information as a basis for optimization can have the same effect.
In the course of a study on inline substitution with commercial FORTRAN compilers, we encountered unexpected performance problems in one of the programs. This paper describes the specific problem that we encountered, explores its origins, and examines the ability of several analytical techniques to help the compiler avoid similar problems.
- 1 BURKE, M., COOPER, K. D., KENNEDY, K., AND TORCZON, L. Interprocedural optimization: Eliminating unnecessary recompilation. Tech. Rep. RC 15968 (70983), IBM Research Division, July 1990.Google Scholar
- 2 CALLAHAN, D. The program summary graph and flow-sensitive interprocedural data flow analysis. In Proceedings of the A CM SIGPLAN '88 Conference on Programming Language Design and Implementation. SIGPLAN Not. 23, 7 (July 1988), 47-56. Google ScholarDigital Library
- 3 CALLAHAN, D., CARR, S., AND KENNEDY, K. Improving register allocation for subscripted variables. In Proceedings of the A CM SIGPLAN '90 Conference on Programming Language Design and Implementation. SIGPLAN Not. 25, 6 (June 1990), 53-65. Google ScholarDigital Library
- 4 CALLAHAN, D., COCKE, J., AND KENNEDY, K. Estimating interlock and improving balance for pipelined architectures. J. Parallel Distrib. Comput. 5 (Aug. 1988), 334-358. Google ScholarDigital Library
- 5 CHOW, F.C. Minimizing register usage penalty at procedure calls. In Proceedings of the ACM SIGPLAN '88 Conference on Programming Language Design and Implementation. SIGPLAN Not. 23, 7 (July 1988), 85-94. Google ScholarDigital Library
- 6 COOPER, g. D., HALL, M., AND TORCZON, L. An experiment with inline substitution. Softw. Pract. Exper. 21, 6 (June 1991), 581-601. Google ScholarDigital Library
- 7 COOPER, K. D., AND KENNEDY, K. interprocedural side-effect analysis in linear time. In Proceedings of the ACM SIGPLAN '88 Conference on Programming Languages Design and Implementation. SIGPLAN Not. 23, 7 (July 1988), 57-66. Google ScholarDigital Library
- 8 COOPER, K. D., AND KENNEDY, K. Fast interprocedural alias analysis. In Conference Record of the Sixteenth Annual A CM Symposium on Principles of Programming Languages (Austin, Tex., Jan. 1989), pp. 49-59. Google ScholarDigital Library
- 9 COOPER, K. D., KENNEDY, g., AND TORCZON, L. The impact of interprocedural analysis and optimization in the R~ programming environment. ACM Trans. Program. Lang. Syst. 8, 4 (Oct. 1986), 491-523. Google ScholarDigital Library
- 10 DAVIDSON, J. W., AND HOLLER, A.M. A study of a C function inliner. Softw. Pract. Exper. 18, 8 (Aug. 1988), 775-790. Google ScholarDigital Library
- 11 DONGARRA, J., BUNCH, J., MOLER, C., AND STEWART, G. LINPACK User's Guide. SIAM, Philadelphia, Pa., 1979.Google Scholar
- 12 HAVLAK, P., AND KENNEDY, K. Experience with interprocedural analysis of array side effects. In Proceedings of Supercomputing 90 (New York, Nov. 1990), IEEE Computer Society Press, pp. 952-961. Google ScholarDigital Library
- 13 HOLLER, A.M. A study of the effects of subprogram inlining. Ph.D. dissertation, Univ. of Virginia, Charlottesville, May 1991. Google ScholarDigital Library
- 14 Hwu, W. W., AND CHANG, P. P. Inline function expansion for inlining C programs. In Proceedings of the A CM SIGPLAN '89 Conference on Programming Language Design and Implementation. SIGPLAN Not. 24, 7 (July 1989), 246-257. Google ScholarDigital Library
- 15 KUCK, D.J. The Structure of Computers and Computations, Volume 1. Wiley, New York, 1978. Google ScholarDigital Library
- 16 LAM, M. Software pipelining: An effective scheduling technique for VLIW machines. In Proceedings of the A CM SIGPLAN "88 Conference on Programming Language Design and Implementation. SIGPLAN Not. 23, 7 (July 1988), 318-328. Google ScholarDigital Library
- 17 RICHARDSON, S., AND GANAPATHI, M. Interprocedural analysis versus procedure integration. Inf. Proce~8. Lett. 32, 3 (Aug. 1989), 137-142. Google ScholarDigital Library
- 18 RICHARDSON, S., AND GANAPATHI, M. interprocedural optimization: Experimental results. Soft. Pract. Exper. 19, 2 (Feb. 1989), 149-169. Google ScholarCross Ref
- 19 SANTHANAM, V., AND ODNERT, D. Register allocation across procedure and module boundaries. In Proceedings of the A CM SIGPLAN '90 Conference on Programming Language Design and Implementation. SIGPLAN Not. 25, 6 (June 1990), 28-39. Google ScholarDigital Library
- 20 STEENKISTE, P. A., AND HENNESSY, J. L. A simple interprocedural register allocation algorithm and its effectiveness for LISP. A CM Trans. Program. Lang. Syst. 11, 1 (Jan 1989), 1-32. Google ScholarDigital Library
- 21 WALL, D. Register windows vs. register allocation. In Proceedings of the ACM SIGPLAN "88 Conference on Programming Language Design and Implementation. SIGPLAN Not. 23, 7 (July 1988), 67-78. Google ScholarDigital Library
Index Terms
- Unexpected side effects of inline substitution: a case study
Recommendations
A framework for unrestricted whole-program optimization
Proceedings of the 2006 PLDI ConferenceProcedures have long been the basic units of compilation in conventional optimization frameworks. However, procedures are typically formed to serve software engineering rather than optimization goals, arbitrarily constraining code transformations. ...
Interprocedural pointer alias analysis
We present practical approximation methods for computing and representing interprocedural aliases for a program written in a language that includes pointers, reference parameters, and recursion. We present the following contributions: (1) a framework ...
A framework for unrestricted whole-program optimization
PLDI '06: Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and ImplementationProcedures have long been the basic units of compilation in conventional optimization frameworks. However, procedures are typically formed to serve software engineering rather than optimization goals, arbitrarily constraining code transformations. ...
Reviews
Rajeev Kumar Pandey
Inline substitution is an often-used and well-known optimization. Inline substitution can be viewed as the upper bound on the improvement that can be arrived at using interprocedural dataflow information. Interprocedural analysis and transformation has a subtle side effect, however: implicit information encoded within the structure of a program that may aid in optimization may be lost in the process. The authors point out this side effect and suggest some possible remedies in this fascinating paper. While engaged in a study of inline substitution in commercial FORTRAN compilers, the authors discovered a LINPACK benchmark program that displayed an increase in runtime upon performing inline substitution. Using various analysis tools, they were able to pinpoint the conditions that led to the program displaying this nonintuitive behavior. They show that the interaction between the FORTRAN 77 standard, lost aliasing information due to inlining, and limited alias analysis results in memory and pipeline latencies that the scheduler cannot overcome with the information available. The resulting analysis is an engaging discussion of the synergy between language semantics, compilers, and computer architecture. The authors examine classical analysis techniques, such as alias analysis and cloning, but illustrate that more powerful analysis techniques such as regular section analysis, dependence analysis, or maintaining optimization histories may be required to overcome this problem. The paper is concise, well-written, and accompanied by adequate references, and it should appeal strongly to students of programming languages and compilers. One paragraph of text and a code example suffer from poor typesetting, but this is a minor drawback in an otherwise excellent paper.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments