[llvm-dev] Collectively dominance

[Daniel Berlin via llvm-dev]

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.
>>
> 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/97207329/attachment-0001.html>