Prevent InstCombine from miscompiling `operator delete`

[davide]

Summary

It's not legal inventing calls to operator delete.

[davide]

Side note: instcombine speculates these calls to free using pattern matching.
In my opinion, it shouldn't. Hoisting shouldn't be done in instcombine, and hoisting shouldn't be done on a per-name basis. Presumably, the frontend should attach an attribute to this call to make sure they can be hoisted.
If there's not enough information in the frontend, then the middle-end should compute this information (the attribute) and then some pass should be responsible for the sinking/hoisting.

[rsmith]

lib/Analysis/MemoryBuiltins.cpp

351

This is a really confusing name. It sounds like it's detecting whether a call is free of side-effects, whereas it's *actually* detecting whether the call is to a free-like function that has side-effects.

363–368

I really don't like duplicating this list here, in a way that means we would miscompile again if the list in isFreeCall is extended but this list is not. (Notably, this list is already missing cases from isFreeCall, and as it happens, the one in isFreeCall is also missing cases.)

Perhaps instead changing this function to determine whether a call is known to be side-effect free when given a null pointer, and special-casing the very small number of functions for which that's true, would be a better and more maintainable approach?

393–394

Note that this function returns the wrong value for a nobuiltin call, and thus may still miscompile calls to free when building with -fno-builtin=free.

lib/Transforms/InstCombine/InstructionCombining.cpp

2231

This is wrong too. Either passing undef to *any* pointer parameter in a function call results in UB, or you cannot assume that passing undef to ::operator delete results in UB. The user-provided ::operator delete might ignore its argument, for example.

I don't know if this is the reason, but LLVM miscompiles calls to operator delete in cases where it ignores its argument too: https://godbolt.org/g/dvvirQ

2242

Wrong for operator delete.

[davide]

So, from what I can see no transformation made for free() is valid in case of operator delete.
What do you think instead of introducing a predicate isCallToOperatorDelete() and bail out at the beginning of visitFree() ?
Alternatively, we could add a boolean argument to isFreeCall() which doesn't include operator delete (still trying to pick a name for the argument).

I'm leaning towards 1), what do you think?

lib/Analysis/MemoryBuiltins.cpp

351

Not really happy about the name either, have a better proposal?

[rsmith]

In D37933#872815, @davide wrote:

So, from what I can see no transformation made for free() is valid in case of operator delete.
What do you think instead of introducing a predicate isCallToOperatorDelete() and bail out at the beginning of visitFree() ?

Sounds fine (but we should also check whether the call is a nobuiltin call to free, which should also not be optimized).

lib/Analysis/MemoryBuiltins.cpp

351

Maybe freeCallHasSideEffects? (Or, if we revert the sense of this as suggested below, freeCallHasNoSideEffects.)

352–353

This should presumably also be checking whether the call is nobuiltin.

[dnsampaio]

Hi @davide, do you have any plans to address this issue? Regards.

[rsmith]

https://reviews.llvm.org/D79378 addresses this issue and moves the optimization to the frontend where it can be done correctly.

[davide]

This is really ancient history.

include/llvm/Analysis/MemoryBuiltins.h

static inline CallInst *extractCallocCall(Value *I,
   return const_cast<CallInst*>(extractCallocCall((const Value*)I, TLI));
 }
 
 
 //===----------------------------------------------------------------------===//
 //  free Call Utility Functions.
 //
 
+/// hasSideEffectsFreeCall - Returns true if the call has side effects.
+bool hasSideEffectsFreeCall(const CallInst *CI, const TargetLibraryInfo &TLI);
+
 /// isFreeCall - Returns non-null if the value is a call to the builtin free()
 const CallInst *isFreeCall(const Value *I, const TargetLibraryInfo *TLI);
 
 static inline CallInst *isFreeCall(Value *I, const TargetLibraryInfo *TLI) {
   return const_cast<CallInst*>(isFreeCall((const Value*)I, TLI));
 }
 
 //===----------------------------------------------------------------------===//

lib/Analysis/MemoryBuiltins.cpp

 
 /// extractCallocCall - Returns the corresponding CallInst if the instruction
 /// is a calloc call.
 const CallInst *llvm::extractCallocCall(const Value *I,
                                         const TargetLibraryInfo *TLI) {
   return isCallocLikeFn(I, TLI) ? cast<CallInst>(I) : nullptr;
 }
 
