Ensure a complete post-dominance tree is built in the presence of unreachables

[grosser]

Summary

This patch ensures a full post-dominance tree is built for all reachable parts
of a CFG even if some parts of the CFG are unreachable. Before this change,
we treated basic blocks that end in both return statements or unreachable
instructions as roots of the post-dominance tree. As a result, as soon as an
unreachable statement was part of the CFG, parts of the post-dominance relation
in the reachable part of the CFG was lost. With this patch, we now only add
returning basic blocks, but not unreachable basic blocks as root nodes to the
post-dominance tree. This means the unreachable blocks are treated identical to
infinite loops. They do not show up in the post-dominance relation and they do
not affect the post-dominance tree of the reachable part of the CFG.

[• dberlin]

So, IIRC, in the dominance tree, unreachable blocks are deliberately part of the domtree, and we have dominance queries answerable about them.
What is the reason we should have different behavior for the two?

(Also, what happens if i try to make a post-dominates query about an unreachable block now?
It would be good to have a unit test for this)

I'm also not suggesting your patch is wrong, i'm suggesting our behavior in dominators may be undesirable as well, though i haven't thought about it.

Also note that your change to when we do addRoot will still not handle infinite loops properly:
We will end up with a null root node in some cases (infinite self-loops, for example), because it has predecessors, (the entry and itself), and a successor (itself)
This will cause child_begin != child_end, and thus, return false from isDomExit, which will cause us not to add a root, and end up with a null root node instead of a proper virtual root node.

It's one thing to leave the blocks out, it's another to say "there is no root node at all". We are still supposed to have a root node, even if it's virtual.

Note that in general, it's not going to be possible to determine reachability, and what we should exclude anyway, without a DFS walk

Given that we know that the only way (at least, i can think of) to avoid adding another DFS walk is to make the root finding part of dom tree construction, i'd rather not add see us add isDomExit, because it's another thing that will need to be cleaned up to make this happen.
(The bug has more details).

include/llvm/IR/Dominators.h

119

This is not a sufficient check for non-reachability.

What if i have a infinite self-loop?

https://llvm.org/bugs/show_bug.cgi?id=24415

(extend it to multiple blocks if you like)

[grosser]

Thank you Daniel for joining the discussion. It seems the corner
cases of (post)dominance analysis are always worth some thoughts.

dberlin added a comment.

So, IIRC, in the dominance tree, unreachable blocks are deliberately part of the domtree, and we have dominance queries answerable about them.
What is the reason we should have different behavior for the two?

B is dominated by A if every path from the entry of the function to B goes through A.

For unreachables this seems well defined:

Example 1:

entry:
   br label %exit

exit:
   unreachable

Inorder Dominator Tree:

[1] %entry {0,3}
  [2] %exit {1,2}

The basic blocks that we leave out of the dominance tree (and which I believe
are similar to unreachables in the post-dominance tree) are the once to which
there is no path from the entry at all. Something like:

Example 2:

entry:
   br label %exit

otherbb:
   br label %exit

exit:
   ret void

Inorder Dominator Tree:

[1] %entry {0,3}
  [2] %exit {1,2}

'otherbb' is left out.

If we now look at the post-dominance tree of example 2, 'otherbb' shows up again as there
is a path going backwards from exit to otherbb:

Inorder PostDominator Tree:

[1] %exit {0,5}
  [2] %otherbb {1,2}
  [2] %entry {3,4}

This means 'exit' is post-dominating by 'otherbb'. This relation is reflected in the post-dominator
tree.

(Also, what happens if i try to make a post-dominates query about an unreachable block now?
It would be good to have a unit test for this)

The same as what happens today with infinite loops in post-dominator trees or 'otherbb' in
example 2, we return nullptr:

DomTreeNodeBase<NodeT> *getNode(NodeT *BB) const {
  auto I = DomTreeNodes.find(BB);
  if (I != DomTreeNodes.end())
    return I->second.get();
  return nullptr;
}

