Post-dom fix - connect virtual edges to last reverse-reachable BB

[grosser]

Summary

This change is an adapted version of Daniel's "Fix PR 24415 (at least), by
making our post-dominator tree behavior sane." patch, which ensures that we do not loose existing post-dominance information and can consequently correctly detect SESE regions that contain non-reverse reachable infinite loops.

To remain consistent we handle unreachable() basic blocks the same way as
infinite loops.

This is a proof-of-concept patch used in the discussion on how to properly
complete the post-dominator tree to include reverse unreachable nodes.

[grosser]

Here an example that illustrates the difference between the original patch Daniel proposed in https://reviews.llvm.org/D29705 and the slightly modified one we prose her:

Daniel's patch

Inorder PostDominator Tree:

[1]  <<exit node>> {0,19}
  [2] %"4" {1,4}
    [3] %"3" {2,3}
  [2] %"1" {5,8}
    [3] %"0" {6,7}
  [2] %"6" {9,18}
    [3] %"12" {10,11}
    [3] %"5" {12,15}
      [4] %"2" {13,14}
    [3] %"11" {16,17}

This patch

[1]  <<exit node>> {0,19}
  [2] %"4" {1,18}
    [3] %"3" {2,17}
      [4] %"1" {3,16}
        [5] %"0" {4,5}
        [5] %"6" {6,15}
          [6] %"12" {7,8}
          [6] %"5" {9,12}
            [7] %"2" {10,11}
          [6] %"11" {13,14}

The main difference is that %1 still post-dominates %2 and all the other basic blocks in the reverse-unreachable region. This behavior only requires

[efriedma]

I see a couple problems with this:

1. There isn't any easy way for passes which use PostDominatorTree to walk the CFG including these fake edges.
2. For consistency, we would want other analysis and transform passes (DominatorTree/DominanceFrontier/LoopInfo/etc.) to reason about the CFG using the same fake edges as the PostDominatorTree; otherwise, you can't really rely on the results of the PostDominatorTree analysis. I'm not exactly sure what the total impact would be, but it seems complicated at first glance.

[• dberlin]

In D30890#699658, @efriedma wrote:

I see a couple problems with this:

1. There isn't any easy way for passes which use PostDominatorTree to walk the CFG including these fake edges.
2. For consistency, we would want other analysis and transform passes (DominatorTree/DominanceFrontier/LoopInfo/etc.) to reason about the CFG using the same fake edges as the PostDominatorTree; otherwise, you can't really rely on the results of the PostDominatorTree analysis. I'm not exactly sure what the total impact would be, but it seems complicated at first glance.

Yes, besides the ongoing discussion of "maintain path invariant" vs "not maintain path invariant" for things, the connect to exit is easy because if there was a fake exit node, it would be the same and have the same predecessor edges, as the post-dom tree's virtual exit node.

For example, for IDF calculator, ignoring the path invariant it depends on for correctness (again, not gonna rehash the thread), you would need to add "j-edges" for these fake edges, such that they got walked at the same time the other predecessor edges did.

I'm not even sure where you store the fake edges, let alone modify the iterators to walk them.
It seems like at least right now, you'd have to hack up a bunch of stuff (IE store the edges with the PDT, and then audit everywhere that walked preds, ...)
That seems, as you said, complicated, even with the zip iterator/etc.

I'm actually a big fan of real edge structures and enabling fake edges vs what we do now in llvm, but that's also a huge change.

[grosser]

Hi Daniel, hi Eli,

thanks for your comments. I agree with Eli that the complexity of the approach in this patch is indeed concerning. Not saying this is the perfect solution. ;-)

@dberlin : Also thanks for your comments. I will reply in the thread.

I came up with another example that illustrates how the flattened tree "breaks" region-info, in some way.

Here one more example:

Inorder PostDominator Tree:

[1]  <<exit node>> {0,29}
  [2] %bb24 {1,2}
  [2] %bb3 {3,10}
    [3] %bb22 {4,7}
      [4] %bb21 {5,6}
    [3] %bb {8,9}
  [2] %bb5 {11,18}
    [3] %bb19 {12,15}
      [4] %bb18 {13,14}
    [3] %bb4 {16,17}
  [2] %bb7 {19,24}
    [3] %bb16 {20,21}
    [3] %bb6 {22,23}
  [2] %bb8 {25,26}
  [2] %infloop {27,28}

Connect in tree

Inorder PostDominator Tree:

