[llvm-dev] Collectively dominance

[Daniel Berlin via llvm-dev]

There is a trivial algorithm to do it, it's making it fast that is hard.

The trivial algorithm is:
Disconnect the incoming edges from the nodes in the set you are testing.

Do a pre-order DFS walk from the root.
If the target node is still reachable, the set does not jointly dominate it.

By definition, if set {a, b, ...} dominates y, then all paths that reach y
go through {a, b, ...}.

If you remove the incoming edges from those nodes, and y is still
reachable, there must be another path to y, so the set does not jointly
dominate it.

Obviously, you can do this in O(N) per test

I imagine there is some precomputation way to build a spanning forest or
something that gives you faster answers.




On Sat, May 20, 2017 at 4:43 PM, Zaks, Ayal <ayal.zaks at intel.com> wrote:

> Curious to learn how this is eventually working out?
>
>
>
> Some (“well-structured”?) cases could well be solved quickly, e.g. by
> covering dominators, but this seems a sufficient rather than a necessary
> condition in general. A set of nodes S could collectively dominate a given
> node N, where each node in S dominates only itself.
>
>
>
> Ayal.
>
>
>
>
>
>
>
> *From:* llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] *On Behalf Of *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
>
>
>
>
>
>
>
>
>
>
>
> ---------------------------------------------------------------------
> Intel Israel (74) Limited
>
> This e-mail and any attachments may contain confidential material for
> the sole use of the intended recipient(s). Any review or distribution
> by others is strictly prohibited. If you are not the intended
> recipient, please contact the sender and delete all copies.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170520/b713fde5/attachment.html>