<html><head><meta http-equiv="Content-Type" content="text/html charset=windows-1252"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><br><div><div>On Feb 15, 2014, at 2:07 PM, Paul Vario <<a href="mailto:paul.paul.mit@gmail.com">paul.paul.mit@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div dir="ltr">Hi Andy,<div><br></div><div> 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.</div></div></blockquote><div><br></div>It would be nice to have robust incremental updates behind a simple API. It’s the kind of thing that doesn’t get worked on because it's too easy to rerun DT analysis when needed.</div><div><br></div><div>-Andy</div><div><br><blockquote type="cite"><div dir="ltr">
<div><br></div><div>Best Regards,</div><div>Paul</div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Fri, Feb 14, 2014 at 1:13 PM, Andrew Trick <span dir="ltr"><<a href="mailto:atrick@apple.com" target="_blank">atrick@apple.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><br><div><div class=""><div>On Feb 14, 2014, at 9:50 AM, Paul Vario <<a href="mailto:paul.paul.mit@gmail.com" target="_blank">paul.paul.mit@gmail.com</a>> wrote:</div>
<br><blockquote type="cite"><div dir="ltr">Hi Andrew,<div><br></div><div> Thanks a lot. But the function "DT->dominate(A,B)" decides the dominance relationship through comparing the <span style="font-family:arial,sans-serif;font-size:13px">DFS numbers, right? At least, in my example, when I check whether the newly split node (i.e., %</span><b style="color:rgb(80,0,80)">for.end.split</b><span style="font-family:arial,sans-serif;font-size:13px">) DOMINATES the original node (I.e., %for.end), the answer is true, which is obviously wrong.</span></div>
</div></blockquote><div><br></div></div><div>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.</div><div><br></div><div>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.</div>
<div><br></div><div>-Andy</div><div><div class="h5"><br><blockquote type="cite"><div dir="ltr">
<div><span style="font-family:arial,sans-serif;font-size:13px">Paul </span></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">
On Fri, Feb 14, 2014 at 1:59 AM, Andrew Trick <span dir="ltr"><<a href="mailto:atrick@apple.com" target="_blank">atrick@apple.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div style="word-wrap:break-word"><br><div><div><div>On Feb 13, 2014, at 4:34 PM, Paul Vario <<a href="mailto:paul.paul.mit@gmail.com" target="_blank">paul.paul.mit@gmail.com</a>> wrote:</div><br><blockquote type="cite">
<div dir="ltr"><div>Hi Fellows,</div><div><br></div><div> 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. <span style="color:rgb(68,68,68);font-family:arial,sans-serif;line-height:16.1200008392334px">Any suggestions on how to approach this</span><span style="color:rgb(68,68,68);font-family:arial,sans-serif;line-height:16.1200008392334px"> situation?</span> Thanks a bunch in advance.</div>
</div></blockquote><div><br></div></div>Hi Paul,</div><div><br></div><div>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.</div>
<div><br></div><div>At any rate, invalid DFS numbers does not mean something is wrong with the analysis.</div><div><br></div><div>-Andy</div><div><br></div><div><blockquote type="cite"><div><div dir="ltr">
<div><br></div><div><br></div><div>------------------------- The actual dump of my dominator tree after SplitBlock --------------------</div><div><br></div><div>Inorder Dominator Tree: DFSNumbers invalid: 1 slow queries.</div>
<div> [1] %entry.barrier {0,27}</div><div> [2] %entry {1,26}</div><div> [3] %for.cond {2,25}</div><div> [4] %for.body {3,6}</div><div> [5] %for.inc {4,5}</div><div> [4] %for.end {7,24}</div>
<div> <b>[5] %for.end.split {4294967295,4294967295}</b></div><div> [6] %if.then {8,15}</div><div> [7] %if.then13 {9,10}</div><div> [7] %if.end {11,12}</div><div> [7] %if.then.if.end_crit_edge {13,14}</div>
<div> [6] %if.end14 {16,21}</div><div> [7] %exit.b4.barrier {17,20}</div><div> [8] %exit.barrier {18,19}</div><div> [6] %for.end.if.end14_crit_edge {22,23}</div><div><br>
</div>
</div></div>
_______________________________________________<br>LLVM Developers mailing list<br><a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu/" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br></blockquote></div><br></div></blockquote></div><br></div>
</blockquote></div></div></div><br></div></blockquote></div><br></div>
</blockquote></div><br></body></html>