Web page for IU Compiler Course for Fall 2020
View the Project on GitHub IUCompilerCourse/IU-P423-P523-E313-E513-Fall-2020
Example program:
(let ([sum (vector 0)])
(let ([_ (for ([x (vector 1 2 3)])
(vector-set! sum 0 (+ x (vector-ref sum 0))))])
(vector-ref sum 0)))
(assign y (for ([x seq]) body)) cont-label
===>
vec = seq'
i = 0
n = (vector-length vec)
goto loop-label
loop-label:
if (eq? i n)
goto cont-label
else
goto body-label
body-label:
x = (vector-ref vec i)
body'
i = i + 1
goto loop-label
Recall that this is a backwards analysis.
The rule for an assignment statement:
(S - {x}) \/ R(e)
x = e
S
state = set of variables
transfer function:
f(x = e, S) = (S - {x}) \/ R(e)
meet operator: (merge state information)
meet : set * set -> set
meet S1 S2 = S1 \/ S2 (set union)
partial order:
set containment (reverse of subset-or-equal)
apply the transfer function to all the blocks, over and over again until the live-before sets for the blocks stop changing.
start: {} vec = (vector 1 2 3) {vec} i = 0 {i,vec} n = (vector-length vec) {i,n,vec} goto loop-label
loop-label: {i,n,vec} if (eq? i n) {} goto conclusion else {i,n,vec} goto body-label
body-label: {i,n,vec} x = (vector-ref vec i) {x,i,n,vec} body’ {i,n,vec} i = i + 1 {i,n,vec} goto loop-label
suppose a function has three variables: x,y,z
lattice of “states” meet = greatest lower bound
{}__________ top
| \ \
{x} {y} {z}
| / \ / \
{x,y} {y,z} {x,z}
| /_________/
{x,y,z} bottom