thr3ads.net - llvm dev - [llvm-dev] When can the dominator tree not contain a node for a basic block? [Sep 2015]

If this information is useful, please help other people find it:
Share via:

Philip Reames via llvm-dev

2015-Sep-21 16:26 UTC

[llvm-dev] When can the dominator tree not contain a node for a basic block?

When looking into https://llvm.org/bugs/show_bug.cgi?id=24866, I 
discovered that the root cause of the crash is that I was expecting 
every basic block to have a corresponding Node in the dominator tree.  
Apparently, the "while.end" basic block in the example does not have a
Node in the Dominator Tree.  Can anyone tell me if this is expected?   
If so, under what circumstances?

Interestingly, the crash in question appears to be fairly recently 
introduced.  A checkout from week before last didn't crash, whereas a 
checkout from this morning does.  I have yet tried to isolate the change 
in question; before doing so, I wanted to determine if this was a newly 
introduced problem (i.e. every BB should have a Node), or merely a newly 
exposed problem (i.e. not every BB does).

Philip

For reference, here's the reproduction command:
opt -S <input> -value-tracking-dom-conditions -licm -load-combine

And here's the IR:
; ModuleID = '../bugpoint-reduced-simplified.bc'
target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-windows-msvc18.0.0"

%struct.c_derived_tbl.2.5.8.11.14.17.23.38.59.80.92.98.104.107.155.183 = 
type { [256 x i32], [256 x i8] }

; Function Attrs: nounwind uwtable
define void 
@encode_one_blockX2(%struct.c_derived_tbl.2.5.8.11.14.17.23.38.59.80.92.98.104.107.155.183*
nocapture readonly %actbl) #0 {
entry:
   br i1 undef, label %L_KLOOP_01, label %L_KLOOP.preheader

L_KLOOP_01:                                       ; preds = %while.end, 
%entry
   br label %L_KLOOP.preheader

L_KLOOP_08:                                       ; preds = %while.end
   br label %L_KLOOP.preheader

L_KLOOP.preheader:                                ; preds = %L_KLOOP_08, 
%L_KLOOP_01, %entry
   %r.2.ph = phi i32 [ undef, %L_KLOOP_08 ], [ 0, %entry ], [ undef, 
%L_KLOOP_01 ]
   br label %L_KLOOP

L_KLOOP:                                          ; preds = %while.end, 
%L_KLOOP.preheader
   %r.2 = phi i32 [ 0, %while.end ], [ %r.2.ph, %L_KLOOP.preheader ]
   br i1 undef, label %while.body, label %while.end

while.body:                                       ; preds = %while.body, 
%L_KLOOP
   br label %while.body

while.end:                                        ; preds = %L_KLOOP
   %shl105 = shl i32 %r.2, 4
   %add106 = add nsw i32 %shl105, undef ;; <-- THIS is the context 
instruction.  V is undef
   %idxprom107 = sext i32 %add106 to i64
   %arrayidx108 = getelementptr inbounds 
%struct.c_derived_tbl.2.5.8.11.14.17.23.38.59.80.92.98.104.107.155.183, 
%struct.c_derived_tbl.2.5.8.11.14.17.23.38.59.80.92.98.104.107.155.183* 
%actbl, i64 0, i32 0, i64 %idxprom107
   %0 = load i32, i32* %arrayidx108, align 4, !tbaa !2
   %arrayidx110 = getelementptr inbounds 
%struct.c_derived_tbl.2.5.8.11.14.17.23.38.59.80.92.98.104.107.155.183, 
%struct.c_derived_tbl.2.5.8.11.14.17.23.38.59.80.92.98.104.107.155.183* 
%actbl, i64 0, i32 1, i64 %idxprom107
   %1 = load i8, i8* %arrayidx110, align 1, !tbaa !6
   indirectbr i8* undef, [label %L_KLOOP_DONE, label %L_KLOOP_01, label 
%L_KLOOP_08, label %L_KLOOP]

L_KLOOP_DONE:                                     ; preds = %while.end
   ret void
}

attributes #0 = { nounwind uwtable
"disable-tail-calls"="false"
"less-precise-fpmad"="false"
"no-frame-pointer-elim"="false"
"no-infs-fp-math"="false"
"no-nans-fp-math"="false"
"stack-protector-buffer-size"="8"
"target-cpu"="x86-64"
"target-features"="+sse,+sse2"
"unsafe-fp-math"="false"
"use-soft-float"="false" }

