[llvm-dev] Collectively dominance

[Hongbin Zheng via llvm-dev]

On Tue, Apr 25, 2017 at 6:32 PM, Daniel Berlin <dberlin at dberlin.org> wrote:

>
>
> On Tue, Apr 25, 2017 at 6:17 PM, Hongbin Zheng <etherzhhb at gmail.com>
> wrote:
>
>> Hi Daniel,
>>
>> I mean "*As a set*, B + C dominate D".
>>
>> On Tue, Apr 25, 2017 at 5:42 PM, Daniel Berlin <dberlin at dberlin.org>
>> wrote:
>>
>>> When you say collectively, you mean "would dominate it if considered a
>>> single block together?
>>>
>>> IE
>>>
>>>    A
>>> /      \
>>> B    C
>>>   \  /
>>>    D
>>>
>>> As a set, B + C dominate D.
>>>
>>> The set you are looking for there is (i believe):
>>>
>>> For each predecessor, walk the idom tree until you hit NCA of all
>>> predecessors.
>>>
>> "For each predecessor" do you mean "For each predecessor of the basic
blocks in the set"? I.e. for each predecessor of B and C in this example.

Thanks
Hongbin


> What do you mean by NCA?
>>
>
> Nearest common ancestor
>
> If you have dfs numbers for the dom tree, you can do this very fast.
>
>
>>
>>
>>
>>> While you walk it, place all nodes on each branch in a set.
>>>
>>> Any set that collectively dominates D must contain at least one member
>>> from each of these set, or be on the idom path between NCA and root.
>>>
>>> IE above, it would be that
>>> Set 1 = {B}
>>> Set 2 = {C}
>>> Set IDOM to root = {A}.
>>>
>>> If you find something in "set IDOM to root", the answer is always "yes",
>>> since that block alone dominates it, the collective set must dominate it.
>>> (unless you use a stricter definition of collective)
>>>
>>> For the tree
>>>   A
>>>  /   \
>>> B   D
>>> |     |
>>> C   E
>>>  \   /
>>>    F
>>>
>>> Set 1 = {B, C}
>>> Set 2 = {D, E}
>>> set IDOM to root = {A}
>>>
>>>
>> Thanks a lot
>> Hongbin
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170425/c40aba63/attachment.html>