Index: llvm/include/llvm/Analysis/MemoryBuiltins.h
===================================================================
--- llvm/include/llvm/Analysis/MemoryBuiltins.h
+++ llvm/include/llvm/Analysis/MemoryBuiltins.h
@@ -84,6 +84,11 @@
 bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
                    bool LookThroughBitCast = false);
 
+/// Tests if a value is a call or invoke to a library function that allocates
+/// memory but never returns null (like the standard operator new).
+bool isOpNewLikeFn(const Value *V, const TargetLibraryInfo *TLI,
+                   bool LookThroughBitCast = false);
+
 //===----------------------------------------------------------------------===//
 //  malloc Call Utility Functions.
 //
Index: llvm/lib/Analysis/MemoryBuiltins.cpp
===================================================================
--- llvm/lib/Analysis/MemoryBuiltins.cpp
+++ llvm/lib/Analysis/MemoryBuiltins.cpp
@@ -264,6 +264,11 @@
   return getAllocationData(V, AllocLike, TLI, LookThroughBitCast).hasValue();
 }
 
+bool llvm::isOpNewLikeFn(const Value *V, const TargetLibraryInfo *TLI,
+                         bool LookThroughBitCast) {
+  return getAllocationData(V, OpNewLike, TLI, LookThroughBitCast).hasValue();
+}
+
 /// extractMallocCall - Returns the corresponding CallInst if the instruction
 /// is a malloc call.  Since CallInst::CreateMalloc() only creates calls, we
 /// ignore InvokeInst here.
