1
\$\begingroup\$

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-004-computation-structures-spring-2017/c12/c12s3/procedures_answers.pdf

I don't understand how the linkage pointer can be the same value for multiple iterations in problem 2. Shouldn't the BR(f,LP) instruction change the LP value?

Here is the doc for the ISA: https://computationstructures.org/notes/pdfs/beta.pdf

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

First it's important to recognize that this is a recursive algorithm, so the code is going to keep calling itself until the answers start bubbling back up.

BR(f,LP) branches to the label f, and stores the PC+4 into the designated register LR.

Each time that executes, the value of LR will be updated; but it's repeatedly executing from the same line of code, so it's going to be setting the the address of the next instruction each time, too.

In a RISC type machine such as the Beta, if a procedure wants to use the conventional linkage register (for example to make another call, in this case the recursive one) then it needs to save that value and later restore it, and in fact we see exactly that in the provided code:

PUSH LP
do stuff that trashes LP
POP LP
JMP LP

What actually is a bit odd about this is that they are targeting a register-rich 32-bit RISC architecture with an ABI calling convention that puts procedure arguments on the stack rather than in registers the way something like a typical ARM ABI would for efficiency... a teaching simplification, I guess.

And then the greater irony is that even though this is C code, it hails from the realm of Scheme, so it's a little surprising to see they haven't managed to get this seemingly(?) tail-recursive algorithm to compile to the favorite 6.001 theme of tail recursion, rather than create a new stack frame for each nested call...


Incidentally, generally speaking questions here need to stand on their own and not rely on links for key material, as this one did.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.