6.001 Recitation – May 07, 2003

• 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)

• What is a compiler?
• How?
• Why can compile optimize better?

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. (save env)

2. (save continue)

3. (assign continue (label after-pred21))

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

5. after-pred21

6.

7. (restore continue)

8. (restore env)

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

10. (branch (label false-branch23))

11. true-branch22

12.

13.

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

15. (goto (label continue))

16. false-branch23

17.

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

19. (goto (label continue))

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

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

3. (branch (label false-branch23))

4.true-branch22

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

6. (goto (label continue))

7.false-branch23

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

9. (goto (label continue))

2. Compile with linkage

EC-Eval

(assign val (reg exp))

(goto (reg continue))

Temp

(assign <target> (const <expr>)

(goto (reg continue))

` ,

(define (cpr exp target)

`(assign ,target (const ,exp)))

(cpr 'x 'val)

;Value: (assign val (const x))

(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 (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)))))))

(compile '10 'val 'next)

->

(assign val (const 10))

(compile '10 'val 'return)

->

(assign val (const 10))

(goto (reg continue))

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

->

(assign val (const 10))

(goto (label after-x-lookup))

(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))))))

(compile 'x 'val 'next)

->

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

(compile 'x 'val 'return)

->

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

(goto (reg continue))

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

->

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

(goto (label after-x-lookup))

3. Preserving registers

(preserving (list <reg₁> <reg₂>) <seq₁> <seq₂>)

produces one of the following four sequences of instructions, depending on how <seq₁> and <seq₂> use <reg₁> and <reg₂>:

What registers has to be preserved when compiling a combination?

[(save continue)]

[(save env)]

<evaluate operator; result in proc>

[(restore env)]

[(save proc)]

<evaluate operands; result in argl>

[(restore proc)]

[(restore continue)]

<apply procedure in proc to args in argl, and link>

(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

(assign val (const 3))

(perform (op define-variable!)

(const x) (reg val) (reg env))

(assign val (const ok))

(goto (reg continue))

ð (define x 3)

Decompile following to a scheme expression:

For the evaluation of a combination, look for

• The procedure to be put into the proc register

• The consing up of the argument list in the argl register.

• Remember that the arguments are evaluated right to left in the compiler

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))

(+ x 2)

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))

 
(if a b c)
 
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

(lambda (x) (+ x 2))

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?

(> a 0)

B. For lines 30-40?

(- a)

C. For line 8-40?

(if (> a 0) a (- a))

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

(define f (lambda(a) (if …)))

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?

(f x)

B. For lines11-36?

(f (f x))

C. For lines 9-35?

(lambda (x) (f (f x)))

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

(lambda (f) (lambda (x) (f (f x))))