Index: include/llvm/Support/GenericDomTree.h
===================================================================
--- include/llvm/Support/GenericDomTree.h
+++ include/llvm/Support/GenericDomTree.h
@@ -571,16 +571,37 @@
   // API to update (Post)DominatorTree information based on modifications to
   // the CFG...
 
-  /// addNewBlock - Add a new node to the dominator tree information.  This
-  /// creates a new node as a child of DomBB dominator node,linking it into
-  /// the children list of the immediate dominator.
+  /// Add a new node to the dominator tree information.
+  ///
+  /// This creates a new node as a child of DomBB dominator node, linking it
+  /// into the children list of the immediate dominator.
+  ///
+  /// \param BB New node in CFG.
+  /// \param DomBB CFG node that is dominator for BB, nullptr if the new CFG
+  ///              node becomes a new root.
+  /// \returns New dominator tree node that represents new CFG node.
+  ///
   DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
     assert(getNode(BB) == nullptr && "Block already in dominator tree!");
-    DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
-    assert(IDomNode && "Not immediate dominator specified for block!");
     DFSInfoValid = false;
-    return (DomTreeNodes[BB] = IDomNode->addChild(
+    if (DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB)) {
+      return (DomTreeNodes[BB] = IDomNode->addChild(
                 llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get();
+    }
+    // The new node becomes a tree root.
+    auto &Roots = DominatorBase<NodeT>::Roots;
+    DomTreeNodeBase<NodeT> *NewNode = (DomTreeNodes[BB] =
+                  llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, nullptr)).get();
+    if (Roots.empty()) {
+      addRoot(BB);
+    } else {
+      assert(Roots.size() == 1);
+      NodeT *OldRoot = Roots.front();
+      DomTreeNodes[OldRoot] =
+          NewNode->addChild(std::move(DomTreeNodes[OldRoot]));
+      Roots[0] = BB;
+    }
+    return RootNode = NewNode;
   }
 
   /// changeImmediateDominator - This method is used to update the dominator
Index: lib/Transforms/Scalar/StructurizeCFG.cpp
===================================================================
--- lib/Transforms/Scalar/StructurizeCFG.cpp
+++ lib/Transforms/Scalar/StructurizeCFG.cpp
@@ -792,6 +792,7 @@
                          LoopFunc,
                          LoopStart);
     BranchInst::Create(LoopStart, NewEntry);
+    DT->addNewBlock(NewEntry, nullptr);
   }
 
   // Create an extra loop end node
Index: test/Transforms/StructurizeCFG/no-branch-to-entry.ll
===================================================================
--- test/Transforms/StructurizeCFG/no-branch-to-entry.ll
+++ test/Transforms/StructurizeCFG/no-branch-to-entry.ll
@@ -1,4 +1,4 @@
-; RUN: opt -S -o - -structurizecfg < %s | FileCheck %s
+; RUN: opt -S -o - -structurizecfg -verify-dom-info < %s | FileCheck %s
 
 ; CHECK-LABEL: @no_branch_to_entry_undef(
 ; CHECK: entry: