CS525 -- Programming Project Four

In this final part of the project, you will implement an IC code optimizer and a simple MIPS code generator. This will be for a restricted language which does not include floats or subroutines. You will write your compiler so that it outputs MiniMIPS assembly language to the standard output instead of IC code (I had planned on having you generate the hex code, but this does not seem to be worth it in the time we have left). This code should follow the MiniMIPS language presented in the handout on the website and distributed in class.

Details of the Project

Your project must provide the following functionality:

Source Language

Target Language

• There are 16 registers ($0 -- $15), where $0 is constant 0, $13 -- $15 are reserved for special uses, and $1 -- $12 are general purpose registers that you may use to hold operands during the MIPS program.
• You will not use the instructions jr and jal; for our purposes there will be no difference between signed and unsigned numbers, so you can forget about "addiu" as well.
• In arithmetic instructions, constants can ONLY occur in one place: the third argument to "addi". Target and source operands of all other arithmetic instructions (add, sub, mult, div, mod) MUST be registers. Constants can be negative, so "subi" could be simulated by adding a negative constant.
• In your IC program, all jumps and branches use absolute word addresses; but in MiniMIPS, jumps ("j") use the word address of the target, and hence the targets in our IC jump statements are correct; however, branches ("beq") use a word offset from the instruction following the branch. Thus, you will need to convert your IC branch statements to offset form (this can be done any time after optimization).
• The only instructions which can refer to memory locations are lw and sw; these instructions must use constant offsets and registers as base, in the form "offset(base)". Offsets may be negative, and are in bytes.
• References to static variables (which are the only kind of variables we will have) must be made by using their offset within the static region. For simplicity, we will assume the memory addresses start at 0 in the static region (instead of 0x400000). Thus, if the variable A occurs at offset 12 within the static data region, and B is an array of ints starting at offset 20, you would do the following:

  Action             MiniMIPS Code
  ------             -------------
  
  $4 = A;            lw $4, 12($0)
  
  A = $3;            sw $3, 12($0)
  
  $2 = B[2];         lw $2, 28($0)
  
  B[A] = $5;         addi $1, $0, 12
                     sw $5, 20($1)
  

  Note carefully how in the last example, you must load the offset of one of the variables into a register, and then use this as base.

Code Optimization

• Branch/jump folding -- No branch or jump should have a jump as a target; you must propagate targets so that a branch or jump will proceed directly to the final target of a series of jumps. Note that a jump to a branch can not be folded, since you do not know whether the branch will be taken or not.
• Constant folding -- I will NOT require you to do aggressive constant folding as described in class (i.e., all computation involving constants is performed at compile time), but I WILL require you to rewrite the rules for computing offsets for arrays and structs, so that as much precomputing of constant offsets is performed as possible at compile time. The notes provided a silly method of accumulating values with a temporary variable, and you should rewrite this so that whenever the offset from a structure or array variable is in fact constant, then this constant will appear in the reference (e.g., "A[24]") instead of being computed in the code. You do not need to fold constants that are introduced by dumb programmers who write things like "A = 5; B = A + 5;".
• Dead code elimination -- If a statement is unreachable, it should be eliminated. There is a fairly straight-forward way to do this, based on a recursive depth-first search. Mark statements as "visited" using a recursive procedure which starts at the top of the program and traverses all possible execution paths (default is to visit the next statement, but you should take all jumps, and go both ways at a branch). Take a look at an algorithms for depth-first traversal of a graph in your nearest algorithms book for inspiration. After finding out which instructions are reachable, you can delete the unreachable ones; just make sure to adjust your jump and branch targets to account for the new ordering of statements.

Code Generation

You must generate code using the method shown in class, by calculating next use information for all variables and then allocating registers using the algorithm from lecture (GetReg()).

Error Checking

Friendly Advice

You can proceed one of two basic ways to do this: (1) Keep your IC code generator exactly as it is, and add code to optimize your IC program, and then perform the translation into MiniMIPS, or (2) modify your IC generator so that it generates MiniMIPS code, but without registers.

