A critical analysis of the global optimization problem for horizontal microcode (phase-coupled, compaction, code motion, compilation)
Vicki H. Allan · 1986
The major phases of microcode generation include register assignment, code selection, global optimization, and local compaction. Register assignment binds target machine registers to intermediate language variables. Code selection replaces an intermediate language specification of the function of the microprogram with a target machine implementation of that function. Global optimization performs code motion and code transformations within and beyond basic block boundaries. Little research has been done on the problems of phase-coupled code generation and microcode generation. This thesis investigates of the problem of phase-coupled microcode generation, noting that the problem has not been adequately defined, and therefore the proposal of solutions is somewhat premature. The purpose is to expose the nature of the problem, propose an efficient method for computing microprogram properties, to lay out interdependencies between the various phases, and to weigh possible solutions to problems of phase-coupling. A working retargetable microcode compiler is used to test various hypotheses. In-roads have been made in defining how the phases interact and at what level the interaction should be manipulated. Results indicate there is great potential in attempting to solve the microcode generation problem in a phase-coupled manner, but much study is required at every level of interaction. Pre code selection possibilities are numerous, but difficult to assess. Symbolic register assignment is helpful as it eliminates extra loads and stores that occur when register assignment between blocks is not coordinated. Compaction under timing restrictions is studied, algorithms suggested, and heuristics applied. The use of absolute node timings is found to be of importance in the compaction process. Compacting in forward and reverse directions are compared. The interactions between various phases are studied and possible mechanisms for interaction are explored. Although no set of specific heuristics can be proposed at this time, the research strongly suggests that coupling has great potential and effort used tuning heuristics and refining interactions will be well spent. The dependency of heuristics on the architecture is a recurring theme in the research.