[llvm-dev] [RFC] Adding support for marking allocator functions in LLVM IR

[Augie Fackler via llvm-dev]

Hi everyone! I’m working on making the Rust compiler being able to track LLVM HEAD more closely, and as part of that we need to obviate a patch[0] that teaches LLVM about some Rust allocator implementation details. This proposal is the product of many conversations and a couple of failed attempts at simpler implementations.

Background

========

Rust uses LLVM for codegen, and has its own allocator functions. In order for LLVM to correctly optimize out allocations we have to tell the optimizer about the allocation/deallocation functions used by Rust.

Languages supported by Clang, such as C and C++, have stable symbol names for their allocation functions, which are hardcoded in LLVM[1][2]. Unfortunately, this strategy does not work for Rust, where developers don't want to commit to a particular symbol name and calling convention yet.

Proposal

=======

We add two attributes to LLVM IR:

 * `allocator(FAMILY)`: Marks a function as part of an allocator family, named by the “primary” allocation function (e.g. `allocator(“malloc”)`, `allocator(“_Znwm”)`, or `allocator(“__rust_alloc”)`).

 * `releaseptr(idx)`: Indicates that the function releases the pointer that is its Nth argument.

These attributes, combined with the existing `allocsize(n[, m])` attribute lets us annotate alloc, realloc, and free type functions in LLVM IR, which relieves Rust of the need to carry a patch to describe its allocator functions to LLVM’s optimizer. Some example IR of what this might look like:

; Function Attrs: nounwind ssp

define i8* @test5(i32 %n) #4 {

entry:

  %0 = tail call noalias dereferenceable_or_null(20) i8* @malloc(i32 20) #8

  %1 = load i8*, i8** @s, align 8

  call void @llvm.memcpy.p0i8.p0i8.i32(i8* noundef nonnull align 1 dereferenceable(10) %0, i8* noundef nonnull align 1 dereferenceable(10) %1, i32 10, i1 false) #0

  ret i8* %0

}

attributes #8 = { nounwind allocsize(0) "allocator"="malloc" }

Similarly, the call `free(foo)` would get the attributes `”allocator”=”malloc” releaseptr(1)` and `realloc(foo, N)` gets `”allocator”=”malloc” releaseptr(1) allocsize(1)`. Note that the `releaseptr(n)` attribute is 1-indexed to avoid issues with storing zero values in attributes in my current draft - I’m very open to suggestions to change that, this just seemed like the right solution rather than adding getters/setters everywhere to increment/decrement a value.

Benefits

=======

In addition to the benefits for Rust, the LLVM optimizer could also be improved to not optimize away defects like

{

  auto *foo = new Thing();

  free(foo);

}

which would then correctly crash instead of silently “working” until something actually uses the allocation. Similarly, there’s a potential defect when only one side of an overridden operator::new and operator::delete is visible to the optimizer and inlineable, which can look indistinguishable from the above after inlining.

This also probably opens the door to fixing issues like https://bugs.llvm.org/show_bug.cgi?id=49022 caused by overloading the `builtin` annotation on allocator functions, but I’m unlikely to continue in that direction.

What do people think?

Thanks,

Augie

[0] https://github.com/rust-lang/llvm-project/commit/b1f55f7159540862c407a2d89d49434ce65892e5

[1] https://github.com/llvm/llvm-project/blob/cd5f582c3dd747ab97b57df37642b0dffba398ee/llvm/lib/Analysis/MemoryBuiltins.cpp#L73

[2] https://github.com/llvm/llvm-project/blob/cd5f582c3dd747ab97b57df37642b0dffba398ee/llvm/lib/Analysis/MemoryBuiltins.cpp#L433

[Jessica Clarke via llvm-dev]