+/// hasSideEffectsFreeCall - Returns true if the call has side effects.
+bool llvm::hasSideEffectsFreeCall(const CallInst *CI,
+                                  const TargetLibraryInfo &TLI) {
+  Function *Callee = CI->getCalledFunction();
+  if (Callee == nullptr)
+    return false;
+
+  StringRef FnName = Callee->getName();
+  LibFunc TLIFn;
+  if (!TLI.getLibFunc(FnName, TLIFn) || !TLI.has(TLIFn))
+    return false;
+
+  return TLIFn == LibFunc_ZdlPv ||                   // operator delete(void*)
+         TLIFn == LibFunc_ZdaPv ||                   // operator delete[](void*)
+         TLIFn == LibFunc_msvc_delete_ptr32 ||       // operator delete(void*)
+         TLIFn == LibFunc_msvc_delete_ptr64 ||       // operator delete(void*)
+         TLIFn == LibFunc_msvc_delete_array_ptr32 || // operator delete[](void*)
+         TLIFn == LibFunc_msvc_delete_array_ptr64;   // operator delete[](void*)
+}
+
 /// isFreeCall - Returns non-null if the value is a call to the builtin free()
 const CallInst *llvm::isFreeCall(const Value *I, const TargetLibraryInfo *TLI) {
   const CallInst *CI = dyn_cast<CallInst>(I);
   if (!CI || isa<IntrinsicInst>(CI))
     return nullptr;
   Function *Callee = CI->getCalledFunction();
   if (Callee == nullptr)
     return nullptr;
else if (TLIFn == LibFunc_ZdlPvj ||              // delete(void*, uint)
            TLIFn == LibFunc_msvc_delete_array_ptr64_longlong || // delete[](void*, ulonglong)
            TLIFn == LibFunc_msvc_delete_array_ptr32_nothrow || // delete[](void*, nothrow)
            TLIFn == LibFunc_msvc_delete_array_ptr64_nothrow)   // delete[](void*, nothrow)
     ExpectedNumParams = 2;
   else
     return nullptr;
 
   // Check free prototype.
   // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin
   // attribute will exist.
   FunctionType *FTy = Callee->getFunctionType();
   if (!FTy->getReturnType()->isVoidTy())
     return nullptr;
   if (FTy->getNumParams() != ExpectedNumParams)
     return nullptr;
   if (FTy->getParamType(0) != Type::getInt8PtrTy(Callee->getContext()))
     return nullptr;
 

lib/Transforms/InstCombine/InstructionCombining.cpp

   FI.moveBefore(TI);
   return &FI;
 }
 
 
 Instruction *InstCombiner::visitFree(CallInst &FI) {
   Value *Op = FI.getArgOperand(0);
 
   // free undef -> unreachable.
   if (isa<UndefValue>(Op)) {
     // Insert a new store to null because we cannot modify the CFG here.
     Builder.CreateStore(ConstantInt::getTrue(FI.getContext()),
                         UndefValue::get(Type::getInt1PtrTy(FI.getContext())));
     return eraseInstFromFunction(FI);
   }
 
   // If we have 'free null' delete the instruction.  This can happen in stl code
   // when lots of inlining happens.
   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 we can't really do it in the case of `operator delete` as this one
+  // can have visible side effects.
+  if (MinimizeSize && !hasSideEffectsFreeCall(&FI, TLI))
     if (Instruction *I = tryToMoveFreeBeforeNullTest(FI))
       return I;
 
   return nullptr;
 }
 
 Instruction *InstCombiner::visitReturnInst(ReturnInst &RI) {
   if (RI.getNumOperands() == 0) // ret void

test/Transforms/InstCombine/pr34581.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; Instcombine is not free of doing anything hazy like hoisting calls to operator
+; delete. This is PR34581.
+
+; RUN: opt -instcombine %s -S | FileCheck %s
+
+define void @patatino(i8* %c) #0 {
+; CHECK-LABEL: @patatino(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ISNULL:%.*]] = icmp eq i8* [[C:%.*]], null
+; CHECK-NEXT:    br i1 [[ISNULL]], label [[DELETE_END:%.*]], label [[DELETE_NOTNULL:%.*]]
+; CHECK:       delete.notnull:
+; CHECK-NEXT:    call void @_ZdlPv(i8* [[C]])
+; CHECK-NEXT:    br label [[DELETE_END]]
+; CHECK:       delete.end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %isnull = icmp eq i8* %c, null
+  br i1 %isnull, label %delete.end, label %delete.notnull
+
+delete.notnull:
+  call void @_ZdlPv(i8* %c)
+  br label %delete.end
+
+delete.end:
+  ret void
+}
+
+declare void @_ZdlPv(i8*)
+
+attributes #0 = { minsize }