[Attributor] Heap2stack doesn't handle alignment correctly

[jyknight]

Attributor's heap2stack pass does not preserve alignment of allocations correctly.

E.g., look at the checked-in test-case llvm/test/Transforms/Attributor/heap_to_stack.ll which creates an under-aligned alloca i8,i64 4, align 1 from malloc(4):

define void @test3() {
; IS________NPM-LABEL: define {{[^@]+}}@test3() {
; IS________NPM-NEXT:    [[TMP1:%.*]] = alloca i8, i64 4, align 1
; IS________NPM-NEXT:    tail call void @no_sync_func(i8* noalias nocapture nofree [[TMP1]])
; IS________NPM-NEXT:    ret void
;
  %1 = tail call noalias i8* @malloc(i64 4)
  tail call void @no_sync_func(i8* %1)
  tail call void @free(i8* %1)
  ret void
}

Conversation forked from @durin42's alignment attributes proposal https://discourse.llvm.org/t/rfc-attributes-for-allocator-functions-in-llvm-ir/61464 which mentioned:

Note that for a function with an implied alignment like malloc we can’t determine the alignment, nor can we trust the align attribute because that is semantically an _under_estimate of the alignment returned by the function. Rather, we should be using an _over_estimate of the alignment promised to users instead. This bug is present in the existing heap-to-stack logic in the Attributor, and is not addressed or affected by this proposal. Fortunately, the heap2stack logic in the Attributor is not included in the set of default passes (though it does run for OpenMP code.)

And to which @jdoerfert replied:

Given that it is run we should take this as a bug and seriously. I suppose we have to give up on h2s if getAllocAlignment is returning a nullptr, right?

That would work, though note that getAllocAlignment only deals with alignment-specified-as-a-parameter; the most common allocator calls don't have a alignment parameter, so that would make this optimization pass nearly never apply.

Can we teach it about the default alignment of known runtime functions? So spec seems to say malloc returns a pointer aligned properly for any built-in type, which seems to be something we could know (in clang).

Right -- we can't correctly use the "align" attribute on the return value to determine the required alignment, but we provide some other data. The problem is, malloc's alignment rules are rather complicated. The current Standard's rule is that malloc returns memory which is required to be sufficiently-aligned for any fundamental object that fits within the requested size (thus: malloc(1) only needs 1-byte alignment, while malloc(16) might require 16-byte alignment).

We could hardcode that rule, though that's a little ugly.

Of course, on some implementations, malloc always provides the same alignment (e.g. 16-byte), rather than following the size. On some other implementations, it may follow the size only down to some minimum alignment (e.g. 8 bytes). On such implementations, could a program validly depend on those additional implementation-defined semantics? (That is: may Clang break code saying void*x = malloc(1); assert((x & 0x4) == 0); by providing only alignment 1 -- even if the libc implementation in use may always provide higher alignment?)

[jdoerfert]

OpenMP (for GPUs) relies on Heap-2-Stack heavily but there we have a custom allocator with alignment annotated by clang. So requiring getAllocAlignment will at least not make it useless for that case. We could also default to min(bytes, 16) alignment with a command line option to get always N bytes at least, or no heap-2-stack if alignment is unknown.

All that said, I will probably implement one of these soon to lower the risk of things breaking if used. Then we should still consider a way to make getAllocAlignment aware of common allocators or add align to them in clang with an escape hatch for custom implementations.

[davidbolvansky]

Probably it makes sense to reimplement https://reviews.llvm.org/D118804 with additional check “NewAlign >= AllocSize”.

[jyknight]

I don't think that's a solution.

Using the align attribute on the return value to derive an allocation's REQUIRED minimum alignment seems just semantically invalid, as far as I can see. The align attribute is only a guarantee that the pointer value has at least the alignment specified. It should always be valid to drop it or reduce it.