This document shows how a few of the Mac1 machine language instructions are fetched, decoded, and executed via the microprogram which functions as the interpreter for machine language. Example: Store Local STOL x 1001 xxxx xxxx xxxx 0: mar := pc; rd; { fetch } 1: pc := pc + 1; rd; 2: ir := mbr; if n then goto 28; { decode } 28: tir := lshift(ir + ir); if n then goto 40; 29: tir := lshift(tir); if n then goto 35; 30: alu := tir; if n then goto 33; 33: a := ir + sp; { execute: 1001 STOL } 34: mar := a; mbr := ac; wr; goto 10; 10: wr; goto 0; Note that line 2 checks the first bit of the 1001 xxxx xxxx xxxx. Since this bit is a 1, the number is seen as negative, and the jump to line 28 in the microcode is taken. Line 28 is tricky. It checks the second bit of the 1001 xxxx xxxx xxxx since the sum of the ir and itself is just double the number, which is the same as left shifting the 1001 xxxx xxxx xxxx by 1 bit. Thus it is checking to see if 001x xxxx xxxx xxx0 is negative. The answer is no, so the jump is not taken. After this number goes through the ALU, the shifter left shifts it one more bit and the result, 01xx xxxx xxxx xx00, is put into the tir register. Line 29 then checks this number to see if it is negative, thus checking the 3 bit of the original number 1001 xxxx xxxx xxxx. Remember that the left shift is done after the ALU operations, so that the test for negative is not affected by the shifter at all. The shifted value, 1xxx xxxx xxxx x000, is put in the tir and the jump to line 35 is not taken. Line 30 just passes the new tir value through the ALU to test it. Since it starts with a 1, it is negative, and the jump to line 33 in the microcode is taken. Line 33 begins the execution of the STOL instruction. It adds to the stack pointer value the original ir value, 1001 xxxx xxxx xxxx. This may seem strange due to the leading 1001 bits. However, the low order 12 bits just contain the sum of the sp value and the xxxx xxxx xxxx. This number is used as the address of where to write to in main memory. (Since the mar and the bus leading to it are only 12 bits wide, the first 4 garbage bits don't affect things at all.) The AC value is thus written to this sp + x spot in main memory. We have now indeed stored the AC value at a location in memory x items below the top of stack. That's a store local. It took 2.5 cycles to fetch the instruction, 3.5 cycles to decode it, and 3 cycles to execute it. All together it took 9 cycles to handle the STOL instruction. Example: Subtract Direct SUBD x 0011 xxxx xxxx xxxx 0: mar := pc; rd; { fetch } 1: pc := pc + 1; rd; 2: ir := mbr; if n then goto 28; { decode } 3: tir := lshift(ir + ir); if n then goto 19; 4: tir := lshift(tir); if n then goto 11; 11: alu := tir; if n then goto 15; 15: mar := ir; rd; { execute: 0011 SUBD } 16: ac := ac + 1; rd; { use x - y = x + 1 + inv(y) } 17: a := inv(mbr); 18: ac := ac + a; goto 0; To do subtraction when the hardware ALU does not do subtraction, you use addition and boolean not (inverse): R - T = R + 2's complement(T) = R + inv(T) + 1 = R + 1 + inv(T) Thus the microprogram carries out subtraction by doing a boolean not and two additions. It took 2.5 cycles to fetch the instruction, 3.5 cycles to decode it, and 4 cycles to execute it. All together it took 10 cycles to handle the SUBD instruction. Example: Jump Positive (really jump non-negative) JPOS x 0100 xxxx xxxx xxxx 0: mar := pc; rd; { fetch } 1: pc := pc + 1; rd; 2: ir := mbr; if n then goto 28; { decode } 3: tir := lshift(ir + ir); if n then goto 19; 19: tir := lshift(tir); if n then goto 25; 20: alu := tir; if n then goto 23; 21: alu := ac; if n then goto 0; { execute } 22: pc := band(ir, amask); goto 0; Note that if the AC value is negative, line 21 simply sends us back to line 0 in the microcode to start fetching the next machine language instruction. But if the AC value is non-negative, the jump in the machine language code is done by putting a new value into the program counter (line 22 of the microcode). This new PC value is found by doing a boolean AND of the instruction itself, the 0100 xxxx xxxx xxxx, with amask, which contains 0000 1111 1111 1111, so that the result is 0000 xxxx xxxx xxxx. In other words, this extracts the low order 12 bits from the instruction and uses this as the address to jump to. It took 2.5 cycles to fetch this instruction, 3.5 cycles to decode it, and either 1 or 2 cycles to execute it. In all, it takes 7 or 8 cycles to handle the JPOS instruction. Example: Increment Stack Pointer INSP x 1111 1100 xxxx xxxx 0: mar := pc; rd; { fetch } 1: pc := pc + 1; rd; 2: ir := mbr; if n then goto 28; { decode } 28: tir := lshift(ir + ir); if n then goto 40; 40: tir := lshift(tir); if n then goto 46; 46: tir := lshift(tir); if n then goto 50; 50: tir := lshift(tir); if n then goto 65; 65: tir := lshift(tir); if n then goto 73; 73: tir := lshift(tir); if n then goto 76; 74: a := band(ir, smask); { execute: 1111 110* INSP } 75: sp := sp + a; goto 0; Note that the microprogram interpreter only really checks the first 7 bits in the decoding process. The 8th bit is not checked as there is no machine language instruction 1111 1101 xxxx xxxx. The microprogram thus executes it as INSP just the same as 1111 1100 xxxx xxxx. The smask contains 0000 0000 1111 1111, so that the result of doing the boolean AND of ir and smask is xxxx xxxx, the low order 8 bits of the INSP instruction. This is the number added onto the stack pointer. It took 2.5 cycles to fetch this instruction, 6.5 cycles to decode it, and 2 cycles to execute it. All together it took 11 cycles to handle the INSP instruction. How to add a new machine language instruction to the machine: We can use the fact, noted above, that the bit pattern 1111 1101 is not used. We will change the microprogram interpreter so that it recognizes this bit pattern as our new instruction, but still correctly sees 1111 1100 as INSP. (There are other unused bit patterns that could be taken over by new machine language instructions if you wish.) We need to change the microprogram starting at line 73. The lines that follow get moved down by 1 so that we can insert a new line 74 to do decoding based on the 8th bit. That is, the new line 74 decides whether we have the new instruction or INSP. 73: tir := lshift(tir); if n then goto 77; { 1111 110x or 1111 111x ? } 74: alu := tir; if n then goto 81; { 1111 1100 or 1111 1101 ? } 75: a := band(ir, smask); { execute: 1111 1100 INSP } 76: sp := sp + a; goto 0; 77: alu := tir; if n then goto 84; { 1111 1110 or 1111 1111 } 78: a := band(ir, smask); { execute: 1111 1110 DESP } 79: a := inv(a); 80: a := a + 1; goto 76; 81: ... code for NEW instruction ... { execute: 1111 1101 } 82: ... code for NEW instruction ... 83: ... code for NEW instruction ... Note that line 73 now has a condition jump to line 77, not 76. Line 77 has a conditional jump to line 84. This is the one past the last line number for the microprogram. Jumping here stops the simulator. Here I am assuming that executing the new instruction takes 3 lines of microcode. You must adjust the number in line 77 to be 1 more than the number of the last microinstruction. It may be 84, it may not. Finally, note that line 80 has been adjusted to contain a jump to line 76, not 75. Of course, in the end you must modify the 80 lines of 32 bits to reflect the revised microcode. The number of lines will now be more than 80, so be sure to change the line that gives the number of microinstructions. Begin with a file, such as mic015.txt, that contains the old microcode and edit it carefully.