!llvm.module.flags = !{!0}
!llvm.ident = !{!1}

!0 = !{i32 1, !"PIC Level", i32 2}
!1 = !{!"clang version 3.8.0 (http://llvm.org/git/clang.git 
37c860b7d0d43dde1edcd324e00a10a62b2c5776) (http://llvm.org/git/llvm.git 
fb73c0262af4183555253a5c8c13025a6e7630bc)"}
!2 = !{!3, !3, i64 0}
!3 = !{!"int", !4, i64 0}
!4 = !{!"omnipotent char", !5, i64 0}
!5 = !{!"Simple C/C++ TBAA"}
!6 = !{!4, !4, i64 0}

Krzysztof Parzyszek via llvm-dev

2015-Sep-21 16:43 UTC

head link

[llvm-dev] When can the dominator tree not contain a node for a basic block?

On 9/21/2015 11:26 AM, Philip Reames via llvm-dev wrote:> When looking into https://llvm.org/bugs/show_bug.cgi?id=24866, I
> discovered that the root cause of the crash is that I was expecting
> every basic block to have a corresponding Node in the dominator tree.
> Apparently, the "while.end" basic block in the example does not
have a
> Node in the Dominator Tree.  Can anyone tell me if this is expected? If
> so, under what circumstances?
This happens when the block is not reachable.  In such cases, there is 
no way to connect this block into the dominator tree (and keep it as a 
tree, not a forest).

> Interestingly, the crash in question appears to be fairly recently
> introduced.  A checkout from week before last didn't crash, whereas a
> checkout from this morning does.  I have yet tried to isolate the change
> in question; before doing so, I wanted to determine if this was a newly
> introduced problem (i.e. every BB should have a Node), or merely a newly
> exposed problem (i.e. not every BB does).
Given that the predecessor has a branch with the condition being undef, 
I suppose this may be caused by treating undef as "true" in
conditional
branches.

-Krzysztof

-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
hosted by The Linux Foundation

Daniel Berlin via llvm-dev

2015-Sep-21 16:48 UTC

head link

[llvm-dev] When can the dominator tree not contain a node for a basic block?

So, there is no good answer.
It's not documented anywhere, and genericdomtree.h makes assumptions both
ways.

For example, :
 void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const
{
...

 if (!RN)
       return; // If R is unreachable, it will not be present in the DOM
tree. :)
...
}
vs

dominates()
{
...
  // Any unreachable use is dominated, even if Def == User.
   if (!isReachableFromEntry(UseBB))
     return true;

   // Unreachable definitions don't dominate anything.
   if (!isReachableFromEntry(DefBB))
     return false;
}
...
>From what I can tell, the split here is because we expect that nodes that*become unreachable* from entry will still be in the dom tree, but nodes
that are completely unreachable generally don't end up in the domtree.
GetNode will work on the former, but not the latter.  This seems ... wrong.

This is *dominators*, mind you.
post-dominators goes through explicit machinations (and fails in some
cases) when building to try to make sure even unreachable nodes end up in
the dominator tree.

My suggestion would be that we clearly think about this, document and
define what should happen, declare anything violating these invariants to
be a bug, and go fix them.

As to what "the right answers are", this seems harder.

I've previously pointed out why giving dominance answers on unreachable
nodes rarely, if ever, makes sense given the formal definition of a
dominator:
 "a node <https://en.wikipedia.org/wiki/Basic_block> *d* *dominates*
a node
*n* if every path from the *entry node* to *n* must go through *d"*

If n is unreachable, it is not dominated  by anything, since no path from
the entry node to n exist, and of the 0 paths that exist, none of them go
through any other node.  Essentially, right now we claim the opposite -
that *every* path from the entry node goes to the unreachable node, and in
fact, that it goes through *every* block.

This means, for example, that if you tried to reconstruct the dominator
tree by calling dominates on pairs of instructions, you'd get wrong answers
(you'd simultaneously try to make the unreachable block a child of every
node in the dominator tree, as well as no node in the dominator tree)

In fact, you can show that most dominance algorithms will never consider an
unreachable node to dominate anything, even going back to the Lowry and
Medlock algorithm from 1969, or even the original Prosser description of a
dominator on flow diagrams from 1959:
"We say box i dominates box j if every path (leading from input to output
through the diagram) which passes through box j must also pass through box
i. Thus box i dominates box j if box j is subordinate to box i in the
program"

