1. Field of the Invention
This application relates to compilers and, specifically, to generating code sequences.
2. Background Art
Automatic code generation is as old as FORTRAN, but the code sequences produced by these standard techniques are very far from optimal. Conventional tools for automatic code generation, and even optimization, are designed as part of a compiler used in edit-compile-debug loops. Automatic code generation tools are constrained by the requirement that they be able to generate hundreds, thousands, or millions of instructions per second. Although such tools can generate indifferent code quickly they have little hope of generating code that is nearly optimal.
The only automatic code generation approaches known to aim at near optimal code are Massalin's “supercompiler” and Granlund's GNU “superoptimizer”. Massalin's supercompiler uses brute-force enumeration of all possible code sequences, and is therefore glacially slow. (See: Henry Massalin, “Superoptimizer—A Look at the Smallest Program,” Proceedings of the Second International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS II), Oct. 5–8, 1987, Palo Alto, Calif., ACM Press, IEEE-CS, ISBN 0-89791-238-1; SIGARCH Computer Architecture News 15(5), SIGOPS Operating System Review 21(4), SIGPLAN Notices 22(10). pages 122–126). Introduced by Torbjorn Granlund of MIT, the GNU superoptimizer uses the same technique as Massalin's (See: ftp://prep.ai.mit.edu/pub/gnu/superopt/superopt-2.5.tar.gz). Granlund states about the GNU superoptimizer that: “[t]he superoptimizer is a function sequence generator that uses an exhaustive generate-and-test approach to finding the shortest assembly instruction sequence for a given function.” Namely, conventional approaches use an exhaustive search and test of all possible code sequences to find a shorter program. For target processor architectures such as the 68000, the program found with conventional approaches is the shortest and presumably fastest, but for more complex multiple-issue architectures this may not be the case. Accordingly, to achieve better results the present invention addresses these and related issues.