David Golombek
6.035 pset #1
TA: Jeremy Brown
Problem 1

1a)
--------------------------------------b1
[1]  i := 0
[2]  m := 0
[3]  label L1:
[4]  t1 := size(a)
[5]  if i >= t1 goto L2
--------------------------------------b6
[6]  t2 := i < 0
[7]  fail-if t2 "array index too low"
[8]  t3 := size(a)
[9]  t4 := i >= t3
[10] fail-if t4 "array index too high"
[11] t5 := a[i]
[12] t6 := i < 0
[13] fail-if t6 "array index too low"
[14] t7 := size(b)
[15] t8 := i >= t7
[16] fail-if t8 "array index too high"
[17] t9 := b[i]
[18] t10 := t5 + t9
[19] if t10 <= m goto L3
-------------------------------------b20
[20] t11 := i < 0
[21] fail-if t11 "array index too low"
[22] t12 := size(a)
[23] t13 := i >= t12
[24] fail-if t13 "array index too high"
[25] t14 := a[i]
[26] t15 := i < 0
[27] fail-if t15 "array index too low"
[28] t16 := size(b)
[29] t17 := i >= t16
[30] fail-if t17 "array index too high"
[31] t18 := b[i]
[32] m := t14 + t18
-------------------------------------b33
[33] label L3:
[34] i := i + 1
[35] goto L1
-------------------------------------b36
[36] label L2:
[37] print m








David Golombek
6.035 pset #1
TA: Jeremy Brown
Problem 2


2a)
--------------------------------------	IN			OUT
[1]  a := 1							a
[2]  label L0:				a			a
[3]  if a > 1000 goto L1		a			a
[4]  if a < 0 goto L2			a			a
[5]  b := a + 1				a			a,b
[6]  c := a * b				a,b			c
[7]  goto L3				c			c
[8]  label L2:				c			c
[9]  d := a - 1				a			a,d
[10] c := a * d				a, d			c
[11] label L3:				c			c
[12] a := -c				c			a
[13] goto L0				a			a
[14] label L1:				a			a
[15] write a				a			a

2b)








2c)

/* Forward Pass */
Push variable C and neighbors-list {} on stack
Delete variable C from interference graph
Push variable B and neighbors-list {A} on stack
Delete variable B from interference graph
Push variable A and neighbors-list {D} on stack
Delete variable A from interference graph
Push variable D and neighbors-list {} on stack
Delete variable D from interference graph

/* Reverse Pass */

Pop variable D and neighbors-list {} from stack
Insert variable D into G with no edges
Assign variable D register $t2
Pop variable A and neighbors-list {D} from stack
Insert variable A into G with edge to D
Assign variable A register $t1
Pop variable B and neighbors-list {A} from stack
Insert variable B into G with edge to A
Assign variable B register $t2
Pop variable C and neighbors-list {} from stack
Insert variable C into G with no edges
Assign variable C any register $t1 or $t2


David Golombek
6.035 pset #1
TA: Jeremy Brown
Problem 3

3a)

d			du-chain(d)
def of a in [1]		{(a,3,1), (a,4,2), (a,6,4), (a,8,1), (a,9,2)}
def of b in [2]		{(b,3,2), (b,5,2), (b,6,2)}
def of c in [3]		{(c,4,2), (c,9,1)}
def of d in [4]		{(d,5,2), (d,10,2), (d,11,2)}
def of d in [5]		{(d,10,2), (d,11,2)}
def of d in [6]		{(d,5,2)}
def of e in [7]		{}
def of b in [8]		{(b,3,2), (b,5,2), (b,6,2), (b,10,1)}
def of e in [9]		{(e,7,1)}
def of a in [10]	{(a,11,1)}
def of b in [11]	{}

3b)

/* initialize */
out[b1] = {a:const,b:const,c:undef,d:undef,e:undef}
out[b2] = {a:undef,b:undef,c:undef,d:undef,e:undef}
out[b3] = {a:undef,b:undef,c:undef,d:undef,e:undef}
out[b4] = {a:undef,b:undef,c:undef,d:undef,e:undef}
out[b5] = {a:undef,b:undef,c:undef,d:undef,e:undef}
out[b6] = {a:undef,b:undef,c:undef,d:undef,e:undef}

/* while loop */

in[b6] = {a:undef,b:undef,c:undef,d:undef,e:undef}
out[b6] = {a:undef,b:undef,c:undef,d:undef,e:undef}

in[b5] = {a:undef,b:undef,c:undef,d:undef,e:undef}
out[b5] = {a:undef,b:undef,c:undef,d:undef,e:undef}

in[b4] = {a:undef,b:undef,c:undef,d:undef,e:undef}
out[b4] = {a:undef,b:undef,c:undef,d:undef,e:undef}

in[b3] = {a:undef,b:undef,c:undef,d:undef,e:undef}
out[b3] = {a:undef,b:undef,c:undef,d:undef,e:undef}

in[b2] = {a:const,b:const,c:undef,d:undef,e:undef}
out[b2] = {a:const,b:const,c:const,d:const,e:undef}

CHANGE = TRUE

in[b6] = {a:undef,b:undef,c:undef,d:undef,e:undef}
out[b6] = {a:undef,b:undef,c:undef,d:undef,e:undef}

in[b5] = {a:const,b:const,c:const,d:const,e:undef}
out[b5] = {a:const,b:const,c:const,d:const,e:const}

