[LLVMdev] DominatorTree not updated properly after calling the llvm::SplitBlock.

[Andrew Trick]

On Feb 15, 2014, at 2:07 PM, Paul Vario <paul.paul.mit at gmail.com> wrote:

> 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.

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.

-Andy

> 
> 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/6f30eab8/attachment.html>