Consider a flow graph, where each graph node corresponds to a basic block. An ex

Question

Consider a flow graph, where each graph node corresponds to a basic block. An example is shown at the right hand side. We say a node x dominates y if every possible execution path from program entry to y includes x. More specifically, x dominates y if and only if x = y x is a unique immediate predecessor of y x is a dominator of all immediate predecessors of y Mark TF for the following statements T/F 2 dominates 4 T/F 3 dominates 5 T/F 1 dominates 7 T/F 4 dominates 7 T/F 5 dominates 6 When x dominates y, we say x is a dominator of y. Develop a dataflow algorithm to compute the set of dominators (the dataflow fact) for each node by following the following procedures. Write down the transfer functions for each node for nodes 1, 2, 3, 4, 5, 6, 7, 8, 9 Let In(s) and Out(s) to be the set of dominators entering and leaving a statement s and Pred(s) and Succ(s) to be the predecessors and successors of statement s. Write down the dataflow equations below. Mark the in (s) and Out(s) after the first 2 iterations of the dataflow algorithms

Explanation / Answer

1)

As per given explanation node dominates other when

x=y

x is unique immediate predecessor of y

x is dominator of all immediate predecessors of y.

a) 2 dominates 4

Let us see which condition it fits, 2 is not equal to 4

2 is immediate predecessor of 4 but here there is cycle from 4 to 2 so nothing is predecessor here.

and no point of checking 3rd condition now

False

b) 3 dominates 5

3 is not equal to 5

3 is immediate predecessor of 5

True

c) 1 dominates 7

1 is not equal to 7

1 is the root of given tree hence is the dominator of every node and hence 1 is dominator of all predecessor of 7

True

d) 4 dominates 7

4 is not equal 7

4 is predecessor of 7 but not unique as 6 is also a predecessor and as well there is a cycle from 4 to 7

False

e) 5 dominates 6

5 is not equal to 6

5 is not predecessor of 6 as there is cycle between 5 and 6

False.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.