On 5 Jan 2022, at 22:32, Augie Fackler via llvm-dev <llvm...@lists.llvm.org> wrote:
>
> Hi everyone! I’m working on making the Rust compiler being able to track LLVM HEAD more closely, and as part of that we need to obviate a patch[0] that teaches LLVM about some Rust allocator implementation details. This proposal is the product of many conversations and a couple of failed attempts at simpler implementations.
>
> Background
> ========
> Rust uses LLVM for codegen, and has its own allocator functions. In order for LLVM to correctly optimize out allocations we have to tell the optimizer about the allocation/deallocation functions used by Rust.
>
> Languages supported by Clang, such as C and C++, have stable symbol names for their allocation functions, which are hardcoded in LLVM[1][2]. Unfortunately, this strategy does not work for Rust, where developers don't want to commit to a particular symbol name and calling convention yet.
>
> Proposal
> =======
> We add two attributes to LLVM IR:
>
> * `allocator(FAMILY)`: Marks a function as part of an allocator family, named by the “primary” allocation function (e.g. `allocator(“malloc”)`, `allocator(“_Znwm”)`, or `allocator(“__rust_alloc”)`).

Why do you need a family? What’s insufficient about just using allocsize(idx), as used by __attribute__((alloc_size(...)) in GNU C? (Which you acknowledge the existence of, but don’t justify why you need your own attribute.) What to use as the allocator “family” string for C++ operator new seems pretty unclear too, so I’m not sure how good an idea this free-form string argument is in your proposal.

> * `releaseptr(idx)`: Indicates that the function releases the pointer that is its Nth argument.

This should probably just be free(idx)/frees(idx)/willfree(idx) (we already have nofree as an attribute for arguments), or an attribute on the argument itself. Talking about releasing makes it sound like reference counting semantics.

Jess

> These attributes, combined with the existing `allocsize(n[, m])` attribute lets us annotate alloc, realloc, and free type functions in LLVM IR, which relieves Rust of the need to carry a patch to describe its allocator functions to LLVM’s optimizer. Some example IR of what this might look like:
>
> ; Function Attrs: nounwind ssp
> define i8* @test5(i32 %n) #4 {
> entry:
> %0 = tail call noalias dereferenceable_or_null(20) i8* @malloc(i32 20) #8
> %1 = load i8*, i8** @s, align 8
> call void @llvm.memcpy.p0i8.p0i8.i32(i8* noundef nonnull align 1 dereferenceable(10) %0, i8* noundef nonnull align 1 dereferenceable(10) %1, i32 10, i1 false) #0
> ret i8* %0
> }
>
> attributes #8 = { nounwind allocsize(0) "allocator"="malloc" }
>
> Similarly, the call `free(foo)` would get the attributes `”allocator”=”malloc” releaseptr(1)` and `realloc(foo, N)` gets `”allocator”=”malloc” releaseptr(1) allocsize(1)`. Note that the `releaseptr(n)` attribute is 1-indexed to avoid issues with storing zero values in attributes in my current draft - I’m very open to suggestions to change that, this just seemed like the right solution rather than adding getters/setters everywhere to increment/decrement a value.
>
> Benefits
> =======
> In addition to the benefits for Rust, the LLVM optimizer could also be improved to not optimize away defects like
>
> {
> auto *foo = new Thing();
> free(foo);
> }
>
> which would then correctly crash instead of silently “working” until something actually uses the allocation. Similarly, there’s a potential defect when only one side of an overridden operator::new and operator::delete is visible to the optimizer and inlineable, which can look indistinguishable from the above after inlining.
>
> This also probably opens the door to fixing issues like https://bugs.llvm.org/show_bug.cgi?id=49022 caused by overloading the `builtin` annotation on allocator functions, but I’m unlikely to continue in that direction.
>
> What do people think?
>
> Thanks,
> Augie
>
> [0] https://github.com/rust-lang/llvm-project/commit/b1f55f7159540862c407a2d89d49434ce65892e5
> [1] https://github.com/llvm/llvm-project/blob/cd5f582c3dd747ab97b57df37642b0dffba398ee/llvm/lib/Analysis/MemoryBuiltins.cpp#L73
> [2] https://github.com/llvm/llvm-project/blob/cd5f582c3dd747ab97b57df37642b0dffba398ee/llvm/lib/Analysis/MemoryBuiltins.cpp#L433
>

> _______________________________________________
> LLVM Developers mailing list
> llvm...@lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

_______________________________________________
LLVM Developers mailing list
llvm...@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

[Nikita Popov via llvm-dev]

An important bit I'm missing in this proposal is what the actual semantics of the "allocator" attribute are -- what optimizations is LLVM permitted to perform if this attribute is present?

