Do not verify Dominator tree if it has no roots

[sepavloff]

Summary

If dominator tree has no roots, the pass that calculates it is
likely to be skipped, it occures for instance in the case of
entities with linkage available_externally. Do not run tree
verification in such case.

[mcrosier]

This seems reasonable to me, but I've added more reviews to see if they have any additional feedback.

IIRC, when I wrote the patch to add the verifyDomTree function here it was taken verbatim from the IR level dominator tree verifier. Therefore, it might be a good idea to make a similar change to the IR-level verifier.

lib/CodeGen/MachineDominators.cpp

147

I'd probably drop this comment in favor of the title of this revision, "Do not verify Dominator tree if it has no root."

[sepavloff]

Added similar check in IR/Dominators.

[sepavloff]

IIRC, when I wrote the patch to add the verifyDomTree function here it was taken verbatim from the IR level dominator tree verifier. Therefore, it might be a good idea to make a similar change to the IR-level verifier.

This change fixes 11 test fails observer when llvm was build with LLVM_ENABLE_EXPENSIVE_CHECKS turned on. None of them occurs in IR but some time ago there were such fails. So added the respective check.

lib/CodeGen/MachineDominators.cpp

147

Rephrased the comment.

[mssimpso]

This patch looks good to me, but please let someone else approve.

[mcrosier]

LGTM. It would be nice if we had a test case that covered the IR version as well.

[• dberlin]

This looks, IMHO, very wrong.
We require domtrees to have roots at all times.
See getRoot, for example, which says:

NodeT *getRoot() const {
  assert(this->Roots.size() == 1 && "Should always have entry node!");
  return this->Roots[0];
}

So if we've created a DominatorTree to call verifyDomTree on,and it doesn't have a root, we have in fact, created a broken dom tree and verification *should* fail.

I'm not sure why we are creating such a tree, but it's *definitely invalid* according to how we work right now.
All this patch does is paper over that by calling getRoots instead of getRoot, because getRoots happens to not assert (we should add a non-emptyness assert there too).

I think you need to fix the underlying problem of creating DominatorTrees without roots, or start a discussion on llvmdev about whether the empty dom tree should be valid.
(Preferably, the former).

Because so far, we've never considered "the completely empty" domtree to be valid, and we haven't audited our functions to make sure they all work properly in such a world.

[mcrosier]

I very much trust Danny's opinion. Thus, this has been reverted in r293075. I defer Danny's other comments/suggestions (i.e., fixing DT creation w/o roots or starting a discussion on LLVM Dev) to Serge.

lib/CodeGen/MachineDominators.cpp

if (IsNewIDom[Idx])
       DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode);
     ++Idx;
   }
   NewBBs.clear();
   CriticalEdgesToSplit.clear();
 }
 
 void MachineDominatorTree::verifyDomTree() const {
+  if (getRoots().empty())
+    // If dominator tree is unavailable, skip verification.
+    return;
+
   MachineFunction &F = *getRoot()->getParent();
 
   MachineDominatorTree OtherDT;
   OtherDT.DT->recalculate(F);
   if (compare(OtherDT)) {
     errs() << "MachineDominatorTree is not up to date!\nComputed:\n";
     print(errs(), nullptr);
     errs() << "\nActual:\n";
     OtherDT.print(errs(), nullptr);
     abort();
   }
 }

lib/IR/Dominators.cpp

bool DominatorTree::isReachableFromEntry(const Use &U) const {
   if (PHINode *PN = dyn_cast<PHINode>(I))
     return isReachableFromEntry(PN->getIncomingBlock(U));
 
   // Everything else uses their operands in their own block.
   return isReachableFromEntry(I->getParent());
 }
 
 void DominatorTree::verifyDomTree() const {
+  if (getRoots().empty())
+    // If dominator tree is unavailable, skip verification.
+    return;
+
   Function &F = *getRoot()->getParent();
 
   DominatorTree OtherDT;
   OtherDT.recalculate(F);
   if (compare(OtherDT)) {
     errs() << "DominatorTree is not up to date!\nComputed:\n";
     print(errs());
     errs() << "\nActual:\n";

test/CodeGen/Generic/externally_available.ll

-; RUN: llc < %s | not grep test_
+; RUN: llc -verify-machine-dom-info < %s | not grep test_
 
 ; test_function should not be emitted to the .s file.
 define available_externally i32 @test_function() {
   ret i32 4
 }
 
 ; test_global should not be emitted to the .s file.
 @test_global = available_externally global i32 4