Code Generation


To understand how to determine execution order, allocate registers and produce assembly language text:

Due dates

You must complete the PEP tasks (individually), and then hand in the requested material (as a group) at the beginning of class on Monday, December 7. This assignment is worth 40 points.


This assignment assumes that you are familiar with the SPIM abstraction described in An Encoder for SPIM. That specification can be used directly in an Eli implementation, or it can serve as a design document for a C++ implementation.

Operand Evaluation Order

The target program tree imposes order on evaluation of certain of its nodes, and allows others to be evaluated in any order (see Waite, Section 9.1.3). As discussed in Section 11.1, the child with the largest register requirement should be evaluated first if there is a choice. Sethi-Ullman numbering is a method for determining the register requirements of a tree.

Left-to-right evaluation is provided as a default for the children of every node in the abstract target program tree. Part of the code generator implementation is to override that default for nodes in which a choice on the basis of register requirements is allowed by the SPIM abstraction (e.g. in iRegrr and fRegrr constructs).

Another situation in which the default evaluation order must be overridden is when the semantics of the language define short circuit evaluation. The SPIM abstraction itself must be extended to express short-circuit evaluation, and then assembly language text appropriate to that abstraction must be generated.

The default evaluation order is established by a lower-context symbol computation of the Code attribute. This computation is usually overridden by a rule computation in the specific context of interest (e.g. in the iRegrr rule).

Register Assignment

The fundamental principle in assigning registers is to minimize the number of instructions that simply move values about. An Encoder for SPIM defines the top-down algorithm discussed in class: Each node has an integer-valued attribute defining the set of free registers of a certain class and an integer-valued attribute defining the actual register number. This algorithm is sufficient for allocating SPIM registers.

Instruction selection

The PTGNode-valued attribute Instr is used in SpimAsm.fw to represent the assembly code implementation of the specific action required by a node. By default, execution of the Instr action follows evaluation of the children of that node. When the default evaluation order is overridden, the PTGNode described by the Instr attribute can be placed anywhere in the evaluating sequence.

By using a separate attribute for the specific action required by a node, the specification separates concerns: evaluation order and instruction selection can be specified separately. In determining the final sequence, the Instr attribute represents the node's local action independent of what that action is; the Instr attribute can be defined independent of where the action it represents occurs relative to execution of the node's children.


Implement the code generation task of a compiler that translates C-- to assembly code for the MIPS R2000, using any tools and techniques you wish. Combine your code generator with the , name analyzer, type analyzer, data mapper, and action mapper that you implemented for earlier assignments. The resulting program must read input text, construct the corresponding source program tree, and report violations of all context conditions if the text is lexically and syntactically correct. If the input text is incorrect according to the lexical or syntactic rules of C--, your program must report at least the first error. It may terminate immediately after reporting the first error, or it may continue in an attempt to detect further errors.

If no errors are detected in the input text, your program must construct the corresponding SPIM assembly code program, and print a representation of that program. If errors are detected, your program may construct and print assembly code or it may terminate after reporting all of the errors. The assembly code constructed in this case need not reflect the source program, but it must be acceptable as input to the SPIM assembler.

Test your program by applying it to the C-- test suite. If you feel that the test suite is inadequate, provide any additional tests you deem necessary. Your program should not detect any errors in any conformance test, and it should detect at least one error in every deviance test. The SPIM simulator should be able to execute the assembly code translations of all of the programs in the conformance test suite. When appropriate data is supplied, each simulated execution should output the correct result for that input data.

Hand in the assembly code translation of the factorial program. A directory containing the complete source code (or specifications, if you used tools) for your program must be permitted for world read by 1700 on the due date for this assignment. You need not make it available to be read by others before that time. Hand in the location of this directory (machine and path name).

Complete your personal postmortem, and submit it via the web before class on the due date of this assignment.

Revision 1.4 (1998/11/21 16:05:10)