[Local] Fix a bug in the domtree update logic for MergeBasicBlockIntoOnlyPred.

[bmakam]

Summary

For some irreducible CFG the domtree nodes might be dead, do not update domtree for dead nodes.

[kuhar]

For some irreducible CFG the domtree nodes might be dead, do not update domtree for dead nodes.

Can you show some example of such CFG and add a comment explaining this check?

DomTree::getNode return nullptr only for forward-unreachable CFG nodes.

[bmakam]

In D38960#898701, @kuhar wrote:

For some irreducible CFG the domtree nodes might be dead, do not update domtree for dead nodes.

Can you show some example of such CFG and add a comment explaining this check?

DomTree::getNode return nullptr only for forward-unreachable CFG nodes.

I found this bug while testing D37343. When D37343 is applied, test/Transforms/CodeGenPrepare/2008-11-24-RAUW-Self.ll will crash because of this.

[kuhar]

I think that this deserves a comment with a (partial) example, otherwise the change looks suspicious.

[bmakam]

In D38960#898713, @kuhar wrote:

I think that this deserves a comment with a (partial) example, otherwise the change looks suspicious.

Fair point. All the users of MergeBasicBlockIntoOnlyPred in the tree, do not pass DT to the function, so it is never exposed. Is there a way to test this in tree by passing DT to MergeBasicBlockIntoOnlyPred?

[kuhar]

In D38960#898723, @bmakam wrote:

In D38960#898713, @kuhar wrote:

I think that this deserves a comment with a (partial) example, otherwise the change looks suspicious.

Fair point. All the users of MergeBasicBlockIntoOnlyPred in the tree, do not pass DT to the function, so it is never exposed. Is there a way to test this in tree by passing DT to MergeBasicBlockIntoOnlyPred?

It shouldn't be difficult to turn it into a unit test. I haven't checked how Local.cpp is tested, but you can find some existing dominator tree tests in IRTests/DominatorTree.cpp.

[bmakam]

Add unittest and a comment.

[kuhar]

Thanks for adding the comment.

The testcase seems really long and it's not obvious why what it tries to exercise -- have you tried reducing it with bugpoint to something shorter and easier to reason about?

[bmakam]

In D38960#899142, @kuhar wrote:

Thanks for adding the comment.

The testcase seems really long and it's not obvious why what it tries to exercise -- have you tried reducing it with bugpoint to something shorter and easier to reason about?

Sorry for the long testcase, but this untitest was extracted after using bugpoint to reduce the lit test in test/Transforms/CodeGenPrepare/2008-11-24-RAUW-Self.ll. Is there a way to reduce a unittest using bugpoint?

[bmakam]

Reduce unittest.

[kuhar]

This reduced IR is much nicer.

[bmakam]

Thanks for the reviews.

llvm/trunk/lib/Transforms/Utils/Local.cpp

void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, DominatorTree *DT) {
   DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList());
 
   // If the PredBB is the entry block of the function, move DestBB up to
   // become the entry block after we erase PredBB.
   if (PredBB == &DestBB->getParent()->getEntryBlock())
     DestBB->moveAfter(PredBB);
 
   if (DT) {
-    BasicBlock *PredBBIDom = DT->getNode(PredBB)->getIDom()->getBlock();
+    // For some irreducible CFG we end up having forward-unreachable blocks
+    // so check if getNode returns a valid node before updating the domtree.
+    if (DomTreeNode *DTN = DT->getNode(PredBB)) {
+      BasicBlock *PredBBIDom = DTN->getIDom()->getBlock();
       DT->changeImmediateDominator(DestBB, PredBBIDom);
       DT->eraseNode(PredBB);
     }
+  }
   // Nuke BB.
   PredBB->eraseFromParent();
 }
 
 /// CanMergeValues - Return true if we can choose one of these values to use
 /// in place of the other. Note that we will always choose the non-undef
 /// value to keep.
 static bool CanMergeValues(Value *First, Value *Second) {

llvm/trunk/unittests/Transforms/Utils/Local.cpp

TEST(Local, ReplaceDbgDeclare) {
 
   // There should be exactly two dbg.declares.
   int Declares = 0;
   for (const Instruction &I : F->front())
     if (isa<DbgDeclareInst>(I))
       Declares++;
   EXPECT_EQ(2, Declares);
 }
+
+/// Build the dominator tree for the function and run the Test.
+static void runWithDomTree(
+    Module &M, StringRef FuncName,
+    function_ref<void(Function &F, DominatorTree *DT)> Test) {
+  auto *F = M.getFunction(FuncName);
+  ASSERT_NE(F, nullptr) << "Could not find " << FuncName;
+  // Compute the dominator tree for the function.
+  DominatorTree DT(*F);
+  Test(*F, &DT);
+}
+
+TEST(Local, MergeBasicBlockIntoOnlyPred) {
+  LLVMContext C;
+
+  std::unique_ptr<Module> M = parseIR(
+      C,
+      "define i32 @f(i8* %str) {\n"
+      "entry:\n"
+      "  br label %bb2.i\n"
+      "bb2.i:                                            ; preds = %bb4.i, %entry\n"
+      "  br i1 false, label %bb4.i, label %base2flt.exit204\n"
+      "bb4.i:                                            ; preds = %bb2.i\n"
+      "  br i1 false, label %base2flt.exit204, label %bb2.i\n"
+      "bb10.i196.bb7.i197_crit_edge:                     ; No predecessors!\n"
+      "  br label %bb7.i197\n"
+      "bb7.i197:                                         ; preds = %bb10.i196.bb7.i197_crit_edge\n"
+      "  %.reg2mem.0 = phi i32 [ %.reg2mem.0, %bb10.i196.bb7.i197_crit_edge ]\n"
+      "  br i1 undef, label %base2flt.exit204, label %base2flt.exit204\n"
+      "base2flt.exit204:                                 ; preds = %bb7.i197, %bb7.i197, %bb2.i, %bb4.i\n"
+      "  ret i32 0\n"
+      "}\n");
+  runWithDomTree(
+      *M, "f", [&](Function &F, DominatorTree *DT) {
+        for (Function::iterator I = F.begin(), E = F.end(); I != E;) {
+          BasicBlock *BB = &*I++;
+          BasicBlock *SinglePred = BB->getSinglePredecessor();
+          if (!SinglePred || SinglePred == BB || BB->hasAddressTaken()) continue;
+          BranchInst *Term = dyn_cast<BranchInst>(SinglePred->getTerminator());
+          if (Term && !Term->isConditional())
+            MergeBasicBlockIntoOnlyPred(BB, DT);
+        }
+        EXPECT_TRUE(DT->verify());
+      });
+}