Now, whether we care about this or not, it's up in the air.

(Note that forward/reverse unreachable for dom/post-dom is different from
"never exits", since never-exiting nodes are reachable)






On Mon, Sep 21, 2015 at 9:26 AM, Philip Reames <listmail at
philipreames.com>
wrote:
> When looking into https://llvm.org/bugs/show_bug.cgi?id=24866, I
> discovered that the root cause of the crash is that I was expecting every
> basic block to have a corresponding Node in the dominator tree.
> Apparently, the "while.end" basic block in the example does not
have a Node
> in the Dominator Tree.  Can anyone tell me if this is expected?   If so,
> under what circumstances?
>
> Interestingly, the crash in question appears to be fairly recently
> introduced.  A checkout from week before last didn't crash, whereas a
> checkout from this morning does.  I have yet tried to isolate the change in
> question; before doing so, I wanted to determine if this was a newly
> introduced problem (i.e. every BB should have a Node), or merely a newly
> exposed problem (i.e. not every BB does).
>
> Philip
>
> For reference, here's the reproduction command:
> opt -S <input> -value-tracking-dom-conditions -licm -load-combine
>
> And here's the IR:
> ; ModuleID = '../bugpoint-reduced-simplified.bc'
> target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"
> target triple = "x86_64-pc-windows-msvc18.0.0"
>
> %struct.c_derived_tbl.2.5.8.11.14.17.23.38.59.80.92.98.104.107.155.183 >
type { [256 x i32], [256 x i8] }
>
> ; Function Attrs: nounwind uwtable
> define void
>
@encode_one_blockX2(%struct.c_derived_tbl.2.5.8.11.14.17.23.38.59.80.92.98.104.107.155.183*
> nocapture readonly %actbl) #0 {
> entry:
>   br i1 undef, label %L_KLOOP_01, label %L_KLOOP.preheader
>
> L_KLOOP_01:                                       ; preds = %while.end,
> %entry
>   br label %L_KLOOP.preheader
>
> L_KLOOP_08:                                       ; preds = %while.end
>   br label %L_KLOOP.preheader
>
> L_KLOOP.preheader:                                ; preds = %L_KLOOP_08,
> %L_KLOOP_01, %entry
>   %r.2.ph = phi i32 [ undef, %L_KLOOP_08 ], [ 0, %entry ], [ undef,
> %L_KLOOP_01 ]
>   br label %L_KLOOP
>
> L_KLOOP:                                          ; preds = %while.end,
> %L_KLOOP.preheader
>   %r.2 = phi i32 [ 0, %while.end ], [ %r.2.ph, %L_KLOOP.preheader ]
>   br i1 undef, label %while.body, label %while.end
>
> while.body:                                       ; preds = %while.body,
> %L_KLOOP
>   br label %while.body
>
> while.end:                                        ; preds = %L_KLOOP
>   %shl105 = shl i32 %r.2, 4
>   %add106 = add nsw i32 %shl105, undef ;; <-- THIS is the context
> instruction.  V is undef
>   %idxprom107 = sext i32 %add106 to i64
>   %arrayidx108 = getelementptr inbounds
> %struct.c_derived_tbl.2.5.8.11.14.17.23.38.59.80.92.98.104.107.155.183,
> %struct.c_derived_tbl.2.5.8.11.14.17.23.38.59.80.92.98.104.107.155.183*
> %actbl, i64 0, i32 0, i64 %idxprom107
>   %0 = load i32, i32* %arrayidx108, align 4, !tbaa !2
>   %arrayidx110 = getelementptr inbounds
> %struct.c_derived_tbl.2.5.8.11.14.17.23.38.59.80.92.98.104.107.155.183,
> %struct.c_derived_tbl.2.5.8.11.14.17.23.38.59.80.92.98.104.107.155.183*
> %actbl, i64 0, i32 1, i64 %idxprom107
>   %1 = load i8, i8* %arrayidx110, align 1, !tbaa !6
>   indirectbr i8* undef, [label %L_KLOOP_DONE, label %L_KLOOP_01, label
> %L_KLOOP_08, label %L_KLOOP]
>
> L_KLOOP_DONE:                                     ; preds = %while.end
>   ret void
> }
>
> attributes #0 = { nounwind uwtable
"disable-tail-calls"="false"
> "less-precise-fpmad"="false"
"no-frame-pointer-elim"="false"
> "no-infs-fp-math"="false"
"no-nans-fp-math"="false"
> "stack-protector-buffer-size"="8"
"target-cpu"="x86-64"
> "target-features"="+sse,+sse2"
"unsafe-fp-math"="false"
> "use-soft-float"="false" }
>
> !llvm.module.flags = !{!0}
> !llvm.ident = !{!1}
>
> !0 = !{i32 1, !"PIC Level", i32 2}
> !1 = !{!"clang version 3.8.0 (http://llvm.org/git/clang.git
> 37c860b7d0d43dde1edcd324e00a10a62b2c5776) (http://llvm.org/git/llvm.git
> fb73c0262af4183555253a5c8c13025a6e7630bc)"}
> !2 = !{!3, !3, i64 0}
> !3 = !{!"int", !4, i64 0}
> !4 = !{!"omnipotent char", !5, i64 0}
> !5 = !{!"Simple C/C++ TBAA"}
> !6 = !{!4, !4, i64 0}
>
>-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150921/5eff3b5a/attachment.html>

