Page MenuHomePhabricator

Introduce support for lib function aligned_alloc
AbandonedPublic

Authored by bondhugula on Dec 14 2019, 9:26 PM.

Details

Summary

aligned_alloc is a standard lib function and has been in glibc since 2.16 and in the C11 standard. It has semantics similar to malloc/calloc for several analyses/transforms.

- update target library info
- update passes to be aware of aligned_alloc in ways similar to malloc,
  calloc, etc.

This change will also be useful to LLVM generators that need to allocate buffers of vector elements larger than 16 bytes (for eg. 256-bit ones), element boundary alignment for which is not typically provided by malloc.

Addresses: https://bugs.llvm.org/show_bug.cgi?id=44062

Diff Detail

Event Timeline

bondhugula created this revision.Dec 14 2019, 9:26 PM
bondhugula edited the summary of this revision. (Show Details)Dec 14 2019, 9:45 PM
lebedev.ri added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
4305

Hm, why are these comparisons signed?

jdoerfert added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
9

You can commit the wording/spelling fixes in the Attributor without additional review.

4144

Upper case letter please: Alignment.

4305

Good question. I doubt we have a test for this. @sstefan1 Can you comment on this, and/or write a test and make it unsigned?

4317

Shouldn't the isa<ConstantInt>(I.getOperand(0) be inside the if (IsAlignedAllocLike)?

Do we really want to skip on heap 2 stack if the alignment is dynamic?

4356

Can we split the aligned alloc stuff from the heap 2 stack stuff? I think it is nicer and easier if we don't merge them.

sstefan1 added inline comments.Dec 15 2019, 1:34 PM
llvm/lib/Transforms/IPO/Attributor.cpp
4305

Yes, this is my bad. There is at least one more place where signed comparison was used. I'll make sure to fix it and add a test.

Thanks for noticing.

bondhugula marked 4 inline comments as done.Dec 15 2019, 5:34 PM

Thanks for the comments. Responses inline.

llvm/lib/Transforms/IPO/Attributor.cpp
4305

I didn't pay attention to this part myself beyond reusing from malloc handling. Looks like the values being compared are all unsigned or size_t.

4317

The 'alloca' instruction takes a constant alignment (both from the langref and the AllocaInst ctors). Also, a dynamic alignment would be tantamount to a dynamic sized allocation, which we aren't converting to stack allocations. (The padding needed for a dynamic alignment could effectively lead to an allocation of at least that size in the worst case.)

4317

Shouldn't the isa<ConstantInt>(I.getOperand(0) be inside the if (IsAlignedAllocLike)?

It'd be the same that way, but you'll need an extra line and indent for the rest. I can drop the comment under.

4356

This patch is all about support for aligned_alloc in analyses/transforms on par with malloc/calloc, and so I felt it would be incomplete if we split up some of that. We are making a similar impact on InstCombine, GVN, NewGVN, and BasicAliasAnalysis, and so logically this should all be together?

This test contains various changes in different parts of the code plus unrelated fixes (in comments, spelling, formatting, ...).

I think it is beneficial to have a patch that recognizes aligned_alloc, which should be testable through existing calls to isAllocLike, and one that teaches the transformations about it. All the unrelated NFC changes can go in as NFC patches before hand and without pre-review. Generally speaking, smaller patches are good. More practically, you now need reviewers that accept changes in various places. Granted, the changes are not complex in nature, but the general logic still applies.

We should also determine if aligned_alloc is the only one we want to support in this family or not. I mean, there is stuff like posix_memalign, memalign, pvalloc, ...

llvm/lib/Analysis/MemoryBuiltins.cpp
61

I'm not sure we want to pretend aligned_alloc is malloc or calloc like. It might not matter at the end of the day but for example they (can) behave differently when it comes to freeing memory. Would it be a problem to put it under AllocLike only?

llvm/lib/Transforms/IPO/Attributor.cpp
4317

It'd be the same that way, but you'll need an extra line and indent for the rest. I can drop the comment under.

I'm aware it is the same but it would be the same style as the surrounding code. Having an extra lines is not a problem, having these lines indented one more level is neither. I don't know what you mean by "drop the comment under".

no dynamic alignment

OK.

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
4300

If the alignment is constant we should add a align attribute as well.

bondhugula marked 3 inline comments as done.Dec 15 2019, 8:04 PM

