Add ContiguousDisjointSet datastructure #15418
Conversation
Yeah, this is a data structure used in finding / construction of the loop nesting forest of a CFG |
clonker
force-pushed
the
liveness-disjoint-set
branch
from
f54429f to
a13a86f
Compare
clonker
force-pushed
the
liveness-disjoint-set
branch
from
a13a86f to
7f582e4
Compare
| return rootElement; | ||
| } | ||
|
|
||
| void ContiguousDisjointSet::merge(value_type const _x, value_type const _y, bool const _mergeBySize) |
There was a problem hiding this comment.
Are we planning to add rank in the future? Or is there a situation where we would have this false?
just a nitpick...
ps: I see it set to false in the test, but realistically, should be better to always have it on (or switched to rank), right?
There was a problem hiding this comment.
Good question:) The place we need it for now (loop detection with Tarjan"s algorithm) relies on merging with "by size/rank" being switched off. That way a representative of a set can stay stable under merge operations. In particular this is used for loop headers (think a loop header as a vertex of a CFG represent a set of vertices that comprise the loop body). You can see this in PR 15419.
So generally I am inclined to agree that by rank is better - although potential problems with "by-size" are somewhat mitigated by path compression - but in our case it doesn"t really matter. For now. :D
There was a problem hiding this comment.
Oh and there is just one test that has mergeBySize disabled, to check exactly that stability property of the set representative... the rest does have it enabled..
There was a problem hiding this comment.
Thanks for the explanation @clonker !
needed for loop nesting forest construction in liveness analysis