[1]  <<exit node>> {0,29}
  [2] %bb24 {1,28}
    [3] %bb3 {2,27}
      [4] %bb22 {3,24}
        [5] %bb21 {4,23}
          [6] %bb5 {5,22}
            [7] %bb19 {6,19}
              [8] %bb18 {7,18}
                [9] %bb7 {8,17}
                  [10] %bb16 {9,14}
                    [11] %bb8 {10,13}
                      [12] %infloop {11,12}
                  [10] %bb6 {15,16}
            [7] %bb4 {20,21}
      [4] %bb {25,26}

[• dberlin]

You and i fundamentally disagree over whether one is correct or not :)
I don't think that will change.

You believe that everything that does not exit should not affect the precision of things that do. That would be great if possible.
I believe that is impossible to do without breaking the invariants of the dominator tree, when extended to the unreachable nodes to them .
You do not seem to disagree with that, but your response is to break those invariants anyway to produce a "better" result for the reachable nodes.
I'm unwilling to do that, because it defeats, to me, the whole purpose of having them in the post-dom tree.
As I said there, i am more than happy to produce you a postdomwithoutunreachablenodes that produces that result (note that isn't what you are getting *now*, you are getting something in the middle where it sometimes is like that and sometimes not).
I do not believe there are a lot of things you can use that for safely, but if it's what you want, and you are sure, i'm happy to give it to you.

I just think it is not what we should be doing by default. I believe the thing we should do by default is the thing that makes optimizations work correctly without special casing, which is why it is the path, as your investigation shows, every compiler to confront the issue has chosen in the end.

include/llvm/ADT/GraphTraits.h

struct GraphTraits {
   // typedef  ...iterator nodes_iterator; - dereference to a NodeRef
   // static nodes_iterator nodes_begin(GraphType *G)
   // static nodes_iterator nodes_end  (GraphType *G)
   //    nodes_iterator/begin/end - Allow iteration over all nodes in the graph
 
   // static unsigned       size       (GraphType *G)
   //    Return total number of nodes in the graph
   //
+  // static bool isExit(NodeRef);
 
 
   // If anyone tries to use this class without having an appropriate
   // specialization, make an error.  If you get this error, it's because you
   // need to include the appropriate specialization of GraphTraits<> for your
   // graph, or you need to define it for a new graph type. Either that or
   // your argument to XXX_begin(...) is unknown or needs to have the proper .h
   // file #include'd.
   //
   typedef typename GraphType::UnknownGraphTypeError NodeRef;
 };
 
+template <class GraphType>
+bool isExit(GraphType Node) {
+  typedef GraphTraits<GraphType> GraphT;
+  return GraphT::child_begin(Node) == GraphT::child_end(Node);
+}
 
 // Inverse - This class is used as a little marker class to tell the graph
 // iterator to iterate over the graph in a graph defined "Inverse" ordering.
 // Not all graphs define an inverse ordering, and if they do, it depends on
 // the graph exactly what that is.  Here's an example of usage with the
 // df_iterator:
 //
 // idf_iterator<Method*> I = idf_begin(M), E = idf_end(M);

include/llvm/Analysis/RegionInfoImpl.h

 
 template <class Tr>
 bool RegionInfoBase<Tr>::isTrivialRegion(BlockT *entry, BlockT *exit) const {
   assert(entry && exit && "entry and exit must not be null!");
 
   unsigned num_successors =
       BlockTraits::child_end(entry) - BlockTraits::child_begin(entry);
 
+  if (num_successors == 0)
+    return true;
+
   if (num_successors <= 1 && exit == *(BlockTraits::child_begin(entry)))
     return true;
 
   return false;
 }
 
 template <class Tr>
 typename Tr::RegionT *RegionInfoBase<Tr>::createRegion(BlockT *entry,

include/llvm/IR/CFG.h

 #define LLVM_IR_CFG_H
 
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/iterator.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstrTypes.h"
+#include "llvm/IR/Instructions.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/type_traits.h"
 #include <cassert>
 #include <cstddef>
 #include <iterator>
 
 namespace llvm {
template <> struct GraphTraits<const BasicBlock*> {
   typedef succ_const_iterator ChildIteratorType;
 
   static NodeRef getEntryNode(const BasicBlock *BB) { return BB; }
 
   static ChildIteratorType child_begin(NodeRef N) { return succ_begin(N); }
   static ChildIteratorType child_end(NodeRef N) { return succ_end(N); }
 };
 
+
+template <>
+inline bool isExit(BasicBlock *Node) {
+  typedef GraphTraits<BasicBlock*> GraphT;
+  return GraphT::child_begin(Node) == GraphT::child_end(Node)
+    && !isa<UnreachableInst>(Node->getTerminator());
+}
+
 // Provide specializations of GraphTraits to be able to treat a function as a
 // graph of basic blocks... and to walk it in inverse order.  Inverse order for
 // a function is considered to be when traversing the predecessor edges of a BB
 // instead of the successor edges.
 //
 template <> struct GraphTraits<Inverse<BasicBlock*>> {
   typedef BasicBlock *NodeRef;
   typedef pred_iterator ChildIteratorType;

include/llvm/Support/GenericDomTree.h

void updateDFSNumbers() const {
     }
 
     SlowQueries = 0;
     DFSInfoValid = true;
   }
 
   /// recalculate - compute a dominator tree for the given function
   template <class FT> void recalculate(FT &F) {
-    typedef GraphTraits<FT *> TraitsTy;
     reset();
     this->Vertex.push_back(nullptr);
 
     if (!this->IsPostDominators) {
-      // Initialize root
-      NodeT *entry = TraitsTy::getEntryNode(&F);
-      addRoot(entry);
-
       Calculate<FT, NodeT *>(*this, F);
     } else {
-      // Initialize the roots list
-      for (auto *Node : nodes(&F))
-        if (TraitsTy::child_begin(Node) == TraitsTy::child_end(Node))
-          addRoot(Node);
-
       Calculate<FT, Inverse<NodeT *>>(*this, F);
     }
   }
 };
 
 // These two functions are declared out of line as a workaround for building
 // with old (< r147295) versions of clang because of pr11642.
 template <class NodeT>

include/llvm/Support/GenericDomTreeConstruction.h

 /// faster than the almost-linear O(n*alpha(n)) version, even for large CFGs.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
 #define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
 
 #include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Support/GenericDomTree.h"
 
 namespace llvm {
 
 // External storage for depth first iterator that reuses the info lookup map
 // domtree already has.  We don't have a set, but a map instead, so we are
 // converting the one argument insert calls.
 template <class NodeRef, class InfoType> struct df_iterator_dom_storage {
 public:
   typedef DenseMap<NodeRef, InfoType> BaseSet;
   df_iterator_dom_storage(BaseSet &Storage) : Storage(Storage) {}
 
   typedef typename BaseSet::iterator iterator;
-  std::pair<iterator, bool> insert(NodeRef N) {
-    return Storage.insert({N, InfoType()});
+  std::pair<iterator, bool> insert(NodeRef To) {
+    auto Result = Storage.insert({To, InfoType()});
+
+    return Result;
   }
   void completed(NodeRef) {}
 
 private:
   BaseSet &Storage;
 };
 
 template <class GraphT>
 unsigned ReverseDFSPass(DominatorTreeBaseByGraphTraits<GraphT> &DT,
                         typename GraphT::NodeRef V, unsigned N) {
   df_iterator_dom_storage<
       typename GraphT::NodeRef,
       typename DominatorTreeBaseByGraphTraits<GraphT>::InfoRec>
       DFStorage(DT.Info);
-  bool IsChildOfArtificialExit = (N != 0);
   for (auto I = idf_ext_begin(V, DFStorage), E = idf_ext_end(V, DFStorage);
        I != E; ++I) {
     typename GraphT::NodeRef BB = *I;
     auto &BBInfo = DT.Info[BB];
     BBInfo.DFSNum = BBInfo.Semi = ++N;
     BBInfo.Label = BB;
     // Set the parent to the top of the visited stack.  The stack includes us,
     // and is 1 based, so we subtract to account for both of these.
     if (I.getPathLength() > 1)
       BBInfo.Parent = DT.Info[I.getPath(I.getPathLength() - 2)].DFSNum;
     DT.Vertex.push_back(BB); // Vertex[n] = V;
-
-    if (IsChildOfArtificialExit)
-      BBInfo.Parent = 1;
-
-    IsChildOfArtificialExit = false;
   }
   return N;
 }
 template <class GraphT>
 unsigned DFSPass(DominatorTreeBaseByGraphTraits<GraphT> &DT,
                  typename GraphT::NodeRef V, unsigned N) {
   df_iterator_dom_storage<
       typename GraphT::NodeRef,
typename GraphT::NodeRef Eval(DominatorTreeBaseByGraphTraits<GraphT> &DT,
 
   return VInInfo.Label;
 }
 
 template <class FuncT, class NodeT>
 void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<NodeT>> &DT,
                FuncT &F) {
   typedef GraphTraits<NodeT> GraphT;
+  typedef GraphTraits<FuncT *> FuncGraphT;
   static_assert(std::is_pointer<typename GraphT::NodeRef>::value,
                 "NodeRef should be pointer type");
   typedef typename std::remove_pointer<typename GraphT::NodeRef>::type NodeType;
 
   unsigned N = 0;
-  bool MultipleRoots = (DT.Roots.size() > 1);
-  if (MultipleRoots) {
+  bool NeedFakeRoot = DT.isPostDominator();
+  // If this is post dominators, push a fake node to start
+  if (NeedFakeRoot) {
     auto &BBInfo = DT.Info[nullptr];
     BBInfo.DFSNum = BBInfo.Semi = ++N;
     BBInfo.Label = nullptr;
-
-    DT.Vertex.push_back(nullptr);       // Vertex[n] = V;
+    DT.Vertex.push_back(nullptr); // Vertex[n] = V;
+  } else {
+    // The root is the entry block of the CFG
+    DT.addRoot(FuncGraphT::getEntryNode(&F));
   }
 
   // Step #1: Number blocks in depth-first order and initialize variables used
   // in later stages of the algorithm.
-  if (DT.isPostDominator()){
-    for (unsigned i = 0, e = static_cast<unsigned>(DT.Roots.size());
-         i != e; ++i)
-      N = ReverseDFSPass<GraphT>(DT, DT.Roots[i], N);
+  if (DT.isPostDominator()) {
+    unsigned Total = 0;
+    for (auto I : nodes(&F)) {
+      ++Total;
+      // If it has no *successors*, it is definitely a root.
+      if (isExit(I)) {
+        N = ReverseDFSPass<GraphT>(DT, I, N);
+        DT.Info[I].Parent = 1;
+        DT.addRoot(I);
+      }
+    }
+    // Accounting for the virtual exit, see if we had any unreachable nodes
+    if (Total + 1 != N) {
+      // Make another DFS pass over all other nodes to find the unreachable
+      // blocks, and find the furthest paths we'll be able to make.
+      // Note that this looks N^2, but it's really 2N worst case, if every node
+      // is unreachable. This is because we are still going to only visit each
+      // unreachable node once, we may just visit it in two directions,
+      // depending on how lucky we get.
+      std::map<NodeType *, NodeType *> BlocksToConnect;
+      for (auto I : nodes(&F))
+        if (!DT.Info.count(I)) {
+          // Find the furthest away we can get by following successors, then
+          // follow them in reverse.  This gives us some reasonable answer about
+          // the post-dom tree inside any infinite loop.  In particular, it
+          // guarantees we get to the farthest away point along *some*
+          // path. This also matches GCC behavior.  If we really wanted a
+          // totally complete picture of dominance inside this infinite loop, we
+          // could do it with SCC-like algorithms to find the lowest and highest
+          // points in the infinite loop.  In theory, it would be nice to give
+          // the canonical backedge for the loop, but it's expensive.
+          auto *FurthestAway = *po_begin(I);
+          NodeType *ConnectionPoint = nullptr;
+          for (auto Child : children<NodeT>(I))
+            if (DT.Info.count(Child))
+              ConnectionPoint = Child;
+
+          BlocksToConnect[FurthestAway] = ConnectionPoint;
+          N = ReverseDFSPass<GraphT>(DT, FurthestAway, N);
+        }
+      // Finally, now everything should be visited, and anything with parent ==
+      // 0 should be connected to virtual exit.
+      for (auto Pair : BlocksToConnect) {
+        auto *Node = Pair.first;
+        auto *Prev = Pair.second;
+        auto FindResult = DT.Info.find(Node);
+        assert(FindResult != DT.Info.end() &&
+               "Everything should have been visited by now");
+        if (FindResult->second.Parent == 0) {
+          if (DT.Info.count(Prev)) {
+            FindResult->second.Parent = DT.Info[Prev].DFSNum;
           } else {
-    N = DFSPass<GraphT>(DT, DT.Roots[0], N);
+            FindResult->second.Parent = 1;
+            DT.addRoot(Node);
+          }
+        }
+      }
+    }
+  } else {
+    N = DFSPass<GraphT>(DT, GraphTraits<FuncT *>::getEntryNode(&F), N);
   }
-
-  // it might be that some blocks did not get a DFS number (e.g., blocks of
-  // infinite loops). In these cases an artificial exit node is required.
-  MultipleRoots |= (DT.isPostDominator() && N != GraphTraits<FuncT*>::size(&F));
 
   // When naively implemented, the Lengauer-Tarjan algorithm requires a separate
   // bucket for each vertex. However, this is unnecessary, because each vertex
   // is only placed into a single bucket (that of its semidominator), and each
   // vertex's bucket is processed before it is added to any bucket itself.
   //
   // Instead of using a bucket per vertex, we use a single array Buckets that
   // has two purposes. Before the vertex V with preorder number i is processed,
void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<NodeT>> &DT,
   // Step #4: Explicitly define the immediate dominator of each vertex
   for (unsigned i = 2; i <= N; ++i) {
     typename GraphT::NodeRef W = DT.Vertex[i];
     typename GraphT::NodeRef &WIDom = DT.IDoms[W];
     if (WIDom != DT.Vertex[DT.Info[W].Semi])
       WIDom = DT.IDoms[WIDom];
   }
 
-  if (DT.Roots.empty()) return;
-
   // Add a node for the root.  This node might be the actual root, if there is
   // one exit block, or it may be the virtual exit (denoted by (BasicBlock *)0)
   // which postdominates all real exits if there are multiple exit blocks, or
   // an infinite loop.
-  typename GraphT::NodeRef Root = !MultipleRoots ? DT.Roots[0] : nullptr;
+  typename GraphT::NodeRef Root = NeedFakeRoot ? nullptr : DT.Roots[0];
 
   DT.RootNode =
       (DT.DomTreeNodes[Root] =
            llvm::make_unique<DomTreeNodeBase<NodeType>>(Root, nullptr))
           .get();
 
   // Loop over all of the reachable blocks in the function...
   for (unsigned i = 2; i <= N; ++i) {

lib/Transforms/Scalar/ADCE.cpp

for (auto *BB: depth_first_ext(&F.getEntryBlock(), State)) {
         if (State.onStack(Succ)) {
           // back edge....
           markLive(Term);
           break;
         }
     }
   }
 
-  // Mark blocks live if there is no path from the block to the
-  // return of the function or a successor for which this is true.
-  // This protects IDFCalculator which cannot handle such blocks.
-  for (auto &BBInfoPair : BlockInfo) {
-    auto &BBInfo = BBInfoPair.second;
-    if (BBInfo.terminatorIsLive())
-      continue;
-    auto *BB = BBInfo.BB;
-    if (!PDT.getNode(BB)) {
-      markLive(BBInfo.Terminator);
-      continue;
-    }
-    for (auto *Succ : successors(BB))
-      if (!PDT.getNode(Succ)) {
-        markLive(BBInfo.Terminator);
-        break;
-      }
-  }
-
-  // Mark blocks live if there is no path from the block to the
-  // return of the function or a successor for which this is true.
-  // This protects IDFCalculator which cannot handle such blocks.
-  for (auto &BBInfoPair : BlockInfo) {
-    auto &BBInfo = BBInfoPair.second;
-    if (BBInfo.terminatorIsLive())
-      continue;
-    auto *BB = BBInfo.BB;
-    if (!PDT.getNode(BB)) {
-      DEBUG(dbgs() << "Not post-dominated by return: " << BB->getName()
+  // Mark blocks live if there is no path from the block to a
+  // return of the function.
+  // We do this by seeing which of the postdomtree root children exit the
+  // program, and for all others, mark the subtree live.
+  for (auto &PDTChild : children<DomTreeNode *>(PDT.getRootNode())) {
+    auto *BB = PDTChild->getBlock();
+    auto &Info = BlockInfo[BB];
+    // Real function return
+    if (isa<ReturnInst>(Info.Terminator)) {
+      DEBUG(dbgs() << "post-dom root child is not a return: " << BB->getName()
                    << '\n';);
-      markLive(BBInfo.Terminator);
       continue;
     }
-    for (auto *Succ : successors(BB))
-      if (!PDT.getNode(Succ)) {
-        DEBUG(dbgs() << "Successor not post-dominated by return: "
-                     << BB->getName() << '\n';);
-        markLive(BBInfo.Terminator);
-        break;
-      }
+
+    // This child is something else, like an infinite loop.
+    for (auto DFNode : depth_first(PDTChild))
+      markLive(BlockInfo[DFNode->getBlock()].Terminator);
   }
 
   // Treat the entry block as always live
   auto *BB = &F.getEntryBlock();
   auto &EntryInfo = BlockInfo[BB];
   EntryInfo.Live = true;
   if (EntryInfo.UnconditionalBranch)
     markLive(EntryInfo.Terminator);

test/Analysis/PostDominators/pr24415.ll

+; RUN: opt < %s -postdomtree -analyze | FileCheck %s
+; RUN: opt < %s -passes='print<postdomtree>' 2>&1 | FileCheck %s
+
+; Function Attrs: nounwind ssp uwtable
+define void @foo() {
+  br label %1
+
+; <label>:1                                       ; preds = %0, %1
+  br label %1
+                                                  ; No predecessors!
+  ret void
+}
+
+; CHECK: Inorder PostDominator Tree: 
+; CHECK-NEXT:   [1]  <<exit node>> {0,7}
+; CHECK-NEXT:     [2] %2 {1,2}
+; CHECK-NEXT:     [2] %1 {3,6}
+; CHECK-NEXT:       [3] %0 {4,5}

test/Analysis/PostDominators/pr6047_a.ll

 ; RUN: opt < %s -postdomtree -analyze | FileCheck %s
 define internal void @f() {
 entry:
   br i1 undef, label %bb35, label %bb3.i
 
 bb3.i:
   br label %bb3.i
 
 bb35.loopexit3:
   br label %bb35
 
 bb35:
   ret void
 }
-; CHECK: [3] %entry
+;CHECK:Inorder PostDominator Tree: 
+;CHECK-NEXT:  [1]  <<exit node>> {0,9}
+;CHECK-NEXT:    [2] %bb35 {1,8}
+;CHECK-NEXT:      [3] %bb35.loopexit3 {2,3}
+;CHECK-NEXT:      [3] %entry {4,7}
+;CHECK-NEXT:        [4] %bb3.i {5,6}

test/Analysis/PostDominators/pr6047_b.ll

 
 
 bb35.loopexit3:
   br label %bb35
 
 bb35:
   ret void
 }
-; CHECK: [4] %entry
+; CHECK: Inorder PostDominator Tree:
+; CHECK-NEXT:   [1]  <<exit node>> {0,11}
+; CHECK-NEXT:     [2] %bb35 {1,10}
+; CHECK-NEXT:       [3] %bb35.loopexit3 {2,3}
+; CHECK-NEXT:       [3] %a {4,9}
+; CHECK-NEXT:         [4] %entry {5,8}
+; CHECK-NEXT:           [5] %bb3.i {6,7}

test/Analysis/PostDominators/pr6047_c.ll

bb35.loopexit:
   br label %bb35
 
 bb35.loopexit3:
   br label %bb35
 
 bb35:
   ret void
 }
-; CHECK: [3] %entry
+; CHECK: Inorder PostDominator Tree: 
+; CHECK-NEXT:   [1]  <<exit node>> {0,97}
+; CHECK-NEXT:     [2] %bb35 {1,96}
+; CHECK-NEXT:       [3] %bb35.loopexit3 {2,3}
+; CHECK-NEXT:       [3] %bb35.loopexit {4,5}
+; CHECK-NEXT:       [3] %bb31 {6,7}
+; CHECK-NEXT:       [3] %bb30 {8,9}
+; CHECK-NEXT:       [3] %bb30.loopexit1 {10,11}
+; CHECK-NEXT:       [3] %bb30.loopexit {12,13}
+; CHECK-NEXT:       [3] %bb23 {14,15}
+; CHECK-NEXT:       [3] %bb23.us {16,17}
+; CHECK-NEXT:       [3] %bb23.preheader {18,19}
+; CHECK-NEXT:       [3] %bb23.us.preheader {20,21}
+; CHECK-NEXT:       [3] %bb.nph {22,23}
+; CHECK-NEXT:       [3] %bb29.preheader {24,25}
+; CHECK-NEXT:       [3] %bb20 {26,27}
+; CHECK-NEXT:       [3] %bb19 {28,29}
+; CHECK-NEXT:       [3] %bb.nph14 {30,31}
+; CHECK-NEXT:       [3] %bb17.loopexit.split {32,33}
+; CHECK-NEXT:       [3] %bb16 {34,35}
+; CHECK-NEXT:       [3] %bb15 {36,37}
+; CHECK-NEXT:       [3] %bb15.loopexit2 {38,39}
+; CHECK-NEXT:       [3] %bb15.loopexit {40,41}
+; CHECK-NEXT:       [3] %bb8 {42,43}
+; CHECK-NEXT:       [3] %bb8.us {44,45}
+; CHECK-NEXT:       [3] %bb8.preheader {46,47}
+; CHECK-NEXT:       [3] %bb8.us.preheader {48,49}
+; CHECK-NEXT:       [3] %bb.nph18 {50,51}
+; CHECK-NEXT:       [3] %bb14.preheader {52,53}
+; CHECK-NEXT:       [3] %bb5 {54,55}
+; CHECK-NEXT:       [3] %bb4 {56,57}
+; CHECK-NEXT:       [3] %bb.nph21 {58,59}
+; CHECK-NEXT:       [3] %bb3.i.loopexit.us {60,61}
+; CHECK-NEXT:       [3] %bb8.i.us {62,63}
+; CHECK-NEXT:       [3] %bb4.i.us {64,65}
+; CHECK-NEXT:       [3] %bb6.i.us {66,67}
+; CHECK-NEXT:       [3] %bb1.i.us {68,69}
+; CHECK-NEXT:       [3] %bb.i4.us.backedge {70,71}
+; CHECK-NEXT:       [3] %bb7.i.us {72,73}
+; CHECK-NEXT:       [3] %bb.i4.us {74,75}
+; CHECK-NEXT:       [3] %bb3.split.us {76,77}
+; CHECK-NEXT:       [3] %bb3 {78,79}
+; CHECK-NEXT:       [3] %bb32.preheader {80,81}
+; CHECK-NEXT:       [3] %_float32_unpack.exit8 {82,83}
+; CHECK-NEXT:       [3] %bb.i5 {84,85}
+; CHECK-NEXT:       [3] %_float32_unpack.exit {86,87}
+; CHECK-NEXT:       [3] %bb.i {88,89}
+; CHECK-NEXT:       [3] %bb {90,91}
+; CHECK-NEXT:       [3] %entry {92,95}
+; CHECK-NEXT:         [4] %bb3.i {93,94}

test/Analysis/PostDominators/pr6047_d.ll

bb3.i:
   br label %bb3.i
 
 bb35.loopexit3:
   br label %bb35
 
 bb35:
   ret void
 }
-; CHECK: [4] %entry
+; CHECK: Inorder PostDominator Tree:
+; CHECK-NEXT:   [1]  <<exit node>> {0,15}
+; CHECK-NEXT:     [2] %bb35 {1,14}
+; CHECK-NEXT:       [3] %bb35.loopexit3 {2,3}
+; CHECK-NEXT:       [3] %c {4,13}
+; CHECK-NEXT:         [4] %b {5,6}
+; CHECK-NEXT:         [4] %entry {7,8}
+; CHECK-NEXT:         [4] %a {9,10}
+; CHECK-NEXT:         [4] %bb3.i {11,12}

test/Analysis/RegionInfo/infinite_loop.ll

2:
   br label %"2"
 3:
   br label %"4"
 4:
   ret void
 }
 ; CHECK-NOT: =>
 ; CHECK: [0] 0 => <Function Return>
-; CHECK: [1] 1 => 4
-; STAT: 2 region - The # of regions
+; CHECK-NEXT: [1] 1 => 3
+; CHECK-NEXT:   [2] 2 => 1
+; STAT: 3 region - The # of regions
 ; STAT: 1 region - The # of simple regions

test/Analysis/RegionInfo/infinite_loop_2.ll

 6:
         br label %"2"
 3:
   br label %"4"
 4:
   ret void
 }
 ; CHECK-NOT: =>
-; CHECK: [0] 0 => <Function Return>
-; CHECK: [1] 1 => 3
-; STAT: 2 region - The # of regions
+; CHECK:      [0] 0 => <Function Return>
+; CHECK-NEXT:   [1] 1 => 3
+; CHECK-NEXT:     [2] 2 => 1
+; CHECK-NEXT:       [3] 5 => 6
+; STAT: 4 region - The # of regions
 ; STAT: 1 region - The # of simple regions
 
 ; BBIT: 0, 1, 2, 5, 11, 6, 12, 3, 4,
 ; BBIT: 1, 2, 5, 11, 6, 12,
+; BBIT: 2, 5, 11, 6, 12,
+; BBIT: 5, 11, 12,
 
 ; RNIT: 0, 1 => 3, 3, 4,
-; RNIT: 1, 2, 5, 11, 6, 12,
+; RNIT: 1, 2 => 1,
+; RNIT: 2, 5 => 6, 6,
+; RNIT: 5, 11, 12,

test/Analysis/RegionInfo/infinite_loop_3.ll

 10:
         br label %"8"
 3:
   br label %"4"
 4:
   ret void
 }
 ; CHECK-NOT: =>
-; CHECK: [0] 0 => <Function Return>
-; CHECK-NEXT: [1] 1 => 3
-; CHECK-NEXT: [1] 7 => 1
-; STAT: 3 region - The # of regions
+; CHECK:      [0] 0 => <Function Return>
+; CHECK-NEXT:   [1] 7 => 1
+; CHECK-NEXT:     [2] 8 => 7
+; CHECK-NEXT:       [3] 9 => 10
+; CHECK-NEXT:   [1] 1 => 3
+; CHECK-NEXT:     [2] 2 => 1
+; CHECK-NEXT:       [3] 5 => 6
+
+; STAT: 7 region - The # of regions
 ; STAT: 2 region - The # of simple regions
 
 ; BBIT: 0, 7, 1, 2, 5, 11, 6, 12, 3, 4, 8, 9, 13, 10, 14,
 ; BBIT: 7, 8, 9, 13, 10, 14,
+; BBIT: 8, 9, 13, 10, 14,
+; BBIT: 9, 13, 14,
 ; BBIT: 1, 2, 5, 11, 6, 12,
+; BBIT: 2, 5, 11, 6, 12,
+; BBIT: 5, 11, 12,
 
 ; RNIT: 0, 7 => 1, 1 => 3, 3, 4,
-; RNIT: 7, 8, 9, 13, 10, 14,
-; RNIT: 1, 2, 5, 11, 6, 12,
+; RNIT: 7, 8 => 7,
+; RNIT: 8, 9 => 10, 10,
+; RNIT: 9, 13, 14,
+; RNIT: 1, 2 => 1,
+; RNIT: 2, 5 => 6, 6,
+; RNIT: 5, 11, 12,

test/Analysis/RegionInfo/infinite_loop_4.ll

 10:
         br label %"8"
 3:
   br label %"4"
 4:
   ret void
 }
 ; CHECK-NOT: =>
-; CHECK: [0] 0 => <Function Return>
-; CHECK-NEXT: [1] 7 => 3
-; STAT: 2 region - The # of regions
-; STAT: 1 region - The # of simple regions
+; CHECK:      [0] 0 => <Function Return>
+; CHECK-NEXT:   [1] 7 => 3
+; CHECK-NEXT:     [2] 2 => 10
+; CHECK-NEXT:       [3] 5 => 6
+; STAT: 4 region - The # of regions
+; STAT: 2 region - The # of simple regions
 
 ; BBIT: 0, 7, 1, 2, 5, 11, 6, 10, 8, 9, 13, 14, 12, 3, 4,
 ; BBIT: 7, 1, 2, 5, 11, 6, 10, 8, 9, 13, 14, 12,
+; BBIT: 2, 5, 11, 6, 12,
+; BBIT: 5, 11, 12,
 
 ; RNIT: 0, 7 => 3, 3, 4,
-; RNIT: 7, 1, 2, 5, 11, 6, 10, 8, 9, 13, 14, 12,
+; RNIT: 7, 1, 2 => 10, 10, 8, 9, 13, 14,
+; RNIT: 2, 5 => 6, 6,
+; RNIT: 5, 11, 12,

test/Analysis/RegionInfo/infinite_loop_5_a.ll

3:
     br label %"4"
 4:
     ret void
 }
 
 ; CHECK:      Region tree:
 ; CHECK-NEXT: [0] 0 => <Function Return>
 ; CHECK-NEXT:   [1] 7 => 3
+; CHECK-NEXT:      [2] 8 => 1
 ; CHECK-NEXT: End region tree
 

test/Analysis/RegionInfo/infinite_loop_5_b.ll

3:
     br label %"4"
 4:
     ret void
 }
 
 ; CHECK:      Region tree:
 ; CHECK-NEXT: [0] 0 => <Function Return>
 ; CHECK-NEXT:   [1] 7 => 3
+; CHECK-NEXT:     [2] 9 => 1
+; CHECK-NEXT:       [3] 8 => 7
 ; CHECK-NEXT: End region tree

test/Transforms/StructurizeCFG/branch-on-argument.ll

 ; RUN: opt -S -o - -structurizecfg < %s | FileCheck %s
 
 ; CHECK-LABEL: @invert_branch_on_arg_inf_loop(
 ; CHECK: entry:
 ; CHECK: %arg.inv = xor i1 %arg, true
-; CHECK: phi i1 [ false, %Flow1 ], [ %arg.inv, %entry ]
 define void @invert_branch_on_arg_inf_loop(i32 addrspace(1)* %out, i1 %arg) {
 entry:
-  br i1 %arg, label %for.end, label %for.body
+  br i1 %arg, label %for.end, label %sesestart
+sesestart:
+  br label %for.body
 
 for.body:                                         ; preds = %entry, %for.body
   store i32 999, i32 addrspace(1)* %out, align 4
-  br label %for.body
+  br i1 %arg, label %for.body, label %seseend
+seseend:
+  ret void
 
 for.end:                                          ; preds = %Flow
   ret void
 }
 
 
 ; CHECK-LABEL: @invert_branch_on_arg_jump_into_loop(
 ; CHECK: entry:

test/Transforms/StructurizeCFG/no-branch-to-entry.ll

+; XFAIL: *
 ; RUN: opt -S -o - -structurizecfg -verify-dom-info < %s | FileCheck %s
 
 ; CHECK-LABEL: @no_branch_to_entry_undef(
 ; CHECK: entry:
 ; CHECK-NEXT: br label %entry.orig
 define void @no_branch_to_entry_undef(i32 addrspace(1)* %out) {
 entry:
   br i1 undef, label %for.end, label %for.body