Superoptimizer: a look at the smallest program
Open Access
- 1 October 1987
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 122-126
- https://doi.org/10.1145/36206.36194
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.Keywords
This publication has 3 references indexed in Scilit:
- Discovering machine-specific code improvementsPublished by Association for Computing Machinery (ACM) ,1986
- Automatic generation of peephole optimizationsPublished by Association for Computing Machinery (ACM) ,1984
- A practical method for code generation based on exhaustive searchPublished by Association for Computing Machinery (ACM) ,1982