Philip Reames via llvm-dev

2015-Sep-21 21:06 UTC

head link

[llvm-dev] When can the dominator tree not contain a node for a basic block?

On 09/21/2015 09:48 AM, Daniel Berlin wrote:> So, there is no good answer.
> It's not documented anywhere, and genericdomtree.h makes assumptions 
> both ways.
>
> For example, :
>  void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result)
const {
> ...
>
>  if (!RN)
>        return; // If R is unreachable, it will not be present in the 
> DOM tree. :)
> ...
> }
> vs
>
> dominates()
> {
> ...
>   // Any unreachable use is dominated, even if Def == User.
>    if (!isReachableFromEntry(UseBB))
>      return true;
>
>    // Unreachable definitions don't dominate anything.
>    if (!isReachableFromEntry(DefBB))
>      return false;
> }
> ...
>
> From what I can tell, the split here is because we expect that nodes 
> that *become unreachable* from entry will still be in the dom tree, 
> but nodes that are completely unreachable generally don't end up in 
> the domtree.  GetNode will work on the former, but not the latter.  
> This seems ... wrong.This actually seems completely defensible to me.  Or at least
explainable.>
> This is *dominators*, mind you.
> post-dominators goes through explicit machinations (and fails in some 
> cases) when building to try to make sure even unreachable nodes end up 
> in the dominator tree.
>
> My suggestion would be that we clearly think about this, document and 
> define what should happen, declare anything violating these invariants 
> to be a bug, and go fix them.
+1 to the documentation at least.  :)>
> As to what "the right answers are", this seems harder.
>
> I've previously pointed out why giving dominance answers on 
> unreachable nodes rarely, if ever, makes sense given the formal 
> definition of a dominator:
>  "a node
<https://en.wikipedia.org/wiki/Basic_block>*d*/dominates/ a
> node *n* if every path from the /entry node/ to *n* must go through
*d"*
> *
> *
> If n is unreachable, it is not dominated  by anything, since no path 
> from the entry node to n exist, and of the 0 paths that exist, none of 
> them go through any other node. Essentially, right now we claim the 
> opposite - that *every* path from the entry node goes to the 
> unreachable node, and in fact, that it goes through *every* block.
>
> This means, for example, that if you tried to reconstruct the 
> dominator tree by calling dominates on pairs of instructions, you'd 
> get wrong answers (you'd simultaneously try to make the unreachable 
> block a child of every node in the dominator tree, as well as no node 
> in the dominator tree)
>
> In fact, you can show that most dominance algorithms will never 
> consider an unreachable node to dominate anything, even going back to 
> the Lowry and Medlock algorithm from 1969, or even the original 
> Prosser description of a dominator on flow diagrams from 1959:
> "We say box i dominates box j if every path (leading from input to 
> output through the diagram) which passes through box j must also pass 
> through box i. Thus box i dominates box j if box j is subordinate to 
> box i in the program"
>
> Now, whether we care about this or not, it's up in the air.
>
> (Note that forward/reverse unreachable for dom/post-dom is different 
> from "never exits", since never-exiting nodes are reachable)I'm in favor of revising the definition, but I'd like to start by 
documenting and understanding current behavior.  What you said above 
about initially unreachable vs became unreachable seems like a clear and 
understandable rule today.  Unless you object, I'll update the 
documentation to reflect this, possibly with a note that we'd like to 
strengthen the definition in the future.>
>
>
>
>
>
> On Mon, Sep 21, 2015 at 9:26 AM, Philip Reames 
> <listmail at philipreames.com <mailto:listmail at
philipreames.com>> wrote:
>
>     When looking into https://llvm.org/bugs/show_bug.cgi?id=24866, I
>     discovered that the root cause of the crash is that I was
>     expecting every basic block to have a corresponding Node in the
>     dominator tree.  Apparently, the "while.end" basic block in
the
>     example does not have a Node in the Dominator Tree. Can anyone
>     tell me if this is expected?   If so, under what circumstances?
>
>     Interestingly, the crash in question appears to be fairly recently
>     introduced.  A checkout from week before last didn't crash,
>     whereas a checkout from this morning does.  I have yet tried to
>     isolate the change in question; before doing so, I wanted to
>     determine if this was a newly introduced problem (i.e. every BB
>     should have a Node), or merely a newly exposed problem (i.e. not
>     every BB does).
>
>     Philip
>
>     For reference, here's the reproduction command:
>     opt -S <input> -value-tracking-dom-conditions -licm -load-combine
>
>     And here's the IR:
>     ; ModuleID = '../bugpoint-reduced-simplified.bc'
>     target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"
>     target triple = "x86_64-pc-windows-msvc18.0.0"
>
>     %struct.c_derived_tbl.2.5.8.11.14.17.23.38.59.80.92.98.104.107.155.183
>     = type { [256 x i32], [256 x i8] }
>
>     ; Function Attrs: nounwind uwtable
>     define void
>    
@encode_one_blockX2(%struct.c_derived_tbl.2.5.8.11.14.17.23.38.59.80.92.98.104.107.155.183*
>     nocapture readonly %actbl) #0 {
>     entry:
>       br i1 undef, label %L_KLOOP_01, label %L_KLOOP.preheader
>
>     L_KLOOP_01:                                       ; preds >    
%while.end, %entry
>       br label %L_KLOOP.preheader
>
>     L_KLOOP_08:                                       ; preds = %while.end
>       br label %L_KLOOP.preheader
>
>     L_KLOOP.preheader:                                ; preds >    
%L_KLOOP_08, %L_KLOOP_01, %entry
>       %r.2.ph <http://r.2.ph> = phi i32 [ undef, %L_KLOOP_08 ], [ 0,
>     %entry ], [ undef, %L_KLOOP_01 ]
>       br label %L_KLOOP
>
>     L_KLOOP:                                          ; preds >    
%while.end, %L_KLOOP.preheader
>       %r.2 = phi i32 [ 0, %while.end ], [ %r.2.ph <http://r.2.ph>,
>     %L_KLOOP.preheader ]
>       br i1 undef, label %while.body, label %while.end
>
>     while.body:                                       ; preds >    
%while.body, %L_KLOOP
>       br label %while.body
>
>     while.end:                                        ; preds = %L_KLOOP
>       %shl105 = shl i32 %r.2, 4
>       %add106 = add nsw i32 %shl105, undef ;; <-- THIS is the context
>     instruction.  V is undef
>       %idxprom107 = sext i32 %add106 to i64
>       %arrayidx108 = getelementptr inbounds
>     %struct.c_derived_tbl.2.5.8.11.14.17.23.38.59.80.92.98.104.107.155.183,
>     %struct.c_derived_tbl.2.5.8.11.14.17.23.38.59.80.92.98.104.107.155.183*
>     %actbl, i64 0, i32 0, i64 %idxprom107
>       %0 = load i32, i32* %arrayidx108, align 4, !tbaa !2
>       %arrayidx110 = getelementptr inbounds
>     %struct.c_derived_tbl.2.5.8.11.14.17.23.38.59.80.92.98.104.107.155.183,
>     %struct.c_derived_tbl.2.5.8.11.14.17.23.38.59.80.92.98.104.107.155.183*
>     %actbl, i64 0, i32 1, i64 %idxprom107
>       %1 = load i8, i8* %arrayidx110, align 1, !tbaa !6
>       indirectbr i8* undef, [label %L_KLOOP_DONE, label %L_KLOOP_01,
>     label %L_KLOOP_08, label %L_KLOOP]
>
>     L_KLOOP_DONE:                                     ; preds = %while.end
>       ret void
>     }
>
>     attributes #0 = { nounwind uwtable
"disable-tail-calls"="false"
>     "less-precise-fpmad"="false"
"no-frame-pointer-elim"="false"
>     "no-infs-fp-math"="false"
"no-nans-fp-math"="false"
>     "stack-protector-buffer-size"="8"
"target-cpu"="x86-64"
>     "target-features"="+sse,+sse2"
"unsafe-fp-math"="false"
>     "use-soft-float"="false" }
>
>     !llvm.module.flags = !{!0}
>     !llvm.ident = !{!1}
>
>     !0 = !{i32 1, !"PIC Level", i32 2}
>     !1 = !{!"clang version 3.8.0 (http://llvm.org/git/clang.git
>     37c860b7d0d43dde1edcd324e00a10a62b2c5776)
>     (http://llvm.org/git/llvm.git
>     fb73c0262af4183555253a5c8c13025a6e7630bc)"}
>     !2 = !{!3, !3, i64 0}
>     !3 = !{!"int", !4, i64 0}
>     !4 = !{!"omnipotent char", !5, i64 0}
>     !5 = !{!"Simple C/C++ TBAA"}
>     !6 = !{!4, !4, i64 0}
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150921/7132600b/attachment.html>

