The calling convention passes the integer argument in
$a0, returns the result in $v0, and uses jal with $ra for a call and its return address. The callee returns using jr $ra. Its stack frame grows downwards from $sp and must be removed before returning, restoring the caller's stack pointer.The
$s processor registers are callee-saved registers: a callee that uses $s0 or $s1 must restore their incoming values. The $a, $v, and $t processor registers are caller-saved registers; a caller must preserve any of their values that it needs after a call. Consequently foo keeps its own argument in $s0 and the first call's result in $s1, where nested calls preserve them. Because a nested jal overwrites $ra, foo also saves its incoming return address. Every recursive activation has its own stack frame.The supplied MIPS instructions use the paper's simplified convention: pseudoinstructions such as
subi are accepted, and control transfers have no branch delay slot. The completed code below follows that convention. A hardware implementation with delayed control transfers requires suitable scheduling or nop instructions throughout the supplied code as well.The entry sequence creates one 12-byte stack frame, then preserves the return address and both used callee-saved registers:The closing sequence reverses these effects:Loads must precede deallocation because their offsets refer to the current stack frame. The return value in
subi $sp, $sp, 12 # allocate three four-byte words
sw $ra, 0($sp) # save return address of this activation
sw $s0, 4($sp) # save caller's s0
sw $s1, 8($sp) # save caller's s1lw $ra, 0($sp) # recover return address of this activation
lw $s0, 4($sp) # restore caller's s0
lw $s1, 8($sp) # restore caller's s1
addi $sp, $sp, 12 # deallocate the frame
jr $ra # return to the caller$v0 is deliberately retained. Saving $ra is essential even though it is not an $s processor register: otherwise the second nested call would destroy the address to which this activation must return.The missing MIPS instructions, in order, areThe comparison
bne $t0, $0, fooRet1
subi $a0, $s0, 3
add $v0, $s1, $v0slti $t0, $s0, 3 makes $t0 nonzero exactly when , so the first instruction selects the base case. The second forms from the saved argument, rather than relying on $a0 surviving the first call. After the second call, $s1 holds bar(y-2) and $v0 holds bar(y-3); the final addition puts their sum in $v0, as required by the calling convention.The blanks are Although the immediate call increases the argument, substitution into
x < 2 and return x - foo(x + 1). The compiled slti and bne select the first branch exactly for . Otherwise addi forms , jal foo returns its value in $v0, and sub $v0, $s0, $v0 subtracts that value from the preserved . Thus the complete high-level implementation isproc bar(val x : int) : int
begin if x < 2 then
return 1
else
return x - foo(x + 1)
end
endfoo's two recursive calls decreases the corresponding bar arguments to and whenever the recursive branch is entered. The mutual recursion therefore terminates on ordinary integer inputs, assuming sufficient stack space and no machine arithmetic overflow.Keep both the limit and current argument in callee-saved registers, so a call to At every
foo preserves them. Under the same no-delay-slot convention, useli $s0, n
li $s1, 1
slti $t0, $s0, 1
bne $t0, $0, testEnd
testLoop:
move $a0, $s1
jal foo
break 1
beq $s1, $s0, testEnd
addi $s1, $s1, 1
b testLoop
testEnd:
break 0
b testEndbreak 1, $s1 is the tested value and $v0 is its result. Resuming after the breakpoint continues to the next value; after the program reaches its separate final stop. The initial guard handles with no calls. Testing equality before incrementing also avoids overflowing the loop variable after the final call when is the largest positive machine integer. As with the supplied procedures, evaluating all calls assumes enough stack space and representable arithmetic results. Articles by others on the same topic
There are currently no matching articles.