Code Optimization

Single correct

• AB4: $\{b + i\}$, B5: $\{c + m\}$
• BB4: $\{g * k\}$, B5: $\{c + m\}$
• CB4: $\{g * k,\ b + i\}$, B5: $\{\}$
• DB4: $\{g * k\}$, B5: $\{\}$

Single correct

• AB1: $\{a, b, c, e, f\}$, B2: $\{d, e\}$, B3: $\{b, c, e, f\}$, B4: $\emptyset$
• BB1: $\emptyset$, B2: $\{d, e\}$, B3: $\{a, c, f\}$, B4: $\emptyset$
• CB1: $\{a, b, c, e, f\}$, B2: $\{d, e\}$, B3: $\{c, e, f\}$, B4: $\emptyset$
• DB1: $\emptyset$, B2: $\{d, e, f\}$, B3: $\{a, b, c, e, f\}$, B4: $\emptyset$

Single correct

• ARun-time function call management
• BRegister assignment to variables
• CStrength reduction
• DConstant folding

L1:   t1 = -1
L2:   t2 = 0
L3:   t3 = 0
L4:   t4 = 4 * t3
L5:   t5 = 4 * t2
L6:   t6 = t5 * M
L7:   t7 = t4 + t6
L8:   t8 = a[t7]
L9:   if t8 <= max goto L11
L10:  t1 = t8
L11:  t3 = t3 + 1
L12:  if t3 < M goto L4
L13:  t2 = t2 + 1
L14:  if t2 < N goto L3
L15:  max = t1

Single correct

• A6 and 6
• B6 and 7
• C7 and 7
• D7 and 6

Single correct

• AB1: {}, B2: {a}, B3: {a}, B4: {a}
• BB1: {i, j}, B2: {a}, B3: {a}, B4: {i}
• CB1: {a, i, j}, B2: {a, i, j}, B3: {a, i}, B4: {a}
• DB1: {a, i, j}, B2: {a, j}, B3: {a, j}, B4: {a, i, j}

Answer key coming soon

z = x + 3 + y->f1 + y->f2;
for (i = 0; i < 200; i = i + 2){
  if (z > i) {
    p = p + x + 3;
    q = q + y->f1;
  } else {
    p = p + y->f2;
    q = q + x + 3;
  }
}

Single correct

• A403 and 102
• B203 and 2
• C303 and 102
• D303 and 2

Answer key coming soon

Single correct

• A$OUT(S_1) = IN(S_2)$
• B$OUT(S_1) = IN(S_1) \cup USE(S_1)$
• C$OUT(S_1) = IN(S_2) \cup OUT(S_2)$
• D$OUT(S_1) = USE(S_1) \cup IN(S_2)$

Answer key coming soon

Single correct

• A$p, s, u$
• B$r, s, u$
• C$r, u$
• D$q, v$

(1)  i = 1
(2)  j = 1
(3)  t1 = 5 * i
(4)  t2 = t1 + j
(5)  t3 = 4 * t2
(6)  t4 = t3
(7)  a[t4] = -1
(8)  j = j + 1
(9)  if j<=5 goto (3)
(10) i=i+1
(11) if i<5 goto (2)

Single correct

• A5 and 7
• B6 and 7
• C5 and 5
• D7 and 8

Single correct

• AA basic block is a sequence of instructions where control enters the sequence at the beginning and exits at the end.
• BAvailable expression analysis can be used for common subexpression elimination.
• CLive variable analysis can be used for dead code elimination.
• D$x = 4 * 5 \Rightarrow x = 20$ is an example of common subexpression elimination.

a = b + c
c = a + d
d = b + c
e = d - b
a = e + b

Single correct

• A6 and 6
• B8 and 10
• C9 and 12
• D4 and 4

c = a + b;
d = c * a;
e = c + a;
x = c * c;
if (x > a) {
   y = a * a;
}
else {
   d = d * d;
   e = e * e;
}

Single correct

• A0
• B1
• C2
• D3

Answer key coming soon

c = a + b;
d = c * a;
e = c + a;
x = c * c;
if (x > a) {
   y = a * a;
}
else {
   d = d * d;
   e = e * e;
}

Single correct

• A3
• B4
• C5
• D6

Answer key coming soon

Single correct

• A2
• B9
• C5
• D3

Answer key coming soon