PR34581: Don't remove an 'if (p)' guarding a call to 'operator delete(p)' under -Oz.

[rsmith]

Summary

This transformation is correct for a builtin call to 'free(p)', but not
for 'operator delete(p)'. There is no guarantee that a user replacement
'operator delete' has no effect when called on a null pointer.

However, the principle behind the transformation *is* correct, and can
be applied more broadly: a 'delete p' expression is permitted to
unconditionally call 'operator delete(p)'. So do that in Clang under
-Oz where possible. We do this whether or not 'p' has trivial
destruction, since the destruction might turn out to be trivial after
inlining, and even for a class-specific (but non-virtual,
non-destroying, non-array) 'operator delete'.

[rjmccall]

Is it reasonable to figure out ahead of time that we can skip the null check completely? It'd be kindof nice to also take advantage of this at -O0 whenever we don't have real work to do.

[dnsampaio]

I believe we can avoid creating some blocks for latter removing them, no?

clang/lib/CodeGen/CGExprCXX.cpp

2049–2062

Unless I missed something, isn't it better to just avoid emitting this check and basic blocks all together if we are optimizing for size and when we know that Ptr is never null?
I would consider in doing something alike:

const bool emitNullCheck = CGM.getCodeGenOpts().OptimizeSize <= 1;
llvm::BasicBlock *DeleteNotNull;
llvm::BasicBlock *DeleteEnd;
if (emitNullCheck){
  // Null check the pointer.
  DeleteNotNull = createBasicBlock("delete.notnull");
  DeleteEnd = createBasicBlock("delete.end");

  llvm::Value *IsNull = Builder.CreateIsNull(Ptr.getPointer(), "isnull");

  Builder.CreateCondBr(IsNull, DeleteEnd, DeleteNotNull);
  EmitBlock(DeleteNotNull);
}

and we use the same emitNullCheck to avoid EmitBlocks below.

2103–2104

If avoiding the emission above it would not require changing EmitObjectDelete at all.

[rsmith]

In D79378#2019336, @rjmccall wrote:

Is it reasonable to figure out ahead of time that we can skip the null check completely? It'd be kindof nice to also take advantage of this at -O0 whenever we don't have real work to do.

In simple cases, we could get a win at -O0 (deleting an object or array with a trivial (and therefore non-virtual) destructor + non-destroying operator delete + no array cookie). Perhaps in those cases we could sidestep the whole process and just generate a direct call to operator delete. That's a different optimization from the one I'm suggesting here (which in turn is trying to be the non-miscompiling subset of the original LLVM-side optimization), though there's lots of overlap. If we don't care about the -Oz cases where the destructor is non-trivial before optimization but can be removed by the optimizer, then we could do that instead of this change. If we decide we care about both situations (removing the branch at -O0 for trivial deletes and removing the branch at -Oz for deletes that optimize into being trivial deletes), then I think we need both something like this *and* that check.

What do you think? I'm somewhat inclined to prefer special-casing deletes that the frontend can see are trivial, rather than making the delete unconditional under -Oz. That means we might see a code size regression in some cases for -Oz, but I suspect that's mostly a theoretical risk.

If we do special-case trivial deletes, should we still insert the branch for them at -O1 and above? In order for that to be profitable, I think the branch would need to be both well-predicted and usually null, which seems like it could happen but is unlikely to be the common case. I suspect the best answer may be to do this regardless of optimization level.

clang/lib/CodeGen/CGExprCXX.cpp

2049–2062

I don't think we can reasonably do this. There are a lot of different ways that delete emission can be performed, and many of them (for example, calling a virtual deleting destructor, destroying operator delete, or array delete with cookie) require the null check to be performed in advance for correctness. It would be brittle to duplicate all of those checks here.

We *could* sink the null checks into the various paths through EmitArrayDelete and EmitObjectDelete, but I think that makes the code significantly more poorly factored.

[dnsampaio]

From my point it does LGTM.

clang/lib/CodeGen/CGExprCXX.cpp

2049–2062

Fair enough.

[rjmccall]

In D79378#2028705, @rsmith wrote:

In D79378#2019336, @rjmccall wrote:

Is it reasonable to figure out ahead of time that we can skip the null check completely? It'd be kindof nice to also take advantage of this at -O0 whenever we don't have real work to do.