I think this makes sense, but you are right that a unittest would probablynot hurt. I would
be glad to add one.

I'm also not suggesting your patch is wrong, i'm suggesting our behavior in dominators may be undesirable as well, though i haven't thought about it.

I think leaving unreachables in dominators is right, but this does not mean that they should be part of the post-dominator tree.

In case of an unreachable (or an infinite loop), there can not be any path from a function exit through an unreachable/infinite-loop basic block that
could establish a post-dominance relation.

Also note that your change to when we do addRoot will still not handle infinite loops properly:
We will end up with a null root node in some cases (infinite self-loops, for example), because it has predecessors, (the entry and itself), and a successor (itself)
This will cause child_begin != child_end, and thus, return false from isDomExit, which will cause us not to add a root, and end up with a null root node instead of a proper virtual root node.

This patch was not intended to address the issue you are pointing me to (I was not aware of it). It leaves the behavior for this case unchanged.

Looking at the example below, we see that infinite loops are left out of the post-dominator tree exactly the way I suggest us to do for the unreachable blocks.

define void @foo() {
entry:
   br i1 true, label %next, label %exit

next:
   br label %next

exit:
   ret void
}

Inorder PostDominator Tree:

[1]  <<exit node>> {0,5}
  [2] %exit {1,4}
    [3] %entry {2,3}

This result is what I expect.

Now for the case where there is no reachable node at all, we do - as you observe - not even get a virtual exit node:

define void @foo() {
entry:
   br label %next

next:
   br label %next
}

Printing analysis 'Post-Dominator Tree Construction' for function 'foo':

Inorder PostDominator Tree: DFSNumbers invalid: 0 slow queries.

It's one thing to leave the blocks out, it's another to say "there is no root node at all". We are still supposed to have a root node, even if it's virtual.

I do not have a strong opinion here, but adding a virtual exit in case there is not even a single root node seems to be simple.

If we agree that is the right behavior, I could add this in a follow-up patch.

Note that in general, it's not going to be possible to determine reachability, and what we should exclude anyway, without a DFS walk

I think these are two issues: I am in this patch mainly concerned about the post-dominator tree being correct for dominance relations that are caused by a path
that goes through two basic blocks and ends at an exit of the function. This is what is well defined and for this I do not see why another DFS walk would be needed.
The set of exits is well defined and can just be added, no?

What you seem to aim for below is to define a relation similar to post-dominance for blocks that are not on any path that
finishes in an exit block of the function. To my understanding, this would correspond to adding 'otherbb' somehow into the dominator tree (e.g. to
establish a dominance-like relation in parts of the tree that can not be reached from the exit node. I believe this is considerably more involved and indeed
requires some larger restructuring. Do you have use cases were having such relation actually is beneficial in some way? I thought about this myself, but did
not yet find an example where this would be useful.

Given that we know that the only way (at least, i can think of) to avoid adding another DFS walk is to make the root finding part of dom tree construction, i'd rather not add see us add isDomExit, because it's another thing that will need to be cleaned up to make this happen.
(The bug has more details).

Given my explanation above, I think this patch makes sense. However, let's see first if we can reach a common understanding on the issues.

Comment at: include/llvm/IR/Dominators.h:119
@@ +118,3 @@
+ GraphTraits<Function *>::child_end(N))
+ return false;

+

This is not a sufficient check for non-reachability.

What if i have a infinite self-loop?

https://llvm.org/bugs/show_bug.cgi?id=24415

(extend it to multiple blocks if you like)

This is not intended as check for non-reachability. This is intended as a check of where to start the DFS search that determines reachability.

Best,
Tobias

include/llvm/IR/Dominators.h

 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/GenericDomTree.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 
 namespace llvm {
 
const BasicBlock *getStart() const {
     return Start;
   }
   const BasicBlock *getEnd() const {
     return End;
   }
   bool isSingleEdge() const;
 };
 