I've looked through various uses of isAllocLikeFn(), and I think a few of them can be replaced by isNoAliasCall() instead, which is our existing mechanism to annotate that a function returns a distinct memory object. Sample change for LICM here: https://reviews.llvm.org/D116728 I think we should try to migrate isAllocLikeFn() -> isNoAliasCall() for cases that don't need any additional guarantees.

I assume the only optimization that "allocator" should control is the elimination of unused alloc+free pairs. Is that correct? Or are there other optimizations that should be bound to it?

Regards,

Nikita

[Reid Kleckner via llvm-dev]

On Thu, Jan 6, 2022 at 1:41 AM Nikita Popov via llvm-dev <llvm...@lists.llvm.org> wrote:

An important bit I'm missing in this proposal is what the actual semantics of the "allocator" attribute are -- what optimizations is LLVM permitted to perform if this attribute is present?

...

I assume the only optimization that "allocator" should control is the elimination of unused alloc+free pairs. Is that correct? Or are there other optimizations that should be bound to it?

Not to speak for Augie, but I think these predicates exist to support a higher level goal of teaching LLVM to promote heap allocations to stack allocations. LLVM can only currently do this when other passes (GVN+DSE) promote all loads and stores to an allocation to registers, but you can imagine building out more annotations to make other transforms possible.

[Augie Fackler via llvm-dev]

Yep. Any kind of noalias annotations should be separate, and we can just keep the `allocator` attribute down to just "you can optimize this pair of calls away if circumstances are right." 

[Augie Fackler via llvm-dev]

On Wed, Jan 5, 2022 at 7:58 PM Jessica Clarke <jrt...@jrtc27.com> wrote:

On 5 Jan 2022, at 22:32, Augie Fackler via llvm-dev <llvm...@lists.llvm.org> wrote:
> Proposal
> =======
> We add two attributes to LLVM IR:
>
>  * `allocator(FAMILY)`: Marks a function as part of an allocator family, named by the “primary” allocation function (e.g. `allocator(“malloc”)`, `allocator(“_Znwm”)`, or `allocator(“__rust_alloc”)`).

