<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<br>
<br>
<div class="moz-cite-prefix">On 09/21/2015 09:48 AM, Daniel Berlin
wrote:<br>
</div>
<blockquote
cite="mid:CABTcG6KzfxZ-hfNquHFWNrhj4xQuZTxXT9CVA1JwZV66aQEgpA@mail.gmail.com"
type="cite">
<div dir="ltr">So, there is no good answer.
<div>It's not documented anywhere, and genericdomtree.h makes
assumptions both ways.</div>
<div><br>
</div>
<div>For example, :</div>
<div> void getDescendants(NodeT *R, SmallVectorImpl<NodeT
*> &Result) const {<br>
</div>
<div>...</div>
<div><br>
</div>
<div> if (!RN)</div>
<div> return; // If R is unreachable, it will not be
present in the DOM tree. :)</div>
<div>...</div>
<div>}</div>
<div>vs</div>
<div><br>
</div>
<div>dominates()</div>
<div>{<br>
...</div>
<div>
<div> // Any unreachable use is dominated, even if Def ==
User.</div>
<div> if (!isReachableFromEntry(UseBB))</div>
<div> return true;</div>
<div><br>
</div>
<div> // Unreachable definitions don't dominate anything.</div>
<div> if (!isReachableFromEntry(DefBB))</div>
<div> return false;</div>
</div>
<div>}</div>
<div>...</div>
<div><br>
</div>
<div>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.</div>
</div>
</blockquote>
This actually seems completely defensible to me. Or at least
explainable. <br>
<blockquote
cite="mid:CABTcG6KzfxZ-hfNquHFWNrhj4xQuZTxXT9CVA1JwZV66aQEgpA@mail.gmail.com"
type="cite">
<div dir="ltr">
<div><br>
</div>
<div>This is *dominators*, mind you.</div>
<div>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.</div>
<div><br>
</div>
<div>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.</div>
</div>
</blockquote>
+1 to the documentation at least. :)<br>
<blockquote
cite="mid:CABTcG6KzfxZ-hfNquHFWNrhj4xQuZTxXT9CVA1JwZV66aQEgpA@mail.gmail.com"
type="cite">
<div dir="ltr">
<div><br>
</div>
<div>As to what "the right answers are", this seems harder.</div>
<div><br>
</div>
<div>I've previously pointed out why giving dominance answers on
unreachable nodes rarely, if ever, makes sense given the
formal definition of a dominator:<br>
<span
style="color:rgb(37,37,37);font-family:sans-serif;font-size:14px;line-height:22.4px"> "a </span><a
moz-do-not-send="true"
href="https://en.wikipedia.org/wiki/Basic_block"
title="Basic block"
style="text-decoration:none;color:rgb(11,0,128);font-family:sans-serif;font-size:14px;line-height:22.4px;background-image:none;background-repeat:initial">node</a><span
style="color:rgb(37,37,37);font-family:sans-serif;font-size:14px;line-height:22.4px"> </span><b
style="color:rgb(37,37,37);font-family:sans-serif;font-size:14px;line-height:22.4px">d</b><span
style="color:rgb(37,37,37);font-family:sans-serif;font-size:14px;line-height:22.4px"> </span><i
style="color:rgb(37,37,37);font-family:sans-serif;font-size:14px;line-height:22.4px">dominates</i><span
style="color:rgb(37,37,37);font-family:sans-serif;font-size:14px;line-height:22.4px"> a
node </span><b
style="color:rgb(37,37,37);font-family:sans-serif;font-size:14px;line-height:22.4px">n</b><span
style="color:rgb(37,37,37);font-family:sans-serif;font-size:14px;line-height:22.4px"> if
every path from the </span><i
style="color:rgb(37,37,37);font-family:sans-serif;font-size:14px;line-height:22.4px">entry
node</i><span
style="color:rgb(37,37,37);font-family:sans-serif;font-size:14px;line-height:22.4px"> to </span><b
style="color:rgb(37,37,37);font-family:sans-serif;font-size:14px;line-height:22.4px">n</b><span
style="color:rgb(37,37,37);font-family:sans-serif;font-size:14px;line-height:22.4px"> must
go through </span><b
style="color:rgb(37,37,37);font-family:sans-serif;font-size:14px;line-height:22.4px">d"</b></div>
<div><b
style="color:rgb(37,37,37);font-family:sans-serif;font-size:14px;line-height:22.4px"><br>
</b></div>
<div>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.</div>
<div><br>
</div>
<div>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)</div>
<div><br>
</div>
<div>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:<br>
"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"<br>
</div>
<div><br>
</div>
<div>Now, whether we care about this or not, it's up in the air.</div>
<div><br>
</div>
<div>(Note that forward/reverse unreachable for dom/post-dom is
different from "never exits", since never-exiting nodes are
reachable)</div>
</div>
</blockquote>
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. <br>
<blockquote
cite="mid:CABTcG6KzfxZ-hfNquHFWNrhj4xQuZTxXT9CVA1JwZV66aQEgpA@mail.gmail.com"
type="cite">
<div dir="ltr">
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Mon, Sep 21, 2015 at 9:26 AM, Philip
Reames <span dir="ltr"><<a moz-do-not-send="true"
href="mailto:listmail@philipreames.com" target="_blank">listmail@philipreames.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">When
looking into <a moz-do-not-send="true"
href="https://llvm.org/bugs/show_bug.cgi?id=24866"
rel="noreferrer" target="_blank">https://llvm.org/bugs/show_bug.cgi?id=24866</a>,
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?<br>
<br>
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).<br>
<br>
Philip<br>
<br>
For reference, here's the reproduction command:<br>
opt -S <input> -value-tracking-dom-conditions -licm
-load-combine<br>
<br>
And here's the IR:<br>
; ModuleID = '../bugpoint-reduced-simplified.bc'<br>
target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"<br>
target triple = "x86_64-pc-windows-msvc18.0.0"<br>
<br>
%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] }<br>
<br>
; Function Attrs: nounwind uwtable<br>
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 {<br>
entry:<br>
br i1 undef, label %L_KLOOP_01, label %L_KLOOP.preheader<br>
<br>
L_KLOOP_01: ; preds =
%while.end, %entry<br>
br label %L_KLOOP.preheader<br>
<br>
L_KLOOP_08: ; preds =
%while.end<br>
br label %L_KLOOP.preheader<br>
<br>
L_KLOOP.preheader: ; preds =
%L_KLOOP_08, %L_KLOOP_01, %entry<br>
%<a moz-do-not-send="true" href="http://r.2.ph"
rel="noreferrer" target="_blank">r.2.ph</a> = phi i32 [
undef, %L_KLOOP_08 ], [ 0, %entry ], [ undef, %L_KLOOP_01 ]<br>
br label %L_KLOOP<br>
<br>
L_KLOOP: ; preds =
%while.end, %L_KLOOP.preheader<br>
%r.2 = phi i32 [ 0, %while.end ], [ %<a
moz-do-not-send="true" href="http://r.2.ph"
rel="noreferrer" target="_blank">r.2.ph</a>,
%L_KLOOP.preheader ]<br>
br i1 undef, label %while.body, label %while.end<br>
<br>
while.body: ; preds =
%while.body, %L_KLOOP<br>
br label %while.body<br>
<br>
while.end: ; preds =
%L_KLOOP<br>
%shl105 = shl i32 %r.2, 4<br>
%add106 = add nsw i32 %shl105, undef ;; <-- THIS is the
context instruction. V is undef<br>
%idxprom107 = sext i32 %add106 to i64<br>
%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<br>
%0 = load i32, i32* %arrayidx108, align 4, !tbaa !2<br>
%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<br>
%1 = load i8, i8* %arrayidx110, align 1, !tbaa !6<br>
indirectbr i8* undef, [label %L_KLOOP_DONE, label
%L_KLOOP_01, label %L_KLOOP_08, label %L_KLOOP]<br>
<br>
L_KLOOP_DONE: ; preds =
%while.end<br>
ret void<br>
}<br>
<br>
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" }<br>
<br>
!llvm.module.flags = !{!0}<br>
!llvm.ident = !{!1}<br>
<br>
!0 = !{i32 1, !"PIC Level", i32 2}<br>
!1 = !{!"clang version 3.8.0 (<a moz-do-not-send="true"
href="http://llvm.org/git/clang.git" rel="noreferrer"
target="_blank">http://llvm.org/git/clang.git</a>
37c860b7d0d43dde1edcd324e00a10a62b2c5776) (<a
moz-do-not-send="true" href="http://llvm.org/git/llvm.git"
rel="noreferrer" target="_blank"><a class="moz-txt-link-freetext" href="http://llvm.org/git/llvm.git">http://llvm.org/git/llvm.git</a></a>
fb73c0262af4183555253a5c8c13025a6e7630bc)"}<br>
!2 = !{!3, !3, i64 0}<br>
!3 = !{!"int", !4, i64 0}<br>
!4 = !{!"omnipotent char", !5, i64 0}<br>
!5 = !{!"Simple C/C++ TBAA"}<br>
!6 = !{!4, !4, i64 0}<br>
<br>
</blockquote>
</div>
<br>
</div>
</blockquote>
<br>
</body>
</html>