A MIPS R-type instruction has the 32-bit instruction encodingFor
add $x,$y,$z, the processor register indices are , and , while . The main opcode selects the R-type family and the function field selects addition. The register file reads its two operands from instruction bits 25:21 and 20:16. In the original datapath, RegDst=1 selects bits 15:11 as the destination, ALUSrc=0 selects the second register file output, and ALUFunc=ADD makes the arithmetic logic unit add its inputs. The result returns to wdata; RegWrite=1 writes it to at the active clock edge. The zero output is irrelevant here.[ref]Digital systems, linear algebra, introduction to formal proof examination paper by the University of Oxford (2014). Question 1 datapath, printed page 2: the input-0 and input-1 multiplexer labels determine these control polarities
A MIPS I-type instruction instead has the instruction encodingFor
addi $x,$y,n, , , and the low sixteen bits contain the immediate operand. The register file supplies to the first arithmetic logic unit input. Set RegDst=0 to select bits 20:16 for the destination, and ALUSrc=1 to select the extended immediate operand for the second input. The opcode directly requests addition, so ALUFunc=ADD and RegWrite=1. The second register file read is unused. The returned result is written into .The sign extension circuit retains the low sixteen bits and copies bit 15 into all sixteen new high positions:Thus sign extension preserves the signed two's complement value:
0x7fff becomes 0x00007fff, whereas 0x8000 becomes 0xffff8000. For both instructions, the architectural result above assumes no signed overflow; the full MIPS architecture specifies an overflow exception, which is outside this simplified datapath.Add zero extension alongside sign extension, and a multiplexer controlled by a new signal
ExtSign to select between them before the existing immediate-input connection. Equivalently, make the extender itself selectable:Decode ori to ExtSign=0, RegDst=0, ALUSrc=1, RegWrite=1 and ALUFunc=OR. The arithmetic logic unit then performs bitwise OR between and the zero-extended immediate operand and writes the result to . Extend the arithmetic logic unit's control decoding if OR was not already available. Decode addi to ExtSign=1; the new signal is irrelevant for MIPS R-type instructions because ALUSrc=0.Zero extension matters even when the most significant immediate bit is one:
ori with 0x8000 must only affect the low half of the destination, whereas sign extension would incorrectly force every high bit to one.[ref]MIPS32 Architecture For Programmers Volume II by MIPS Technologies. ORI instruction entry: the 16-bit immediate is zero-extended before the logical operation
Use byte addresses, so adjacent 32-bit array elements are four bytes apart. The following MIPS instructions include harmless
sll $zero,$zero,0 instructions in every branch delay slot; the second load is followed by another independent instruction before its value is consumed, also accommodating an early MIPS architecture with a load-use delay. All mnemonics here denote individual machine instructions. beq $t3,$zero,done # n=0: do not access any array
sll $zero,$zero,0
loop:
lw $t4,0($t0) # current a element
lw $t5,0($t1) # current b element
addiu $t0,$t0,4 # advance a; also separates lw from its use
subu $t6,$t4,$t5 # current difference, modulo 2^32
sw $t6,0($t2) # store current c element
addiu $t1,$t1,4
addiu $t2,$t2,4
addiu $t3,$t3,-1 # one fewer element remains
bne $t3,$zero,loop
sll $zero,$zero,0
done:A loop invariant at the head of the loop, after completed iterations, is that the three addresses point to elements , the count is , and every output element before equals the corresponding difference. One iteration reads element , stores its difference and advances to , preserving the loop invariant. The remaining count is a nonnegative loop variant decreasing by one, so the loop ends with .
The code uses
subu to avoid signed-overflow traps: the suffix does not restrict the operands to unsigned values. Its precise result isFor representable signed differences this is exactly . If trapping signed arithmetic is required instead, use sub and assume all differences are representable. The arrays must occupy valid word-aligned storage with no address wrap; the usual separate output array avoids overwriting unread inputs.Make the code a leaf procedure called
array_diff, copy the four argument processor registers into the temporaries used above, and replace the final label by a return. The copies are real addu instructions, avoiding an unexplained move pseudo-instruction:array_diff:
addu $t0,$a0,$zero
addu $t1,$a1,$zero
addu $t2,$a2,$zero
addu $t3,$a3,$zero
# insert the code of (i), including its initial zero-count test
# use the local label array_diff_done in place of done
array_diff_done:
jr $ra
sll $zero,$zero,0In the literal insertion, the
done: line from (i) is the array_diff_done: line displayed here; it is not a second return block. Under the usual calling convention, temporary processor registers are caller-saved. This procedure calls no other procedure and changes no saved processor registers, so it needs no stack frame or saved return address.For a 32-bit constant , define and using its unsigned binary representation. Load it with
lui followed by ori; both are single MIPS instructions. For base addresses and count , the main program is:main:
lui $a0,H_A
ori $a0,$a0,L_A
lui $a1,H_B
ori $a1,$a1,L_B
lui $a2,H_C
ori $a2,$a2,L_C
lui $a3,H_N
ori $a3,$a3,L_N
jal array_diff
sll $zero,$zero,0
main_after_call:
# c now contains the differences; continue the main program hereHere each
H_... and L_... is an assembler-time numeric constant, not an executed operation. lui places the high half and clears the low half; ori inserts the low half without sign extension. ThusThe jal instruction saves the return address after its branch delay slot in $ra; jr $ra resumes at main_after_call. A main routine that itself needs to return to a caller must save its incoming $ra before jal and restore it afterwards. Articles by others on the same topic
There are currently no matching articles.