Unexpected side effects of inline substitution: a case study

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.

REFERENCES

• 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.
• 2: D. Callahan, The program summary graph and flow-sensitive interprocedual data flow analysis, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.47-56, June 20-24, 1988, Atlanta, Georgia, United States
• 3: David Callahan , Steve Carr , Ken Kennedy, Improving register allocation for subscripted variables, ACM SIGPLAN Notices, v.25 n.6, p.53-65, Jun. 1990
• 4: David Callahan , John Cocke , Ken Kennedy, Estimating interlock and improving balance for pipelined architectures, Journal of Parallel and Distributed Computing, v.5 n.4, p.334-358, August 1988 [doi>10.1016/0743-7315(88)90002-0]
• 5: F. C. Chow, Minimizing register usage penalty at procedure calls, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.85-94, June 20-24, 1988, Atlanta, Georgia, United States
• 6: Keith D. Cooper , Mary W. Hall , Linda Torczon, An experiment with inline substitution, Software—Practice & Experience, v.21 n.6, p.581-601, June 1991 [doi>10.1002/spe.4380210604]
• 7: K. D. Cooper , K. Kennedy, Interprocedural side-effect analysis in linear time, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.57-66, June 20-24, 1988, Atlanta, Georgia, United States
• 8: K. D. Cooper , K. Kennedy, Fast interprocedual alias analysis, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.49-59, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75282]
• 9: Keith D. Cooper , Ken Kennedy , Linda Torczon, The impact of interprocedural analysis and optimization in the Rⁿ programming environment, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.4, p.491-523, Oct. 1986 [doi>10.1145/6465.6489]
• 10: Jack W. Davidson , Anne M. Holler, A study of a C function inliner, Software—Practice & Experience, v.18 n.8, p.775-790, August 1988 [doi>10.1002/spe.4380180805]
• 11: DONGARRA, J., BUNCH, J., MOLER, C., AND STEWART, G. LINPACK User's Guide. SIAM, Philadelphia, Pa., 1979.
• 12: Paul Havlak , Ken Kennedy, Experience with interprocedural analysis of array side effects, Proceedings of the 1990 conference on Supercomputing, p.952-961, October 1990, New York, New York, United States
• 13: Anne Marie Holler, A study of the effects of subprogram inlining, University of Virginia, Charlottesville, VA, 1992
• 14: P. P. Chang , W.-W. Hwu, Inline function expansion for compiling C programs, ACM SIGPLAN Notices, v.24 n.7, p.246-257, July 1989
• 15: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• 16: M. Lam, Software pipelining: an effective scheduling technique for VLIW machines, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.318-328, June 20-24, 1988, Atlanta, Georgia, United States
• 17: Stephen Richardson , Mahadevan Ganapathi, Interprocedural analysis vs. procedure integration, Information Processing Letters, v.32 n.3, p.137-142, August 24, 1989 [doi>10.1016/0020-0190(89)90014-8]
• 18: S. Richardson , M. Ganapathi, Interprocedual optimization: experimental results, Software—Practice & Experience, v.19 n.2, p.149-169, February 1989 [doi>10.1002/spe.4380190205]
• 19: Vatsa Santhanam , Daryl Odnert, Register allocation across procedure and module boundaries, ACM SIGPLAN Notices, v.25 n.6, p.28-39, Jun. 1990
• 20: Peter A. Steenkiste , John L. Hennessy, A simple interprocedural register allocation algorithm and its effectiveness for LISP, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.1, p.1-32, Jan. 1989 [doi>10.1145/59287.59289]
• 21: D. W. Wall, Register windows vs. register allocation, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.67-78, June 20-24, 1988, Atlanta, Georgia, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Experimentation, Languages, Performance

Keywords:
inline substitution, interprocedural analysis, interprocedural optimization