Utils: Fix DomTree update for entry block

[arsenm]

Summary

If SplitBlockPredecessors was used on a function entry block,
it wouldn't update the dominator tree.

[kuhar]

lib/Transforms/Utils/BasicBlockUtils.cpp

513

Shouldn't this be handled in UpdateAnalysisInformation?
I think that it would also make sense to assert that BB used to be the first BB in the function -- this would only fire when someone passed in an already incorrect DomTree. Otherwise, this can hide this kind of bugs.

[kuhar]

We should also try to get this fix into 6.0, the surrounding lines are not new. In fact, they were last modified 9-10 years ago. I wonder why it stayed unnoticed for so long.

[davide]

lib/Transforms/Utils/BasicBlockUtils.cpp

513

agree with Kuba

[brzycki]

I too am curious how this managed to not be found for several years. @arsenm how did you discover this?

[arsenm]

Move into UpdateAnalysisInformation and add assert

[arsenm]

In D42406#985160, @brzycki wrote:

I too am curious how this managed to not be found for several years. @arsenm how did you discover this?

I'm working on a replacement for StructurizeCFG which needs to insert a block before certain blocks. Sometimes that ends up picking the entry block

[brzycki]

In D42406#985221, @arsenm wrote:

In D42406#985160, @brzycki wrote:

I too am curious how this managed to not be found for several years. @arsenm how did you discover this?

I'm working on a replacement for StructurizeCFG which needs to insert a block before certain blocks. Sometimes that ends up picking the entry block

Thanks @arsenm for the explanation. I was curious to know if you found this with a specific .c/.cpp file or if it was from changing the middle-end. The latter makes a lot more sense to discover a latent bug like this.

LGTM.

[kuhar]

lib/Transforms/Utils/BasicBlockUtils.cpp

324

Can you also add a comment explaining why we need this special case here? I think the reason is that DT.splitBlock expects NewBB to have a non-empty set of predecessors.

327

Without the patch, was the crash happening inside Split in GenericDomTree.h? If it doesn't support it, maybe it would make sense to assert in DT->split that NewBB != getRootNode() for (forward) dominators?

[arsenm]

In D42406#985160, @brzycki wrote:

I too am curious how this managed to not be found for several years. @arsenm how did you discover this?

I'm working on a replacement for StructurizeCFG which needs to insert a block before certain blocks. Sometimes that ends up picking the entry block

lib/Transforms/Utils/BasicBlockUtils.cpp

327

It was hitting
Assertion failed: (!PredBlocks.empty() && "No predblocks?"), function Split, file ../include/llvm/Support/GenericDomTree.h, line 808.

[arsenm]

r323928

lib/Transforms/Utils/BasicBlockUtils.cpp

 }
 
 /// Update DominatorTree, LoopInfo, and LCCSA analysis information.
 static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB,
                                       ArrayRef<BasicBlock *> Preds,
                                       DominatorTree *DT, LoopInfo *LI,
                                       bool PreserveLCSSA, bool &HasLoopExit) {
   // Update dominator tree if available.
-  if (DT)
+  if (DT) {
+    if (OldBB == DT->getRootNode()->getBlock()) {
+      assert(NewBB == &NewBB->getParent()->getEntryBlock());
+      DT->setNewRoot(NewBB);
+    } else
       DT->splitBlock(NewBB);
+  }
 
   // The rest of the logic is only relevant for updating the loop structures.
   if (!LI)
     return;
 
   assert(DT && "DT should be available to update LoopInfo!");
   Loop *L = LI->getLoopFor(OldBB);
 
BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB,
   // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI
   // node becomes an incoming value for BB's phi node.  However, if the Preds
   // list is empty, we need to insert dummy entries into the PHI nodes in BB to
   // account for the newly created predecessor.
   if (Preds.empty()) {
     // Insert dummy values as the incoming value.
     for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I)
       cast<PHINode>(I)->addIncoming(UndefValue::get(I->getType()), NewBB);
-    return NewBB;
   }
 
   // Update DominatorTree, LoopInfo, and LCCSA analysis information.
   bool HasLoopExit = false;
   UpdateAnalysisInformation(BB, NewBB, Preds, DT, LI, PreserveLCSSA,
                             HasLoopExit);
 
+  if (!Preds.empty()) {
     // Update the PHI nodes in BB with the values coming from NewBB.
     UpdatePHINodes(BB, NewBB, Preds, BI, HasLoopExit);
+  }
+
   return NewBB;
 }
 
 void llvm::SplitLandingPadPredecessors(BasicBlock *OrigBB,
                                        ArrayRef<BasicBlock *> Preds,
                                        const char *Suffix1, const char *Suffix2,
                                        SmallVectorImpl<BasicBlock *> &NewBBs,
                                        DominatorTree *DT, LoopInfo *LI,

unittests/Transforms/Utils/BasicBlockUtils.cpp

+//===- BasicBlockUtils.cpp - Unit tests for BasicBlockUtils ---------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/AsmParser/Parser.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/Support/SourceMgr.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {
+  SMDiagnostic Err;
+  std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);
+  if (!Mod)
+    Err.print("BasicBlockUtilsTests", errs());
+  return Mod;
+}
+
+TEST(BasicBlockUtils, SplitBlockPredecessors) {
+  LLVMContext C;
+
+  std::unique_ptr<Module> M = parseIR(
+    C,
+    "define i32 @basic_func(i1 %cond) {\n"
+    "entry:\n"
+    "  br i1 %cond, label %bb0, label %bb1\n"
+    "bb0:\n"
+    "  br label %bb1\n"
+    "bb1:\n"
+    "  %phi = phi i32 [ 0, %entry ], [ 1, %bb0 ]"
+    "  ret i32 %phi\n"
+    "}\n"
+    "\n"
+    );
+
+  auto *F = M->getFunction("basic_func");
+  DominatorTree DT(*F);
+
+  // Make sure the dominator tree is properly updated if calling this on the
+  // entry block.
+  SplitBlockPredecessors(&F->getEntryBlock(), {}, "split.entry", &DT);
+  EXPECT_TRUE(DT.verify());
+}

unittests/Transforms/Utils/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Analysis
   AsmParser
   Core
   Support
   TransformUtils
   )
 
 add_llvm_unittest(UtilsTests
   ASanStackFrameLayoutTest.cpp
+  BasicBlockUtils.cpp
   Cloning.cpp
   CodeExtractor.cpp
   FunctionComparator.cpp
   IntegerDivision.cpp
   Local.cpp
   OrderedInstructions.cpp
   ValueMapperTest.cpp
   )

unittests/Transforms/Utils/Local.cpp

TEST(Local, RemoveDuplicatePHINodes) {
   BranchInst::Create(BB, BB);
 
   // Verify that we can eliminate PHIs that become duplicates after chaning PHIs
   // downstream.
   EXPECT_TRUE(EliminateDuplicatePHINodes(BB));
   EXPECT_EQ(3U, BB->size());
 }
 
-std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {
+static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {
   SMDiagnostic Err;
   std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);
   if (!Mod)
     Err.print("UtilsTests", errs());
   return Mod;
 }
 
 TEST(Local, ReplaceDbgDeclare) {