This test contains various changes in different parts of the code plus unrelated fixes (in comments, spelling, formatting, ...).

I think it is beneficial to have a patch that recognizes aligned_alloc, which should be testable through existing calls to isAllocLike, and one that teaches the transformations about it. All the unrelated NFC changes can go in as NFC patches before hand and without pre-review. Generally speaking, smaller patches are good. More practically, you now need reviewers that accept changes in various places. Granted, the changes are not complex in nature, but the general logic still applies.

I'll defer it to you and other reviewers on how you'd like this to be split once the changes are finalized.

We should also determine if aligned_alloc is the only one we want to support in this family or not. I mean, there is stuff like posix_memalign, memalign, pvalloc, ...

posix_memalign is unfortunately very different - it doesn't return the pointer, but instead takes the address of the pointer as an argument. It's going to be quite non-trivial to support that AFAICS albeit it is similar to aligned_alloc on other aspects. valloc, pvalloc, memalign are all obsolete - I think aligned_alloc will by itself really addresses a lot of use cases. On a side note, there is little that posix_memalign provides that aligned_alloc doesn't because if you want an alignment that malloc doesn't already provide you (> 16 bytes), you will basically have large "elements" (>= 256-bit vectors typically) and as such your allocation size will already be a multiple of that alignment, which is a constraint with aligned_alloc but not with posix_memalign.

llvm/lib/Analysis/MemoryBuiltins.cpp
61

I'm not sure we want to pretend aligned_alloc is malloc or calloc like. It might not matter at the end of the day but for example they (can) behave differently when it comes to freeing memory. Would it be a problem to put it under AllocLike only?

I actually thought about this, and looking at how MallocOrCallocLike is used, aligned_alloc behaves the same way as far as this property goes. The freeing of memory works the same way, and the fact that malloc and calloc already have size arguments appearing in different positions/ways makes aligned_alloc fit with the common property implied by MallocOrCallocLike. It's nice thus that all the places that were already using MallocOrCallocLike now get the benefit of being able to deal with aligned_alloc as well transparently.

llvm/lib/Transforms/IPO/Attributor.cpp
4317

The code comment right under saying "alignment and size being constant" was sort of misplaced - I meant dropping it given where I had the extra guard (&&). Anyway, I'm fine with moving the guard inside.

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
4300

Actually, it need not be! :-) The alignment with the aligned_alloc call can be dynamic - it's just that we convert it to a stack allocation only when it's constant.

jdoerfert requested changes to this revision.Dec 15 2019, 9:16 PM

This test contains various changes in different parts of the code plus unrelated fixes (in comments, spelling, formatting, ...).

I think it is beneficial to have a patch that recognizes aligned_alloc, which should be testable through existing calls to isAllocLike, and one that teaches the transformations about it. All the unrelated NFC changes can go in as NFC patches before hand and without pre-review. Generally speaking, smaller patches are good. More practically, you now need reviewers that accept changes in various places. Granted, the changes are not complex in nature, but the general logic still applies.

I'll defer it to you and other reviewers on how you'd like this to be split once the changes are finalized.

Generally speaking again, if a reviewer ask to split a patch, it most often means they will not review the one they deem to big.

We should also determine if aligned_alloc is the only one we want to support in this family or not. I mean, there is stuff like posix_memalign, memalign, pvalloc, ...

posix_memalign is unfortunately very different - it doesn't return the pointer, but instead takes the address of the pointer as an argument. It's going to be quite non-trivial to support that AFAICS albeit it is similar to aligned_alloc on other aspects.

We could still encode the allocation nature and/or the alignment it if we deem it important enough. Though we will either need to introduce new attributes/logic, a load, or a wrapper. The TODO in the code is probably fine for this case.

valloc, pvalloc, memalign are all obsolete

I don't know what difference this really makes. FWIW, We recognize memalign/valloc already in some places but we don't treat them as allocators for some reason.

I think aligned_alloc will by itself really addresses a lot of use cases.

Sure. Getting all of them, especially if there is almost no extra cost, is still worth it. Not everybody writes C11 and/or updated their code.

This revision now requires changes to proceed.Dec 15 2019, 9:16 PM
jdoerfert added inline comments.Dec 15 2019, 9:21 PM
llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
4300

Actually, it need not be! :-) The alignment with the aligned_alloc call can be dynamic - it's just that we convert it to a stack allocation only when it's constant.

I am aware.

