Essentials of Compilation
Jeremy G. Siek
Indiana University
Mutable Variables and Remove Complex Operands
Consider the following program that does a set! within an operand of an addition.
Why isn't this issue a problem in Python?
(let ([x 2])
(+ x (begin (set! x 40) x)))
What is the result?
Naive version of Remove Complex Operands would produce:
(let ([x 2])
(let ([tmp (begin (set! x 40) x)])
(+ x tmp)))
What is the result?
Pass: Uncover get!
Core issue: reading from a mutable variable is not a "pure" operation, so we shouldn't treat it as atomic for purposes of Remove Complex Operands.
First, we mark reads from mutables with get!.
(let ([x 2])
(let ([y 0])
(+ y (+ x (begin (set! x 40) x)))))
(let ([x 2])
(let ([y 0])
(+ y (+ (get! x) (begin (set! x 40) (get! x))))))
Remove Complex Operands with get!
Second, translate get! like any other complex operand.
(let ([x 2])
(let ([y 0])
(+ y (let ([t1 (get! x)])
(let ([t2 (begin (set! x 40) (get! x))])
(+ t1 t2))))))
(let ([x 2])
(let ([y 0])
(+ y (+ (get! x) (begin (set! x 40) (get! x))))))
Explicate Control: Loops
explicate_stmt(While(test, body, []), cont) =
test'
body'
cont
Explicate Control: Effect Contexts
With the addition of Begin, the Racket folks now need explicate_effect.
explicate-effect : exp -> tail -> tail
(define/override (explicate-assign e x cont)
(match e
[(Begin es body)
(define body^ (explicate-assign body x cont))
(for/foldr ([curr body^]) ([e es])
(explicate-effect e curr))]
…
[else (super explicate-assign e x cont-block)]
))
Explicate Effect
It's like explicate_tail, but when exp has no side effects, it can be discarded.
(define/public (pure? e)
(match e
[(Var x) #t]
[(Int n) #t]
…
[else #f]))
(define/public (explicate-effect e cont)
(match e
[(? pure?) cont]
[(SetBang x rhs) (explicate-assign rhs x cont)]
…
))
Register Allocation
Use the dataflow analysis we discussed last lecture to implement liveness analysis.
Building the interference graph stays the same, as does the graph coloring.
Challenge: Constant Propagation
When a variable's value is a constant, replace uses of the variable with the constant.
Implement this optimization using dataflow analysis.
start:
movq $42, a
movq a, b
movq b, %rax
jmp conclusion
start:
movq $42, a
movq $42, b
movq $42, %rax
jmp conclusion