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