llvm dev - Feb 2014 - [LLVMdev] DominatorTree not updated properly after calling the llvm::SplitBlock.

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.


-------------------------  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}
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140213/f758a137/attachment.html>

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/20140213/d3fb6b0e/attachment.html>

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>