[llvm-dev] Collectively dominance

[Daniel Berlin via llvm-dev]

Like I said, i'm nearly positive there is a much faster way, as the sets
are mostly shared except in the cyclic case, and in all reducible cyclic
cases, removal of back-arcs does not affect dominance

(because in any reducible flowgraph, v dominates u whenever u,v is a
back-arc)


On Tue, Apr 25, 2017 at 7:38 PM, Hongbin Zheng <etherzhhb at gmail.com> wrote:

> 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/8cf26f4e/attachment.html>