Trace selection for compiling large C application programs to microcode

ABSTRACT

Microcode optimization techniques such as code scheduling and resource allocation can benefit significantly by reducing uncertainties in program control flow. A trace selection algorithm with profiling information reduces the uncertainties in program control flow by identifying sequences of frequently invoked basic blocks as traces. These traces are treated as sequential codes for optimization purposes. Optimization based on traces is especially useful when the code size is large and the control structure is complicated enough to defeat hand optimizations. However, most of the experimental results reported to date are based on small benchmarks with simple control structures. For different trace selection algorithms, we report the distribution of control transfers categorized according to their potential impact on the microcode optimizations. The experimental results are based on ten C application programs which exhibit large code size and complicated control structure. The measured data for each program is accumulated across a large number of input files to ensure the reliability of the result. All experiments are performed automatically using our IMPACT C compiler which contains integrated profiling and analysis tools.

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: D. J. Kuck , R. H. Kuhn , D. A. Padua , B. Leasure , M. Wolfe, Dependence graphs and compiler optimizations, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-218, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567555]
• 3: Ron Cytron and Jeanne Ferrante, "The Value of Renaming for Parallelism Detection and Storage Allocation," Proceedings of the 1987 International Conference on Parallel Processing, Aug., 1987.
• 4: Mario Tokoro, Eiji Tamura and Takashi Takizuka, "Optimization of Microprograms," IEEE Transactions on Computers, vol. c-30, no.7, July, 1981.
• 5: Joseph A. Fisher, "Trace Scheduling: A Technique for Global Microcode Compaction," IEEE Transactions on Computers, vol. c-30, no.7, July, 1981.
• 6: John L. Hennessy , Thomas Gross, Postpass Code Optimization of Pipeline Constraints, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.422-448, July 1983 [doi>10.1145/2166.357217]
• 7: B. Su , S. Ding , J. Xia, URPR—An extension of URCR for software pipelining, Proceedings of the 19th annual workshop on Microprogramming, p.94-103, October 15-17, 1986, New York, New York, United States
• 8: W. W. Hwu , P. P. Chang, Exploiting parallel microprocessor microarchitectures with a compiler code generator, Proceedings of the 15th Annual International Symposium on Computer architecture, p.45-53, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 9: J.L. Linn, "SRDAG Compaction: A Generalization of Trace Scheduling to Increase the Use of Global Context Information," Proceedings of the 16th Microprogramming Workshop, Downingtown, PA., Oct., 1983.
• 10: Bogong Su , Shiyuan Ding , Lan Jin, An improvement of trace scheduling for global microcode compaction, Proceedings of the 17th annual workshop on Microprogramming, p.78-85, December 1984
• 11: John R. Ellis, Bulldog: a compiler for VLSI architectures, MIT Press, Cambridge, MA, 1986
• 12: Michael A. Howland , Robert A. Mueller , Philip H. Sweany, Trace scheduling optimization in a retargetable microcode compiler, Proceedings of the 20th annual workshop on Microprogramming, p.106-114, December 01-04, 1987, Colorado Springs, Colorado, United States [doi>10.1145/255305.255325]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Optimization

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: C

General Terms:
Algorithms, Design, Languages, Performance