int x = 3;
int t = 0;
while (x < 4) {
int y = x;
while (y < 10) {
y = y + 1;
t = t + y;
if (t % 2 == 0) {
print "even";
} else {
print "odd";
}
}
x = x + 1;
}
XXXXXXXXXXRD solutions
entry solutions:
label 1: { (t, ?) (x, ?) (y, ?) }
label 2: { (t, ?) (x, 1) (y, ?) }
label 3: { (t, 2) (t, 7) (x, 1) (x, 11) (y, ?) (y, 4) (y, 6) }
label 4: { (t, 2) (t, 7) (x, 1) (x, 11) (y, ?) (y, 4) (y, 6) }
label 5: { (t, 2) (t, 7) (x, 1) (x, 11) (y, 4) (y, 6) }
label 6: { (t, 2) (t, 7) (x, 1) (x, 11) (y, 4) (y, 6) }
label 7: { (t, 2) (t, 7) (x, 1) (x, 11) (y, 6) }
label 8: { (t, 7) (x, 1) (x, 11) (y, 6) }
label 9: { (t, 7) (x, 1) (x, 11) (y, 6) }
label 10: { (t, 7) (x, 1) (x, 11) (y, 6) }
label 11: { (t, 2) (t, 7) (x, 1) (x, 11) (y, 4) (y, 6) }
label 12: { (t, 2) (t, 7) (x, 1) (x, 11) (y, ?) (y, 4) (y, 6) }
exit solutions:
label 1: { (t, ?) (x, 1) (y, ?) }
label 2: { (t, 2) (x, 1) (y, ?) }
label 3: { (t, 2) (t, 7) (x, 1) (x, 11) (y, ?) (y, 4) (y, 6) }
label 4: { (t, 2) (t, 7) (x, 1) (x, 11) (y, 4) }
label 5: { (t, 2) (t, 7) (x, 1) (x, 11) (y, 4) (y, 6) }
label 6: { (t, 2) (t, 7) (x, 1) (x, 11) (y, 6) }
label 7: { (t, 7) (x, 1) (x, 11) (y, 6) }
label 8: { (t, 7) (x, 1) (x, 11) (y, 6) }
label 9: { (t, 7) (x, 1) (x, 11) (y, 6) }
label 10: { (t, 7) (x, 1) (x, 11) (y, 6) }
label 11: { (t, 2) (t, 7) (x, 11) (y, 4) (y, 6) }
label 12: { (t, 2) (t, 7) (x, 1) (x, 11) (y, ?) (y, 4) (y, 6) }
CSI 5350: Implementation of worklist algorithm
This project is a continuation of Project 4. You are required to implement the
worklist algorithm for one of these data flow analyses: reaching definitions, avail-
able expressions, live variables, and very busy expressions. You may complete
this project in a group of three.
• Implement the worklist algorithm and add it to your analyzer;
• Test your analyzer with a suit of 5 test programs in myC–; and
• Submit your project along with the test programs and test results.
1
XXXXXXXXXXCFG Label/AST Map Verification
Label: 1 Stmt: int x = 3
Label: 2 Stmt: int t = 0
Label: 3 Stmt: while ((x < 4))
Label: 4 Stmt: int y = x
Label: 5 Stmt: while ((y < 10))
Label: 6 Stmt: y = (y + 1)
Label: 7 Stmt: t = (t + y)
Label: 8 Stmt: if (((t % 2) == 0))
Label: 9 Stmt: print "even"
Label: 10 Stmt: print "odd"
Label: 11 Stmt: x = (x + 1)
Label: 12 Stmt: print t
XXXXXXXXXXCFG EdgeMap Verification
(1,2)
(2,3)
(3,4)
(3,12)
(4,5)
(5,6)
(5,11)
(6,7)
(7,8)
(8,9)
(8,10)
(9,5)
(10,5)
(11,3)
XXXXXXXXXXentry equations
RD_entry(1) = { (t, ?) (x, ?) (y, ?) }
RD_entry(2) = RD_exit(1)
RD_entry(3) = RD_exit(11) U RD_exit(2)
RD_entry(4) = RD_exit(3)
RD_entry(5) = RD_exit(9) U RD_exit(10) U RD_exit(4)
RD_entry(6) = RD_exit(5)
RD_entry(7) = RD_exit(6)
RD_entry(8) = RD_exit(7)
RD_entry(9) = RD_exit(8)
RD_entry(10) = RD_exit(8)
RD_entry(11) = RD_exit(5)
RD_entry(12) = RD_exit(3)
XXXXXXXXXXexit equations
RD_exit(1) = (RD_entry(1) \ { (x, ?) (x, 1) (x, 11) }) U { (x, 1) }
RD_exit(2) = (RD_entry(2) \ { (t, ?) (t, 2) (t, 7) }) U { (t, 2) }
RD_exit(3) = (RD_entry(3) \ {}) U {}
RD_exit(4) = (RD_entry(4) \ { (y, ?) (y, 4) (y, 6) }) U { (y, 4) }
RD_exit(5) = (RD_entry(5) \ {}) U {}
RD_exit(6) = (RD_entry(6) \ { (y, ?) (y, 4) (y, 6) }) U { (y, 6) }
RD_exit(7) = (RD_entry(7) \ { (t, ?) (t, 2) (t, 7) }) U { (t, 7) }
RD_exit(8) = (RD_entry(8) \ {}) U {}
RD_exit(9) = (RD_entry(9) \ {}) U {}
RD_exit(10) = (RD_entry(10) \ {}) U {}
RD_exit(11) = (RD_entry(11) \ { (x, ?) (x, 1) (x, 11) }) U { (x, 11) }
RD_exit(12) = (RD_entry(12) \ {}) U {}