6.001 Recitation – May 07, 2003

 

RI: Konrad Tollmar

 

Compile / Decompiling

 

http://mitpress.mit.edu/sicp/code/

 

(load "load-eceval-compiler")

 

(load "compiler")

 

(define test-expression

     '(define (f x y) (* (+ x y) (- x y))))

 

(define result (compile test-expression 'val 'return))

 

(pp result)

 

 

 

 

 

1. Compile using ec-eval

Compile

(if a b c) using a naive compiler that simply collect the used instructions.

What lines can be removed from the above compilation to more efficiently handle

ifs of this type?

 

1.   ev-if

2.       (assign unev (reg exp))

3.       (save unev)

4.       (save env)

5.       (save continue)

6.       (assign continue (label ev-if-decide))

7.       (assign exp (op if-predicate) (reg unev))

8.       (goto (label eval-dispatch))

9.   ev-if-decide

10.       (restore continue)

11.       (restore env)

12.       (restore unev)

13.       (test (op false?) (reg val))

14.       (branch (label ev-if-consequent))

15.  ev-if-alternative

16.       (assign exp (op if-alternative) (reg unev))

17.       (goto (label eval-dispatch))

18.  ev-if-consequent

19.       (assign exp (op if-consequent) (reg unev))

20.       (goto (label eval-dispatch))

 

 

 

2. Compile with linkage

 

(define (compile exp target linkage)

  (cond ((self-evaluating? exp)

         (compile-self-evaluating exp target linkage))

...

        ((application? exp)

         (compile-application exp target linkage))

        (else (error "Unknown exp type -- COMPILE” exp))))

 

 

 

(define (compile-self-evaluating exp target linkage)

 (end-with-linkage linkage

   (make-instruction-sequence '(env) (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))))))

 

(define (end-with-linkage linkage instruction-sequence)

  (preserving '(continue)   ;ignore this for now

   instruction-sequence

   (compile-linkage linkage)))

 

 

(define (compile-linkage linkage)

  (cond ((eq? linkage 'return)

         (make-instruction-sequence '(continue) '()

           '((goto (reg continue)))))

 

        ((eq? linkage 'next)

         (empty-instruction-sequence))

 

        (else

         (make-instruction-sequence '() '()

           `((goto (label ,linkage)))))))

 

 

 

a.     (compile '10 'val 'next)

b.     (compile '10 'val 'return)

c.     (compile '10 'val 'after-x-lookup)

 

d.     (compile 'x 'val 'next)

e.     (compile 'x 'val 'return)

f.     (compile 'x 'val 'after-x-lookup)

 

3. Preserving registers

What registers has to be preserved when compiling a combination?

 

(define (compile-application exp target linkage)

  (let ((proc-code (compile (operator exp) 'proc 'next))

        (operand-codes

         (map (lambda (operand) (compile operand 'val 'next))

              (operands exp))))

    (preserving '(env continue)

     proc-code

     (preserving '(proc continue)

      (construct-arglist operand-codes)

      (compile-procedure-call target linkage)))))

 

 

4. Decompiling

Decompile following to a scheme expression:

 

1.      (assign proc (op lookup-variable-value) (const -) (reg env))

2.      (assign val (const 2))

3.      (assign argl (op list) (reg val))

4.      (assign val (op lookup-variable-value) (const x) (reg env))

5.      (assign argl (op cons) (reg val) (reg argl))

6.      (test (op primitive-procedure?) (reg proc))

7.      (branch (label primitive-branch14))

8.     compiled-branch13

9.      (assign continue (label after-call12))

10.   (assign val (op compiled-procedure-entry) (reg proc))

11.   (goto (reg val))

12.  primitive-branch14

13.   (assign val (op apply-primitive-procedure) (reg proc) (reg argl))

14.  after-call12

15.   (goto (reg continue))

 

1.     (assign val (op lookup-variable-value) (const a) (reg env))

2.     (test (op false?) (reg val))

3.     (branch (label false-branch16))

4.     true-branch17

5.     (assign val (op lookup-variable-value) (const b) (reg env))

6.     (goto (label after-if15))

7.     false-branch16

8.     (assign val (op lookup-variable-value) (const c) (reg env))

9.     after-if15

10.  (goto (reg continue))

 
1.      (assign val (op make-compiled-procedure) (label entry4) (reg env))
2.      (goto (reg continue))
3.     entry4
4.      (assign env (op compiled-procedure-env) (reg proc))
5.      (assign env (op extend-environment) (const (x)) (reg argl) (reg env))
6.      (assign proc (op lookup-variable-value) (const +) (reg env))
7.      (assign val (const 2))
8.      (assign argl (op list) (reg val))
9.      (assign val (op lookup-variable-value) (const x) (reg env))
10.   (assign argl (op cons) (reg val) (reg argl))
11.   (test (op primitive-procedure?) (reg proc))
12.   (branch (label primitive-branch7))
13.  compiled-branch6
14.   (assign val (op compiled-procedure-entry) (reg proc))
15.   (goto (reg val))
16.  primitive-branch7
17.   (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
18.   (goto (reg continue))
19.after-call5

 

 

 

5. A larger example

Consider the following code output by the compiler:

 

     1.    (assign val (op make-compiled-procedure) (label entry2) (reg env))

     2.    (goto (label after-lambda1))

     3.  entry2

     4.    (assign env (op compiled-procedure-env) (reg proc))

     5.    (assign env (op extend-environment) (const (a)) (reg argl) (reg env))

     6.    (save continue)

     7.    (save env)

     8.    (assign proc (op lookup-variable-value) (const >) (reg env))

     9.    (assign val (const 0))

    10.    (assign argl (op list) (reg val))

    11.    (assign val (op lookup-variable-value) (const a) (reg env))

    12.    (assign argl (op cons) (reg val) (reg argl))

    13.    (test (op primitive-procedure?) (reg proc))

    14.    (branch (label primitive-branch11))

    15.  compiled-branch10

    16.    (assign continue (label after-call9))

    17.    (assign val (op compiled-procedure-entry) (reg proc))

    18.    (goto (reg val))

    19.  primitive-branch11

    20.    (assign val (op apply-primitive-procedure) (reg proc) (reg argl))

    21.  after-call9

    22.    (restore env)

    23.    (restore continue)

    24.    (test (op false?) (reg val))

    25.    (branch (label false-branch4))

    26.  true-branch5

    27.    (assign val (op lookup-variable-value) (const a) (reg env))

    28.    (goto (reg continue))

    29.  false-branch4

    30.    (assign proc (op lookup-variable-value) (const -) (reg env))

    31.    (assign val (op lookup-variable-value) (const a) (reg env))

    32.    (assign argl (op list) (reg val))

    33.    (test (op primitive-procedure?) (reg proc))

    34.    (branch (label primitive-branch8))

    35.  compiled-branch7

    36.    (assign val (op compiled-procedure-entry) (reg proc))

    37.    (goto (reg val))

    38.  primitive-branch8

    39.    (assign val (op apply-primitive-procedure) (reg proc) (reg argl))

     40.    (goto (reg continue))

    41.  after-call6

    42.  after-if3

    43.  after-lambda1

    44.    (perform (op define-variable!) (const f) (reg val) (reg env))

    45.    (assign val (const ok)))

    46.    (goto (reg continue))

 

A. What source code expression was compiled to produce lines 8-20 of the object code?

B. For lines 30-40?

C. For line 8-40?

D. What is the overall expression that compiled into the object code shown?

 

 

6. A second larger example

Consider the following code output by the compiler:

 

1.     (assign val (op make-compiled-procedure) (label entry24) (reg env))

2.     (goto (reg continue))

3.     entry24

4.     (assign env (op compiled-procedure-env) (reg proc))

5.     (assign env (op extend-environment) (const (f)) (reg argl) (reg env))

6.     (assign val (op make-compiled-procedure) (label entry25) (reg env))

7.     (goto (reg continue))

8.     entry25

9.     (assign env (op compiled-procedure-env) (reg proc))

10.  (assign env (op extend-environment) (const (x)) (reg argl) (reg env))

11.  (assign proc (op lookup-variable-value) (const f) (reg env))

12.  (save continue)

13.  (save proc)

14.  (assign proc (op lookup-variable-value) (const f) (reg env))

15.  (assign val (op lookup-variable-value) (const x) (reg env))

16.  (assign argl (op list) (reg val))

17.  (test (op primitive-procedure?) (reg proc))

18.  (branch (label primitive-branch28))

19.  compiled-branch27

20.  (assign continue (label after-call26))

21.  (assign val (op compiled-procedure-entry) (reg proc))

22.  (goto (reg val))

23.  primitive-branch28

24.  (assign val (op apply-primitive-procedure) (reg proc) (reg argl))

25.  after-call26

26.  (assign argl (op list) (reg val))

27.  (restore proc)

28.  (restore continue)

29.  (test (op primitive-procedure?) (reg proc))

30.  (branch (label primitive-branch31))

31.  compiled-branch30

32.  (assign val (op compiled-procedure-entry) (reg proc))

33.  (goto (reg val))

34.  primitive-branch31

35.  (assign val (op apply-primitive-procedure) (reg proc) (reg argl))

36.  (goto (reg continue))

37.  after-call29

 

A. What source code expression was compiled to produce lines 14-24 of the object code?

B. For lines11-36?

C. For lines 9-35?

D. What is the overall expression that compiled into the object code shown?

E. This code was compiled in such a way that a tail recursive call was produced. How would it differ if a simpler compiler had ignored that optimization?

F. How can you hand optimize out the need for binding

x in the environment?

G. Can you do the same for

f?