Joseph Tremoulet via llvm-dev

2015-Sep-22 01:11 UTC

head link

[llvm-dev] When can the dominator tree not contain a node for a basic block?

<pedantry>
FWIW, I've always understood "unreachable nodes are dominated by
everything and dominate nothing but other unreachable nodes" to be the
conventional interpretation of the formal definition, since universal
quantification over an empty set is vacuously true; i.e. " of the 0 paths
that exist, *all* of them go through any other node ".
> we claim … that *every* path from the entry node goes to the unreachable
nodeI don't think that follows; saying that d doesn't dominate n says that a
path exists form start to n that doesn't go through d, but saying that d
does dominate n just says something about all paths in a possibly empty set.
> most dominance algorithms will never consider an unreachable node to
dominate anythingAgreed, but I think here we're talking about the inverse; whether anything
dominates an unreachable node.
</pedantry>

As to the more important point, I've certainly seen dominance queries on
unreachable code cause trouble before and agree there's just not a good
answer.  I don't know if this would be acceptable for the API in LLVM, but
you'd almost want dominates(d, n) to assert that n is reachable and force
callers to decide what they want to do with unreachable code.
I agree with your point that confusion/problems arise when people expect
pairwise dominance queries to equate to reachability in a tree and
"extra" edges to unreachable nodes defeat their expectations.  I think
what happens if you go all the way to the other extreme (and effectively use the
predicate "d dominates n and n is reachable" in place of "d
dominates n") is that sometimes a pass will be processing a fragment of the
CFG (like the diamond of an if/else) and expect certain dominance properties on
it (like that the head dominates both arms and the join point), which would then
be reported as false if the whole fragment is unreachable.  Likewise, one would
expect entry to dominate all nodes, etc.
I suppose that many unreachable code fragments have natural heads and you could
figure out the "expected" answers for those, but cycle-breaking would
still be arbitrary and I think usually the right answer is that the caller
should be ignoring or pre-removing unreachable code.

Thanks
-Joseph

From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of Daniel
Berlin via llvm-dev
Sent: Monday, September 21, 2015 12:48 PM
To: Philip Reames <listmail at philipreames.com>
Cc: llvm-dev <llvm-dev at lists.llvm.org>
Subject: Re: [llvm-dev] When can the dominator tree not contain a node for a
basic block?

So, there is no good answer.
It's not documented anywhere, and genericdomtree.h makes assumptions both
ways.

For example, :
 void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const
{
...

 if (!RN)
       return; // If R is unreachable, it will not be present in the DOM tree.
:)
...
}
vs

