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?> 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/480b598c/attachment.html>
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>
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 basicblocks in the set"? I.e. for each predecessor of B and C in this example. 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/c40aba63/attachment.html>