Why do you need a family? What’s insufficient about just using allocsize(idx), as used by __attribute__((alloc_size(...)) in GNU C? (Which you acknowledge the existence of, but don’t justify why you need your own attribute.) What to use as the allocator “family” string for C++ operator new seems pretty unclear too, so I’m not sure how good an idea this free-form string argument is in your proposal.

For C++ new we'd use the mangled form of ::operator::new, aka _Znwm. The reason for the family is so that we can track which allocations are related, so that incorrect code like

{

  auto *foo = new Foo();

  free(foo);

}

doesn't get optimized away. I believe others I talked to while designing this might have had more interesting ideas for how the family could be used, but it's easy to put in today, and roughly impossible to add via an IR upgrade if we don't put it in, so it seems sensible to try and track the family now. I actually initially argued against the family argument, but was won over by the limitation that we'd be unable to upgrade it in the future.

 

>  * `releaseptr(idx)`: Indicates that the function releases the pointer that is its Nth argument.

This should probably just be free(idx)/frees(idx)/willfree(idx) (we already have nofree as an attribute for arguments), or an attribute on the argument itself. Talking about releasing makes it sound like reference counting semantics.

Sure, that seems reasonable. I'll update my prototype to use that name instead. Thanks!

 

Jess

[James Y Knight via llvm-dev]

On Wed, Jan 5, 2022 at 5:32 PM Augie Fackler via llvm-dev <llvm...@lists.llvm.org> wrote:

In addition to the benefits for Rust, the LLVM optimizer could also be improved to not optimize away defects like

{

  auto *foo = new Thing();

  free(foo);

}

which would then correctly crash instead of silently “working” until something actually uses the allocation. Similarly, there’s a potential defect when only one side of an overridden operator::new and operator::delete is visible to the optimizer and inlineable, which can look indistinguishable from the above after inlining.

I think this is important to note -- tracking the pairing is something we should be doing already with the existing hardcoded list, as well. E.g. compile the following example with -O1 (https://godbolt.org/z/WsYKcexYG).

When compiling "main", at first we cannot see the matched new/delete pair, because delete is hidden in the "deleteit" function. Then, we run the inliner, which inlines the "operator new" and "deleteit" functions. Now, main has a call to malloc followed by ::operator delete, which we proceed to remove, because they're allocation functions. But they're unmatched allocation functions, so this weirdly ends up skipping the side-effects of our custom operator delete, but NOT those of our custom operator new.

#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);

}

[Philip Reames via llvm-dev]

On 1/6/22 7:45 AM, Augie Fackler via llvm-dev wrote:

On Wed, Jan 5, 2022 at 7:58 PM Jessica Clarke <jrt...@jrtc27.com> wrote:

On 5 Jan 2022, at 22:32, Augie Fackler via llvm-dev <llvm...@lists.llvm.org> wrote:
> Proposal
> =======
> We add two attributes to LLVM IR:
>
>  * `allocator(FAMILY)`: Marks a function as part of an allocator family, named by the “primary” allocation function (e.g. `allocator(“malloc”)`, `allocator(“_Znwm”)`, or `allocator(“__rust_alloc”)`).

Why do you need a family? What’s insufficient about just using allocsize(idx), as used by __attribute__((alloc_size(...)) in GNU C? (Which you acknowledge the existence of, but don’t justify why you need your own attribute.) What to use as the allocator “family” string for C++ operator new seems pretty unclear too, so I’m not sure how good an idea this free-form string argument is in your proposal.

For C++ new we'd use the mangled form of ::operator::new, aka _Znwm. The reason for the family is so that we can track which allocations are related, so that incorrect code like

{

  auto *foo = new Foo();

  free(foo);

}

doesn't get optimized away. I believe others I talked to while designing this might have had more interesting ideas for how the family could be used, but it's easy to put in today, and roughly impossible to add via an IR upgrade if we don't put it in, so it seems sensible to try and track the family now. I actually initially argued against the family argument, but was won over by the limitation that we'd be unable to upgrade it in the future.

JFYI, this example does not provide the motivation you seem to think it does.  This example is to my knowledge, immediate UB.  As such, there's no need to "avoid" the optimization.  If anything, we should be more aggressive and convert this to an unreachable. 

 

>  * `releaseptr(idx)`: Indicates that the function releases the pointer that is its Nth argument.

This should probably just be free(idx)/frees(idx)/willfree(idx) (we already have nofree as an attribute for arguments), or an attribute on the argument itself. Talking about releasing makes it sound like reference counting semantics.

Sure, that seems reasonable. I'll update my prototype to use that name instead. Thanks!

 

Jess

[Philip Reames via llvm-dev]

Ok, this point needs amplified.  I was actually thinking about this just yesterday.

In C/C++, there's a debate about whether a call to malloc is "observable".  That is, are statistics collected by your malloc information about e.g. allocation count part of the program state which must be observed.  If the answer is "yes", then most allocation eliminations are unsound.  Note that most other languages choose a strong "no" and thus allocation elimination is sound and worthwhile. 

I had been planning to send a proposal for making the "is observable" state of an allocator routine explicit.  (I hadn't yet sat down to figure out how to express that, so TBD...)  My motivation is to support allocation eliminations optimizations upstream with clean LIT testing. 

Augie, are there *other* semantics you want to attach to the allocator attribute?  As Nikita said, we really need a list of the intended semantics.  Most likely, we'll end up splitting them into individual attributes (and use of existing ones), so having a list of concrete examples to work with is important.

Philip

[Philip Reames via llvm-dev]

On 1/5/22 2:32 PM, Augie Fackler via llvm-dev wrote:

Hi everyone! I’m working on making the Rust compiler being able to track LLVM HEAD more closely, and as part of that we need to obviate a patch[0] that teaches LLVM about some Rust allocator implementation details. This proposal is the product of many conversations and a couple of failed attempts at simpler implementations.

Background

========

Rust uses LLVM for codegen, and has its own allocator functions. In order for LLVM to correctly optimize out allocations we have to tell the optimizer about the allocation/deallocation functions used by Rust.

Languages supported by Clang, such as C and C++, have stable symbol names for their allocation functions, which are hardcoded in LLVM[1][2]. Unfortunately, this strategy does not work for Rust, where developers don't want to commit to a particular symbol name and calling convention yet.

Proposal

=======

We add two attributes to LLVM IR:

 * `allocator(FAMILY)`: Marks a function as part of an allocator family, named by the “primary” allocation function (e.g. `allocator(“malloc”)`, `allocator(“_Znwm”)`, or `allocator(“__rust_alloc”)`).

 * `releaseptr(idx)`: Indicates that the function releases the pointer that is its Nth argument.

Can you expand a bit on the motivation for this one?  What are some small examples that you think this will enable?

I don't see how this could allow allocation elimination without aggressive inlining.  Maybe you could use it to prove a particular bit of storage is undefined after return, but what does that buy you in terms of practical optimization benefit?  Do you have something else in mind?

p.s. In terms of spelling, I strongly agree with the suggestion elsewhere to recast this as a parameter attribute and use the "free" naming. 

These attributes, combined with the existing `allocsize(n[, m])` attribute lets us annotate alloc, realloc, and free type functions in LLVM IR, which relieves Rust of the need to carry a patch to describe its allocator functions to LLVM’s optimizer. Some example IR of what this might look like:

; Function Attrs: nounwind ssp

define i8* @test5(i32 %n) #4 {

entry:

  %0 = tail call noalias dereferenceable_or_null(20) i8* @malloc(i32 20) #8

  %1 = load i8*, i8** @s, align 8

  call void @llvm.memcpy.p0i8.p0i8.i32(i8* noundef nonnull align 1 dereferenceable(10) %0, i8* noundef nonnull align 1 dereferenceable(10) %1, i32 10, i1 false) #0

  ret i8* %0

}

attributes #8 = { nounwind allocsize(0) "allocator"="malloc" }

Similarly, the call `free(foo)` would get the attributes `”allocator”=”malloc” releaseptr(1)` and `realloc(foo, N)` gets `”allocator”=”malloc” releaseptr(1) allocsize(1)`. Note that the `releaseptr(n)` attribute is 1-indexed to avoid issues with storing zero values in attributes in my current draft - I’m very open to suggestions to change that, this just seemed like the right solution rather than adding getters/setters everywhere to increment/decrement a value.

Benefits

=======

In addition to the benefits for Rust, the LLVM optimizer could also be improved to not optimize away defects like

{

  auto *foo = new Thing();

  free(foo);

}

which would then correctly crash instead of silently “working” until something actually uses the allocation. Similarly, there’s a potential defect when only one side of an overridden operator::new and operator::delete is visible to the optimizer and inlineable, which can look indistinguishable from the above after inlining.

This also probably opens the door to fixing issues like https://bugs.llvm.org/show_bug.cgi?id=49022 caused by overloading the `builtin` annotation on allocator functions, but I’m unlikely to continue in that direction.

What do people think?

Thanks,

Augie

[0] https://github.com/rust-lang/llvm-project/commit/b1f55f7159540862c407a2d89d49434ce65892e5

[1] https://github.com/llvm/llvm-project/blob/cd5f582c3dd747ab97b57df37642b0dffba398ee/llvm/lib/Analysis/MemoryBuiltins.cpp#L73

[2] https://github.com/llvm/llvm-project/blob/cd5f582c3dd747ab97b57df37642b0dffba398ee/llvm/lib/Analysis/MemoryBuiltins.cpp#L433

[James Y Knight via llvm-dev]

On Thu, Jan 6, 2022 at 11:40 AM Philip Reames via llvm-dev <llvm...@lists.llvm.org> wrote:

On 1/5/22 2:32 PM, Augie Fackler via llvm-dev wrote:

Hi everyone! I’m working on making the Rust compiler being able to track LLVM HEAD more closely, and as part of that we need to obviate a patch[0] that teaches LLVM about some Rust allocator implementation details. This proposal is the product of many conversations and a couple of failed attempts at simpler implementations.

Background

========

Rust uses LLVM for codegen, and has its own allocator functions. In order for LLVM to correctly optimize out allocations we have to tell the optimizer about the allocation/deallocation functions used by Rust.

Languages supported by Clang, such as C and C++, have stable symbol names for their allocation functions, which are hardcoded in LLVM[1][2]. Unfortunately, this strategy does not work for Rust, where developers don't want to commit to a particular symbol name and calling convention yet.

Proposal

=======

We add two attributes to LLVM IR:

 * `allocator(FAMILY)`: Marks a function as part of an allocator family, named by the “primary” allocation function (e.g. `allocator(“malloc”)`, `allocator(“_Znwm”)`, or `allocator(“__rust_alloc”)`).

 * `releaseptr(idx)`: Indicates that the function releases the pointer that is its Nth argument.

Can you expand a bit on the motivation for this one?  What are some small examples that you think this will enable?

I don't see how this could allow allocation elimination without aggressive inlining.  Maybe you could use it to prove a particular bit of storage is undefined after return, but what does that buy you in terms of practical optimization benefit?  Do you have something else in mind?

The example was written below -- `free(foo)` would get the attributes `”allocator”=”malloc” releaseptr(1)`. The "allocator" attribute declares that the function is an allocator function (and is thus removable if matched), while the releaseptr attribute declares that it is a freeing function (or, combined with allocsize, a realloc-like function), which frees the 1st argument.

Remember that the genesis of the proposal is to enable all the optimizations LLVM previously enabled via the hardcoded lists in MemoryBuiltins.cpp. So this attribute is effectively intended to support the same optimizations that "llvm::isFreeCall" does today. (Certainly, "What LLVM does today" is insufficient for a spec, but it does clearly describe the motivation!)

[Philip Reames via llvm-dev]

Oh!  I'd been assuming the free routine would just be annotated with the allocator family.  Functions which return new objects allocate, those which take arguments free.  (Realloc does both.)

I do see that's somewhat vague, and the appeal to annotating them both.  I just didn't get that from the original text.  :)

Philip

[Johannes Doerfert via llvm-dev]

If you want to do Heap2Stack, create an Attributor, seed AAHeapToStack
for each function, run it to completion. It works for known
malloc/alloc/calloc-like and free-like calls, so if you register your
calls there (as we did for __kmpc_alloc_shared/__kmpc_free_shared) you
will get heap2stack.

Examples:
https://github.com/llvm/llvm-project/blob/main/llvm/test/Transforms/Attributor/heap_to_stack.ll

~ Johannes

[Augie Fackler via llvm-dev]

On Thu, Jan 6, 2022 at 12:22 PM Johannes Doerfert <johannes...@gmail.com> wrote:

On 1/6/22 09:23, Reid Kleckner via llvm-dev wrote:
> On Thu, Jan 6, 2022 at 1:41 AM Nikita Popov via llvm-dev <
> llvm...@lists.llvm.org> wrote:
>
>> An important bit I'm missing in this proposal is what the actual semantics
>> of the "allocator" attribute are -- what optimizations is LLVM permitted to
>> perform if this attribute is present?
>> ...
>> I assume the only optimization that "allocator" should control is the
>> elimination of unused alloc+free pairs. Is that correct? Or are there other
>> optimizations that should be bound to it?
>>
> Not to speak for Augie, but I think these predicates exist to support a
> higher level goal of teaching LLVM to promote heap allocations to stack
> allocations. LLVM can only currently do this when other passes (GVN+DSE)
> promote all loads and stores to an allocation to registers, but you can
> imagine building out more annotations to make other transforms possible.
>
If you want to do Heap2Stack, create an Attributor, seed AAHeapToStack
for each function, run it to completion. It works for known
malloc/alloc/calloc-like and free-like calls, so if you register your
calls there (as we did for __kmpc_alloc_shared/__kmpc_free_shared) you
will get heap2stack.

It's an explicit goal of this work that we not have to freeze the Rust allocator function signatures and give LLVM Rust-specific knowledge. Rust has been carrying patches that do exactly that in their fork of the latest LLVM stable for years, but even then it occasionally bitrots and requires maintenance to correctly identify the allocator functions. Doing this with an attribute feels like it cleans up some technical debt, thus the motivation to invest the time.

Thanks,

Augie

[Johannes Doerfert via llvm-dev]

I don't mind using an attribute for allocation/deallocation functions,
it will make things more flexible. What I tried to say is that heap2stack
can fall out of the box if the proper functions know these are allocators/
deallocators.

~ Johannes

[Bryce Wilson via llvm-dev]

Hi all,

It's quite a coincidence to see this proposal. I just joined this list a few days ago specifically to ask about the correct way to annotate allocation and freeing functions. I'll create a separate thread to ask questions about my specific situation but I wanted to add my support for this proposal here.

My main question is if there should be some way to specify the kind of allocation function. In the hardcoded AllocationFnData array, there is a field to specify if the function acts like malloc, new, calloc, realloc, etc. This could be added to the annotation but I think a better way would be to specify the actual properties of interest. Can it return null, does it align the allocation, and what are the values in the newly allocated space (undef for malloc, 0 for calloc, something unknown but defined for strdup). This would also allow for creating new types of allocators that don't already exist.

I've created a patch with what this might look like for the existing hardcoded functions here: https://reviews.llvm.org/D116797. In my initial implementation, I realized that there are a lot of places where argument positions are hardcoded and special detection of strdup and strndup is hardcoded. Regardless of if we add the ability to specify these properties in attribute form or not, we will at least need to ensure that the correct arguments are used based on an allocsize annotation if available.

Sincerely,
Bryce Michael Wilson

[Philip Reames via llvm-dev]

On 1/7/22 1:23 AM, Bryce Wilson via llvm-dev wrote:

Hi all,

It's quite a coincidence to see this proposal. I just joined this list a few days ago specifically to ask about the correct way to annotate allocation and freeing functions. I'll create a separate thread to ask questions about my specific situation but I wanted to add my support for this proposal here.

My main question is if there should be some way to specify the kind of allocation function. In the hardcoded AllocationFnData array, there is a field to specify if the function acts like malloc, new, calloc, realloc, etc. This could be added to the annotation but I think a better way would be to specify the actual properties of interest. Can it return null, does it align the allocation, and what are the values in the newly allocated space (undef for malloc, 0 for calloc, something unknown but defined for strdup). This would also allow for creating new types of allocators that don't already exist.

Bryce, I completely agree with this property based approach.  In fact, I've spent the last day or so landing patches which move us in exactly that direction.  Unfortunately, I think a good amount of your patch is now redundant, but if you wanted to swap notes on remaining things to fix, please feel free to ping me directly.  I'll also start adding you on reviews where appropriate.

One subtle but important point: we do not want to have any property of an allocation function which can be expressed with existing attributes.  So, for instance, we do not want code to be dependent on throwing operator new never returning null.  Instead, we want said functions annotated nonnull, and the generic code to drive the optimization. 

I've created a patch with what this might look like for the existing hardcoded functions here: https://reviews.llvm.org/D116797. In my initial implementation, I realized that there are a lot of places where argument positions are hardcoded and special detection of strdup and strndup is hardcoded. Regardless of if we add the ability to specify these properties in attribute form or not, we will at least need to ensure that the correct arguments are used based on an allocsize annotation if available.

I think I've already killed several of the ones you note.  I agree there's definite room to improve the handling of strdup/strndup.  If you wanted to write a patch for that specifically, I'd be happy to review. 

Sincerely,
Bryce Michael Wilson

[James Y Knight via llvm-dev]

On Fri, Jan 7, 2022 at 4:48 PM Philip Reames via llvm-dev <llvm...@lists.llvm.org> wrote:

I think I've already killed several of the ones you note.  I agree there's definite room to improve the handling of strdup/strndup.  If you wanted to write a patch for that specifically, I'd be happy to review.

IMO, it doesn't seem worthwhile to make strdup handling expressible with generic attributes. We special case many other libc functions too, so this is not unusual, and unlike other allocator properties, "strdup-like" does not seem likely to be a very interesting thing to apply to other functions.

[Philip Reames via llvm-dev]

Er, I was apparently unclear.

The sole remaining property of a strndup that we can't get from generic attributes (which already exist) is the clamp on result size.  We can entirely remove strdup special casing (by having either the frontend or BuildLibCalls annotate it with appropriate attributes.)  We can *almost* do the same for strndup minus the size special casing.

So, we can remove a bunch of existing special case code.  We would not be adding any new attribute motivated by strdup.  I agree it appears to be an uncommon pattern.

One potential interaction I've not looked at is the nobuiltin bit, but presumably we must have already solved that as we're adding attributes to lots of other libfuncs. 

Do drive this through, we do need to switch a bunch of transforms from isAllocLike to noalias return driven as well.  (I'm assuming we want to do that for all kinds of reasons.)

Philip