Generalized instruction selection using SSA-graphs

ABSTRACT

Instruction selection is a well-studied compiler phase that translates the compiler's intermediate representation of programs to a sequence of target-dependent machine instructions optimizing for various compiler objectives (e.g. speed and space). Most existing instruction selection techniques are limited to the scope of a single statement or a basic block and cannot cope with irregular instruction sets that are frequently found in embedded systems.

We consider an optimal technique for instruction selection that uses Static Single Assignment (SSA) graphs as an intermediate representation of programs and employs the Partitioned Boolean Quadratic Problem (PBQP) for finding an optimal instruction selection. While existing approaches are limited to instruction patterns that can be expressed in a simple tree structure, we consider complex patterns producing multiple results at the same time including pre/post increment addressing modes, div-mod instructions, and SIMD extensions frequently found in embedded systems. Although both instruction selection on SSA-graphs and PBQP are known to be NP-complete, the problem can be solved efficiently - even for very large instances.

Our approach has been implemented in LLVM for an embedded ARMv5 architecture. Extensive experiments show speedups of up to 57% on typical DSP kernels and up to 10% on SPECINT 2000 and MiBench benchmarks. All of the test programs could be compiled within less than half a minute using a heuristic PBQP solver that solves 99.83% of all instances optimally.

REFERENCES

• 1: Warren P. Adams and Richard J. Forrester. A simple recipe for concise mixed 0-1 linearizations. Oper. Res. Lett., 33(1):55--61, 2005.
• 2: A. V. Aho , S. C. Johnson, Optimal Code Generation for Expression Trees, Journal of the ACM (JACM), v.23 n.3, p.488-501, July 1976 [doi>10.1145/321958.321970]
• 3: A. Balachandran , D. M. Dhamdhere , S. Biswas, Efficient retargetable code generation using bottom-up tree pattern matching, Computer Languages, v.15 n.3, p.127-140, 1990 [doi>10.1016/0096-0551(90)90006-B]
• 4: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 5: João Dias and Norman Ramsey. Converting intermediate code to assembly code using declarative machine descriptions. In Alan Mycroft and Andreas Zeller, editors, CC, volume 3923 of Lecture Notes in Computer Science, pages 217--231. Springer, 2006.
• 6: Erik Eckstein. Code Optimization for Digital Signal Processors. PhD Thesis. TU Wien, November 2003.
• 7: Erik Eckstein, Oliver König, and Bernhard Scholz. Code Instruction Selection Based on SSA-Graphs. In Andreas Krall, editor, SCOPES, volume 2826 of Lecture Notes in Computer Science, pages 49--65. Springer, 2003.
• 8: M. Anton Ertl, Optimal code selection in DAGs, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.242-249, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292562]
• 9: M. Anton Ertl , Kevin Casey , David Gregg, Fast and flexible instruction selection with on-demand tree-parsing automata, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 10: Robert W. Floyd, Algorithm 97: Shortest path, Communications of the ACM, v.5 n.6, p.345, June 1962 [doi>10.1145/367766.368168]
• 11: Christopher W. Fraser , Robert R. Henry , Todd A. Proebsting, BURG: fast optimal instruction selection and tree parsing, ACM SIGPLAN Notices, v.27 n.4, p.68-76, April 1992 [doi>10.1145/131080.131089]
• 12: Christopher W. Fraser , David R. Hanson , Todd A. Proebsting, Engineering a simple, efficient code-generator generator, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.3, p.213-226, Sept. 1992 [doi>10.1145/151640.151642]
• 13: Michael P. Gerlek , Eric Stoltz , Michael Wolfe, Beyond induction variables: detecting and classifying sequences using a demand-driven SSA form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.1, p.85-122, Jan. 1995 [doi>10.1145/200994.201003]
• 14: J. Guo, T. Limberg, E. Matus, B. Mennenga, R. Klemm, and G. Fettweis. Code generation for STA architecture. In Proc. of the 12th European Conference on Parallel Computing (Euro-Par'06). Springer LNCS, 2006.
• 15: Lang Hames and Bernhard Scholz. Nearly optimal register allocation with PBQP. In David E. Lightfoot and Clemens A. Szyperski, editors, JMLC, volume 4228 of Lecture Notes in Computer Science, pages 346--361. Springer, 2006.
• 16: Hannes Jakschitsch. "Befehlsauswahl auf SSA-Graphen". Master's thesis, Fakultät für Informatik, Universität Karlsruhe (TH),Germany, 2004.
• 17: SPEC2000 Website. http://www.spec.org.
• 18: Chris Lattner , Vikram Adve, LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.75, March 20-24, 2004, Palo Alto, California
• 19: Rainer LEUPERS Leupers , Steven Bashford, Graph-based code selection techniques for embedded processors, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.4, p.794-814, Oct. 2000 [doi>10.1145/362652.362661]
• 20: Stan Liao , Srinivas Devadas , Kurt Keutzer , Steve Tjiang, Instruction selection using binate covering for code size optimization, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.393-399, November 05-09, 1995, San Jose, California, United States
• 21: MiBench Website. http://www.eecs.umich.edu/mibench/.
• 22: Albert Nymeyer and Joost-Pieter Katoen. Code generation based on formal BURS therory and heuristic search. Acta Inf., 34(8):597--635, 1997.
• 23: Todd A. Proebsting. Least-Cost Instruction Selection in DAGs is NP-Complete. http://research.microsoft.com/~toddpro/papers/proof.htm, 1998.
• 24: Stefan Schäfer , Bernhard Scholz, Optimal chain rule placement for instruction selection based on SSA graphs, Proceedingsof the 10th international workshop on Software & compilers for embedded systems, April 20-20, 2007, Nice, France [doi>10.1145/1269843.1269857]
• 25: Bernhard Scholz , Erik Eckstein, Register allocation for irregular architectures, Proceedings of the joint conference on Languages, compilers and tools for embedded systems: software and compilers for embedded systems, June 19-21, 2002, Berlin, Germany
• 26: Vojin živojnovi#263;, Juan M. Velarde, Christian Schläger, and Heinrich Meyr. DSPSTONE: A DSP-oriented benchmarking methodology. In Proceedings of the International Conference on Signal Processing and Technology (ICSPAT'94), 1994.

INDEX TERMS

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

General Terms:
Algorithms, Languages, Performance

Keywords:
code generation, compiler, instruction selection, pbqp