In simple cases, we could get a win at -O0 (deleting an object or array with a trivial (and therefore non-virtual) destructor + non-destroying operator delete + no array cookie). Perhaps in those cases we could sidestep the whole process and just generate a direct call to operator delete. That's a different optimization from the one I'm suggesting here (which in turn is trying to be the non-miscompiling subset of the original LLVM-side optimization), though there's lots of overlap. If we don't care about the -Oz cases where the destructor is non-trivial before optimization but can be removed by the optimizer, then we could do that instead of this change. If we decide we care about both situations (removing the branch at -O0 for trivial deletes and removing the branch at -Oz for deletes that optimize into being trivial deletes), then I think we need both something like this *and* that check.

What do you think? I'm somewhat inclined to prefer special-casing deletes that the frontend can see are trivial, rather than making the delete unconditional under -Oz. That means we might see a code size regression in some cases for -Oz, but I suspect that's mostly a theoretical risk.

If we do special-case trivial deletes, should we still insert the branch for them at -O1 and above? In order for that to be profitable, I think the branch would need to be both well-predicted and usually null, which seems like it could happen but is unlikely to be the common case. I suspect the best answer may be to do this regardless of optimization level.

It doesn't have to be *usually* null, just null often enough that it pays for itself. I think that isn't that unlikely given that a lot of deletes are from abstracted locations like destructors.

On balance, I think I'm okay with your current approach, as long as we document our assumption that skipping the check is not usually a performance win. I'm not too worried about the -O0 cost.

[dnsampaio]

LGTM, as far @rjmccall 's concern about documentation is addressed.

[dnsampaio]

Hi @rsmith,
are you still looking into this?
cheers

[rsmith]

In D79378#2058753, @dnsampaio wrote:

Hi @rsmith,
are you still looking into this?
cheers

Sorry for the delay, I'll be getting back to this soon.

[shiva0217]

Hi,

I have a question for the delete function call sinking in -Oz.

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3690.pdf.
According to 3.7.4.2/3
The value of the first argument supplied to a deallocation function may be a null pointer value; if so, and if the deallocation function is one supplied in the standard library, the call has no effect. Otherwise, the behavior is undefined

It seems the null checking can be skipped only when the delete is not from the standard library(have been overloaded by the user), isn't it?

[rjmccall]

In D79378#4101613, @shiva0217 wrote:

Hi,

I have a question for the delete function call sinking in -Oz.

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3690.pdf.
According to 3.7.4.2/3
The value of the first argument supplied to a deallocation function may be a null pointer value; if so, and if the deallocation function is one supplied in the standard library, the call has no effect. Otherwise, the behavior is undefined

It seems the null checking can be skipped only when the delete is not from the standard library(have been overloaded by the user), isn't it?

The paragraph you just quoted says that the deallocation functions provided by the standard library are required have no effect on null pointers. That means it's fine to call them with a null pointer even if the source wouldn't normally execute that call. We could just insert these calls into random other code if we wanted to.

As discussed in the original review, removing null checks around calls to operator delete is rarely going to be a good code-speed optimization, but it is a good code-size optimization, and -Oz in Clang is a request to minimize code size even if it makes the code slower.

[shiva0217]

In D79378#4101829, @rjmccall wrote:

In D79378#4101613, @shiva0217 wrote:

Hi,

I have a question for the delete function call sinking in -Oz.

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3690.pdf.
According to 3.7.4.2/3
The value of the first argument supplied to a deallocation function may be a null pointer value; if so, and if the deallocation function is one supplied in the standard library, the call has no effect. Otherwise, the behavior is undefined

It seems the null checking can be skipped only when the delete is not from the standard library(have been overloaded by the user), isn't it?

The paragraph you just quoted says that the deallocation functions provided by the standard library are required have no effect on null pointers. That means it's fine to call them with a null pointer even if the source wouldn't normally execute that call. We could just insert these calls into random other code if we wanted to.

Is a null operand of delete in the source code no effect because there will be null pointer checking generated? Or the delete(null) in assembly code also valid?

As discussed in the original review, removing null checks around calls to operator delete is rarely going to be a good code-speed optimization, but it is a good code-size optimization, and -Oz in Clang is a request to minimize code size even if it makes the code slower.

[rjmccall]

In D79378#4101935, @shiva0217 wrote:

In D79378#4101829, @rjmccall wrote:

In D79378#4101613, @shiva0217 wrote:

Hi,

I have a question for the delete function call sinking in -Oz.

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3690.pdf.
According to 3.7.4.2/3
The value of the first argument supplied to a deallocation function may be a null pointer value; if so, and if the deallocation function is one supplied in the standard library, the call has no effect. Otherwise, the behavior is undefined

It seems the null checking can be skipped only when the delete is not from the standard library(have been overloaded by the user), isn't it?