dominates()
{
...
  // Any unreachable use is dominated, even if Def == User.
   if (!isReachableFromEntry(UseBB))
     return true;

   // Unreachable definitions don't dominate anything.
   if (!isReachableFromEntry(DefBB))
     return false;
}
...

From what I can tell, the split here is because we expect that nodes that
*become unreachable* from entry will still be in the dom tree, but nodes that
are completely unreachable generally don't end up in the domtree.  GetNode
will work on the former, but not the latter.  This seems ... wrong.

This is *dominators*, mind you.
post-dominators goes through explicit machinations (and fails in some cases)
when building to try to make sure even unreachable nodes end up in the dominator
tree.

My suggestion would be that we clearly think about this, document and define
what should happen, declare anything violating these invariants to be a bug, and
go fix them.

As to what "the right answers are", this seems harder.

I've previously pointed out why giving dominance answers on unreachable
nodes rarely, if ever, makes sense given the formal definition of a dominator:
 "a
node<https://na01.safelinks.protection.outlook.com/?url=https%3a%2f%2fen.wikipedia.org%2fwiki%2fBasic_block&data=01%7c01%7cjotrem%40microsoft.com%7c0eaa02c7e0ca4450610008d2c2a47ef5%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=ZIpgDcoJDbRUlp1xT%2bvQTEdSshYDO3cT2CLRsVDikB4%3d>
d dominates a node n if every path from the entry node to n must go through
d"

