Exercise 5.11.  When we introduced save and restore in section 5.1.4, we 
didn't specify what would happen if you tried to restore a register that 
was not the last one saved, as in the sequence

(save y)
(save x)
(restore y)

There are several reasonable possibilities for the meaning of restore:

a.  (restore y) puts into y the last value saved on the stack, 
regardless of what register that value came from. This is the way our 
simulator behaves. Show how to take advantage of this behavior to 
eliminate one instruction from the Fibonacci machine of section 5.1.4 
(figure 5.12).

b.  (restore y) puts into y the last value saved on the stack, but only 
if that value was saved from y; otherwise, it signals an error. Modify 
the simulator to behave this way. You will have to change save to put 
the register name on the stack along with the value.

c.  (restore y) puts into y the last value saved from y regardless of 
what other registers were saved after y and not restored. Modify the 
simulator to behave this way. You will have to associate a separate 
stack with each register. You should make the initialize-stack operation 
initialize all the register stacks.

————————————————————————————————————————————————————————————————————————

a.

Fig. 5.12 from text:

(controller
   (assign continue (label fib-done))
 fib-loop
   (test (op <) (reg n) (const 2))
   (branch (label immediate-answer))
   ;; set up to compute Fib(n - 1)
   (save continue)
   (assign continue (label afterfib-n-1))
   (save n)                           ; save old value of n
   (assign n (op -) (reg n) (const 1)); clobber n to n - 1
   (goto (label fib-loop))            ; perform recursive call
 afterfib-n-1                         ; upon return, val contains Fib(n - 1)
   (restore n)
   (restore continue)
   ;; set up to compute Fib(n - 2)
   (assign n (op -) (reg n) (const 2))
   (save continue)
   (assign continue (label afterfib-n-2))
   (save val)                         ; save Fib(n - 1)
   (goto (label fib-loop))
 afterfib-n-2                         ; upon return, val contains Fib(n - 2)
   (assign n (reg val))               ; n now contains Fib(n - 2)
   (restore val)                      ; val now contains Fib(n - 1)
   (restore continue)
   (assign val                        ;  Fib(n - 1) +  Fib(n - 2)
           (op +) (reg val) (reg n)) 
   (goto (reg continue))              ; return to caller, answer is in val
 immediate-answer
   (assign val (reg n))               ; base case:  Fib(n) = n
   (goto (reg continue))
 fib-done)

After afterfib-n-2, the register val will be altered, and a goto will be 
performed.  The goto will always be returning to either afterfib-n-1, 
afterfib-n-2, or fib-done.  In any of these cases, the value remaining 
in register n is not used.  This is why we can use it to hold the old 
value from register val, which we then add to the previous value which 
is restored into val, to get the total sum of Fib(n - 1) + Fib(n - 2).

The optimization then is to restore the saved value from val into n 
instead:

 afterfib-n-2
   (restore n)                        ; the value being restored actually was saved from val
   (restore continue)
   (assign val
           (op +) (reg n) (reg val))
   (goto (reg continue))



b.

(define (make-save inst machine stack pc)
  (let ((reg (get-register machine
                           (stack-inst-reg-name inst))))
    (lambda ()
      (push stack (list (stack-inst-reg-name inst) (get-contents reg)))    ;; changed
      (advance-pc pc))))
(define (make-restore inst machine stack pc)
  (let ((reg (get-register machine
                           (stack-inst-reg-name inst))))
    (lambda ()
      (let ((stored (pop stack)))
        (if (eq? (car stored) (stack-inst-reg-name inst))                  ;; changed
            (set-contents! reg (cadr stored))
            (error "restoring from stack value pushed from a different register")))
      (advance-pc pc))))

c.

skipped