Fix PR 24415 (at least), by making our post-dominator tree behavior sane.

[• dberlin]

Summary

Currently, our post-dom tree tries to ignore and remove the effects of
infinite loops. It fails miserably at this, because it tries to do it
ahead of time, and thus can only detect self-loops, and any other type
of infinite loop, it pretends doesn't exist at all.

This can, in a bunch of cases, lead to wrong answers and a completely
empty post-dom tree.

Wrong answer:

declare void foo()
define internal void @f() {
entry:
  br i1 undef, label %bb35, label %bb3.i

bb3.i:
  call void @foo()
  br label %bb3.i

bb35.loopexit3:
  br label %bb35

bb35:
  ret void
}

We get:

Inorder PostDominator Tree:
  [1]  <<exit node>> {0,7}
    [2] %bb35 {1,6}
      [3] %bb35.loopexit3 {2,3}
      [3] %entry {4,5}

This is a trivial modification of the testcase for PR 6047
Note that we pretend bb3.i doesn't exist.
We also pretend that bb35 post-dominates entry.

While it's true that it does not exit in a theoretical sense, it's not
really helpful to try to ignore the effect and pretend that bb35
post-dominates entry. Worse, we pretend the infinite loop does
nothing (it's usually considered a side-effect), and doesn't even
exist, even when it calls a function. Sadly, this makes it impossible
to use when you are trying to move code safely. All compilers also
create virtual or real single exit nodes (including us), and connect
infinite loops there (which this patch does). In fact, others have
worked around our behavior here, to the point of building their own
post-dom trees:
https://zneak.github.io/fcd/2016/02/17/structuring.html and pointing
out the region infrastructure is near-useless for them with postdom in
this state :(

Completely empty post-dom tree:

define void @spam() #0 {
bb:
  br label %bb1

bb1:                                              ; preds = %bb1, %bb
  br label %bb1

bb2:                                              ; No predecessors!
  ret void
}

Printing analysis 'Post-Dominator Tree Construction' for function 'foo':
=============================--------------------------------
Inorder PostDominator Tree:
  [1]  <<exit node>> {0,1}

:(

(note that even if you ignore the effects of infinite loops, bb2
should be present as an exit node that post-dominates nothing).

This patch changes post-dom to properly handle infinite loops and does
root finding during calculation to prevent empty tress in such cases.

We match gcc's (and the canonical theoretical) behavior for infinite
loops (find the backedge, connect it to the exit block).

Testcases coming as soon as i finish running this on a ton of random graphs :)

[• dberlin]

include/llvm/Support/GenericDomTreeConstruction.h

46

Sorry, this was part of an alternate approach, will revert.

172

Keen observers will note that this ::size call was O(N) since it's an ilist.
:(
So the code i added really only adds O(N) time worst case, since we already wasted O(N) time just counting blocks above.

194

This comment needs updating a bit. It really ends up finding the infinite loop backedge block, which is what we want.
(note that post-dom is not unique, so if there are multiple backedges, you can't win, there is no "best" one)

249

This got clang-formatted, i'll revert

285

and this is leftover from a dead approach too.
i'll remove.

[bryant]

Minor things.

include/llvm/Support/GenericDomTreeConstruction.h

165

Ranged-for? for (NodeType *BB: make_range(FuncGraphT::nodes_begin(&F), FuncGraphT::nodes_end(&F))) {.

177

Typo? "make. block."

184

Ranged-for?

247

Ranged?

[• dberlin]

include/llvm/Support/GenericDomTreeConstruction.h

165

Honestly, i would rather us just improve graph traits to provide ranges here.
I'm not sure i believe the ranged for version is more readable/easier to understand with make_range.
i'm happy to do that as a followup to add "nodes" and "children" to graph traits.

[davide]

The approach looks good to me, if you add a testcase and revert the unrelated changes I'll give it another look (possibly today)

[davide]

I think a test for infinite loops (the one attached to the PR or/and slight modification of them) are fine (at least for me)

[• dberlin]

I have updated all tests.
The region ones were particularly nutso before (IHMO), and now look sane.

there is one failure in ADCE, because previously postdom gave it an empty tree, and now gives it a real tree.
It expects that all not-reachable-from-exit nodes will not have a dom tree node, which is not correct.
It also assumes it will be able to find a safe place to redirect an edge that still exits the function, which is also not correct.
Fixes for both coming.
Then i am going to look at the two structurize cfg failures.

[• dberlin]

adding the last two people to touch structurize CFG.

The code is mostly undocumented, and it seems ... interesting, in many ways .
It has an obsession with assuming regions are started and terminated with branchinsts, when they could, for example, be switches with one successor (it looks like it forces switch lowering instead of fixing the code).
It also gets successors of blocks by trying to grab terminators and walk over the terminator successors, instead of just walking the successors directly.

In any case, there is nothing to fix for these testcases.
There are two failures.
In branch-on-argument.ll, we fail invert_branch_on_arg_inf_loop.
This is because there are no SESE regions here once post-dom is correct.
The only SESE region is function entry to function exit, and structurizeCFG explicitly skips that region,

Ditto for no-branch-to-entry.ll
It's not a SESE region, so it no longer processes it.
I can't make a testcase where it wants to branch to entry anymore.

I'm XFAIL'ing it for someone to determine if it's really still needed. My guess is this was a side effect of broken SESE regions.

[• dberlin]

• Update with fixes for broken testcases, and review comments. Add test case for pr24415

[jlebar]

I'm fine with the structurize cfg changes.

[• dberlin]

Okay. At this point i'm pretty positive i can prove that any region that now it considers the entry to be the start of the loop will be a top-level region that structurizecfg will ignore, and we can delete the test (and associated code in structurizecfg/domtree to handle it). I'm going to do so unless someone objects.

We just gave a bogus region tree before:
Printing analysis 'Detect single entry single exit regions' for function 'no_branch_to_entry_true':

[0] entry => <Function Return>
{
  entry, for.end, for.body,
  [1] entry => for.end
  {
    entry, for.body,
  }
}

#1 is definitely not a sese region. It double definitely does not include for.body, which never exits and never goes to for.end :P :

Let's go from first principles, with a little help from wikipedia:
In graph theory, a single-entry single-exit (SESE) region in a given graph is an ordered edge pair (a, b) of distinct control flow edges a and b where:

a dominates b
b postdominates a
Every cycle containing a also contains b and vice versa.

In the old world, for.end post-dominates entry (and for.body is not in the postdomree), which is wrong:

=============================--------------------------------
Inorder PostDominator Tree:
  [1]  <<exit node>> {0,5}
    [2] %for.end {1,4}
      [3] %entry {2,3}

So it believes entry->for.end is a sese region.
Which would in fact, be true if there was no loop that postdom has ignored.
The region-former then uses the definition of dominance/post-dominance, and believes that such a region must also include the other preds of entry (IE for.body). This is even reasonable and correct given the regular definition of postdom.
But of course, in this case, postdom is wrong,and really,all of the blocks are siblings in the postdomtree.
In the new world,it properly forms the postdomtree:

[1]  <<exit node>> {0,7}
   [2] %for.end {1,2}
   [2] %entry {3,4}
   [2] %for.body {5,6}

There is no sese region to be formed here. The only way you could ever end up with a sese region loop that involves entry is a normal loop:

define void @no_branch_to_entry_undef(i32 addrspace(1)* %out) {
entry:
  br i1 undef, label %for.end, label %for.body
for.body:                                         ; preds = %entry, %for.body
  store i32 999, i32 addrspace(1)* %out, align 4
  br i1 undef, label %for.body, label %for.end
for.end:                                          ; preds = %Flow
  ret void
}

It does not try to modify the entry block for such a normal loop.

Thus, i believe all of this hackery is now dead.

[• dberlin]

(and obviously, i'll xfail in this patch, and then delete it wit associated hackery in a followup)

[• dberlin]

Ping. This is ready to go in and I have a new verifier that depends on it

[davide]

The Domtree changes look good to me but I can't comment on StructurizeCFG

[davide]

LGTM, then

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 (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))
-          addRoot(*I);
-
       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 = FuncGraphT::nodes_begin(&F), E = FuncGraphT::nodes_end(&F);
+         I != E; ++I) {
+      ++Total;
+      // If it has no *successors*, it is definitely a root.
+      if (FuncGraphT::child_begin(*I) == FuncGraphT::child_end(*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.  block.
+      // 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.
+      SmallPtrSet<NodeType *, 4> ConnectToExitBlock;
+      for (auto I = FuncGraphT::nodes_begin(&F), E = FuncGraphT::nodes_end(&F);
+           I != E; ++I)
+        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.
+          auto *FurthestAway = *po_begin(*I);
+          ConnectToExitBlock.insert(FurthestAway);
+          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 *Node : ConnectToExitBlock) {
+        auto FindResult = DT.Info.find(Node);
+        assert(FindResult != DT.Info.end() &&
+               "Everything should have been visited by now");
+        if (FindResult->second.Parent == 0) {
+          FindResult->second.Parent = 1;
+          DT.addRoot(Node);
+        }
+      }
+    }
   } else {
-    N = DFSPass<GraphT>(DT, DT.Roots[0], N);
+    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,
   // Buckets[i] stores the index of the first element in V's bucket. After V's
for (unsigned j = i; Buckets[j] != i; j = Buckets[j]) {
       typename GraphT::NodeRef U = Eval<GraphT>(DT, V, i + 1);
       DT.IDoms[V] = DT.Info[U].Semi < i ? U : W;
     }
 
     // Step #3: Calculate the semidominators of all vertices
 
     // initialize the semi dominator to point to the parent node
     WInfo.Semi = WInfo.Parent;
-    typedef GraphTraits<Inverse<NodeT> > InvTraits;
-    for (typename InvTraits::ChildIteratorType CI =
-         InvTraits::child_begin(W),
-         E = InvTraits::child_end(W); CI != E; ++CI) {
+    typedef GraphTraits<Inverse<NodeT>> InvTraits;
+    for (typename InvTraits::ChildIteratorType CI = InvTraits::child_begin(W),
+                                               E = InvTraits::child_end(W);
+         CI != E; ++CI) {
       typename InvTraits::NodeRef N = *CI;
-      if (DT.Info.count(N)) {  // Only if this predecessor is reachable!
+        // Only if this predecessor is reachable.
+      if (DT.Info.count(N)) {
         unsigned SemiU = DT.Info[Eval<GraphT>(DT, N, i + 1)].Semi;
         if (SemiU < WInfo.Semi)
           WInfo.Semi = SemiU;
       }
     }
 
     // If V is a non-root vertex and sdom(V) = parent(V), then idom(V) is
     // necessarily parent(V). In this case, set idom(V) here and avoid placing
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;
+  // Detect how many roots we need by checking which things ended up with null
+  // idoms.
 
   // 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) {