Page MenuHomePhabricator

InstructionCombining: avoid eliding mismatched alloc/free pairs
Needs ReviewPublic

Authored by durin42 on Fri, Jan 14, 1:18 PM.

Details

Summary

Prior to this change LLVM would happily elide a call to any allocation
function and a call to any free function operating on the same unused
pointer. This can cause problems in some obscure cases, for example if
the body of operator::new can be inlined but the body of
operator::delete can't, as in this example from jyknight:

#include <stdlib.h>
#include <stdio.h>

int allocs = 0;

void *operator new(size_t n) {
    allocs++;
    void *mem = malloc(n);
    if (!mem) abort();
    return mem;
}

__attribute__((noinline)) void operator delete(void *mem) noexcept {
    allocs--;
    free(mem);
}

void deleteit(int*i) { delete i; }
int main() {
    int*i = new int;
    deleteit(i);
    if (allocs != 0)
      printf("MEMORY LEAK! allocs: %d\n", allocs);
}

This patch addresses the issue by introducing the concept of an
allocator function family and uses it to make sure that alloc/free
function pairs are only removed if they're in the same family.

Diff Detail

Event Timeline

durin42 created this revision.Fri, Jan 14, 1:18 PM
durin42 requested review of this revision.Fri, Jan 14, 1:18 PM
Herald added a project: Restricted Project. · View Herald Transcript
durin42 updated this revision to Diff 400130.Fri, Jan 14, 1:21 PM

Fix table formatting goofs.

xbolva00 added a subscriber: xbolva00.

cc @rsmith as he should be aware of these C++ new related changes.

nikic added a reviewer: nikic.Fri, Jan 14, 1:39 PM
nikic added a subscriber: nikic.

Please upload patches with full context (-U99999), minimize the test (remove unnecessary attributes, don't use unnecessary allocas, etc), use update_test_checks.py and omit braces for single-line if statements.

durin42 updated this revision to Diff 400136.Fri, Jan 14, 1:44 PM
durin42 added a subscriber: jyknight.

Split up C++ new families per @jyknight

durin42 updated this revision to Diff 400144.Fri, Jan 14, 2:10 PM

After splitting the ::operator::new flavors into their own families, I'm getting a weird failure from new-delete-itanium.ll. test8 in that file should optimize to just ret void but instead a few calls are surviving:

define void @test8() {
  %nt = alloca i8, align 1
  %naa = call align 8 dereferenceable_or_null(32) i8* @_ZnamSt11align_val_t(i64 32, i64 8) #5
  call void @_ZdaPvSt11align_val_t(i8* %naa, i64 8) #5
  %naja = call align 8 dereferenceable_or_null(32) i8* @_ZnajSt11align_val_t(i32 32, i32 8) #5
  call void @_ZdaPvSt11align_val_t(i8* %naja, i64 8) #5
  %nwat = call align 8 dereferenceable_or_null(32) i8* @_ZnwmSt11align_val_tRKSt9nothrow_t(i64 32, i64 8, i8* nonnull %nt) #5
  call void @_ZdlPvSt11align_val_tRKSt9nothrow_t(i8* %nwat, i64 8, i8* %nt) #5
  %naat = call align 8 dereferenceable_or_null(32) i8* @_ZnamSt11align_val_tRKSt9nothrow_t(i64 32, i64 8, i8* nonnull %nt) #5
  call void @_ZdaPvSt11align_val_tRKSt9nothrow_t(i8* %naat, i64 8, i8* %nt) #5
  %nwjat = call align 8 dereferenceable_or_null(32) i8* @_ZnwjSt11align_val_tRKSt9nothrow_t(i32 32, i32 8, i8* nonnull %nt) #5
  call void @_ZdlPvSt11align_val_tRKSt9nothrow_t(i8* %nwjat, i64 8, i8* %nt) #5
  %najat = call align 8 dereferenceable_or_null(32) i8* @_ZnajSt11align_val_tRKSt9nothrow_t(i32 32, i32 8, i8* nonnull %nt) #5
  call void @_ZdaPvSt11align_val_tRKSt9nothrow_t(i8* %najat, i64 8, i8* %nt) #5
  ret void
}

I don't see anything obviously wrong in my code or the test, but I've also been staring at these mangled names so long today they're kind of blending together. If anyone sees something amiss that looks related please comment!

durin42 updated this revision to Diff 400150.Fri, Jan 14, 2:34 PM

Fixed new-delete-itanium.ll failure. Several comments in the free function list were incorrect and it didn't matter until now. Fixed that while I'm here.

That could just as easily be part of the previous patch if people prefer - please let me know if that's the case.

jyknight added inline comments.Fri, Jan 14, 2:42 PM
llvm/lib/Analysis/MemoryBuiltins.cpp
82

The vec_malloc/vec_calloc/vec_realloc/vec_free functions look like they should be a distinct family.

100

These aren't good family names, since they could be the name of a user-defined function (and aren't actually what the msvc functions are called).