The paragraph you just quoted says that the deallocation functions provided by the standard library are required have no effect on null pointers. That means it's fine to call them with a null pointer even if the source wouldn't normally execute that call. We could just insert these calls into random other code if we wanted to.

Is a null operand of delete in the source code no effect because there will be null pointer checking generated? Or the delete(null) in assembly code also valid?

In [expr.delete], the standard specifies that using the delete operator on a null pointer is required to have no effect. It does not specify how that should be implemented. In [basic.std.dynamic.deallocation], the standard also specifies that the library-provided operator delete functions must have no effect when given a null pointer. This requirement applies no matter how the function is called, so yes, a call from assembly that passed a null pointer would also be required to have no effect. More officially, you can simply take the address of operator delete, yielding an rvalue of void (*)(void *) (or similar, depending on which operator delete you use), which can then be called later in a context that doesn't understand it's calling a deallocation function; such a call is still required to have no effect when passing a null pointer, because the requirement is laid on the function, separate from the circumstances of it being called as part of the delete operator.

Note also that calling operator delete unconditionally when implementing the delete operator is explicitly blessed by [expr.delete]p7:

If the value of the operand of the delete-expression is not a null pointer value, then:

...

Otherwise, it is unspecified whether the deallocation function will be called.

[shiva0217]

In D79378#4103366, @rjmccall wrote:

In D79378#4101935, @shiva0217 wrote:

In D79378#4101829, @rjmccall wrote:

In D79378#4101613, @shiva0217 wrote:

Hi,

I have a question for the delete function call sinking in -Oz.

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3690.pdf.
According to 3.7.4.2/3
The value of the first argument supplied to a deallocation function may be a null pointer value; if so, and if the deallocation function is one supplied in the standard library, the call has no effect. Otherwise, the behavior is undefined

It seems the null checking can be skipped only when the delete is not from the standard library(have been overloaded by the user), isn't it?

The paragraph you just quoted says that the deallocation functions provided by the standard library are required have no effect on null pointers. That means it's fine to call them with a null pointer even if the source wouldn't normally execute that call. We could just insert these calls into random other code if we wanted to.

Is a null operand of delete in the source code no effect because there will be null pointer checking generated? Or the delete(null) in assembly code also valid?

In [expr.delete], the standard specifies that using the delete operator on a null pointer is required to have no effect. It does not specify how that should be implemented. In [basic.std.dynamic.deallocation], the standard also specifies that the library-provided operator delete functions must have no effect when given a null pointer. This requirement applies no matter how the function is called, so yes, a call from assembly that passed a null pointer would also be required to have no effect. More officially, you can simply take the address of operator delete, yielding an rvalue of void (*)(void *) (or similar, depending on which operator delete you use), which can then be called later in a context that doesn't understand it's calling a deallocation function; such a call is still required to have no effect when passing a null pointer, because the requirement is laid on the function, separate from the circumstances of it being called as part of the delete operator.

Note also that calling operator delete unconditionally when implementing the delete operator is explicitly blessed by [expr.delete]p7:

If the value of the operand of the delete-expression is not a null pointer value, then:

...

Otherwise, it is unspecified whether the deallocation function will be called.

Hi @rjmccall,

That make sense to me.
Thanks for sharing your insight of C++ standard and taking time to answer the questions.
Thank you ^^

clang/lib/CodeGen/CGExprCXX.cpp

static void EmitDestroyingObjectDelete(CodeGenFunction &CGF,
   if (Dtor && Dtor->isVirtual())
     CGF.CGM.getCXXABI().emitVirtualObjectDelete(CGF, DE, Ptr, ElementType,
                                                 Dtor);
   else
     CGF.EmitDeleteCall(DE->getOperatorDelete(), Ptr.getPointer(), ElementType);
 }
 
 /// Emit the code for deleting a single object.
-static void EmitObjectDelete(CodeGenFunction &CGF,
+/// \return \c true if we started emitting UnconditionalDeleteBlock, \c false
+/// if not.
+static bool EmitObjectDelete(CodeGenFunction &CGF,
                              const CXXDeleteExpr *DE,
                              Address Ptr,
-                             QualType ElementType) {
+                             QualType ElementType,
+                             llvm::BasicBlock *UnconditionalDeleteBlock) {
   // C++11 [expr.delete]p3:
   //   If the static type of the object to be deleted is different from its
   //   dynamic type, the static type shall be a base class of the dynamic type
   //   of the object to be deleted and the static type shall have a virtual
   //   destructor or the behavior is undefined.
   CGF.EmitTypeCheck(CodeGenFunction::TCK_MemberCall,
                     DE->getExprLoc(), Ptr.getPointer(),
                     ElementType);
if (RD->hasDefinition() && !RD->hasTrivialDestructor()) {
             // devirtualized to the derived type (the type of the inner
             // expression) as in EmitCXXMemberOrOperatorMemberCallExpr.
             UseVirtualCall = true;
           }
         }
         if (UseVirtualCall) {
           CGF.CGM.getCXXABI().emitVirtualObjectDelete(CGF, DE, Ptr, ElementType,
                                                       Dtor);
-          return;
+          return false;
         }
       }
     }
   }
 
   // Make sure that we call delete even if the dtor throws.
   // This doesn't have to a conditional cleanup because we're going
   // to pop it off in a second.