Index: llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
===================================================================
--- llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
+++ llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
@@ -2150,6 +2150,12 @@
 
 static bool isNeverEqualToUnescapedAlloc(Value *V, const TargetLibraryInfo *TLI,
                                          Instruction *AI) {
+  // Most allocation functions can return nullptr (even in systems which
+  // oversubscribe memory, given a large enough request). That would break all
+  // other invariants this function checks for so bail early.
+  if (!isOpNewLikeFn(AI, TLI))
+    return false;
+
   if (isa<ConstantPointerNull>(V))
     return true;
   if (auto *LI = dyn_cast<LoadInst>(V))
Index: llvm/test/Transforms/InstCombine/badmalloc.ll
===================================================================
--- llvm/test/Transforms/InstCombine/badmalloc.ll
+++ llvm/test/Transforms/InstCombine/badmalloc.ll
@@ -5,14 +5,16 @@
 
 declare noalias i8* @malloc(i64) nounwind
 declare void @free(i8*)
+declare noalias i8* @_Znwm(i64) nounwind
+declare void @_ZdlPv(i8*)
 
 ; PR5130
 define i1 @test1() {
-  %A = call noalias i8* @malloc(i64 4) nounwind
+  %A = call noalias i8* @_Znwm(i64 4) nounwind
   %B = icmp eq i8* %A, null
   store i8 0, i8* %A
 
-  call void @free(i8* %A)
+  call void @_ZdlPv(i8* %A)
   ret i1 %B
 
 ; CHECK-LABEL: @test1(
Index: llvm/test/Transforms/InstCombine/compare-unescaped.ll
===================================================================
--- llvm/test/Transforms/InstCombine/compare-unescaped.ll
+++ llvm/test/Transforms/InstCombine/compare-unescaped.ll
@@ -3,9 +3,10 @@
 @gp = global i32* null, align 8
 
 declare i8* @malloc(i64) #1
+declare i8* @_Znwm(i64) #1
 
 define i1 @compare_global_trivialeq() {
-  %m = call i8* @malloc(i64 4)
+  %m = call i8* @_Znwm(i64 4)
   %bc = bitcast i8* %m to i32*
   %lgp = load i32*, i32** @gp, align 8
   %cmp = icmp eq i32* %bc, %lgp
@@ -15,7 +16,7 @@
 }
 
 define i1 @compare_global_trivialne() {
-  %m = call i8* @malloc(i64 4)
+  %m = call i8* @_Znwm(i64 4)
   %bc = bitcast i8* %m to i32*
   %lgp = load i32*, i32** @gp, align 8
   %cmp = icmp ne i32* %bc, %lgp
@@ -83,12 +84,12 @@
  ret i1 %cmp
 }
 
-define i1 @compare_distinct_mallocs() {
-  %m = call i8* @malloc(i64 4)
-  %n = call i8* @malloc(i64 4)
+define i1 @compare_distinct_news() {
+  %m = call i8* @_Znwm(i64 4)
+  %n = call i8* @_Znwm(i64 4)
   %cmp = icmp eq i8* %m, %n
   ret i1 %cmp
-  ; CHECK-LABEL: compare_distinct_mallocs
+  ; CHECK-LABEL: compare_distinct_news
   ; CHECK: ret i1 false
 }
 
@@ -150,13 +151,13 @@
 ; The malloc call for %m cannot be elided since it is used in the call to function f.
 ; However, the cmp can be folded to true as %n doesnt escape and %m, %n are distinct allocations
 define i1 @compare_distinct_pointer_escape() {
-  %m = call i8* @malloc(i64 4)
-  %n = call i8* @malloc(i64 4)
+  %m = call i8* @_Znwm(i64 4)
+  %n = call i8* @_Znwm(i64 4)
   tail call void @f() [ "deopt"(i8* %m) ]
   %cmp = icmp ne i8* %m, %n
   ret i1 %cmp
 ; CHECK-LABEL: compare_distinct_pointer_escape
-; CHECK-NEXT: %m = call i8* @malloc(i64 4)
+; CHECK-NEXT: %m = call i8* @_Znwm(i64 4)
 ; CHECK-NEXT: tail call void @f() [ "deopt"(i8* %m) ]
 ; CHECK-NEXT: ret i1 true
 }
Index: llvm/test/Transforms/InstCombine/malloc-free-delete.ll
===================================================================
--- llvm/test/Transforms/InstCombine/malloc-free-delete.ll
+++ llvm/test/Transforms/InstCombine/malloc-free-delete.ll
@@ -15,15 +15,6 @@
 declare noalias i8* @malloc(i32)
 declare void @free(i8*)
 
-define i1 @foo() {
-; CHECK-LABEL: @foo(
-; CHECK-NEXT: ret i1 false
-  %m = call i8* @malloc(i32 1)
-  %z = icmp eq i8* %m, null
-  call void @free(i8* %m)
-  ret i1 %z
-}
-
 declare void @llvm.lifetime.start.p0i8(i64, i8*)
 declare void @llvm.lifetime.end.p0i8(i64, i8*)
 declare i64 @llvm.objectsize.i64(i8*, i1)
Index: llvm/test/Transforms/InstCombine/malloc-new.ll
===================================================================
--- /dev/null
+++ llvm/test/Transforms/InstCombine/malloc-new.ll
@@ -0,0 +1,67 @@
+; RUN: opt -instcombine -S %s | FileCheck %s
+
+declare i8* @_Znwm(i64)
+declare void @_ZdlPv(i8*)
+
+define i1 @elide_new() {
+; CHECK-LABEL: @elide_new(
+; CHECK-NEXT: ret i1 false
+  %m = call i8* @_Znwm(i64 1)
+  %z = icmp eq i8* %m, null
+  call void @_ZdlPv(i8* %m)
+  ret i1 %z
+}
+
+declare i8* @malloc(i64)
+declare void @free(i8*)
+
+define i1 @keep_malloc() {
+; CHECK-LABEL: @keep_malloc()
+; CHECK: ret i1 %z
+  %m = call i8* @malloc(i64 1)
+  %z = icmp eq i8* %m, null
+  call void @free(i8* %m)
+  ret i1 %z
+}
+
+declare i8* @_ZnwmRKSt9nothrow_t(i64)
+
+define i1 @keep_new_nothrow() {
+; CHECK-LABEL: @keep_new_nothrow()
+; CHECK: ret i1 %z
+  %m = call i8* @_ZnwmRKSt9nothrow_t(i64 1)
+  %z = icmp eq i8* %m, null
+  call void @_ZdlPv(i8* %m)
+  ret i1 %z
+}
+
+declare i8* @strdup(i8*)
+
+define i1 @keep_strdup(i8* %str) {
+; CHECK-LABEL: @keep_strdup(i8* %str)
+; CHECK: ret i1 %z
+  %m = call i8* @strdup(i8* %str)
+  %z = icmp eq i8* %m, null
+  call void @_ZdlPv(i8* %m)
+  ret i1 %z
+}
+
+define i1 @keep_two_mallocs() {
+; CHECK-LABEL: @keep_two_mallocs()
+; CHECK: ret i1 %tst
+  %a = call i8* @malloc(i64 1)
+  %b = call i8* @malloc(i64 1)
+  %tst = icmp eq i8* %a, %b
+  ret i1 %tst
+}
+
+@var = global i8* zeroinitializer
+
+define i1 @keep_malloc_glob() {
+; CHECK-LABEL: @keep_malloc_glob()
+; CHECK: ret i1 %tst
+  %a = call i8* @malloc(i64 1)
+  %b = load i8*, i8** @var
+  %tst = icmp eq i8* %a, %b
+  ret i1 %tst
+}