The Basic Assignment, for Everyone

Make a copy of Assembler.java, and call the copy AdvancedAssembler.java. Write the improved assembler for Part 2 of the lab in AdvancedAssembler.java. The improved assembler should support the following features:

• Immediate values in the li instruction that cannot be represented in 8 bits.
• Labels in the la instruction that cannot be represented in 8 bits.
• Labels in the bneq and bnez instructions for which the offset cannot be represented in 8 bits.
• Immediate values as the third argument to ALU instructions such as add and slt. Allow immediate values that are too big to fit into 8 bits.

For labels, you should take the easy route, which is to treat all labels as if they require more than 8 bits. The technique that you will use for big values will work for small values as well. It will just use more instructions than are really necessary. However, you should not generate extra instructions for li or ALU instructions that contain immediate values in the range -128 to 127. In such cases, you only need one instruction for the li case, and two instructions for the ALU case.

In this version of the assembler, one assembly language instruction can produce more than one machine language instruction. You will have to modify the first pass of your assembler to take that into account. You will have to modify the second (or third) pass to actually generate the extra machine language code.

You will often need to generate machine language code for loading a (potentially) big number into a register. This can be done with five machine language instructions. It can be done with the following method, which you should copy into AdvancedAssembler.java.

    /**
     * Generates 5 machine language instructions and adds them to binary program.
     * The instructions will load the number bigNumber into register number
     * destinationRegister.  Registers 12 and 13 are used for scratch work.
     * @param bigNumber the number to be loaded into destinationRegister.  Only
     *   the low-order 16 bits of this number are used; the other 16 bits are ignored.
     * @param destinationRegister a number in the range 0 to 15 inclusive giving
     *   the number of the register into which bigNumber is to be loaded.
     *   Note that it is ok for the destination register to be register 12 or 13.
     * @throws IllegalArgumentException if destinationRegister is out of range
     */
    private static void generateLoadBig(int bigNumber, int destinationRegister) {
        if (destinationRegister < 0 || destinationRegister > 15)
            throw new IllegalArgumentException("Bad register number: " + destinationRegister);
        int high = (~bigNumber >> 8) & 0xFF;
        int low = (~bigNumber) & 0xFF;
        int ins;
        ins = ISA.LUI << 12 | 12 << 8 | low;
        binaryProgram.add(Convert.decimalToBinary( ins, 16 ));
        ins = ISA.LI << 12 | 13 << 8 | 8;
        binaryProgram.add(Convert.decimalToBinary( ins, 16 ));
        ins = ISA.SRL << 12 | 12 << 8 | 12 << 4 | 13;
        binaryProgram.add(Convert.decimalToBinary( ins, 16 ));
        ins = ISA.LUI << 12 | 13 << 8 | high;
        binaryProgram.add(Convert.decimalToBinary( ins, 16 ));
        ins = ISA.NOR << 12 | destinationRegister << 8 | 13 << 4 | 12;
        binaryProgram.add(Convert.decimalToBinary( ins, 16 ));
    }

In class on Monday, we will discuss how this method works, and we will discuss how to implement some of the other things that you need to do.

Extras for Programming Pairs

For people working in pairs, there are a few more things that your assembler should support:

• Support SIMM values in lw and sw that are outside the range -8 to 7.
• Implement these extended instructions: jal, jr, b, and move.
• Implement these extended ALU instructions for logic: and, or, and not.

Note: The original file Inst.java has a bug that prevented the parser from recognizing the assembly language instruction not. You should get a copy of the fixed version from this link or from /classes/cs220/lab9-files.

Note: NOT A = A NOR 0,   A OR B = NOT (A NOR B),   A AND B = (NOT A) NOR (NOT B).There are a few test programs for this part of the lab in /classes/cs220/lab9-files/tests-c

For Extra Credit

The extra credit part of the assignment is to eliminate some of the unnecessary machine language instructions that are generated by the non-extra-credit version. If you do any extra credit work, be sure to document exactly what you have done in a comment at the top of the program. (Note: I have not done any of this extra credit work myself.)

It is annoying that the assembler generates extra machine language instructions for labels that could be implemented using an 8-bit LIMM and just one instruction. However it is complicated to optimize the number of instructions for these cases. The problem is that you don't necessarily know the location associated with the label during the first assemble pass, when you are counting machine language instructions. In some cases, of course, you do know, and one improvement would be to eliminate the extra machine language instructions in those case where you know during the first pass that you won't need them. This would, at least, provide more optimal code for backward jumps.

For more extra credit, you could be more ambitious than that. One idea is to add another pass to the assembler, after the first pass. The first pass does "worst-case" calculation of machine language instructions counts, and calculates label addresses based on the worst case. The second pass could recalculate the label addresses, using the worst-case information to decide how many machine language instructions to generate for la and for branch instructions. Since the recalculation can only shrink memory addresses, you won't get any invalid results. (However, you might still have some cases in which you use more machine language instructions than you need.)

You might even think of other ways to optimize the code that you generate!