Paul Vario
2014-Feb-14 17:50 UTC
[LLVMdev] DominatorTree not updated properly after calling the llvm::SplitBlock.
Hi Andrew, Thanks a lot. But the function "DT->dominate(A,B)" decides the dominance relationship through comparing the DFS numbers, right? At least, in my example, when I check whether the newly split node (i.e., % *for.end.split*) DOMINATES the original node (I.e., %for.end), the answer is true, which is obviously wrong. Paul On Fri, Feb 14, 2014 at 1:59 AM, Andrew Trick <atrick at apple.com> wrote:> > On Feb 13, 2014, at 4:34 PM, Paul Vario <paul.paul.mit at gmail.com> wrote: > > Hi Fellows, > > I am writing a pass that requires the DominatorTree pass. In the > runOnFunction of my own pass, I call llvm::SplitBlock to split a block > (%for.end) at it's first insert point. Then, when I dump my dominator tree > immediately after, I can see the newly split %for.end.split, but its > DFSNumIn and DFSNumOut are not properly updated in llvm::SplitBlock (i.e., > still the initialized -1). At the same time, the DT->dump() results also > show that DFSInfoValid equals false! I could not figure out what I did > wrong, b/c it seems all the analysis updating should be handled by > llvm::SplitBlock. Any suggestions on how to approach this situation? Thanks > a bunch in advance. > > > Hi Paul, > > DFSNumbers is a cache within the DominatorTree analysis. It is lazily > computed after a certain number of queries. It's kind of hard to > incrementally update these numbers because we may have to shift them all. > > At any rate, invalid DFS numbers does not mean something is wrong with the > analysis. > > -Andy > > > > ------------------------- The actual dump of my dominator tree after > SplitBlock -------------------- > > Inorder Dominator Tree: DFSNumbers invalid: 1 slow queries. > [1] %entry.barrier {0,27} > [2] %entry {1,26} > [3] %for.cond {2,25} > [4] %for.body {3,6} > [5] %for.inc {4,5} > [4] %for.end {7,24} > *[5] %for.end.split {4294967295,4294967295}* > [6] %if.then {8,15} > [7] %if.then13 {9,10} > [7] %if.end {11,12} > [7] %if.then.if.end_crit_edge {13,14} > [6] %if.end14 {16,21} > [7] %exit.b4.barrier {17,20} > [8] %exit.barrier {18,19} > [6] %for.end.if.end14_crit_edge {22,23} > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140214/682f2d71/attachment.html>
Andrew Trick
2014-Feb-14 19:13 UTC
[LLVMdev] DominatorTree not updated properly after calling the llvm::SplitBlock.
On Feb 14, 2014, at 9:50 AM, Paul Vario <paul.paul.mit at gmail.com> wrote:> Hi Andrew, > > Thanks a lot. But the function "DT->dominate(A,B)" decides the dominance relationship through comparing the DFS numbers, right? At least, in my example, when I check whether the newly split node (i.e., %for.end.split) DOMINATES the original node (I.e., %for.end), the answer is true, which is obviously wrong.That sounds like a bug. When DFSInfoValid==false, the DFS number does not affect the query. So I don’t know why you’re getting the wrong answer. I know you don’t have a test case, but I suggest filling a bugzilla PR and attaching a dump of both your IR and Domtree before splitting and after splitting. -Andy> Paul > > > On Fri, Feb 14, 2014 at 1:59 AM, Andrew Trick <atrick at apple.com> wrote: > > On Feb 13, 2014, at 4:34 PM, Paul Vario <paul.paul.mit at gmail.com> wrote: > >> Hi Fellows, >> >> I am writing a pass that requires the DominatorTree pass. In the runOnFunction of my own pass, I call llvm::SplitBlock to split a block (%for.end) at it's first insert point. Then, when I dump my dominator tree immediately after, I can see the newly split %for.end.split, but its DFSNumIn and DFSNumOut are not properly updated in llvm::SplitBlock (i.e., still the initialized -1). At the same time, the DT->dump() results also show that DFSInfoValid equals false! I could not figure out what I did wrong, b/c it seems all the analysis updating should be handled by llvm::SplitBlock. Any suggestions on how to approach this situation? Thanks a bunch in advance. > > Hi Paul, > > DFSNumbers is a cache within the DominatorTree analysis. It is lazily computed after a certain number of queries. It’s kind of hard to incrementally update these numbers because we may have to shift them all. > > At any rate, invalid DFS numbers does not mean something is wrong with the analysis. > > -Andy > >> >> >> ------------------------- The actual dump of my dominator tree after SplitBlock -------------------- >> >> Inorder Dominator Tree: DFSNumbers invalid: 1 slow queries. >> [1] %entry.barrier {0,27} >> [2] %entry {1,26} >> [3] %for.cond {2,25} >> [4] %for.body {3,6} >> [5] %for.inc {4,5} >> [4] %for.end {7,24} >> [5] %for.end.split {4294967295,4294967295} >> [6] %if.then {8,15} >> [7] %if.then13 {9,10} >> [7] %if.end {11,12} >> [7] %if.then.if.end_crit_edge {13,14} >> [6] %if.end14 {16,21} >> [7] %exit.b4.barrier {17,20} >> [8] %exit.barrier {18,19} >> [6] %for.end.if.end14_crit_edge {22,23} >> >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140214/b346d79d/attachment.html>
Paul Vario
2014-Feb-15 22:07 UTC
[LLVMdev] DominatorTree not updated properly after calling the llvm::SplitBlock.
Hi Andy, As it turns out, it was my own mistake. I added a couple of BBs, and forgot to perform "DT->addNewBlock" on them. Still, in the situation where CFG gets modified, the behavior of the DominatorTree is counter-intuitive to what LLVM newbies expected to find .. you would think that DT keeps track of how CFG is being modified, and perform analysis updates on-the-fly automatically. Thanks a lot for the help. Best Regards, Paul On Fri, Feb 14, 2014 at 1:13 PM, Andrew Trick <atrick at apple.com> wrote:> > On Feb 14, 2014, at 9:50 AM, Paul Vario <paul.paul.mit at gmail.com> wrote: > > Hi Andrew, > > Thanks a lot. But the function "DT->dominate(A,B)" decides the > dominance relationship through comparing the DFS numbers, right? At > least, in my example, when I check whether the newly split node (i.e., % > *for.end.split*) DOMINATES the original node (I.e., %for.end), the answer > is true, which is obviously wrong. > > > That sounds like a bug. When DFSInfoValid==false, the DFS number does not > affect the query. So I don't know why you're getting the wrong answer. > > I know you don't have a test case, but I suggest filling a bugzilla PR and > attaching a dump of both your IR and Domtree before splitting and after > splitting. > > -Andy > > Paul > > > On Fri, Feb 14, 2014 at 1:59 AM, Andrew Trick <atrick at apple.com> wrote: > >> >> On Feb 13, 2014, at 4:34 PM, Paul Vario <paul.paul.mit at gmail.com> wrote: >> >> Hi Fellows, >> >> I am writing a pass that requires the DominatorTree pass. In the >> runOnFunction of my own pass, I call llvm::SplitBlock to split a block >> (%for.end) at it's first insert point. Then, when I dump my dominator tree >> immediately after, I can see the newly split %for.end.split, but its >> DFSNumIn and DFSNumOut are not properly updated in llvm::SplitBlock (i.e., >> still the initialized -1). At the same time, the DT->dump() results also >> show that DFSInfoValid equals false! I could not figure out what I did >> wrong, b/c it seems all the analysis updating should be handled by >> llvm::SplitBlock. Any suggestions on how to approach this situation? Thanks >> a bunch in advance. >> >> >> Hi Paul, >> >> DFSNumbers is a cache within the DominatorTree analysis. It is lazily >> computed after a certain number of queries. It's kind of hard to >> incrementally update these numbers because we may have to shift them all. >> >> At any rate, invalid DFS numbers does not mean something is wrong with >> the analysis. >> >> -Andy >> >> >> >> ------------------------- The actual dump of my dominator tree after >> SplitBlock -------------------- >> >> Inorder Dominator Tree: DFSNumbers invalid: 1 slow queries. >> [1] %entry.barrier {0,27} >> [2] %entry {1,26} >> [3] %for.cond {2,25} >> [4] %for.body {3,6} >> [5] %for.inc {4,5} >> [4] %for.end {7,24} >> *[5] %for.end.split {4294967295,4294967295}* >> [6] %if.then {8,15} >> [7] %if.then13 {9,10} >> [7] %if.end {11,12} >> [7] %if.then.if.end_crit_edge {13,14} >> [6] %if.end14 {16,21} >> [7] %exit.b4.barrier {17,20} >> [8] %exit.barrier {18,19} >> [6] %for.end.if.end14_crit_edge {22,23} >> >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >> >> >> > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140215/f346b146/attachment.html>