Omit nullptr check for sufficiently simple delete-expressions

[ahh]

Summary

[expr.delete] is pretty crystal clear that it's OK to invoke a
deallocation-function on a nullptr delete-expression:

"If the value of the operand of the delete-expression is a null
pointer value, it is unspecified whether a deallocation function will
be called as described above."

Even so, we currently check against nullptr unconditionally. This is
wasteful for anything with a trivial destructor; deleting nullptr is
very rare so it's not worth saving the call to ::operator delete, and
this is a useless branch (and waste of code size) in the common case.

Condition emission of the branch on us needing to actually look
through the pointer for a vtable, size cookie, or nontrivial
destructor. (In principle a nontrivial destructor with no side
effects that didn't touch the object would also be safe to run
unconditionally, but I don't know how to test we have one of those and
who in the world would write one?)

On an important and very large (~500 MiB) Google search binary, this
saves approximately 32 KiB of text. Okay, it's not impressive in a
relative sense, but it's still the right thing to do.

A note on optimization: we still successfully elide delete-expressions of
(literal) nullptr. Where before they were stuck behind a never-taken branch,
now they reduce (effectively) to calls to __builtin_operator_delete(nullptr),
which EarlyCSE is capable of optimizing out. So this has no cost in the
already well-optimized case.

[ahh]

On my workstation's checkout of head, one test fails (Clang :: Driver/response-file.c) both with and without this change; everything else appears to pass.

I believe that between the tests I add to delete.cpp and the ones that are already there (and destroying-delete.cpp) we cover every case that has to get a nullptr check, and pretty much every one that should *not*.

Name of the helper function is, uh, good enough for me, but no objections to changing it.

[kimgr]

Peanut gallery observation: there was a discussion on the Boost list years and years ago where someone made the case that if (x != nullptr) delete x; was measurably faster than just calling delete x; I can't find it now, but I think it might have been in the context of their checked_delete library. Anyway, the reasoning was that with an external nullptr check, you'd pay for one comparison, but without it you'd always pay for a jump + a comparison. I suppose that only holds true for null pointers, for non-null pointers the extra check is just waste.

It looks to me like the compiler inserts an external null check, and you're now removing it in select cases, did I understand that right? I wonder if this could have negative effects for frequent deletion of nullptrs (e.g. a sometimes-allocated member of a heavily used value type).

That said, I'm not sure how valid the observation back then still is.

[rsmith]

In D43430#1011269, @kimgr wrote:

I wonder if this could have negative effects for frequent deletion of nullptrs (e.g. a sometimes-allocated member of a heavily used value type).

For that to be better, I think we'd need one of two things to happen:

1. The compiler can statically detect that the pointer is null, and remove the call to operator delete and potentially other code too. (This happens, eg, when inlining vector::push_back on an empty vector.)
2. The condition cannot be determined statically, but dynamically it turns out that the pointer is very frequently null, so that the cost of the extra checks in the non-null case are cheaper than the cost of the function call in the null case.

For case 1, the optimizer already knows that it can remove calls to usual operator delete functions on a null pointer, so that optimization should not be inhibited by this change.

For case 2, it seems to me that our default assumption should probably be that most deleted pointers are not null. But I don't have measurements to back that up. If the user knows that their pointers are usually null, they can express that knowledge with an if, but if we always generate the branch on null here, then there would be no easy way for the programmer to express their intent that the pointer is usually not null.

lib/CodeGen/CGExprCXX.cpp

1977–1978

Reindent.

[rsmith]

LGTM, but I'd also like @rjmccall's opinion.

[ahh]

Fix indentation

[rjmccall]

Discourse nitpick: I would encourage you to just use the ordinary phrase "null pointer", or just "null", when referring to a pointer value that happens to be null and to reserve "nullptr" for *statically* null pointers, especially the nullptr expression.

If the pointer is not null, the runtime overhead of the null check is pretty negligible next to the cost of actually doing the allocation. If the pointer is null, the runtime overhead of making at least one unnecessary call — probably two, if 'operator delete' doesn't do its own null check before calling 'free', and probably one that crosses image boundaries — is not negligible at all. So the relative impact on code that does end up destroying a trivial value is outsized.

On the other hand, if the programmer adds an explicit null-check, it's unlikely to be optimized away; that means that if we did this automatically, there would still be an avenue for them to get the null check back.

The code-size argument against doing the null check seems strong, however. Have you considered just doing this in the code-size-sensitive modes, in particular -Os/-Oz (for obvious reasons) and -O0 (because less code size == faster compiles, especially when it involves control flow)?

[ahh]

