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>
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>
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<mailto: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<mailto:dberlin at dberlin.org>> wrote:
On Tue, Apr 25, 2017 at 6:42 PM, Hongbin Zheng <etherzhhb at
gmail.com<mailto:etherzhhb at gmail.com>> wrote:
On Tue, Apr 25, 2017 at 6:32 PM, Daniel Berlin <dberlin at
dberlin.org<mailto:dberlin at dberlin.org>> wrote:
On Tue, Apr 25, 2017 at 6:17 PM, Hongbin Zheng <etherzhhb at
gmail.com<mailto: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<mailto: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/2a3fe9e7/attachment.html>