Please read my comment as:

For the cases where the alignment is a constant, which we can determine here since we are looking at the actual call, we should ...

I was not expecting this to be ambiguous given that the code you added will also only trigger if the size is a constant. Same thing, but with alignment is missing.

This test contains various changes in different parts of the code plus unrelated fixes (in comments, spelling, formatting, ...).

I think it is beneficial to have a patch that recognizes aligned_alloc, which should be testable through existing calls to isAllocLike, and one that teaches the transformations about it. All the unrelated NFC changes can go in as NFC patches before hand and without pre-review. Generally speaking, smaller patches are good. More practically, you now need reviewers that accept changes in various places. Granted, the changes are not complex in nature, but the general logic still applies.

Your earlier comment suggested splitting the heap to stack stuff from the rest. But what you suggest above appears to be different from that. For eg., InstCombine needs an isAlignedAllocLikeFn: would that go into the patch that "recognizes aligned_alloc" or the one that makes the transformations aware? If it's the former, I don't see why the heap to stack allocation should be split. If it's the latter, then there is really little that would go into the first patch that recognizes aligned_alloc and it would be logically incomplete. aligned_alloc is recognized via all of: MallocOrCallocLike, AlignedAllocLike, AllocLike, and AnyAlloc, and as such transformations are impacted the moment it's added to MemoryBuiltins. Separating the two is harder for reviewing FWIW. I'm happy to split it the way the reviewers prefer but frankly I don't think there is value in splitting this change list.

I think aligned_alloc will by itself really addresses a lot of use cases.

Sure. Getting all of them, especially if there is almost no extra cost, is still worth it. Not everybody writes C11 and/or updated their code.

Note that C++17 std::aligned_alloc() defers to C11's aligned_alloc().

This test contains various changes in different parts of the code plus unrelated fixes (in comments, spelling, formatting, ...).

I think it is beneficial to have a patch that recognizes aligned_alloc, which should be testable through existing calls to isAllocLike, and one that teaches the transformations about it. All the unrelated NFC changes can go in as NFC patches before hand and without pre-review. Generally speaking, smaller patches are good. More practically, you now need reviewers that accept changes in various places. Granted, the changes are not complex in nature, but the general logic still applies.

...

I agree with @jdoerfert, there are several patches here:

  • attributor,etc nfc changes
  • some basic TLI/MemBuiltins changse
  • attributor heap2stack changes
  • gvn changes
  • newgvn changes
  • instcombine attribute deduction changes

I don't know what difference this really makes. FWIW, We recognize memalign/valloc already in some places but we don't treat them as allocators for some reason.

Sure. Getting all of them, especially if there is almost no extra cost, is still worth it. Not everybody writes C11 and/or updated their code.

Reg. valloc, pvalloc: since these don't take an alignment argument, they are actually like malloc (as opposed to aligned_alloc) in nearly all cases except the heap to stack conversion. But this unfortunately means that they'll need another isPVallocLike/isVallocLike. So, modeling them is as much additional cost/code as this changelist I believe. Should be done separately if it's worth it.

bondhugula marked an inline comment as done.Dec 16 2019, 5:09 PM
bondhugula added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
4300

But should we be adding an attribute for something that by itself is already a constant operand? A pass can't possibly rely on the attribute and would anyway need to look at the operand. More importantly, if the alignment operand is updated (although there isn't such a case), the attribute would have to be kept in sync. So, do we need such redundancy? (dereferenceable_or_null attr is different in all these regards.)

bondhugula added a comment.EditedDec 16 2019, 6:10 PM

I agree with @jdoerfert, there are several patches here:

  • attributor,etc nfc changes
  • some basic TLI/MemBuiltins changse
  • attributor heap2stack changes
  • gvn changes
  • newgvn changes
  • instcombine attribute deduction changes

The TLI / MemoryBuiltins changes will themselves have an impact on transformations like dead store elimination via basicaa -- since MallocOrCallocLike, AllocLike, AnyAlloc will now reflect knowledge of aligned_alloc. Would you still want to split it into these pieces given that the patches don't isolate the impact on transformations?

This has been split - first patch is D76970.

bondhugula retitled this revision from Support for library function aligned_alloc to Introduce support for lib function aligned_alloc.Mar 27 2020, 11:33 PM
bondhugula abandoned this revision.Mar 29 2020, 10:05 PM

This has been split into five patches ending with D76976.