4.6 Extending Our Instruction Set

Even though MARIE's instruction set is sufficient to write any program we wish, there are a few instructions we can add to make programming much simpler. We have 4 bits allocated to the opcode, which implies we can have 16 unique instructions, and we are only using 9 of them. We add the instructions from Table 4.6 to extend our instruction set.

0
A
B



C

JnS X]
Clear
AddI X



JumpI X

Store the PC at address X and jump to X + 1.
Put all zeros in AC.
Add indirect: Go to address X. Use the value at X
        as the actual address of the data 
        operand to add to AC.

Jump indirect: Go to address X. Use the value at X
        as the actual address of the location to
        jump to.

The JnS (jump-and-store) instruction allows us to store a pointer to a return instruction and then proceeds to set the PC to a different instruction. This enables us to call procedures and other subroutines, and then return to the calling point in our code once the subroutine has finished. The Clear instruction moves all zeros into the accumulator. This saves the machine cycles that would otherwise be expended in loading a 0 operand from memory.

The AddI instruction (as well as the JumpI instruction) uses a different addressing mode. All previous instructions assume the value in the data portion of the instruction is the direct address of the operand required for the instruction. The AddI instruction uses the indirect addressing mode. (We present more on addressing modes in Chapter 5.) Instead of using the value found at location X as the actual address, we use the value found in X as a pointer to a new memory location that contains the data we wish to use in the instruction. For example, if we have the instruction AddI 400, we would go to location 400, and assuming we found the value 240 stored at location 400, we would go to location 240 to get the actual operand for the instruction. We have, essentially, allowed for pointers in our language.

Returning to our discussion of register transfer notation, our new instructions are represented as follows:

JnS

MBR ¬ PC
MAR ¬ X
M[MAR] ¬ MBR
MBR ¬ X
AC ¬ 1
AC ¬ AC + MBR
PC ¬ AC

Clear

AC ¬ 0

AddI X

MAR ¬ X
MBR ¬ M[MAR]
MAR ¬ MBR
MBR ¬ M[MAR]
AC ¬ AC + MBR

JumpI X

MAR ¬ X
MBR ¬ M[MAR]
PC ¬ MBR

Table 4.7 summarizes MARIE's entire instruction set.

Let's look at some examples using the full instruction set.

Listing 4.1:

Here is an example using a loop to add five numbers:

Address Instruction Comments
    100 Load         Addr /Load address of first number to be added
    101 Store        Next /Store this address as our Next pointer
    102 Load         Num /Load the number of items to be added
    103 Subt         One /Decrement
    104 Store        Ctr /Store this value in Ctr to control looping
    105 Clear        /Clear AC
Loop, 106 Load       Sum/Load the Sum into AC
    107 AddI         Next /Add the value pointed to by location Next
    108 Store        Sum/Store this Sum
    109 Load         Next /Load Next
    10A Add          One /Increment by one to point to next address
    10B Store        Next /Store in our pointer Next
    10C Load         Ctr /Load the loop control variable
    10D Subt         One /Subtract one from the loop control variable
    10E Store        Ctr /Store this new value in the loop control variable
    10F Skipcond     00 /If control variable < 0, skip next instruction
    110 Jump         Loop /Otherwise, go to Loop
    111 Halt         /Terminate program
Addr, 112 Hex        118 /Numbers to be summed start at location 118
Next, 113 Hex         0 /A pointer to the next number to add
Num, 114 Dec         5 /The number of values to add
Sum, 115 Dec         0 /The sum
Ctr, 116 Hex         0 /The loop control variable
One, 117 Dec         1 /Used to increment and decrement by 1
    118 Dec          10 /The values to be added together
    119 Dec          15
    11A Dec          20
    11B Dec          25
    11C Dec          30

Although the comments are reasonably explanatory, let's walk through Example 4.1. Recall that the symbol table stores [label, location] pairs. The Load Addr instruction becomes Load 112, because Addr is located at physical memory address 112. The value of 118 (the value stored at Addr) is then stored in Next. This is the pointer that allows us to "step through" the five values we are adding (located at addresses 118, 119, 11A, 11B, and 11C). The Ctr variable keeps track of how many iterations of the loop we have performed. Since we are checking to see if Ctr is negative to terminate the loop, we start by subtracting one from Ctr. Sum (with an initial value of 0) is then loaded in the AC. The loop begins, using Next as the address of the data we wish to add to the AC. The Skipcond statement terminates the loop when Ctr is negative by skipping the unconditional branch to the top of the loop. The program then terminates when the Halt statement is executed.

Example 4.2 shows how you can use the Skipcond and Jump instructions to perform selection. Although this example illustrates an if/else construct, you can easily modify this to perform an if/then structure, or even a case (or switch) structure.

Listing 4.2:

This example illustrates the use of an if/else construct to allow for selection. In particular, it implements the following:

if X = Y then
  X := X - 2
else
  Y := Y - X;
  
Address     Instruction     Comments
If, 100     Load     X      /Load the first value
    101     Subt     Y      /Subtract value of Y and store result in AC
    102     Skipcond 01     /If AC = 0, skip the next instruction
    103     Jump     Else   /Jump to the Else part if AC is not equal to 0
Then, 104   Load     X      /Reload X so it can be doubled
    105     Add      X      /Double X
    106     Store    X      /Store the new value
    107     Jump     Endif  /Skip over Else part to end of If
Else, 108   Load     Y      /Start the Else part by loading Y
    109     Subt     X      /Subtract X from Y
    10A     Store    Y      /Store Y _ X in Y
Endif,      10B      Halt   /Terminate program (it doesn't do much!)
    X,      10C      Dec     12 /Load the loop control variable
    Y,      10D      Dec     20 /Subtract one from the loop control variable

Example 4.3 demonstrates how JnS and JumpI are used to allow for subroutines. This program includes an END statement, another example of an assembler directive. This statement tells the assembler where the program ends. Other potential directives include statements to let the assembler know where to find the first program instruction, how to set up memory, and whether blocks of code are procedures.

Listing 4.3:

This example illustrates the use of a simple subroutine to double any number and can be coded:

    100 Load    X     /Load the first number to be doubled
    101 Store   Temp     /Use Temp as a parameter to pass value to Subr
    102 JnS     Subr     /Store return address, jump to procedure
    103 Store   X     /Store first number, doubled
    104 Load    Y     /Load the second number to be doubled
    105 Store   Temp     /Use Temp as a parameter to pass value to Subr
    106 JnS     Subr     /Store return address, jump to procedure
    107 Store    Y     /Store second number, doubled
    108 Halt     /End program
X,  109 Dec     20
Y,  10A Dec     48
Temp, 10B Dec   0
Subr, 10C Hex   0     /Store return address here
    10D Clear     /Clear AC as it was modified by JnS
    10E Load    Temp     /Actual subroutine to double numbers
    10F Add     Temp     /AC now holds double the value of Temp
    110 JumpI   Subr     /Return to calling code
        END

Using MARIE's simple instruction set, you should be able to implement any high-level programming language construct, such as loop statements and while statements. These are left as exercises at the end of the chapter.