[Question] Question regarding dominance frontier on slide 64

[jlee335]

I have a question regarding the dominance frontier of C in this slide.

Here, dominance frontier of C is shown to be {}.

However, using the definition of dominance frontier (from slide 71):

DF(C) = {C} as

• C ∉ dom(C)
• There is block D where, (C ∈ dom(D)) ∧ D ∈ pred(C)

[askme143]

I agree that the slide has a tiny mistake. C should be an element of DF(C). (Though the end result( DF({A, B}) = {C, D} ) is not changed)

For the same CFG, consider the case that C is the only node with store. A phinode should be inserted in C. For the another simple CFG: A(init block, i=0)->B(i = i+1; jump B if i < 10; jump C) -> C(return i), B should have a phinode for i, i.e. B in DF(B)

[AnHaechan]

@jeehoonkang Can you check this issue?

[AnHaechan]

DF is irreflexive. That is, forall X, X \notin DF(X).

• Intuitively, dominance frontier of block X is where the domination of that block ends.
• Thus, the dominance frontier of the block including itself is unnatural.

-> slide 64's example is correct. DF(C) = {}. -> slide 71's definition is wrong. We will fix the definition so that forall X, X \notin DF(X).

[kingdoctor123]

@AnHaechan I think if we decide DF to be irreflexive, then inserting phinodes at DF(S), DF(DF(S)), ... may be incorrect. Consider the following example (inspired by someone else's comment).

We have the same CFG as in p.64 of the slide. Suppose p is a memory location.

1. In block C, we have %a = *p; %b = %a + 1; *p = %b (i.e., increase the value stored in p by 1)
2. Every other block only reads from p.
3. We directly jump from initial block to block C (i.e., block C is not the initial block).

In this situation, we should insert phinode at C since p contains different values when we jump from initial block to C and when we jump from block D to C. But, if DF(C)={}, then we will not insert any phinode. Can you exaplain how this situation can be resolved?

[AnHaechan]

@kingdoctor123

I'll assume an example cfg slight different from yours, in the figure below. The only difference is that, P is not initial block. I'll explain the reason later, so please first think within this example.

Your proposition, "a phinode should be inserted at C", is correct. That is not because DF(C) = {C} (="domination of C ends at C" <-- quite weird, intuitively. Right?), but because DF(P) = {C} (="domination of P ends at C").

You mentioned "we should insert phinode at C since p contains different values when we jump from initial block(here, P) to C and when we jump from block D to C". This implicitly assumes that there is store to p in the block P. Hence, a phinode should be inserted at C because domination of P ends at C (i.e. DF(P) = {C}), not because DF(C)={C}.

// I excluded the case where P is initial block, because I myself am not sure about that case, as DF(init) seems to be empty set... maybe professor(@jeehoonkang ) can help for this case.

[kingdoctor123]

@AnHaechan Thank you for your detailed answer. Your mentioning about initialization write is very interesting. Unfortunately, my problem still remains if we assume there is no initialization write at the initial block, and the block C contains both initialization write and update (we should still insert a phinode at C). After reading your response, I found some literatures and resources that argue about dominance frontier.

1. Original definition coincides with the definition written in the paper (section 3.1): (Cytron, Ron; Ferrante, Jeanne; Rosen, Barry K.; Wegman, Mark N.; Zadeck, F. Kenneth (1989). "An Efficient Method of Computing Static Single Assignment Form". Proceedings of the 16th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. POPL ’89: 25–35. doi:10.1145/75277.75280. ISBN 0897912942. S2CID 8301431)
2. Lecture note from Wisconsin university says DF(A)={A} is valid. (https://pages.cs.wisc.edu/~fischer/cs701.f05/lectures/Lecture22.pdf)

You said that "domination of C ends at C" is intuitively weird, but I think it is quite natural if you read DF(C)={C} like this: Domination of C is effective for all blocks below C (according to our example), but it immediately becomes ineffective if we jump back to C.

I feel sorry to ask such a tricky question about the definition of DF many times, but I hope we can reach at deeper understanding of this topic. Thank you in advance.

[AnHaechan]

Whoa, thanks for detailed research. I'm now convinced that DF is not irreflexive(i.e. exists B, B \in DF(B)), after reading the references. I'll reach professors to get confirmed on this subject.

[AnHaechan]

Conclusion: DF is not irreflexive (i.e. exists B, B \in DF(B)).

• Explanation by @kingdoctor123 is correct.
• slide 64's example is wrong -> will be fixed to DF(C) = {C}.
• slide 71's definition is correct.