Superoptimizer: a look at the smallest program

ABSTRACT

Given an instruction set, the superoptimizer finds the shortest program to compute a function. Startling programs have been generated, many of them engaging in convoluted bit-fiddling bearing little resemblance to the source programs which defined the functions. The key idea in the superoptimizer is a probabilistic test that makes exhaustive searches practical for programs of useful size. The search space is defined by the processor's instruction set, which may include the whole set, but it is typically restricted to a subset. By constraining the instructions and observing the effect on the output program, one can gain insight into the design of instruction sets. In addition, superoptimized programs may be used by peephole optimizers to improve the quality of generated code, or by assembly language programmers to improve manually written code.

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: Jack W. Davidson , Christopher W. Fraser, Automatic generation of peephole optimizations, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.111-116, June 17-22, 1984, Montreal, Canada
• 3: Peter B. Kessler, Discovering machine-specific code improvements, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.249-254, June 25-27, 1986, Palo Alto, California, United States
• 4: David W. Krumme , David H. Ackley, A practical method for code generation based on exhaustive search, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.185-196, June 23-25, 1982, Boston, Massachusetts, United States

INDEX TERMS

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

General Terms:
Algorithms, Design