durin42 updated this revision to Diff 400159.Fri, Jan 14, 3:01 PM
durin42 marked 2 inline comments as done.

Split out vec_* functions and updated MSVC ::operator::new/delete to use the _actual_ mangled form.

durin42 updated this revision to Diff 400160.Fri, Jan 14, 3:02 PM
ychen added a subscriber: ychen.Fri, Jan 14, 3:07 PM

Is the issue being addressed similar to PR41039?

Is the issue being addressed similar to PR41039?

I don't know what that is, can you give me a link or something?

Ah, @jyknight bailed me out. That's https://github.com/llvm/llvm-project/issues/40384 which looks related, yes. I suspect that would be resolved by this patch.

ychen added a comment.Fri, Jan 14, 3:53 PM

Ah, @jyknight bailed me out. That's https://github.com/llvm/llvm-project/issues/40384 which looks related, yes. I suspect that would be resolved by this patch.

Agreed that this patch could fix it. However, the underlying issue is that the mismatch is generated by LLVM itself. IMHO preventing the mismatch is a better approach (which D97735 would do, I think we should land that instead. @rsmith (thought?)

I just wanted to say, personally I like this idea a lot. Even if there is a better way to solve the specific problem in https://github.com/llvm/llvm-project/issues/40384, this overall gives more information which may be useful in the future. This is also part of what someone from Rust was asking for on the llvm-dev mailing list (which was the email that got me into contributing at all). I'll leave it up to the more experienced devs whether to approve this patch since they have a better idea of what they want the memory builtins system to look like but I do think it should be approved.

hiraditya added inline comments.Sun, Jan 16, 11:23 PM
llvm/lib/Analysis/MemoryBuiltins.cpp
117–153

should we use _malloc here, as other functions are using the symbol name already?

I don't know enough about C++ semantics to have an opinion, so this response sticks purely to style/code structure issues.

llvm/lib/Analysis/MemoryBuiltins.cpp
110

Please add an implementation private enum for the known families and translate to a StringRef immediately before return in the public accessor.

This will cut out a full family of "oops I mistyped that name" bugs in the table.

This will be less important if we ever move to a full frontend annotation model, but as a stepping stone, it's an important code quality detail.

117–153

Definitely not.

511

The introduction of the getFreeFunctionData helper is a separable NFC. Please separate that change, land it, and rebase.

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
2664

With the semantics you're proposing, having two unannotated alloc/free be removed seems inconsistent.

Also, use compound if clause.

2670–2672

You seem to be missing the analogous check here...

durin42 updated this revision to Diff 401031.Tue, Jan 18, 4:11 PM
durin42 edited the summary of this revision. (Show Details)
durin42 marked 4 inline comments as done.Tue, Jan 18, 4:17 PM

I'll poke the enum later today or first thing tomorrow. I got stuck in a tarpit of being sad about the arc command line tool today.

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
2664

I think we can't fuse the conditions, because if we see a free() call on a newed pointer we should give up on the instruction combining, not allow it to possibly proceed on other methods, right?

Agreed on the unannotated functions meshing being inconsistent. Today that can't happen, but I guess when we move this to supporting attributes it could. Should the logic be something more like:

if (isFreeCall(...)) {

auto FreeFamily = getAllocationFamily(...);
if (FreeFamily == None || FreeFamily != Family) 
  return false;
...

}

or is there more to it than that that I'm missing?

durin42 updated this revision to Diff 401041.Tue, Jan 18, 4:51 PM
durin42 marked an inline comment as done.Tue, Jan 18, 4:52 PM

PTAL