(30 points)
1. (10 points) Given the following C program, construct the dominator tree and postdominator tree.
Read A:LSR = 1 : RSR=A
SR = (LSR+RSR)/2
Repeat (
T=SR*SR:
IF (T>A) RSR =SR:
else if (LSR=SR:RSR=SR)
SR=(LSR+RSR)/2
Untill 9LSR/RSR)”
Print SR:
)
2 (10 pts) 2. Given the statement-based control graph for the program (a) construct the control-dependence graph for the program.
B1 1. A=1
2. B=2
B2
3.
C=A+B
4.
D=C-A
5. D=B*D
B3
T
F
B5
6.
D=A+B
8.
B=A+B
F
7.
E=E+1
9.
E=C-A
B4
T
B6
10.
A=B*D
11.
B=A-D
3. (10 points) Given the program from 2a, construct the program-dependence graph using data dependence and control dependence for the program.
2