If the pointer is not null, the runtime overhead of the null check is pretty negligible next to the cost of actually doing the allocation. If the pointer is null, the runtime overhead of making at least one unnecessary call — probably two, if 'operator delete' doesn't do its own null check before calling 'free', and probably one that crosses image boundaries — is not negligible at all. So the relative impact on code that does end up destroying a trivial value is outsized.

In a reply of mine that I think got eaten by list moderation, I looked into this and benchmarked the cost of ::operator delete; with our tcmalloc, the cost of deleting null is about 8 cycles (compared to an empty loop.) (I don't really know how to benchmark the version with an if around it, but if we assume that's free, 8 cycles is still very cheap.)

I suppose this might go up somewhat in an environment where we have to make some sort of PLT call or even two. My Google centric response is "don't do that"--linking directly against any modern malloc should avoid any jump in ::operator delete and our environment make direct calls quite fast; I'm not sure how generalizable that is. (The linking is I think universally good advice; I'm not sure who runs in an environment that cannot make efficient far calls. But point is that: while your statement is true, the penalty for getting this wrong seems very small, and as you say any programmer can if around it at a "hot" null delete, no?

This is one of the few aspects of malloc calls that I don't have near-infinite telemetry for (our sampling architecture doesn't easily collect it.) So I cannot give you a hard number of the fraction of deletes that are of null pointers, but I am convinced that is very small. Would more (Google-internal, obviously) data on this make a decision easier?

I could see why maybe this could be gated on -Os, but I didn't do this for two reasons:

• I am new at Clang development and wasn't sure how to put that sort of a check in :) Though I can learn if this is a hard requirement.
• From our perspective, I think Google would want this flag in non-size optimization (-O2 or whatever.) We delete null infrequently enough that I'd expect this to be a pure cycle win (if a very small one) and even though (because?) we don't optimize for size, we have a number of very large binaries, and reducing icache hit can help a lot.

I'm unsure exactly how to make progress here, since for one thing I'm unsure how strongly you feel about the potential cost/benefits. Guidance would be greatly appreciated!

[rjmccall]

That is an extremely Google-specific analysis, actually; AFAIK almost nobody else uses static linking all the way down to and including the C and C++ standard libraries unless they're literally building an executable for a fully-static environment, like the kernel. The C and C++ language standards state that operator delete and free are independently overridable by just defining those functions outside the stdlib, so they generally cannot be resolved as direct calls without the sort of whole-program analysis that the linker can only do when linking the final executable.

I think a more reasonable benchmark would be to build a standard Linux executable that dynamically links libc and lib{std,}c++, or perhaps something with the ADK or Darwin.

I'm quite open to the idea that the right thing to do is just to do this in all modes, but I do think we should understand the cost a little better. (Xcode defaults release builds to -Os, so in practice my proposal of "-Os or -O0" or would enable this by default for almost all builds for us at Apple.)

You can check for -Os by just checking getCodeGenOpts().OptimizeSize.

It should be quite easy to collect null-deletion counts by (1) enabling your patch and (2) writing an operator delete that counts nulls before calling free and reports that count in a global destructor. Then you just need to pick a C++-heavy program to count them in. :) Clang compiling 403.gcc isn't an unreasonable choice, although LLVM's use of allocation pools does mean that we're likely to have fewer delete calls than you might think.

lib/CodeGen/CGCXXABI.h

protected:
 
   /// Loads the incoming C++ this pointer as it was passed by the caller.
   llvm::Value *loadIncomingCXXThis(CodeGenFunction &CGF);
 
   void setCXXABIThisValue(CodeGenFunction &CGF, llvm::Value *ThisPtr);
 
   ASTContext &getContext() const { return CGM.getContext(); }
 
-  virtual bool requiresArrayCookie(const CXXDeleteExpr *E, QualType eltType);
-  virtual bool requiresArrayCookie(const CXXNewExpr *E);
+
 
   /// Determine whether there's something special about the rules of
   /// the ABI tell us that 'this' is a complete object within the
   /// given function.  Obvious common logic like being defined on a
   /// final class will have been taken care of by the caller.
   virtual bool isThisCompleteObject(GlobalDecl GD) const = 0;
 
 public:
public:
   /// Gets the pure virtual member call function.
   virtual StringRef GetPureVirtualCallName() = 0;
 
   /// Gets the deleted virtual member call name.
   virtual StringRef GetDeletedVirtualCallName() = 0;
 
   /**************************** Array cookies ******************************/
 