in[b4] = {a:undef,b:undef,c:undef,d:undef,e:undef}
out[b4] = {a:undef,b:undef,c:undef,d:undef,e:undef}

in[b3] = {a:const,b:const,c:const,d:const,e:undef}
out[b3] = {a:const,b:const,c:const,d:const,e:undef}

in[b2] = {a:const,b:nonconst,c:undef,d:undef,e:const}
out[b2] = {a:const,b:nonconst,c:nonconst,d:nonconst,e:const}

CHANGE = TRUE

in[b6] = {a:const,b:const,c:const,d:const,e:const}
out[b6] = {a:const,b:const,c:const,d:const,e:const}

in[b5] = {a:const,b:nonconst,c:nonconst,d:nonnonconst,e:const}
out[b5] = {a:const,b:nonconst,c:nonconst,d:nonconst,e:nonconst}

in[b4] = {a:const,b:const,c:const,d:const,e:undef}
out[b4] = {a:const,b:const,c:const,d:const,e:undef}

in[b3] = {a:const,b:nonconst,c:nonconst,d:nonnonconst,e:const}
out[b3] = {a:const,b:nonconst,c:nonconst,d:nonnonconst,e:const}

in[b2] = {a:const,b:nonconst,c:nonconst,d:nonnonconst,e:nonconst}
out[b2] = {a:const,b:nonconst,c:nonconst,d:nonnonconst,e:nonconst}

CHANGE = TRUE

in[b6] = {a:const,b:nonconst,c:nonconst,d:nonconst,e:nonconst}
out[b6] = {a:const,b:nonconst,c:nonconst,d:nonconst,e:nonconst}

in[b5] = {a:const,b:nonconst,c:nonconst,d:nonconst,e:nonconst}
out[b5] = {a:const,b:nonconst,c:nonconst,d:nonconst,e:nonconst}

in[b4] = {a:const,b:nonconst,c:nonconst,d:nonnonconst,e:const}
out[b4] = {a:const,b:nonconst,c:nonconst,d:nonnonconst,e:const}

in[b3] = {a:const,b:nonconst,c:nonconst,d:nonnonconst,e:nonconst}
out[b3] = {a:const,b:nonconst,c:nonconst,d:nonnonconst,e:nonconst}

in[b2] = {a:const,b:nonconst,c:nonconst,d:nonnonconst,e:nonconst}
out[b2] = {a:const,b:nonconst,c:nonconst,d:nonnonconst,e:nonconst}

CHANGE = TRUE

in[b6] = {a:const,b:nonconst,c:nonconst,d:nonconst,e:nonconst}
out[b6] = {a:const,b:nonconst,c:nonconst,d:nonconst,e:nonconst}

in[b5] = {a:const,b:nonconst,c:nonconst,d:nonconst,e:nonconst}
out[b5] = {a:const,b:nonconst,c:nonconst,d:nonconst,e:nonconst}

in[b4] = {a:const,b:nonconst,c:nonconst,d:nonnonconst,e:nonconst}
out[b4] = {a:const,b:nonconst,c:nonconst,d:nonnonconst,e:nonconst}

in[b3] = {a:const,b:nonconst,c:nonconst,d:nonnonconst,e:nonconst}
out[b3] = {a:const,b:nonconst,c:nonconst,d:nonnonconst,e:nonconst}

in[b2] = {a:const,b:nonconst,c:nonconst,d:nonnonconst,e:nonconst}
out[b2] = {a:const,b:nonconst,c:nonconst,d:nonnonconst,e:nonconst}

CHANGE = TRUE

in[b6] = {a:const,b:nonconst,c:nonconst,d:nonconst,e:nonconst}
out[b6] = {a:const,b:nonconst,c:nonconst,d:nonconst,e:nonconst}

in[b5] = {a:const,b:nonconst,c:nonconst,d:nonconst,e:nonconst}
out[b5] = {a:const,b:nonconst,c:nonconst,d:nonconst,e:nonconst}

in[b4] = {a:const,b:nonconst,c:nonconst,d:nonnonconst,e:nonconst}
out[b4] = {a:const,b:nonconst,c:nonconst,d:nonnonconst,e:nonconst}

in[b3] = {a:const,b:nonconst,c:nonconst,d:nonnonconst,e:nonconst}
out[b3] = {a:const,b:nonconst,c:nonconst,d:nonnonconst,e:nonconst}

in[b2] = {a:const,b:nonconst,c:nonconst,d:nonnonconst,e:nonconst}
out[b2] = {a:const,b:nonconst,c:nonconst,d:nonnonconst,e:nonconst}

CHANGE = FALSE

3c)

a is constant on lines 3,4,6,8,9


David Golombek
6.035 pset #1
TA: Jeremy Brown
Problem 4

4b) The code for a[i] + b[i] is common:  the IL code is
[6]  t2 := i < 0
[7]  fail-if t2 "array index too low"
[8]  t3 := size(a)
[9]  t4 := i >= t3
[10] fail-if t4 "array index too high"
[11] t5 := a[i]
[12] t6 := i < 0
[13] fail-if t6 "array index too low"
[14] t7 := size(b)
[15] t8 := i >= t7
[16] fail-if t8 "array index too high"
[17] t9 := b[i]
[18] t10 := t5 + t9

4d)   This code will be evaluated the b6 block, then reused in the b20
block.