diff --git a/llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.h b/llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.h
--- a/llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.h
+++ b/llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.h
@@ -159,7 +159,9 @@
   const SDValue &getSDValue(TableId &Id) {
     RemapId(Id);
     assert(Id && "TableId should be non-zero");
-    return IdToValueMap[Id];
+    auto I = IdToValueMap.find(Id);
+    assert(I != IdToValueMap.end() && "cannot find Id in map");
+    return I->second;
   }
 
 public:
@@ -176,25 +178,30 @@
   bool run();
 
   void NoteDeletion(SDNode *Old, SDNode *New) {
+    assert(Old != New && "node replaced with self");
     for (unsigned i = 0, e = Old->getNumValues(); i != e; ++i) {
       TableId NewId = getTableId(SDValue(New, i));
       TableId OldId = getTableId(SDValue(Old, i));
 
-      if (OldId != NewId)
+      if (OldId != NewId) {
         ReplacedValues[OldId] = NewId;
 
-      // Delete Node from tables.
+        // Delete Node from tables.  We cannot do this when OldId == NewId,
+        // because NewId can still have table references to it in
+        // ReplacedValues.
+        IdToValueMap.erase(OldId);
+        PromotedIntegers.erase(OldId);
+        ExpandedIntegers.erase(OldId);
+        SoftenedFloats.erase(OldId);
+        PromotedFloats.erase(OldId);
+        SoftPromotedHalfs.erase(OldId);
+        ExpandedFloats.erase(OldId);
+        ScalarizedVectors.erase(OldId);
+        SplitVectors.erase(OldId);
+        WidenedVectors.erase(OldId);
+      }
+
       ValueToIdMap.erase(SDValue(Old, i));
-      IdToValueMap.erase(OldId);
-      PromotedIntegers.erase(OldId);
-      ExpandedIntegers.erase(OldId);
-      SoftenedFloats.erase(OldId);
-      PromotedFloats.erase(OldId);
-      SoftPromotedHalfs.erase(OldId);
-      ExpandedFloats.erase(OldId);
-      ScalarizedVectors.erase(OldId);
-      SplitVectors.erase(OldId);
-      WidenedVectors.erase(OldId);
     }
   }
 
diff --git a/llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp b/llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp
--- a/llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp
@@ -178,6 +178,7 @@
     }
   }
 
+#ifndef NDEBUG
   // Checked that NewNodes are only used by other NewNodes.
   for (unsigned i = 0, e = NewNodes.size(); i != e; ++i) {
     SDNode *N = NewNodes[i];
@@ -185,6 +186,11 @@
          UI != UE; ++UI)
       assert(UI->getNodeId() == NewNode && "NewNode used by non-NewNode!");
   }
+
+  // Check that all of the replacements still exist.
+  for (auto const &I : ReplacedValues)
+    assert(IdToValueMap.count(I.second) && "remapped value missing");
+#endif
 }
 
 /// This is the main entry point for the type legalizer. This does a top-down
diff --git a/llvm/test/CodeGen/X86/legalize-types-remapid.ll b/llvm/test/CodeGen/X86/legalize-types-remapid.ll
--- a/llvm/test/CodeGen/X86/legalize-types-remapid.ll
+++ b/llvm/test/CodeGen/X86/legalize-types-remapid.ll
@@ -14,3 +14,18 @@
   store volatile i32 %t0.i0.cast.i1, i32* @c
   ret void
 }
+
+define void @PR45049() local_unnamed_addr {
+so_basic:
+  %a0 = load i1, i1* undef, align 1
+  %a1 = select i1 %a0, i542 4374501449566023848745004454235242730706338861786424872851541212819905998398751846447026354046107648, i542 0 ; constant is: i542 1 << 331
+  %a00 = zext i1 %a0 to i542
+  %a11 = shl i542 %a00, 331
+  %a2 = shl i542 %a00, 330
+  %a4 = or i542 %a1, %a2
+  %a05 = zext i1 %a0 to i488
+  %a55 = shl i488 %a05, 111
+  store i542 %a4, i542* undef, align 8
+  store i488 %a55, i488* undef, align 8
+  ret void
+}