Fix bug to merge away entry block and update DT correctly.

[trentxintong]

Summary

Fix bug to merge away entry block and update DT correctly.

[trentxintong]

run clang-format

[trentxintong]

Remove some duplicate code.

[davide]

I admit I haven't looked at this code in a while, but I can't understand your fix. Can you please elaborate with an example?

lib/Transforms/Utils/Local.cpp

718

I'm a little confused by this comment. Isn't always the case that the entry block has no idom by definition of dominator tree?

unittests/Transforms/Utils/Local.cpp

221

The predecessors list here looks wrong?

[trentxintong]

lib/Transforms/Utils/Local.cpp

718

I should add "Entry block does not have IDom, do not attempt to getIDom() on it.
The problem with the code is we try to hook up the IDom of PredBB with dominator tree node of DestBB. But if PredBB is entry block, it does not have IDom , we need to recompute.

unittests/Transforms/Utils/Local.cpp

221

Yes, I will fix that.

[dmgreen]

Worth seeing D48202, which plans to remove this function in preference of MergeBlockIntoPredecessor (which does the merge the other way, so doesn't run into the same problem removing the entry block).

[trentxintong]

@dmgreen Thanks for the pointer. I think https://reviews.llvm.org/D48202 will define away the problem. I will abandon this patch.

lib/Transforms/Utils/Local.cpp

void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, DominatorTree *DT,
   PredBB->getTerminator()->eraseFromParent();
   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 (ReplaceEntryBB)
     DestBB->moveAfter(PredBB);
 
-  if (DT) {
+  // Entry block does not have IDom.
+  if (DT && !ReplaceEntryBB) {
     // 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);
     }
   }
 
   if (DDT) {
     DDT->deleteBB(PredBB); // Deferred deletion of BB.
     if (ReplaceEntryBB)
       // The entry block was removed and there is no external interface for the
       // dominator tree to be notified of this change. In this corner-case we
       // recalculate the entire tree.
       DDT->recalculate(*(DestBB->getParent()));
     else
       DDT->applyUpdates(Updates);
   } else {
     PredBB->eraseFromParent(); // Nuke BB.
+    // The entry block was removed and there is no external interface for the
+    // dominator tree to be notified of this change. In this corner-case we
+    // recalculate the entire tree.
+    if (DT && ReplaceEntryBB)
+      DT->recalculate(*(DestBB->getParent()));
   }
 }
 
 /// 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) {
   return First == Second || isa<UndefValue>(First) || isa<UndefValue>(Second);

unittests/Transforms/Utils/Local.cpp

static void runWithDomTree(
   // Compute the dominator tree for the function.
   DominatorTree DT(*F);
   Test(*F, &DT);
 }
 
 TEST(Local, MergeBasicBlockIntoOnlyPred) {
   LLVMContext C;
 
+  auto runMergeBasicBlockIntoOnlyPred = [&](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);
+    }
+  };
+
   std::unique_ptr<Module> M = parseIR(C,
                                       R"(
       define i32 @f(i8* %str) {
       entry:
         br label %bb2.i
       bb2.i:                                            ; preds = %bb4.i, %entry
         br i1 false, label %bb4.i, label %base2flt.exit204
       bb4.i:                                            ; preds = %bb2.i
         br i1 false, label %base2flt.exit204, label %bb2.i
       bb10.i196.bb7.i197_crit_edge:                     ; No predecessors!
         br label %bb7.i197
       bb7.i197:                                         ; preds = %bb10.i196.bb7.i197_crit_edge
         %.reg2mem.0 = phi i32 [ %.reg2mem.0, %bb10.i196.bb7.i197_crit_edge ]
         br i1 undef, label %base2flt.exit204, label %base2flt.exit204
       base2flt.exit204:                                 ; preds = %bb7.i197, %bb7.i197, %bb2.i, %bb4.i
         ret i32 0
       }
       )");
-  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());
-      });
+  runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) {
+    runMergeBasicBlockIntoOnlyPred(F, DT);
+    EXPECT_TRUE(DT->verify());
+  });
+
+  // Test we can merge away entry block and update DT correctly.
+  // entry block does not have IDom.
+  std::unique_ptr<Module> M2 = parseIR(C,
+                                       R"(
+      define i32 @f(i8* %str) {
+      entry:
+        br label %bb2.i
+      bb2.i:                                            ; preds = %bb4.i, %entry
+        br label %base2flt.exit204
+      base2flt.exit204:                                 ; preds = %bb7.i197, %bb7.i197, %bb2.i, %bb4.i
+        ret i32 0
+      )");
+  runWithDomTree(*M2, "f", [&](Function &F, DominatorTree *DT) {
+    runMergeBasicBlockIntoOnlyPred(F, DT);
 }
 
 TEST(Local, ConstantFoldTerminator) {
   LLVMContext C;
 
   std::unique_ptr<Module> M = parseIR(C,
                                       R"(
       define void @br_same_dest() {