Local Code Generation and Compaction in Optimizing Microcode Compilers
Steven R. Vegdahl · 1982
Horizontal microarchitectures often have features that make it difficult for a compiler to produce good object code from a high-level language. Although the problem of compacted microcode into a near-minimal number of microinstructions has received a great deal of attention, other phases of the compiler have not been studied as thoroughly. This dissertation explores methods of generating quality microcode for horizontal microarchitectures, compacting the microcode, and the interaction between code generation and compaction. There are often several code sequences that perform the same computation for a given microarchitecture. If the code generation and compaction phases of the compiler are executed sequentially, the code generator may not be able to determine the best code because a code sequence that compacts well in one situation may contain several bottlenecks in another. This dissertation explores three methods of coupling the code generation and compaction phases of the compiler, and concludes that subtle micromachine features make it very difficult to produce good code unless the code generator actually produces several candidate code sequences that are compacted and compared with one another. This dissertation also explores machine-independent methods of generating microcode. One aspect of the code generation problem--that of generating constants intelligently--is discussed in detail. A technique called constant unfolding is presented that can be used to produce code sequences that generate constants in unusual ways during execution; such code sequences often lead to more compact code when the literal field of the microinstruction is a bottleneck. The classical microcode compaction problem is also examined. We show that this NP-complete problem can be solved in polynomial time if the number of registers in the micromachine is bounded, and use this result to argue that the problem is not general enough. A heuristic algorithm is presented for solving the general problem.