In current microcode generation systems, one simplification that is frequently made is to assume an absence of timing restrictions. It is critical that timing is considered when the target architecture involves branch delays, volatile registers, or microoperations requiring multiple microinstructions to complete. A general form for representing synchronous timing in clocked microarchitectures and methods of compacting data-dependency graphs with general timing are described.>

The vertical migration of complex application code into horizontal microcode makes traditional methods of handwritten and hand-optimized microcode with primitive assembly languages impractical. Higher-level languages that permit abstraction from low-level timing and concurrency details are considered a major step toward alleviating the problem. This approach is feasible only if compilers for these languages exist that can produce high-quality microcode and that can be targeted to new machines with modest effort and high reliability. An overview is provided of the Horizon retargetable microcode compiler, which facilitates the production of highly optimized microcode and the targeting of the compiler to specific machines.>

Most work on automating the translation of high-level microprogramming languages into microcode has dealt with lexical and syntactic analysis and the use of manually produced macro tables for code generation. We describe an approach to and some results on the formalization and automation of the more difficult problem of retargeting local code generation in a machine-independent, optimizing microcode synthesis system. Whereas this problem is similar in many ways to that of retargeting local code generation in high-level language compilers, there are some major differences that call for new approaches. The primary issues addressed in this paper are the representation of target microprogrammable machines, the intermediate representation of local microprogram function, and general algorithmic methods for deriving local microcode from target machine and microcode function specifications. Of particular interest are the use of formal semantics and data flow principles in achieving both a general and reasonably efficient solution. Examples of the modeling of a representative horizontal machine (the PUMA) and the generation of microcode for the PUMA machine model from our working implementation are presented.

We consider the complexity of the problem of encoding microoperations into the fields of a control word on a horizontally microprogrammed machine, and show it to be NP-complete. The major result of this correspondence is a formalization of the microinstruction encoding problem, which makes the complexity argument straightforward.

A semantics based scheme for use in machine-independent microprogram synthesis is described. The input to the synthesis system consists of a micro-instruction set processor model and requirement specifications. Validity and transformation rules which are an integral part of the system are used in an attempt to prove the existence of a microprogram satisfying the requirements and if feasible such a microprogram can be extracted directly from the proof. The primary goal of this paper is to describe a system of validity and transformation rules for use in such a synthesis system.