If n is unreachable, it is not dominated  by anything, since no path from the
entry node to n exist, and of the 0 paths that exist, none of them go through
any other node.  Essentially, right now we claim the opposite - that *every*
path from the entry node goes to the unreachable node, and in fact, that it goes
through *every* block.

This means, for example, that if you tried to reconstruct the dominator tree by
calling dominates on pairs of instructions, you'd get wrong answers
(you'd simultaneously try to make the unreachable block a child of every
node in the dominator tree, as well as no node in the dominator tree)

In fact, you can show that most dominance algorithms will never consider an
unreachable node to dominate anything, even going back to the Lowry and Medlock
algorithm from 1969, or even the original Prosser description of a dominator on
flow diagrams from 1959:
"We say box i dominates box j if every path (leading from input to output
through the diagram) which passes through box j must also pass through box i.
Thus box i dominates box j if box j is subordinate to box i in the program"

Now, whether we care about this or not, it's up in the air.

(Note that forward/reverse unreachable for dom/post-dom is different from
"never exits", since never-exiting nodes are reachable)

On Mon, Sep 21, 2015 at 9:26 AM, Philip Reames <listmail at
philipreames.com<mailto:listmail at philipreames.com>> wrote:
When looking into
https://llvm.org/bugs/show_bug.cgi?id=24866<https://na01.safelinks.protection.outlook.com/?url=https%3a%2f%2fllvm.org%2fbugs%2fshow_bug.cgi%3fid%3d24866&data=01%7c01%7cjotrem%40microsoft.com%7c0eaa02c7e0ca4450610008d2c2a47ef5%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=bNpncZVa7gkv5td%2bmmcfAkf3t%2bffFuZftsg6kJ2Ztpk%3d>,
I discovered that the root cause of the crash is that I was expecting every
basic block to have a corresponding Node in the dominator tree.  Apparently, the
"while.end" basic block in the example does not have a Node in the
Dominator Tree.  Can anyone tell me if this is expected?   If so, under what
circumstances?

Interestingly, the crash in question appears to be fairly recently introduced. 
A checkout from week before last didn't crash, whereas a checkout from this
morning does.  I have yet tried to isolate the change in question; before doing
so, I wanted to determine if this was a newly introduced problem (i.e. every BB
should have a Node), or merely a newly exposed problem (i.e. not every BB does).

Philip

For reference, here's the reproduction command:
opt -S <input> -value-tracking-dom-conditions -licm -load-combine

And here's the IR:
; ModuleID = '../bugpoint-reduced-simplified.bc'
target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-windows-msvc18.0.0"

%struct.c_derived_tbl.2.5.8.11.14.17.23.38.59.80.92.98.104.107.155.183 = type {
[256 x i32], [256 x i8] }

; Function Attrs: nounwind uwtable
define void
@encode_one_blockX2(%struct.c_derived_tbl.2.5.8.11.14.17.23.38.59.80.92.98.104.107.155.183*
nocapture readonly %actbl) #0 {
entry:
  br i1 undef, label %L_KLOOP_01, label %L_KLOOP.preheader

L_KLOOP_01:                                       ; preds = %while.end, %entry
  br label %L_KLOOP.preheader

L_KLOOP_08:                                       ; preds = %while.end
  br label %L_KLOOP.preheader

L_KLOOP.preheader:                                ; preds = %L_KLOOP_08,
%L_KLOOP_01, %entry

%r.2.ph<https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2fr.2.ph&data=01%7c01%7cjotrem%40microsoft.com%7c0eaa02c7e0ca4450610008d2c2a47ef5%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=jXpaIGmv6qhI7eaSNnoEvdGICfE53T553k6j7cGti94%3d>
= phi i32 [ undef, %L_KLOOP_08 ], [ 0, %entry ], [ undef, %L_KLOOP_01 ]
  br label %L_KLOOP

