Recitation 24

Today: Compilation

Basic Idea

What extra work does interpreter do?

Consider a simple combination expression
-- for example, (f 84 96)

Interpreter
-- classifies expression
-- detects end of arg list
-- ...

Compiler just
-- evals operators & operands
-- assembles arg list
-- applies

Result of compiling operator here is
-- (assign proc (op lookup-var) (const f) (reg env))
-- what other optimization has compiler performed?

What about the Analyzer-Evaluator?
-- also eliminated classification at "runtime"
-- but still ready for any contingency
-- saves registers whether or not used (eg in eval of 84 and 96)
-- but compiler can look at whole expression & eliminate unnecessary stack operations

Gross Structure

Look at top-level dispatch:

(define (compile exp target linkage)
  (cond ((self-evaluating? exp)
             (compile-self-evaluating exp target linkage))
        ((quoted? exp) (compile-quoted exp target linkage))
        ((variable? exp)
             (compile-variable exp target linkage))
        ((assignment? exp)
             (compile-assignment exp target linkage))
        ((definition? exp)
             (compile-definition exp target linkage))
        ((if? exp) (compile-if exp target linkage))
            ((lambda? exp) (compile-lambda exp target linkage))
        ((begin? exp)
             (compile-sequence (begin-actions exp)
                               target
                               linkage))
        ((cond? exp) (compile (cond->if exp) target linkage))
        ((application? exp)
             (compile-application exp target linkage))
        (else
             (error "Unknown expression type -- COMPILE" exp))))

(define (compile-self-evaluating exp target linkage)
  (end-with-linkage linkage
   (make-instruction-sequence '() (list target)
    `((assign ,target (const ,exp))))))

(define (compile-variable exp target linkage)
  (end-with-linkage linkage
   (make-instruction-sequence '(env) (list target)
    `((assign ,target
              (op lookup-variable-value)
              (const ,exp)
              (reg env))))))
 

Stack Optimizations

How does compiler avoid unnecessary save/restores?

Instead of just appending instruction sequences
-- use special procedure preserving
-- takes list of registers to be preserved
-- (preserving regs seq1 seq2) produces an instruction sequence
            that is like seq1 appended to seq2
            except that seq2 can assume that registers in reg have the values they had at the start

To implement preserving
-- determine which registers are modified or needed by a sequence
-- then only inserts saves/restores that are actually required
-- this is encapsulated in an ADT for instruction sequences

Example of use of preserving:

