Index: include/llvm/Analysis/CGSCCPassManager.h
===================================================================
--- include/llvm/Analysis/CGSCCPassManager.h
+++ include/llvm/Analysis/CGSCCPassManager.h
@@ -88,6 +88,7 @@
 #ifndef LLVM_ANALYSIS_CGSCCPASSMANAGER_H
 #define LLVM_ANALYSIS_CGSCCPASSMANAGER_H
 
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/PriorityWorklist.h"
 #include "llvm/ADT/STLExtras.h"
@@ -583,10 +584,12 @@
                       SmallVectorImpl<WeakTrackingVH> &CallHandles) {
       assert(CallHandles.empty() && "Must start with a clear set of handles.");
 
-      SmallVector<CallCount, 4> CallCounts;
+      SmallDenseMap<Function *, CallCount> CallCounts;
+      CallCount CountLocal = {0, 0};
       for (LazyCallGraph::Node &N : C) {
-        CallCounts.push_back({0, 0});
-        CallCount &Count = CallCounts.back();
+        CallCount &Count =
+            CallCounts.insert(std::make_pair(&N.getFunction(), CountLocal))
+                .first->second;
         for (Instruction &I : instructions(N.getFunction()))
           if (auto CS = CallSite(&I)) {
             if (CS.getCalledFunction()) {
@@ -626,8 +629,6 @@
       // Check that we didn't miss any update scenario.
       assert(!UR.InvalidatedSCCs.count(C) && "Processing an invalid SCC!");
       assert(C->begin() != C->end() && "Cannot have an empty SCC!");
-      assert((int)CallCounts.size() == C->size() &&
-             "Cannot have changed the size of the SCC!");
 
       // Check whether any of the handles were devirtualized.
       auto IsDevirtualizedHandle = [&](WeakTrackingVH &CallH) {
@@ -642,7 +643,7 @@
         if (!F)
           return false;
 
-        LLVM_DEBUG(dbgs() << "Found devirutalized call from "
+        LLVM_DEBUG(dbgs() << "Found devirtualized call from "
                           << CS.getParent()->getParent()->getName() << " to "
                           << F->getName() << "\n");
 
@@ -664,12 +665,20 @@
       // manner of transformations such as DCE and other things, but seems to
       // work well in practice.
       if (!Devirt)
-        for (int i = 0, Size = C->size(); i < Size; ++i)
-          if (CallCounts[i].Indirect > NewCallCounts[i].Indirect &&
-              CallCounts[i].Direct < NewCallCounts[i].Direct) {
-            Devirt = true;
-            break;
+        // Iterate over the keys in NewCallCounts, if Function also exists in
+        // CallCounts, make the check below.
+        for (auto &Pair : NewCallCounts) {
+          auto &CallCountNew = Pair.second;
+          auto CountIt = CallCounts.find(Pair.first);
+          if (CountIt != CallCounts.end()) {
+            const auto &CallCountOld = CountIt->second;
+            if (CallCountOld.Indirect > CallCountNew.Indirect &&
+                CallCountOld.Direct < CallCountNew.Direct) {
+              Devirt = true;
+              break;
+            }
           }
+        }
 
       if (!Devirt) {
         PA.intersect(std::move(PassPA));
Index: test/Other/new-pm-pr42726-cgscc.ll
===================================================================
--- /dev/null
+++ test/Other/new-pm-pr42726-cgscc.ll
@@ -0,0 +1,56 @@
+; RUN: opt -aa-pipeline=default -passes="default<O1>" %s -S | FileCheck %s
+
+declare void @bar()
+declare void @baz(i32*)
+
+; CHECK-LABEL: @foo1()
+define void @foo1() {
+entry:
+  %tag = alloca i32, align 4
+  call void @baz(i32* %tag)
+  %tmp = load i32, i32* %tag, align 4
+  switch i32 %tmp, label %sw.bb799 [
+    i32 10, label %sw.bb239
+  ]
+
+sw.bb239:
+  call void @foo2()
+  br label %cleanup871
+
+sw.bb799:
+  call void @foo3(i32 undef)
+  br label %cleanup871
+
+cleanup871:
+  call void @bar()
+  unreachable
+}
+
+define void @foo2() {
+  call void @foo4()
+  unreachable
+}
+
+define void @foo3(i32 %ptr) {
+  call void @foo1()
+  unreachable
+}
+
+define void @foo4() {
+entry:
+  %tag = alloca i32, align 4
+  call void @baz(i32* %tag)
+  %tmp = load i32, i32* %tag, align 4
+  switch i32 %tmp, label %sw.bb442 [
+    i32 16, label %sw.bb352
+  ]
+
+sw.bb352:
+  call void @foo3(i32 undef)
+  unreachable
+
+sw.bb442:
+  call void @foo2()
+  unreachable
+}
+