case Qualifiers::OCL_Strong:
       break;
 
     case Qualifiers::OCL_Weak:
       CGF.EmitARCDestroyWeak(Ptr);
       break;
     }
   }
 
+  // When optimizing for size, call 'operator delete' unconditionally.
+  if (CGF.CGM.getCodeGenOpts().OptimizeSize > 1) {
+    CGF.EmitBlock(UnconditionalDeleteBlock);
+    CGF.PopCleanupBlock();
+    return true;
+  }
+
   CGF.PopCleanupBlock();
+  return false;
 }
 
 namespace {
   /// Calls the given 'operator delete' on an array of objects.
   struct CallArrayDelete final : EHScopeStack::Cleanup {
     llvm::Value *Ptr;
     const FunctionDecl *OperatorDelete;
     llvm::Value *NumElements;
static void EmitArrayDelete(CodeGenFunction &CGF,
   // Pop the cleanup block.
   CGF.PopCleanupBlock();
 }
 
 void CodeGenFunction::EmitCXXDeleteExpr(const CXXDeleteExpr *E) {
   const Expr *Arg = E->getArgument();
   Address Ptr = EmitPointerWithAlignment(Arg);
 
   // Null check the pointer.
+  //
+  // We could avoid this null check if we can determine that the object
+  // destruction is trivial and doesn't require an array cookie; we can
+  // unconditionally perform the operator delete call in that case. For now, we
+  // assume that deleted pointers are null rarely enough that it's better to
+  // keep the branch. This might be worth revisiting for a -O0 code size win.
   llvm::BasicBlock *DeleteNotNull = createBasicBlock("delete.notnull");
   llvm::BasicBlock *DeleteEnd = createBasicBlock("delete.end");
 
   llvm::Value *IsNull = Builder.CreateIsNull(Ptr.getPointer(), "isnull");
 
   Builder.CreateCondBr(IsNull, DeleteEnd, DeleteNotNull);
   EmitBlock(DeleteNotNull);
 
   QualType DeleteTy = E->getDestroyedType();
 
   // A destroying operator delete overrides the entire operation of the
   // delete expression.
   if (E->getOperatorDelete()->isDestroyingOperatorDelete()) {
     EmitDestroyingObjectDelete(*this, E, Ptr, DeleteTy);
     EmitBlock(DeleteEnd);
if (DeleteTy->isConstantArrayType()) {
     Ptr = Address(Builder.CreateInBoundsGEP(Ptr.getPointer(), GEP, "del.first"),
                   Ptr.getAlignment());
   }
 
   assert(ConvertTypeForMem(DeleteTy) == Ptr.getElementType());
 
   if (E->isArrayForm()) {
     EmitArrayDelete(*this, E, Ptr, DeleteTy);
+    EmitBlock(DeleteEnd);
   } else {
-    EmitObjectDelete(*this, E, Ptr, DeleteTy);
-  }
-
+    if (!EmitObjectDelete(*this, E, Ptr, DeleteTy, DeleteEnd))
       EmitBlock(DeleteEnd);
   }
+}
 
 static bool isGLValueFromPointerDeref(const Expr *E) {
   E = E->IgnoreParens();
 
   if (const auto *CE = dyn_cast<CastExpr>(E)) {
     if (!CE->getSubExpr()->isGLValue())
       return false;
     return isGLValueFromPointerDeref(CE->getSubExpr());

clang/test/CodeGenCXX/delete.cpp

-// RUN: %clang_cc1 -triple x86_64-apple-darwin10 %s -emit-llvm -o - | FileCheck %s
+// RUN: %clang_cc1 -triple x86_64-apple-darwin10 %s -emit-llvm -o - | FileCheck %s --check-prefixes=CHECK,CHECK-NOSIZE
+// RUN: %clang_cc1 -triple x86_64-apple-darwin10 %s -emit-llvm -o - -Oz -disable-llvm-passes | FileCheck %s --check-prefixes=CHECK,CHECK-SIZE
 
 void t1(int *a) {
   delete a;
 }
 
 struct S {
   int a;
 };
 
 // POD types.
+
+// CHECK-LABEL: define void @_Z2t3P1S
 void t3(S *s) {
+  // CHECK: icmp {{.*}} null
+  // CHECK: br i1
+
+  // CHECK: bitcast
+  // CHECK-NEXT: call void @_ZdlPv
+
+  // Check the delete is inside the 'if !null' check unless we're optimizing
+  // for size. FIXME: We could omit the branch entirely in this case.
+  // CHECK-NOSIZE-NEXT: br
+  // CHECK-SIZE-NEXT: ret
   delete s;
 }
 
 // Non-POD
 struct T {
   ~T();
   int a;
 };
 
 // CHECK-LABEL: define void @_Z2t4P1T
 void t4(T *t) {
   // CHECK: call void @_ZN1TD1Ev
-  // CHECK-NEXT: bitcast
+  // CHECK-NOSIZE-NEXT: bitcast
+  // CHECK-SIZE-NEXT: br
+  // CHECK-SIZE: bitcast
   // CHECK-NEXT: call void @_ZdlPv
   delete t;
 }
 
 // PR5102
 template <typename T>
 class A {
   public: operator T *() const;
struct A {
     void *operator new(__SIZE_TYPE__ sz);
     void operator delete(void *p) { ::operator delete(p); }
     ~A() {}
   };
 
   // CHECK-LABEL: define void @_ZN5test04testEPNS_1AE(
   void test(A *a) {
     // CHECK: call void @_ZN5test01AD1Ev
-    // CHECK-NEXT: bitcast
+    // CHECK-NOSIZE-NEXT: bitcast
+    // CHECK-SIZE-NEXT: br
+    // CHECK-SIZE: bitcast
     // CHECK-NEXT: call void @_ZN5test01AdlEPv
     delete a;
   }
 
   // CHECK-LABEL: define linkonce_odr void @_ZN5test01AD1Ev(%"struct.test0::A"* %this) unnamed_addr
   // CHECK-LABEL: define linkonce_odr void @_ZN5test01AdlEPv
 }
 

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

if (isa<ConstantPointerNull>(Op))
     return eraseInstFromFunction(FI);
 
   // If we optimize for code size, try to move the call to free before the null
   // test so that simplify cfg can remove the empty block and dead code
   // elimination the branch. I.e., helps to turn something like:
   // if (foo) free(foo);
   // into
   // free(foo);
-  if (MinimizeSize)
+  //
+  // Note that we can only do this for 'free' and not for any flavor of
+  // 'operator delete'; there is no 'operator delete' symbol for which we are
+  // permitted to invent a call, even if we're passing in a null pointer.
+  if (MinimizeSize) {
+    LibFunc Func;
+    if (TLI.getLibFunc(FI, Func) && TLI.has(Func) && Func == LibFunc_free)
       if (Instruction *I = tryToMoveFreeBeforeNullTest(FI, DL))
         return I;
+  }
 
   return nullptr;
 }
 
 static bool isMustTailCall(Value *V) {
   if (auto *CI = dyn_cast<CallInst>(V))
     return CI->isMustTailCall();
   return false;

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

 if.then:                                          ; preds = %entry
   tail call void @free(i8* %foo)
   br label %if.end
 
 if.end:                                           ; preds = %entry, %if.then
   ret void
 }
 
+; Same optimization with even a builtin 'operator delete' would be
+; incorrect in general.
+; 'if (p) delete p;' cannot result in a call to 'operator delete(0)'.
+define void @test6a(i8* %foo) minsize {
+; CHECK-LABEL: @test6a(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i8* [[FOO:%.*]], null
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    tail call void @_ZdlPv(i8* [[FOO]])
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    ret void
+entry:
+  %tobool = icmp eq i8* %foo, null
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  tail call void @_ZdlPv(i8* %foo) builtin
+  br label %if.end
+
+if.end:                                           ; preds = %entry, %if.then
+  ret void
+}
+
 declare i8* @_ZnwmRKSt9nothrow_t(i64, i8*) nobuiltin
 declare void @_ZdlPvRKSt9nothrow_t(i8*, i8*) nobuiltin
 declare i32 @__gxx_personality_v0(...)
 declare void @_ZN1AC2Ev(i8* %this)
 
 define void @test7() personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
 ; CHECK-LABEL: @test7(
 ; CHECK-NEXT:  entry: