Sharlit—a tool for building optimizers

ABSTRACT

A complex and time-consuming function of a modern compiler is global optimization. Unlike other functions of a compiler such as parsing and code generation which examine only one statement or one basic block at a time, optimizers are much larger in scope, examining and changing large portions of a program all at once. The larger scope means optimizers must perform many program transformations. Each of these transformations makes its own particular demands on the internal representation of programs; each can interact with and depend on the others in different ways. This makes optimizers large and complex. Despite their complexity, few tools exist to help in building optimizers. This is in stark contrast with other parts of the compiler where years of experience have culminated in tools with which these other parts can be constructed easily. For example, parser generators are used to build front-ends, and peephole optimizers and tree matchers are used to build code generators. This paper presents Sharlit, a tool to support the construction of modular and extensible global optimizers. We will show how Sharlit helps in constructing data-flow analyzers and the transformations that use data-flow analysis information, both are major components of any optimizer. Sharlit is implemented in C++ and uses C++ in the same way that YACC uses C. Thus we assume the reader has some familiarity with C++[9].

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Zahira Ammarguellat , W. L. Harrison, III, Automatic recognition of induction variables and recurrence relations by abstract interpretation, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.283-295, June 1990, White Plains, New York, United States
• 3: M. Berry et al, The PERFECT Club Benchmarks: effective performance evaluation of supercomputers. Technical Report UIUCSRD Rep. No. 827, University of Illinoi,,~ Urbana-Champaign, 1989.
• 4: Jong-Deok Choi , Ron Cytron , Jeanne Ferrante, Automatic construction of sparse data flow evaluation graphs, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.55-66, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99594]
• 5: Frederick Chi-Tak Chow, A portable machine-independent global optimizer--design and measurements, 1984
• 6: M.S. Hecht and J.D. UUman. A simple algorithm for global data-flow analysis programs, In SIAM J. Computing. (4):519-532.
• 7: E. Morel , C. Renvoise, Global optimization by suppression of partial redundancies, Communications of the ACM, v.22 n.2, p.96-103, Feb. 1979 [doi>10.1145/359060.359069]
• 8: M. Sharir. "Structural analysis: a new approach to flow analysis in optimizing compilers". Computer Languages 5 (1980), 141-153.
• 9: Bjarne Stroustrup, The C++ programming language (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 10: R.E. Tarjan. "Testing flow graph reducibility", j. of Comput. and Syst. Sci. (9 1974), 355-365.
• 11: Robert Endre Tarjan, Fast Algorithms for Solving Path Problems, Journal of the ACM (JACM), v.28 n.3, p.594-614, July 1981 [doi>10.1145/322261.322273]
• 12: Steven W. K. Tjiang , Michael E. Wolf , Monica S. Lam , K. Pieper , John L. Hennessy, Integrating Scalar Optimization and Parallelization, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.137-151, August 07-09, 1991
• 13: j.D. Ullman. "Fast algorithms for the elimination of common subexpressions'. Acta Inf. 2, 3 (July 1973), 191- 213.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: C++

General Terms:
Algorithms, Design