Instruction selection, resource allocation, and scheduling in the AVIV retargetable code generator

ABSTRACT

The AVIV retargetable code generator produces optimized machine code for target processors with different instruction set architectures AVIV optimizes for minimum code size. Retargetable code generation requires the development of heuristic algorithms for instruction selection, resource allocation, and scheduling. AVIV addresses these code generation subproblems concurrently, whereas most current code generation systems address them sequentially. It accomplishes this by converting the input application to a graphical (Split-Node DAG) representation that specifies all possible ways of implementing the application on the target processor. The information embedded in this representation in then used to set up a heuristic branch-and-bound step that performs functional unit assignment, operation grouping, register bank allocation, and scheduling concurrently. While detailed register allocation is carried out as a second step, estimates of register requirements are generated during the first step to ensure high quality of the final assembly code. We show that near-optimal code can be generated for basic blocks for different architectures within reasonable amounts of CPU time. Our framework thus allows us to accurately evaluate the performance of different architectures on application code.

REFERENCES

• 1: Rajesh K. Gupta , Giovanni De Micheli, Hardware-Software Cosynthesis for Digital Systems, IEEE Design & Test, v.10 n.3, p.29-41, July 1993 [doi>10.1109/54.232470]
• 2: George Hadjiyiannis , Silvina Hanono , Srinivas Devadas, ISDL: an instruction set description language for retargetability, Proceedings of the 34th annual conference on Design automation, p.299-302, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266108]
• 3: Stanford Compiler Group. The SUIF Library, 1.0 edition, 1994.
• 4: SPAM Research Group. SPAM Compiler User's Manual, 1.0 edition, 1997.
• 5: G. Chaitin, M. Auslander, A. Chandra, J. Cocke, M. Hopkins, and P. Markstein. Register Allocation via Coloring. Computer Languages, 6:47-57, 1981.
• 6: Peter Marwedel, The mimola design system: Tools for the design of digital processors, Proceedings of the 21st conference on Design automation, p.587-593, June 25-27, 1984, Albuquerque, New Mexico, United States
• 7: P. Paulin et al. FlexWare: A Flexible Firmware Development Environment for Embedded Systems. In Code Generation for Embedded Processors, pages 67-84. Kluwer Academic Publishers, 1995.
• 8: D. Lanneer et al. CHESS: Retargetable Code Generation for Embedded DSP Processors. In Code Generation for Embedded Processors, pages 85-102. Kluwer Academic Publishers, 1995.
• 9: T. Wilson et al. An ILP-Based Approach to Code Generation. In Code Generation for Embedded Processors, pages 103- 1 18. Kluwer Academic Publishers, 1995.
• 10: C. Liem, T. May, and P. Paulin. Instruction-Set Matching and Selection for DSP and ASIP Code Generation. In Proceedings of the European Design and Test Conference, pages 31-37, Feb 1994.
• 11: M. Freericks. The nML Machine Description Formalism. Technical report, TU Berlin, 1993.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
  B.8 Performance and Reliability

  C. Computer Systems Organization

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

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  J. Computer Applications

General Terms:
Algorithms, Design, Experimentation, Languages, Measurement, Performance, Theory

Keywords:
MPEG4, codec, design automatian, flip-flops, level converters, low power, placement, synthesis, voltage scaling