I did (1), because I had some existing code to work from, but I recommend strongly that you do (2). This is not the way most books explain the phases of the compilation process, but I think it is actually the simplest thing to do for this last project. Here are the steps I suggest you follow:

1. Rewrite your IC generator to generate code which is just like MiniMIPS code but which uses variables instead of registers:
   • Do not generate the "add $sp, ..." statement at the beginning of the translation of main, nor the "sub $sp, ..." statement at the end of the translation of main.
   • Don't insert "main" into the symbol table (if you did), and DO insert all temporary variables that you generate into the symbol table (they will be integers).
   • Use the "slt" and "beq" combination instead of "blt". This is actually trivial: wherever you generated "blt A, B, ...", now generate "slt Ti, A, B" followed by "beq Ti, 0, ..." for a new temp Ti, and then (since this does the opposite of the blt), change all the relational token to their converse (e.g., replace LESSTHAN with GREATEROREQUAL and so on).
   • Change your arithmetic statements so that the only place a non-zero constant appears is as the third argument of "addi" (which is the only new arithmetic operator, since all our IC integer arithmetic operators are also MiniMIPS operators). A zero will be replaced by the register $0, and all variables will be replaced by registers assigned by your register allocator. For example:

       
     IC Code            MiniMIPS Code
     -------            -------------
     move A, -, B       add A, 0, B
     
     move A, -, 4       addi A, 0, 4
     
     add A, B, C        add A, B, C
     
     sub C, 0, A        sub C, 0, A
     
     add A, B, 4        addi A, B, 4
     
     add A, 8, C        addi A, C, 8
     
     sub A, B, 3        addi A, B, -3
     
     sub A, B, -2       addi A, B, 2
     
     add A, 4, 9        addi Ti, 0, 4
                        addi A, Ti, 9
     
     

     Any of these variables could be array references (e.g. "A[t23]") as well; the only significant issue is where the non-zero constants appear (only in an addi).
   • You must change the silly way of generating offsets for structured data so that offsets are expressed as constants whenever possible, as described in the section on optimization.
   • NOTE: Your MiniMIPS code so far has NO use of lw or sw; these will be introduced by the register allocation process. All variables, including temporaries, are static, and are in the symbol table for static variables and have been assigned offsets in the static region. At this point, there is no difference between temporaries and non-temporaries (except that temps will only be of int type, and non-temps may be ints, structs, or arrays).
2. Add various fields to the data structure for instructions (visited, leader, label, etc.) which will be used during the optimization process. Write your jump folding algorithm and traversal algorithm to find unreachable code.
3. Determine the basic blocks by finding all leaders; this is quite simple, as you simply run through the code and mark as a leader the first statement, every target of a jump or branch, and every statement following a jump or branch. A basic block is a leader plus every following non-leader.
4. Add a label for each statement which is its location in the original array; now a jump or branch is a jump to a statement with a particular label, rather than a location in the array. Now you can do the deletions of unreachable code.
5. Add an array "nextUse" to each entry in the symbol table of some size sufficient to handle any realistic basic block (say 100 entries).
6. Run through the array, and for each leader, stop and calculate for that basic block nextuse information (entering it into the symbol table arrays just mentioned) and then allocate registers as shown in lecture. During register allocation, you will replace a reference to the constant 0 by the register $0, you will leave a reference to a constant (which can occur only as the third argument to addi) unchanged, and you will replace a reference to a variable by a reference to a register. The latter process may involve generating lw or sw instructions (as discussed in lecture) and so you may need to add instructions to the code array (by moving the rest of the code down to provide room for the insertion). At the end of the basic block, you will have to store all registers back out to memory using a series of sw instructions (since in our naive method, no value in a register is considered valid past the end of the basic block.
7. Now run through the code array and for each jump and branch, search for the location of the target by scanning the labels and adjust the jump targets. Finally, for each branch, replace the absolute location by an offset from the location of the instruction following the branch.

What to Hand In