+/// Is a node the exit node of a graph as needed for dominator tree calculation.
+///
+/// All basic blocks that have no successors are exit nodes of the graph, except
+/// the ones that terminate with an UnreachableInst. Not including unreachable
+/// instructions allows us to treat unreachable basic blocks like infinite
+/// loops. This means unreachable parts of the CFG will not be visible in the
+/// post-dominator tree and - more importantly - will not affect the other parts
+/// of the post-dominator tree. If we would model unreachable basic blocks as
+/// exit blocks of the CFG the post-dominator tree would be flattened out and
+/// we would miss important post-dominance relations.
+///
+///
+/// CFG
+/// ===
+///                  |
+///                 bb1
+///                /   \
+///              bb2   ^
+///             /  \   /
+///  unreachable    bb3
+///                  |
+///               exit
+///
+///
+/// Post dominator tree with unreachable nodes as exit node
+/// =======================================================
+///
+///            virtual root
+///            /      |   \
+///     unreachable exit  bb2
+///                   |    |
+///                  bb3  bb1
+///
+/// Post dominator tree without unreachable nodes as exit node
+/// ==========================================================
+///
+///            virtual root
+///                  |
+///                 exit
+///                  |
+///                 bb3
+///                  |
+///                 bb2
+///                  |
+///                 bb1
+///
+/// When ignoring unreachables we can now correctly determine that bb2 is
+/// post-dominated by bb3.
+template <>
+inline bool isDomTreeExit<GraphTraits<Function*>>(
+    typename GraphTraits<Function*>::NodeType *N) {
+  if (GraphTraits<Function *>::child_begin(N) !=
+      GraphTraits<Function *>::child_end(N))
+    return false;
+
+  return !isa<UnreachableInst>(N->getTerminator());
+}
+
 /// \brief Concrete subclass of DominatorTreeBase that is used to compute a
 /// normal dominator tree.
 class DominatorTree : public DominatorTreeBase<BasicBlock> {
 public:
   typedef DominatorTreeBase<BasicBlock> Base;
 
   DominatorTree() : DominatorTreeBase<BasicBlock>(false) {}
   explicit DominatorTree(Function &F) : DominatorTreeBase<BasicBlock>(false) {

include/llvm/Support/GenericDomTree.h

public:
   ///
   const std::vector<NodeT *> &getRoots() const { return Roots; }
 
   /// isPostDominator - Returns true if analysis based of postdoms
   ///
   bool isPostDominator() const { return IsPostDominators; }
 };
 
+/// Is a node the exit node of a graph as needed for dominator tree calculation.
+///
+/// By default we just assume that each node that does not have a successor
+/// is an exit node of the graph. However, specializations of the dominator
+/// tree for specific graph types can overwrite this function in case more
+/// detailed information is available. E.g. one may ignore unreachable
+/// instructions, which have no successors but also do not return from the
+/// function.
+template<class GraphTy>
+bool isDomTreeExit(typename GraphTy::NodeType *N) {
+  return GraphTy::child_begin(N) == GraphTy::child_end(N);
+}
+
 template <class NodeT> class DominatorTreeBase;
 struct PostDominatorTree;
 
 /// \brief Base class for the actual dominator tree node.
 template <class NodeT> class DomTreeNodeBase {
   NodeT *TheBB;
   DomTreeNodeBase<NodeT> *IDom;
   std::vector<DomTreeNodeBase<NodeT> *> Children;
if (!this->IsPostDominators) {
       this->DomTreeNodes[entry] = nullptr;
 
       Calculate<FT, NodeT *>(*this, F);
     } else {
       // Initialize the roots list
       for (typename TraitsTy::nodes_iterator I = TraitsTy::nodes_begin(&F),
                                              E = TraitsTy::nodes_end(&F);
            I != E; ++I) {
-        if (TraitsTy::child_begin(I) == TraitsTy::child_end(I))
+        if (isDomTreeExit<TraitsTy>(I))
           addRoot(I);
 
         // Prepopulate maps so that we don't get iterator invalidation issues
         // later.
         this->IDoms[I] = nullptr;
         this->DomTreeNodes[I] = nullptr;
       }
 

test/Analysis/PostDominators/unreachables.ll

+; RUN: opt -regions -analyze < %s | FileCheck %s
+
+; Make sure we do _not_ add the unreachable node to the root nodes of the post
+; dominator tree, as otherwise the post-dominator tree would flatten out and
+; loose its structure. Instead, unreachable branches are just ignored in
+; the post-dominator tree the same way infinite loops are left out.
+
+; CHECK: Inorder PostDominator Tree:
+; CHECK:   [1]  <<exit node>> {0,11}
+; CHECK:     [2] %exit {1,10}
+; CHECK:       [3] %loop.backedge {2,9}
+; CHECK:         [4] %loop.next {3,8}
+; CHECK:           [5] %loop {4,7}
+; CHECK:             [6] %entry {5,6}
+
+define void @foo.bar() {
+entry:
+  br label %loop
+
+loop:
+  br label %loop.next
+
+loop.next:
+  br i1 false, label %loop.backedge, label %loop.unreachable
+
+loop.unreachable:
+  unreachable
+
+loop.backedge:
+  br i1 false, label %loop, label %exit
+
+exit:
+  ret void
+}

test/Analysis/RegionInfo/condition_complicated_2.ll

then113:
   br label %end124
 
 end124:
   br label %exit
 
 end172:
   br label %exit
 
-
 exit:
-  unreachable
-
-
+  ret void
 }
+
 ; CHECK-NOT: =>
 ; CHECK: [0] end33 => <Function Return>
 ; CHECK-NEXT:      [1] end33 => exit
 ; CHECK-NEXT:   [2] then107 => end124
 
 ; STAT: 3 region - The # of regions
 
 ; BBIT: end33, end124, exit, lor.lhs.false95, then107, then113, end172,
 ; BBIT: end33, end124, lor.lhs.false95, then107, then113, end172,
 ; BBIT: then107, then113,
 
 ; RNIT: end33 => exit, exit,
 ; RNIT: end33, end124, lor.lhs.false95, then107 => end124, end172,
 ; RNIT: then107, then113,

test/Analysis/RegionInfo/unreachable_bb.ll

 ; RUN: opt -regions -analyze < %s | FileCheck %s
 
-; We should not crash if there are some bbs that are not reachable.
-define void @f() {
+; CHECK: Region tree:
+; CHECK: [0] entry => <Function Return>
+; CHECK:   [1] loop => exit
+; CHECK:       [2] loop.next => loop.backedge
+
+define void @foo.bar() {
 entry:
-  br label %for.pre
+  br label %loop
 
-notintree:                                        ; No predecessors!
-  br label %ret
+loop:
+  br label %loop.next
 
-for.pre:                                          ; preds = %entry
-  br label %for
+loop.next:
+  br i1 false, label %loop.backedge, label %loop.unreachable
 
-for:                                              ; preds = %for.inc, %for.pre
-  %indvar = phi i64 [ 0, %for.pre ], [ %indvar.next, %for.inc ]
-  %exitcond = icmp ne i64 %indvar, 200
-  br i1 %exitcond, label %for.inc, label %ret
+loop.unreachable:
+  unreachable
 
-for.inc:                                          ; preds = %for
-  %indvar.next = add i64 %indvar, 1
-  br label %for
+loop.backedge:
+  br i1 false, label %loop, label %exit
 
-ret:                                              ; preds = %for, %notintree
+exit:
   ret void
 }
-
-; CHECK: [0] entry => <Function Return>
-; CHECK:   [1] for => ret
-