The shifts multiply the original array indices by four, and the following additions form byte memory addresses. The load into
$s0 changes the variable itself, but the address of the next element of A has already been saved. The complete effect isi = x
x = A[i]
B[y] = x + A[i + 1]Here
i is a fresh temporary. Both the assignment to and the assignment to matter. Writing only would omit the observable change to . The interpretation assumes four-byte array elements, valid aligned addresses, and arithmetic within range; the source uses trapping signed additions. The address of is computed before changes.Use the conventional integer calling convention:
$a0 holds the argument and $v0 holds the result. The function is recursive, so every call must preserve its own return address and original argument. The first recursive result must also survive the second call; a caller-saved register alone would not protect it.This implementation reserves a 32-byte stack frame, keeping the stack pointer eight-byte aligned. Offsets 0–15 are available as the outgoing argument area, 16 stores the original argument, 20 stores the first result, 24 is padding, and 28 stores the return address. It changes no callee-saved register. Assemble in classic MIPS delayed-branch mode with instruction reordering disabled, such as
.set noreorder.foo:
addiu $sp,$sp,-32 # allocate 32-byte aligned frame
sw $ra,28($sp) # save caller return address
sw $a0,16($sp) # save original n
beq $a0,$zero,foo_base
sll $zero,$zero,0
addiu $t0,$zero,1
beq $a0,$t0,foo_base
sll $zero,$zero,0
addiu $t0,$zero,2
beq $a0,$t0,foo_base
sll $zero,$zero,0
addiu $a0,$a0,-1
jal foo
sll $zero,$zero,0
sw $v0,20($sp) # preserve foo(n-1) across next call
lw $a0,16($sp) # recover original n
sll $zero,$zero,0
addiu $a0,$a0,-3
jal foo
sll $zero,$zero,0
lw $t0,20($sp)
sll $zero,$zero,0
addu $v0,$v0,$t0 # combine the two recursive results
beq $zero,$zero,foo_return
sll $zero,$zero,0
foo_base:
addu $v0,$a0,$zero # base case result is n
foo_return:
lw $ra,28($sp)
sll $zero,$zero,0
addiu $sp,$sp,32 # release the frame
jr $ra
sll $zero,$zero,0All displayed operation mnemonics denote single machine instructions. In particular,
sll $zero,$zero,0 is the actual harmless shift encoding often abbreviated by the pseudoinstruction nop; addu $v0,$a0,$zero performs a copy without the move pseudoinstruction. Each branch or jump has an explicit harmless branch delay slot, and harmless shifts also separate loads from their subsequent uses. The base cases return the original argument; other calls return the sum of the two recursive values. Every return restores the saved return address and exactly undoes the stack allocation.[ref]MIPS32 Architecture For Programmers Volume II by MIPS Technologies. Revision 2.00, ADDIU and ADDU, pp. 37–38; JAL and JR, pp. 139 and 144
The stated domain is nonnegative integer , with sufficient stack space and a result representable in the intended integer type. The non-trapping additions implement that mathematical result within range; beyond it, machine wraparound would require a separately specified integer semantics.
A register file with 256 entries needs bits per register index. Under the intended assumption that eight times as many instructions are obtained by expanding the primary opcode field, its width grows from six to bits. Thus opcode: 9 bits; rs, rt and rd: 8 bits each.
These four fields alone require bits, already exceeding a 32-bit instruction encoding. Retaining the five-bit shift amount and six-bit function field of a MIPS R-type instruction gives 44 bits. The processor's data word need not become wider merely because it has more registers.
The opcode conclusion is conditional: MIPS also uses secondary function fields, so an eightfold increase in the number of semantic operations does not by itself force a nine-bit primary opcode. That is the straightforward field-expansion interpretation of this exercise.
On the same primary-opcode expansion interpretation, opcode: 9 bits; each register field: 8 bits. The printed
rd is a naming slip: a conventional MIPS I-type instruction has fields rs and rt, with the latter sometimes serving as the destination. There is no separate rd field.Keeping the original 16-bit immediate requires bits per instruction. If the instruction encoding were held at 32 bits, only seven bits would remain for the immediate, reducing immediate arithmetic and addressing ranges. A uniform encoding for both enlarged formats would have to accommodate the longer R-type case too; any padding or revised format policy must be specified separately. Register count and instruction width do not determine data-word width.
More processor registers can reduce register spills and the associated loads and stores. A richer instruction set may also replace several old machine instructions by one new operation. Both effects can decrease the number of instructions in a compiled program, although a particular program might obtain no benefit.
Wider instruction encodings increase the bytes per instruction. Consequently the total machine-code size can increase or decrease: approximately, it is instruction count times average encoded instruction width, with alignment and padding also relevant. There is no universal net direction without the program and revised encoding. The length of assembly language source text is a separate matter and is not determined by instruction bit widths.
Articles by others on the same topic
There are currently no matching articles.