<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 06:11 PM, Joseph
Tremoulet wrote:<br>
</div>
<blockquote
cite="mid:BY2PR0301MB0744639B771014DAF37336E8CA450@BY2PR0301MB0744.namprd03.prod.outlook.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered
medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:#1F497D;}
span.EmailStyle18
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
<div class="WordSection1">
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><pedantry><o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">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. "</span> of the 0 paths that exist,
*<b>all*</b> of them go through any other node<span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">
".<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">>
</span>we claim … that *every* path from the entry node goes
to the unreachable node<span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">I
don't think that follows; saying that d
<i>doesn't</i> dominate n says that a path exists form start
to n that doesn't go through d, but saying that d
<i>does</i> dominate n just says something about all paths
in a possibly empty set.<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">>
</span>most dominance algorithms will never consider an
unreachable node to dominate anything<span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Agreed,
but I think here we're talking about the inverse; whether
anything dominates an unreachable node.<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"></pedantry><o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">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.<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">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.<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">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.</span></p>
</div>
</blockquote>
I completely utterly agree with this last point. <br>
<br>
I just don't have the time to go fix all the callers right now. :)<br>
<blockquote
cite="mid:BY2PR0301MB0744639B771014DAF37336E8CA450@BY2PR0301MB0744.namprd03.prod.outlook.com"
type="cite">
<div class="WordSection1">
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Thanks<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">-Joseph<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><a moz-do-not-send="true"
name="_MailEndCompose"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></a></p>
<p class="MsoNormal"><b><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif">
llvm-dev [<a class="moz-txt-link-freetext" href="mailto:llvm-dev-bounces@lists.llvm.org">mailto:llvm-dev-bounces@lists.llvm.org</a>]
<b>On Behalf Of </b>Daniel Berlin via llvm-dev<br>
<b>Sent:</b> Monday, September 21, 2015 12:48 PM<br>
<b>To:</b> Philip Reames <a class="moz-txt-link-rfc2396E" href="mailto:listmail@philipreames.com"><listmail@philipreames.com></a><br>
<b>Cc:</b> llvm-dev <a class="moz-txt-link-rfc2396E" href="mailto:llvm-dev@lists.llvm.org"><llvm-dev@lists.llvm.org></a><br>
<b>Subject:</b> Re: [llvm-dev] When can the dominator tree
not contain a node for a basic block?<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">So, there is no good answer.<o:p></o:p></p>
<div>
<p class="MsoNormal">It's not documented anywhere, and
genericdomtree.h makes assumptions both ways.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">For example, :<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> void getDescendants(NodeT *R,
SmallVectorImpl<NodeT *> &Result) const {<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">...<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"> if (!RN)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> return; // If R is unreachable,
it will not be present in the DOM tree. :)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">...<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">}<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">vs<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">dominates()<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">{<br>
...<o:p></o:p></p>
</div>
<div>
<div>
<p class="MsoNormal"> // Any unreachable use is
dominated, even if Def == User.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> if (!isReachableFromEntry(UseBB))<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> return true;<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"> // Unreachable definitions don't
dominate anything.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> if (!isReachableFromEntry(DefBB))<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> return false;<o:p></o:p></p>
</div>
</div>
<div>
<p class="MsoNormal">}<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">...<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">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.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">This is *dominators*, mind you.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">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.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">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.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">As to what "the right answers are",
this seems harder.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">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="font-size:10.5pt;font-family:"Arial",sans-serif;color:#252525"> "a </span><a
moz-do-not-send="true"
href="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"
title="Basic block"><span
style="font-size:10.5pt;font-family:"Arial",sans-serif;color:#0B0080;text-decoration:none">node</span></a><span
style="font-size:10.5pt;font-family:"Arial",sans-serif;color:#252525"> <b>d</b> <i>dominates</i> a
node <b>n</b> if every path from the <i>entry node</i> to <b>n</b> must
go through <b>d"</b></span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">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.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">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)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">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"<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Now, whether we care about this or not,
it's up in the air.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">(Note that forward/reverse unreachable
for dom/post-dom is different from "never exits", since
never-exiting nodes are reachable)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">On Mon, Sep 21, 2015 at 9:26 AM, Philip
Reames <<a moz-do-not-send="true"
href="mailto:listmail@philipreames.com" target="_blank">listmail@philipreames.com</a>>
wrote:<o:p></o:p></p>
<blockquote style="border:none;border-left:solid #CCCCCC
1.0pt;padding:0in 0in 0in
6.0pt;margin-left:4.8pt;margin-right:0in">
<p class="MsoNormal" style="margin-bottom:12.0pt">When
looking into <a moz-do-not-send="true"
href="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"
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="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"
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="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"
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="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"
target="_blank">http://llvm.org/git/clang.git</a>
37c860b7d0d43dde1edcd324e00a10a62b2c5776) (<a
moz-do-not-send="true"
href="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"
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}<o:p></o:p></p>
</blockquote>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</blockquote>
<br>
</body>
</html>