[llvm-dev] Collectively dominance

[Hongbin Zheng via llvm-dev]

Hi Daniel,

Thanks a lot for all these explanation, I will try it out.

Hongbin

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

>
>
> On Tue, Apr 25, 2017 at 6:42 PM, Hongbin Zheng <etherzhhb at gmail.com>
> wrote:
>
>>
>>
>> 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.
>>
>
> No, for each predecessor of D.
>
> The definition of dominance is that d dominates n if every path from root
> to n goes through d.
> This means for anything to collectively dominate a node, it either must:
> Be be in the idom tree (ie so that the above is definitely true)
> or cover every path into the block.
>
> The only way to cover every path is to cover at least a dominator of all
> of the predecessors.
>
> This would guarantee that collectively, every path to the predecessor must
> go through the set.
>
> Note that this definition is recursive, actually, so while the algorithm i
> gave covers most examples.
> For any block with multiple predecessors, you'd have to apply it
> recursively.
>
>
>
> 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/ba605f5e/attachment.html>