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

Daniel Berlin via llvm-dev llvm-dev at lists.llvm.org
Mon Sep 21 09:48:28 PDT 2015


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>


More information about the llvm-dev mailing list