(define (compile-assignment exp target linkage)
  (let ((var (assignment-variable exp))
        (get-value-code
         (compile (assignment-value exp) 'val 'next)))
    (end-with-linkage linkage
    (preserving '(env)
      get-value-code
      (make-instruction-sequence '(env val) (list target)
       `((perform (op set-variable-value!)
                  (const ,var)
                  (reg val)
                  (reg env))
         (assign ,target (const ok))))))))

Sample Compiled Code

(compile-and-display 'x)
((assign val (op lookup-variable-value) (const x) (reg env)) (goto (reg continue)))
;Value: #[unspecified-return-value]
 

(compile-and-display '#t)
((assign val (const #t)) (goto (reg continue)))
;Value: #[unspecified-return-value]

(compile-and-display '(if x 1 2))
((assign val (op lookup-variable-value) (const x) (reg env))
 (test (op false?) (reg val))
 (branch (label false-branch2))
 true-branch3
 (assign val (const 1))
 (goto (reg continue))
 false-branch2
 (assign val (const 2))
 (goto (reg continue))
 after-if1)
;Value: #[unspecified-return-value]

(compile-and-display '(lambda(x) (if x 1 2)))
((assign val (op make-compiled-procedure) (label entry7) (reg env))
 (goto (reg continue))
 entry7
 (assign env (op compiled-procedure-env) (reg proc))
 (assign env (op extend-environment) (const (x)) (reg argl) (reg env))
 (assign val (op lookup-variable-value) (const x) (reg env))
 (test (op false?) (reg val))
 (branch (label false-branch9))
 true-branch10
 (assign val (const 1))
 (goto (reg continue))
 false-branch9
 (assign val (const 2))
 (goto (reg continue))
 after-if8
 after-lambda6)
;Value: #[unspecified-return-value]

(compile-and-display '(define f (lambda(x) (if x 1 2))))
((assign val (op make-compiled-procedure) (label entry12) (reg env))
 (goto (label after-lambda11))
 entry12
 (assign env (op compiled-procedure-env) (reg proc))
 (assign env (op extend-environment) (const (x)) (reg argl) (reg env))
 (assign val (op lookup-variable-value) (const x) (reg env))
 (test (op false?) (reg val))
 (branch (label false-branch14))
 true-branch15
 (assign val (const 1))
 (goto (reg continue))
 false-branch14
 (assign val (const 2))
 (goto (reg continue))
 after-if13
 after-lambda11
 (perform (op define-variable!) (const f) (reg val) (reg env))
 (assign val (const ok))
 (goto (reg continue)))
;Value: #[unspecified-return-value]

(compile-and-display '(f #f))
((assign proc (op lookup-variable-value) (const f) (reg env))
 (assign val (const #f))
 (assign argl (op list) (reg val))
 (test (op primitive-procedure?) (reg proc))
 (branch (label primitive-branch18))
 compiled-branch17
 (assign val (op compiled-procedure-entry) (reg proc))
 (goto (reg val))
 primitive-branch18
 (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
 (goto (reg continue))
 after-call16)
;Value: #[unspecified-return-value]

(compile-and-display '(f x))
((assign proc (op lookup-variable-value) (const f) (reg env))
 (assign val (op lookup-variable-value) (const x) (reg env))
 (assign argl (op list) (reg val))
 (test (op primitive-procedure?) (reg proc))
 (branch (label primitive-branch21))
 compiled-branch20
 (assign val (op compiled-procedure-entry) (reg proc))
 (goto (reg val))
 primitive-branch21
 (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
 (goto (reg continue))
 after-call19)
;Value: #[unspecified-return-value]

Examples that show save/restore:

(compile-and-display '(if (f x) 1 2))
((save continue)
 (assign proc (op lookup-variable-value) (const f) (reg env))
 (assign val (op lookup-variable-value) (const x) (reg env))
 (assign argl (op list) (reg val))
 (test (op primitive-procedure?) (reg proc))
 (branch (label primitive-branch22))
 compiled-branch21
 (assign continue (label after-call20))
 (assign val (op compiled-procedure-entry) (reg proc))
 (goto (reg val))
 primitive-branch22
 (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
 after-call20
 (restore continue)
 (test (op false?) (reg val))
 (branch (label false-branch18))
 true-branch19
 (assign val (const 1))
 (goto (reg continue))
 false-branch18
 (assign val (const 2))
 (goto (reg continue))
 after-if17)
;Value: #[unspecified-return-value]

(compile-and-display '(+ (f x) 1))
((assign proc (op lookup-variable-value) (const +) (reg env))
 (save continue)
 (save proc)
 (assign val (const 1))
 (assign argl (op list) (reg val))
 (save argl)
 (assign proc (op lookup-variable-value) (const f) (reg env))
 (assign val (op lookup-variable-value) (const x) (reg env))
 (assign argl (op list) (reg val))
 (test (op primitive-procedure?) (reg proc))
 (branch (label primitive-branch37))
 compiled-branch36
 (assign continue (label after-call35))
 (assign val (op compiled-procedure-entry) (reg proc))
 (goto (reg val))
 primitive-branch37
 (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
 after-call35
 (restore argl)
 (assign argl (op cons) (reg val) (reg argl))
 (restore proc)
 (restore continue)
 (test (op primitive-procedure?) (reg proc))
 (branch (label primitive-branch40))
 compiled-branch39
 (assign val (op compiled-procedure-entry) (reg proc))
 (goto (reg val))
 primitive-branch40
 (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
 (goto (reg continue))
 after-call38)
;Value: #[unspecified-return-value]
 

---

Recitation problem

Decompile the following register code
-- ie, what expression was compiled to produce these machine instructions?

•(assign proc (op lookup-variable-value) (const list) (reg env))
•(assign val (op lookup-variable-value) (const y) (reg env))
•(assign argl (op list) (reg val))
•(assign val (op lookup-variable-value) (const x) (reg env))
•(assign argl (op cons) (reg val) (reg argl))
•(assign val (op lookup-variable-value) (const +) (reg env))
•(assign argl (op cons) (reg val) (reg argl))