An orthogonal model for code generation
James R. Cordy · 1986
Code generation is part of programming language compilation that is concerned with choosing the actual implementation of programming language constructs in terms of computer hardware. We can characterize the code generation problem as a mapping from the abstract, mathematical world of programming languages to the concrete, discrete world of computing machines. Objects in each of these worlds can be expressed in terms of two fundamental concepts: operators and operands. Viewed in this way, every existing systematic approach to code generation is based on the same model. This traditional model begins by decomposing abstract operand structure into sequences of abstract operators. Code generation is then accomplished as a single complex process that tends to obscure the mapping between language objects and their machine representation. We propose a new model, which we call the orthogonal model, that separates the implementation of abstract operators and abstract operands into two essentially independent parts. In the orthogonal model, abstract operand structure is left intact until implementation of abstract operators is complete. It then remains to implement abstract operands as a separate step. We present a code generator structure based on this model, which is simpler and more easily understood than existing structures. We present fundamental algorithms of the orthogonal code generator and show how these algorithms can be easily parameterized across a large class of target computers. We show that this parameterization can be achieved using a menu-based technique that describes the target machine as a subset of the union of machine capabilities across the class. Finally, we show how these machine menus can be derived from a machine description which is concise, compact and convenient for human understanding.