Project E: Extensions to the MiniJava Compiler

Due: Friday, March 13 at 11:00 pm. Late assignments will be accepted without penalty until Saturday, March 14 at 11 pm, even if you have no official late days remaining. No assignments will be accepted after that time.

In this assignment you will make two required extensions to the target code generator. There are also some optional extensions you can add to the project for extra credit if you are interested, have time to implement them, and if you have already competed the required parts of the assignment.

Part A. Immediate Operands

Modify the x86 target code generator so that it can generate immediate operands for integer constant arguments, rather than moving the integer constant to a register and then using that register. For example, for MiniJava source like x+1, instead of generating the following x86 target code:

   movl %ebi(xoffset), %eax   // load x from stack
   movl $1, %ebx              // move constant 1 into register
   addl %ebx, %eax            // compute x+1
your modified compiler should generate the following:
   movl %ebi(xoffset), %eax   // load x from stack
   addl $1, %eax              // compute x+1

Your compiler should be able to perform this optimization whenever the first operand of a 2-argument x86 arithmetic, comparison, or move instruction, or the operand of a push instruction, is an integer constant. In the current x86 target code generator, this includes whenever the right-hand side of an assignment, the argument of the int-to-double unary operator, the length of an array allocation, the second argument of a non-divide integer binary expression, the second argument of an integer compare expression, and an argument of a call is an integer constant expression.

While there are obviously different ways to implement this optimization, we suggest you consider the following. Define an alternative version of codegen, e.g. codegenOrImmediate, which is invoked by methods in X86Target for any argument subexpressions that are allowed to be immediate operands. By default, codegenOrImmediate just does codegen, but for an ILIntConstantExpr, codegenOrImmediate invokes a special emit operation on the target, e.g. emitIntConstantOrImmediate, passing the value of the integer constant. This operation is implemented for the x86 to return a special immediate location, e.g. X86IntImmediateLocation, which remembers the constant. (Other targets implement this operation in their own way, to account for that target's treatment of immediate operands. It is always safe for a target to implement emitIntConstantOrImmediate just as emitIntConstant.) Finally, for those operands that allow immediates as an alternative to registers, the call to the regOperand helper can be replaced with a new regOrIntOperand helper, which tests the kind of location passed and invokes either regOperand (if the location is an X86Register) or intOperand (if the location is an X86IntImmediateLocation). To help monitor when the optimization is performed, the code for emitIntConstantOrImmediate can emit a comment indicating that the regular emitIntConstant code was optimized away. (This design, using two versions of codegen and different kinds of result locations, is analogous to how boolean-valued expressions can be code-generated in two different ways, depending on whether the result is being consumed by a conditional branch instruction or not.)

Develop test cases that demonstrate that your optimization is performed when it should be, and not performed when it shouldn't be. (You should also confirm that the existing sample programs continue to run correctly with your optimization enabled.) You can use the -printCode option to the MiniJava compiler to print out the assembly code that it produces.

Part B. Improved Register Allocation

Modify the x86 target code generator to eliminate redundant loads from stack locations for variables. For example, for MiniJava source like x+x, instead of generating the following x86 target code:

   movl %ebi(xoffset), %eax  // load x from stack
   movl %ebi(xoffset), %ebx  // load x from stack
   addl %ebx, %eax           // compute x+x
your modified compiler should generate the following:
   movl %ebi(xoffset), %eax  // load x from stack
   movl %eax, %ebx           // copy x from existing register location
   addl %ebx, %eax           // compute x+x

Likewise, for MiniJava source like x=...; ...x..., instead of generating the following x86 target code:

   movl %eax, %ebi(xoffset)  // store x to stack
   movl %ebi(xoffset), %ebx  // load x from stack
your modified compiler should generate the following:
   movl %eax, %ebi(xoffset)  // store x to stack
   movl %eax, %ebx           // copy x from existing register location

Your modified compiler should be able to replace loads from a variable's home stack location with a register move instruction whenever the variable's value has already been loaded into or stored from a register earlier in the same basic block (or more generally from the same trace back to the previous label statement or function entry) as long as the register hasn't been reallocated to some other value.

To implement this optimization, we suggest that you add an instance variable to the X86Target class that stores a map from stack offsets to register locations. The invariant of this map is that, whenever an offset maps to a register location, then that register holds the same value as the stack at that offset. You can define several helper functions for manipulating this map: clearStackContents() which resets the map to the empty map, forgetStackContents(Location) which drops any mappings for the given location, lookupStackContents(int offset) which returns the register location holding the contents of the stack at the given offset, or null if none, and recordStackContents(int offset, Location) which remembers that the given register location holds the contents of the stack at the given offset. These helpers can then be called to manipulate the map at the right places:

Develop test cases that demonstrate that your optimization is performed when it should be, and not performed when it shouldn't be. (You should also confirm that the existing sample programs continue to run correctly with your optimization enabled.) You can use the -printCodeoption to the MiniJava compiler to print out the assembly code that it produces.

Optional Extra-Credit Extensions

Choose some interesting extension to make to the MiniJava compiler, design and implement it, and develop test cases that demonstrate your new extension. This is strictly for extra credit, but if you have time you will learn a lot from doing this.

Some possible extensions include the following:

You should explain your extension in a separate text file and provide appropriate test cases if you do this. Submit this separately from the required part (if you do an extension). Put it in a separate directory tree in the archive you submit so it is clear which part of your submission is the required part and which is the extension.

What to Hand In

As usual, turn in the following:

  1. The entire source tree needed to build your compiler. Clearly identify any modifications to existing files using comments. We suggest you run a make clean first to reduce the number of files turned in.
  2. Your test cases demonstrating the improvements to your code generator.
  3. A transcript of running your compiler with flags appropriate for demonstrating the correctness of your changes.

Put your test programs in the SamplePrograms directory. Pack everything into an archive (zip or tar) and submit it. If you also do an optional extra-credit extension, this should be separated from the required part and clearly identified.