L_KLOOP:                                          ; preds = %while.end,
%L_KLOOP.preheader
  %r.2 = phi i32 [ 0, %while.end ], [
%r.2.ph<https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2fr.2.ph&data=01%7c01%7cjotrem%40microsoft.com%7c0eaa02c7e0ca4450610008d2c2a47ef5%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=jXpaIGmv6qhI7eaSNnoEvdGICfE53T553k6j7cGti94%3d>,
%L_KLOOP.preheader ]
  br i1 undef, label %while.body, label %while.end

while.body:                                       ; preds = %while.body,
%L_KLOOP
  br label %while.body

while.end:                                        ; preds = %L_KLOOP
  %shl105 = shl i32 %r.2, 4
  %add106 = add nsw i32 %shl105, undef ;; <-- THIS is the context
instruction.  V is undef
  %idxprom107 = sext i32 %add106 to i64
  %arrayidx108 = getelementptr inbounds
%struct.c_derived_tbl.2.5.8.11.14.17.23.38.59.80.92.98.104.107.155.183,
%struct.c_derived_tbl.2.5.8.11.14.17.23.38.59.80.92.98.104.107.155.183* %actbl,
i64 0, i32 0, i64 %idxprom107
  %0 = load i32, i32* %arrayidx108, align 4, !tbaa !2
  %arrayidx110 = getelementptr inbounds
%struct.c_derived_tbl.2.5.8.11.14.17.23.38.59.80.92.98.104.107.155.183,
%struct.c_derived_tbl.2.5.8.11.14.17.23.38.59.80.92.98.104.107.155.183* %actbl,
i64 0, i32 1, i64 %idxprom107
  %1 = load i8, i8* %arrayidx110, align 1, !tbaa !6
  indirectbr i8* undef, [label %L_KLOOP_DONE, label %L_KLOOP_01, label
%L_KLOOP_08, label %L_KLOOP]

L_KLOOP_DONE:                                     ; preds = %while.end
  ret void
}

attributes #0 = { nounwind uwtable
"disable-tail-calls"="false"
"less-precise-fpmad"="false"
"no-frame-pointer-elim"="false"
"no-infs-fp-math"="false"
"no-nans-fp-math"="false"
"stack-protector-buffer-size"="8"
"target-cpu"="x86-64"
"target-features"="+sse,+sse2"
"unsafe-fp-math"="false"
"use-soft-float"="false" }

!llvm.module.flags = !{!0}
!llvm.ident = !{!1}

!0 = !{i32 1, !"PIC Level", i32 2}
!1 = !{!"clang version 3.8.0
(http://llvm.org/git/clang.git<https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2fllvm.org%2fgit%2fclang.git&data=01%7c01%7cjotrem%40microsoft.com%7c0eaa02c7e0ca4450610008d2c2a47ef5%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=5BuQ3CnZsj0Hi7fOkJrCNa9e2n6FCRfyRiMaYYvQrYw%3d>
37c860b7d0d43dde1edcd324e00a10a62b2c5776)
(http://llvm.org/git/llvm.git<https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2fllvm.org%2fgit%2fllvm.git&data=01%7c01%7cjotrem%40microsoft.com%7c0eaa02c7e0ca4450610008d2c2a47ef5%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=wjkU7x%2bTSbgGd6ikqBsqKtOMmAYVUhHV4mtB6VqKMMc%3d>
fb73c0262af4183555253a5c8c13025a6e7630bc)"}
!2 = !{!3, !3, i64 0}
!3 = !{!"int", !4, i64 0}
!4 = !{!"omnipotent char", !5, i64 0}
!5 = !{!"Simple C/C++ TBAA"}
!6 = !{!4, !4, i64 0}

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150922/e7f75a01/attachment.html>

llvm dev - Sep 2015 - When can the dominator tree not contain a node for a basic block?

[llvm-dev] When can the dominator tree not contain a node for a basic block?

[llvm-dev] When can the dominator tree not contain a node for a basic block?

[llvm-dev] When can the dominator tree not contain a node for a basic block?

[llvm-dev] When can the dominator tree not contain a node for a basic block?

[llvm-dev] When can the dominator tree not contain a node for a basic block?