InstCombine: don't assume malloc will never return nullptr

[t.p.northover]

Summary

We've got some code that tries to eliminate unused allocations by inspecting their uses. Unfortunately one of the uses it checks is an icmp, where the code currently assumes that an allocation will never return nullptr. This isn't correct. Most obviously out of memory errors are signalled by nullptr on many systems, but even when the kernel is willing to oversubscribe physical RAM malloc will return nullptr for a large enough single request.

In fact, I believe only certain variants of the C++ operator new never return nullptr (because they throw in error cases). So this patch limits that particular icmp check to the cases where the allocation function is known to be safe.

[efriedma]

I don't think any of your testcases actually indicate a bug.

Yes, the compiler isn't allowed to assume the libc implementation of malloc doesn't return null, but that's not what's happening here. Instead, we're substituting in our own implementation of malloc, and we can make additional guarantees about that implementation. (This is similar to https://reviews.llvm.org/D53362 , except we don't actually allocate any memory because we prove the allocation is dead.)

[t.p.northover]

Interesting; I (obviously) hadn't considered that interpretation of what's going on, or I'd have mentioned it. I think it just about holds water, so thanks for setting me straight!

[efriedma]

It might be worth adding a comment to the code to make this more clear.

[t.p.northover]

Good idea. I committed a comment in r347653.

llvm/include/llvm/Analysis/MemoryBuiltins.h

 bool isMallocOrCallocLikeFn(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 (either malloc, calloc, or strdup like).
 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.
 //
 
 /// extractMallocCall - Returns the corresponding CallInst if the instruction
 /// is a malloc call.  Since CallInst::CreateMalloc() only creates calls, we
 /// ignore InvokeInst here.
 const CallInst *extractMallocCall(const Value *I, const TargetLibraryInfo *TLI);

llvm/lib/Analysis/MemoryBuiltins.cpp

 
 /// Tests if a value is a call or invoke to a library function that
 /// allocates memory (either malloc, calloc, or strdup like).
 bool llvm::isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
                          bool LookThroughBitCast) {
   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.
 const CallInst *llvm::extractMallocCall(const Value *I,
                                         const TargetLibraryInfo *TLI) {
   return isMallocLikeFn(I, TLI) ? dyn_cast<CallInst>(I) : nullptr;
 }
 

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

if (!GEP.isInBounds()) {
     }
   }
 
   return nullptr;
 }
 
 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))
     return isa<GlobalVariable>(LI->getPointerOperand());
   // Two distinct allocations will never be equal.
   // We rely on LookThroughBitCast in isAllocLikeFn being false, since looking
   // through bitcasts of V can cause
   // the result statement below to be true, even when AI and V (ex:

llvm/test/Transforms/InstCombine/badmalloc.ll

 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128"
 target triple = "x86_64-apple-darwin10.0"
 
 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(
 ; CHECK: ret i1 false
 }
 
 ; CHECK-LABEL: @test2(
 define noalias i8* @test2() nounwind {

llvm/test/Transforms/InstCombine/compare-unescaped.ll

 ; RUN: opt -instcombine -S < %s | FileCheck %s
 
 @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
   ret i1 %cmp
 ; CHECK-LABEL: compare_global_trivialeq
 ; CHECK: ret i1 false
 }
 
 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
   ret i1 %cmp
 ; CHECK-LABEL: compare_global_trivialne
 ; CHECK: ret i1 true
 }
 

 escape_call:
  call void @escape(i8* %m)
  ret i1 true
 
 just_return:
  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
 }
 
 ; the compare is folded to true since the folding compare looks through bitcasts. 
 ; call to malloc and the bitcast instructions are elided after that since there are no uses of the malloc 
 define i1 @compare_samepointer_under_bitcast() {
   %m = call i8* @malloc(i64 4)
   %bc = bitcast i8* %m to i32*

 ; CHECK-LABEL: compare_ret_escape
 ; CHECK: %cmp = icmp eq i8* %n, %c
 ; CHECK: %cmp2 = icmp eq i32* %lgp, %bc
 }
 
 ; 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
 }
 
 !0 = !{}

llvm/test/Transforms/InstCombine/malloc-free-delete.ll

; CHECK-LABEL: @main(
     ret i32 0
 ; CHECK-NEXT: ret i32 0
 }
 
 declare noalias i8* @calloc(i32, i32) nounwind
 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)
 declare void @llvm.memcpy.p0i8.p0i8.i32(i8* nocapture, i8* nocapture, i32, i1) nounwind
 declare void @llvm.memmove.p0i8.p0i8.i32(i8* nocapture, i8* nocapture, i32, i1) nounwind
 declare void @llvm.memset.p0i8.i32(i8*, i8, i32, i1) nounwind
 
 define void @test3(i8* %src) {

llvm/test/Transforms/InstCombine/malloc-new.ll

+; 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
+}