+  virtual bool requiresArrayCookie(const CXXDeleteExpr *E, QualType eltType);
+  virtual bool requiresArrayCookie(const CXXNewExpr *E);
+
   /// Returns the extra size required in order to store the array
   /// cookie for the given new-expression.  May return 0 to indicate that no
   /// array cookie is required.
   ///
   /// Several cases are filtered out before this method is called:
   ///   - non-array allocations never need a cookie
   ///   - calls to \::operator new(size_t, void*) never need a cookie
   ///

lib/CodeGen/CGExprCXX.cpp

CGF.emitArrayDestroy(arrayBegin, arrayEnd, elementType, elementAlign,
                          /*checkZeroLength*/ true,
                          CGF.needsEHCleanup(dtorKind));
   }
 
   // Pop the cleanup block.
   CGF.PopCleanupBlock();
 }
 
+// Will we read through the deleted pointer?  If so,
+// we must first check it is not null.
+static bool DeleteMightAccessObject(CodeGenFunction &CGF,
+                                    const CXXDeleteExpr *E, QualType DeleteTy) {
+
+  if (E->getOperatorDelete()->isDestroyingOperatorDelete()) {
+    // It is safe to call destroying operator delete with nullptr arguments
+    // ([expr.delete] tells us it is unspecified whether a deallocation
+    // function is called) but a virtual destructor must be resolved
+    // to find the right function, which we can't do on nullptr.
+    auto *Dtor = DeleteTy->getAsCXXRecordDecl()->getDestructor();
+    return Dtor && Dtor->isVirtual();
+  }
+
+  if (E->isArrayForm()) {
+    return CGF.CGM.getCXXABI().requiresArrayCookie(E, DeleteTy);
+  }
+
+  // Otherwise, we should avoid invoking any nontrivial destructor on
+  // a null object.
+  return DeleteTy.isDestructedType();
+}
+
 void CodeGenFunction::EmitCXXDeleteExpr(const CXXDeleteExpr *E) {
   const Expr *Arg = E->getArgument();
   Address Ptr = EmitPointerWithAlignment(Arg);
+  QualType DeleteTy = E->getDestroyedType();
 
-  // Null check the pointer.
+  // Null check the pointer, unless the destructor is trivial.  In that case,
+  // all we'll be doing is passing Ptr to ::operator delete(), which is
+  // well formed for nullptr arguments (and allowed by [expr.delete.7]
+  // The overwhelming majority of deletes are of non-nullptr, so there's
+  // no efficiency gain to be had by skipping the very rare exceptions, and
+  // it bleeds code size (and unneeded branches.)
+  llvm::BasicBlock *DeleteEnd = nullptr;
+  if (DeleteMightAccessObject(*this, E, DeleteTy)) {
     llvm::BasicBlock *DeleteNotNull = createBasicBlock("delete.notnull");
-  llvm::BasicBlock *DeleteEnd = createBasicBlock("delete.end");
+    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 (DeleteEnd) EmitBlock(DeleteEnd);
     return;
   }
 
   // We might be deleting a pointer to array.  If so, GEP down to the
   // first non-array element.
   // (this assumes that A(*)[3][7] is converted to [3 x [7 x %A]]*)
   if (DeleteTy->isConstantArrayType()) {
     llvm::Value *Zero = Builder.getInt32(0);
while (const ConstantArrayType *Arr
       GEP.push_back(Zero);
     }
 
     Ptr = Address(Builder.CreateInBoundsGEP(Ptr.getPointer(), GEP, "del.first"),
                   Ptr.getAlignment());
   }
 
   assert(ConvertTypeForMem(DeleteTy) == Ptr.getElementType());
   
   if (E->isArrayForm()) {
     EmitArrayDelete(*this, E, Ptr, DeleteTy);
   } else {
     EmitObjectDelete(*this, E, Ptr, DeleteTy);
   }
 
-  EmitBlock(DeleteEnd);
+  if (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;

test/CodeGenCXX/cxx2a-destroying-delete.cpp

 struct A {
   void *data;
   ~A();
   void operator delete(A*, std::destroying_delete_t);
 };
 void delete_A(A *a) { delete a; }
 // CHECK-LABEL: define {{.*}}delete_A
 // CHECK: %[[a:.*]] = load
-// CHECK: icmp eq %{{.*}} %[[a]], null
-// CHECK: br i1
-//
+// CHECK-NOT: icmp eq %{{.*}} %[[a]], null
+// CHECK-NOT: br i1
 // Ensure that we call the destroying delete and not the destructor.
 // CHECK-NOT: call
 // CHECK-ITANIUM: call void @_ZN1AdlEPS_St19destroying_delete_t(%{{.*}}* %[[a]])
 // CHECK-MSABI: call void @"\01??3A@@SAXPEAU0@Udestroying_delete_t@std@@@Z"(%{{.*}}* %[[a]], i8
 // CHECK-NOT: call
 // CHECK: }
 
 struct B {

 // CHECK: %[[c:.*]] = load
 // CHECK: icmp eq %{{.*}} %[[c]], null
 // CHECK: br i1
 //
 // CHECK: %[[base:.*]] = getelementptr {{.*}}, i64 8
 // CHECK: %[[castbase:.*]] = bitcast {{.*}} %[[base]]
 //
 // CHECK: %[[a:.*]] = phi {{.*}} %[[castbase]]
-// CHECK: icmp eq %{{.*}} %[[a]], null
-// CHECK: br i1
+// CHECK-NOT: icmp eq %{{.*}} %[[a]], null
+// CHECK-NOT: br i1
 //
 // CHECK-NOT: call
 // CHECK-ITANIUM: call void @_ZN1AdlEPS_St19destroying_delete_t(%{{.*}}* %[[a]])
 // CHECK-MSABI: call void @"\01??3A@@SAXPEAU0@Udestroying_delete_t@std@@@Z"(%{{.*}}* %[[a]], i8
 // CHECK-NOT: call
 // CHECK: }
 
 struct VDel { virtual ~VDel(); };

test/CodeGenCXX/delete-two-arg.cpp

 // RUN: %clang_cc1 -triple i686-pc-linux-gnu %s -o - -emit-llvm -verify | FileCheck %s
 // expected-no-diagnostics
 
 typedef __typeof(sizeof(int)) size_t;
 
 namespace test1 {
   struct A { void operator delete(void*,size_t); int x; };
 
   // CHECK-LABEL: define void @_ZN5test11aEPNS_1AE(
   void a(A *x) {
     // CHECK:      load
-    // CHECK-NEXT: icmp eq {{.*}}, null
-    // CHECK-NEXT: br i1
+    // CHECK-NOT: icmp eq {{.*}}, null
+    // CHECK-NOT: br i1
     // CHECK:      call void @_ZN5test11AdlEPvj(i8* %{{.*}}, i32 4)
     delete x;
   }
 }
 
 // Check that we make cookies for the two-arg delete even when using
 // the global allocator and deallocator.
 namespace test2 {

test/CodeGenCXX/delete.cpp

 // RUN: %clang_cc1 -triple x86_64-apple-darwin10 %s -emit-llvm -o - | FileCheck %s
 
 void t1(int *a) {
   delete a;
 }
 
 struct S {
   int a;
 };
 
 // POD types.
+// CHECK-LABEL: define void @_Z2t3P1S
 void t3(S *s) {
+  // CHECK-NOT: icmp eq {{.*}}, null
+  // CHECK-NOT: br i1
+  // CHECK: call void @_ZdlPv
+
   delete s;
 }
 
 // Non-POD
 struct T {
   ~T();
   int a;
 };
void f(bool *b) {
     delete b;
     // CHECK: call void @_ZdaPv(i8*
     delete [] b;
   }
 }
 
 namespace test3 {
   void f(int a[10][20]) {
+    // CHECK-NOT: icmp eq {{.*}}, null
+    // CHECK-NOT: br i1
     // CHECK: call void @_ZdaPv(i8*
     delete a;
   }
 }
 
 namespace test4 {
   // PR10341: ::delete with a virtual destructor
   struct X {
     virtual ~X();
     void operator delete (void *);
   };
 
   // CHECK-LABEL: define void @_ZN5test421global_delete_virtualEPNS_1XE
   void global_delete_virtual(X *xp) {
+    // CHECK: icmp eq {{.*}}, null
+    // CHECK: br i1
     //   Load the offset-to-top from the vtable and apply it.
     //   This has to be done first because the dtor can mess it up.
     // CHECK:      [[T0:%.*]] = bitcast [[X:%.*]]* [[XP:%.*]] to i64**
     // CHECK-NEXT: [[VTABLE:%.*]] = load i64*, i64** [[T0]]
     // CHECK-NEXT: [[T0:%.*]] = getelementptr inbounds i64, i64* [[VTABLE]], i64 -2
     // CHECK-NEXT: [[OFFSET:%.*]] = load i64, i64* [[T0]], align 8
     // CHECK-NEXT: [[T0:%.*]] = bitcast [[X]]* [[XP]] to i8*
     // CHECK-NEXT: [[ALLOCATED:%.*]] = getelementptr inbounds i8, i8* [[T0]], i64 [[OFFSET]]