[Question] Domination tree construction equation

[h2oche]

In lecture slides, there is domination tree construction which using equation idom(X) = ⊓_{y \in pred(X)} idom(Y). However, it seems to be incorrect.

For example, for graph 1 -> 2 -> 3, idom(3) = 2, idom(2) = 1, but if I use above equation idom(3) becomes 1.

I think idom(X) = (⊓_{y \in pred(X)} idom(Y)) if not exists y s.t y \in pred(X) and y is idom(X) = ⊓ pred(X) if exists y s.t y \in pred(X) and y is idom(X)

is correct equation.

[h2oche]

Actually, model solution in video also seems to be incorrect. When I give following ir to Domtree in model solution,

fun unit @aa {
init:
  bid: b0
  allocations:

block b0:
  j b1()

block b1:
  j b2()

block b2:
  ret 0:i32
}

It says domtree.parent is {1 -> 0, 2 -> 0} (I guess {1 -> 0, 2 -> 1} is correct result).

Updated : Sorry, in updated video in Register Promotion(Code, Domination), this problem seems to be fixed.

[jeehoonkang]

Thank you for reporting the bug. I agree with you on that "idom(X) = ⊓_{y \in pred(X)} idom(Y)" is wrong.

The fix will be, as you said, like this:

idom(X) = y                                            if y \in pred(X) and forall z \in pred(X), y=z or y dominates z
idom(X) = ⊓_{y \in pred(X)} idom(Y)     otherwise

I'll update the slide.

[jeehoonkang]

Slide updated: https://docs.google.com/presentation/d/1SqtU-Cn60Sd1jkbO0OSsRYKPMIkul0eZoYG9KpMugFE/edit#slide=id.g8489bbc41c_7_22

[h2oche]

Oh, thanks! By the way, notion of domination is really useful to me while doing homework :). May I close this issue?

[jeehoonkang]

I'm glad it's helpful :) I'm closing this issue.