Computing Data Dependence is Hard in General Aliasing A variable can refer to multiple memory locations /objects (1)foo (ClassX x,ClassY y){ (1)intx,yZ,… (2) x.field=…i (2)int*p; (3) y.field; (3)X=… (4)} (4)y=…; (5)p=&xX (6)p=p+z; obj1 new Classx(); (7）.=*p obj2 new ClassY(); foo(obj1,obj2); 21
21 Computing Data Dependence is Hard in General • Aliasing ➢ A variable can refer to multiple memory locations / objects . (1) int x, y, z,…; (2) int *p; (3) x = …; (4) y = …; (5) p = &x; (6) p = p + z; (7) … = *p (1) foo (ClassX x, ClassY y) { (2) x.field = …; (3) … = y.field; (4) } obj1 = new ClassX(); obj2 = new ClassY(); foo(obj1, obj2);
Control Dependence A node (basic block)Y is control-dependent on another X iff X directly determines whether Y executes There is a path from X to End that X >X is not strictly post-dominated by Y. does not pass Y or X ==Y There exits a path from X to Y s.t.every node in the path other than X and Y is post- dominated by Y → No such paths for nodes in a path between X and Y. X Not post-dominated by Y +Every node is post-dominated by Y 22
22 Control Dependence • A node (basic block) Y is control-dependent on another X iff X directly determines whether Y executes ➢ X is not strictly post-dominated by Y. ➢ There exits a path from X to Y s.t. every node in the path other than X and Y is postdominated by Y There is a path from X to End that X does not pass Y or X == Y No such paths for nodes in a path between X and Y
Control Dependence-Example A node (basic block)Y is control-dependent on another X iff X directly determines whether Y executes X is not strictly post-dominated by Y. There exits a path from X to Y s.t.every node in the path other than X and Y is post- dominated by Y 1:sum=0 2:ie1 (1) sum =0 (2) i=1 (3) while (i<N)do 3.while i<N)do (4) i=i+1 (5) sum sum +i 4:j+1 endwhile 5. sum=sum+I (6) print(sum) CD(5)={3} 6:print(sum) CD(3)=3,tricky! 23
23 Control Dependence - Example • A node (basic block) Y is control-dependent on another X iff X directly determines whether Y executes ➢ X is not strictly post-dominated by Y. ➢ There exits a path from X to Y s.t. every node in the path other than X and Y is postdominated by Y (1) sum = 0 (2) i = 1 (3) while (i<N) do (4) i = i+1 (5) sum = sum + i endwhile (6) print (sum) CD(5) = {3} CD(3) = 3, tricky!
Note:Control Dependence is not Syntactically Explicit A node(basic block)Y is control-dependent on another X iff X directly determines whether Y executes X is not strictly post-dominated by Y. There exits a path from X to Y s.t.every node in the path other than X and Y is post- dominated by Y 1:sum=0 (1) sum =0 2:ie1 (2) i=1 3:while (i<N)do (3) while (i<N)do (4) i=i+1 4:1+1 (5) ifi%2=0) 5:if(i%2==0) (6) continue; (7) sumsum +i 7:sum=sum+i endwhile (8) print(sum) 8:print(sum) 24
24 Note: Control Dependence is not Syntactically Explicit • A node (basic block) Y is control-dependent on another X iff X directly determines whether Y executes ➢ X is not strictly post-dominated by Y. ➢ There exits a path from X to Y s.t. every node in the path other than X and Y is postdominated by Y (1) sum = 0 (2) i = 1 (3) while (i<N) do (4) i = i+1 (5) if(i%2 == 0) (6) continue; (7) sum = sum + i endwhile (8) print (sum)
Control Dependence is Tricky! A node (basic block)Y is control-dependent on another X iff X directly determines whether Y executes >X is not strictly post-dominated by Y. There exits a path from X to Y s.t.every node in the path other than X and Y is post- dominated by Y. ● Can one statement control depends on two predicates? 1:?p1 (1) if (p1 |p2) (2) s1; 1:?p2 (3) s2; 2:s1 What if? (1) if(p1&&p2) (2) s1; 3:s2 (3) s2; 25
25 Control Dependence is Tricky! • A node (basic block) Y is control-dependent on another X iff X directly determines whether Y executes ➢ X is not strictly post-dominated by Y. ➢ There exits a path from X to Y s.t. every node in the path other than X and Y is postdominated by Y. • Can one statement control depends on two predicates? (1) if (p1 || p2) (2) s1; (3) s2; What if? (1) if (p1 && p2) (2) s1; (3) s2;