[Clang] Propagate guaranteed alignment for malloc and others

[xbolva00]

Summary

LLVM should be smarter about *known* malloc's alignment and this knowledge may enable other optimizations.

Originally started as LLVM patch - https://reviews.llvm.org/D100862 but this logic should be really in Clang.

[xbolva00]

If this approach makes sense, I will update / add tests.

[xbolva00]

clang/lib/CodeGen/CGCall.cpp

2059

As a followup, I need to teach Clang about aligned_alloc and memalign.

[lebedev.ri]

clang/lib/CodeGen/CGCall.cpp

2060

malloc != new

[xbolva00]

clang/lib/CodeGen/CGCall.cpp

2060

But the comment for the implementation of this value points on eg. gcc's docs:

https://clang.llvm.org/doxygen/Basic_2TargetInfo_8cpp_source.html line 67

// From the glibc documentation, on GNU systems, malloc guarantees 16-byte
// alignment on 64-bit systems and 8-byte alignment on 32-bit systems. See
// https://www.gnu.org/software/libc/manual/html_node/Malloc-Examples.html.
// This alignment guarantee also applies to Windows and Android. On Darwin,
// the alignment is 16 bytes on both 64-bit and 32-bit systems.

So this value is correct to be used for malloc and friends IMHO.

[xbolva00]

GCC already knows about this guaranteed alignment, check:
https://godbolt.org/z/sxn6K7Yq7

Alignment checks were optimized out. I can confirm that with this patch we do same.

[rjmccall]

Please addd tests, including tests that we suppress this assumption under e.g. -fno-builtin-malloc

[xbolva00]

Added tests

[xbolva00]

In D100879#2703979, @rjmccall wrote:

Please addd tests, including tests that we suppress this assumption under e.g. -fno-builtin-malloc

Done

[xbolva00]

Handle also aligned_alloc and memalign.

[xbolva00]

Fixed small typo in tests.

[rjmccall]

Test looks good, thanks.

clang/lib/CodeGen/CGCall.cpp

2060

There's no immediate reason to have two different methods, but we should at least update the comment on getNewAlign to document that we're assuming it describes both operator new and malloc.

[xbolva00]

Updated comment for

getNewAlign()

[rjmccall]

Thanks, LGTM.

[dmgreen]

Hello. Nice idea. Unfortunately this blocks tail folding, making codesize a bit bigger: https://godbolt.org/z/rncPvbh8d
I'm guessing it shouldn't? But the attribute isn't handled somewhere along the way. Any ideas where?

[xbolva00]

In D100879#2714431, @dmgreen wrote:

Hello. Nice idea. Unfortunately this blocks tail folding, making codesize a bit bigger: https://godbolt.org/z/rncPvbh8d
I'm guessing it shouldn't? But the attribute isn't handled somewhere along the way. Any ideas where?

Hmm.. I know probably where to fix it.

diff --git a/llvm/lib/CodeGen/Analysis.cpp b/llvm/lib/CodeGen/Analysis.cpp
index 5d1b00463dc8..425e1b4e8e2d 100644
--- a/llvm/lib/CodeGen/Analysis.cpp
+++ b/llvm/lib/CodeGen/Analysis.cpp
@@ -560,6 +560,8 @@ bool llvm::attributesPermitTailCall(const Function *F, const Instruction *I,
 
   // Following attributes are completely benign as far as calling convention
   // goes, they shouldn't affect whether the call is a tail call.
+  CallerAttrs.removeAttribute(Attribute::Alignment);
+  CalleeAttrs.removeAttribute(Attribute::Alignment);
   CallerAttrs.removeAttribute(Attribute::NoAlias);
   CalleeAttrs.removeAttribute(Attribute::NoAlias);
   CallerAttrs.removeAttribute(Attribute::NonNull);

Your testcase works for me with this modification.

Inspiration: https://github.com/llvm/llvm-project/commit/62ad2128255877ed41c714366861eee9c1da30dd

If you want you can fix it (or I can do that later today).

[collares]

In https://bugzilla.mozilla.org/show_bug.cgi?id=1741454, oxalica discovered this breaks jemalloc-using code, since jemalloc does not guarantee 16-byte alignment.

[xbolva00]

In D100879#3144751, @collares wrote:

In https://bugzilla.mozilla.org/show_bug.cgi?id=1741454, oxalica discovered this breaks jemalloc-using code, since jemalloc does not guarantee 16-byte alignment.

Not sure if jemalloc does the right thing here. (See comment above getNewAlign). You can force 16-byte alignment by configuring with --with-lg-quantum=4.

[collares]

Reproducing oxalica's comment at https://github.com/NixOS/nixpkgs/pull/146817, to make sure it is not missed:

"The divergence here is about how to understand the sentence from C17, 7.22.3. There is already an proposal rephrasing it and making it clear that 8-byte allocation CAN result in only 8-byte alignment, not 16-byte-aligned. It also mentions that forcing jemalloc to have 16-byte alignment will significantly slow down its performance.
http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2293.htm

This N2293 is already accepted in the latest working draft, and should be present in the next C2x standard. Clang should eventually change to support it."

[xbolva00]

Just curious, did you try firefox with rpmalloc? (If you care about the best performance).

“ It also mentions that forcing jemalloc to have 16-byte alignment will significantly slow down its performance.”

It would be interesting to see real world data, like firefox benchmarks. glibc and macOS defaults to 16-byte alignment and I think they have good reasons too.

[rjmccall]

Platforms are permitted to make stronger guarantees than the C standard requires, and it is totally reasonable for compilers to assume that malloc meets the target platform's documented guarantees. Arguably, libraries should not be replacing malloc if they fail to meet the platform's documented guarantees.

With that said, it's probably not unreasonable for Clang to provide an option that controls its assumptions about malloc. We should think somewhat carefully about whether there are other behaviors we'd want to include in that, though.

[jyknight]

I think this patch was wrong -- we should not be assuming 16-byte alignment for an allocation smaller than 16 bytes.

[davidtgoldblatt]

(For background: I'm a jemalloc maintainer and wrote N2293).

In D100879#3145361, @rjmccall wrote:

Platforms are permitted to make stronger guarantees than the C standard requires, and it is totally reasonable for compilers to assume that malloc meets the target platform's documented guarantees. Arguably, libraries should not be replacing malloc if they fail to meet the platform's documented guarantees.

I agree generally that assuming platform guarantees is reasonable for the compiler in targeting that platform, but I don't think I agree that the dlmalloc alignment is one of them. Supporting malloc replacement is a first-class feature for glibc malloc, and related projects avoid relying on alignment guarantees (e.g. libstdc++ at one point considered assuming that 8-byte allocs were 16-byte aligned, and decided not to). At least one Linux distribution using clang (Alpine) uses musl, which is a weak-alignment implementation (contrary to what I claimed in N2293; I screwed up my background research).

With that said, it's probably not unreasonable for Clang to provide an option that controls its assumptions about malloc. We should think somewhat carefully about whether there are other behaviors we'd want to include in that, though.

This makes sense to me; this is broadly how clang handles operator new alignment as well.

[fhahn]

Someone filed https://github.com/llvm/llvm-project/issues/53540, which covers some of the issues also discussed here.

clang/include/clang/Basic/TargetInfo.h

public:
 
   /// getMinGlobalAlign - Return the minimum alignment of a global variable,
   /// unless its alignment is explicitly reduced via attributes.
   virtual unsigned getMinGlobalAlign (uint64_t) const {
     return MinGlobalAlign;
   }
 
   /// Return the largest alignment for which a suitably-sized allocation with
-  /// '::operator new(size_t)' is guaranteed to produce a correctly-aligned
-  /// pointer.
+  /// '::operator new(size_t)' or 'malloc' is guaranteed to produce a
+  /// correctly-aligned pointer.
   unsigned getNewAlign() const {
     return NewAlign ? NewAlign : std::max(LongDoubleAlign, LongLongAlign);
   }
 
   /// getWCharWidth/Align - Return the size of 'wchar_t' for this target, in
   /// bits.
   unsigned getWCharWidth() const { return getTypeWidth(WCharType); }
   unsigned getWCharAlign() const { return getTypeAlign(WCharType); }

clang/lib/CodeGen/CGCall.cpp

         if (Fn->isNoReturn())
           FuncAttrs.addAttribute(llvm::Attribute::NoReturn);
         NBA = Fn->getAttr<NoBuiltinAttr>();
       }
       // Only place nomerge attribute on call sites, never functions. This
       // allows it to work on indirect virtual function calls.
       if (AttrOnCallSite && TargetDecl->hasAttr<NoMergeAttr>())
         FuncAttrs.addAttribute(llvm::Attribute::NoMerge);
+
+      // Add known guaranteed alignment for allocation functions.
+      if (unsigned BuiltinID = Fn->getBuiltinID()) {
+        switch (BuiltinID) {
+        case Builtin::BIaligned_alloc:
+        case Builtin::BIcalloc:
+        case Builtin::BImalloc:
+        case Builtin::BImemalign:
+        case Builtin::BIrealloc:
+        case Builtin::BIstrdup:
+        case Builtin::BIstrndup:
+          RetAttrs.addAlignmentAttr(Context.getTargetInfo().getNewAlign() /
+                                    Context.getTargetInfo().getCharWidth());
+          break;
+        default:
+          break;
+        }
+      }
     }
 
     // 'const', 'pure' and 'noalias' attributed functions are also nounwind.
     if (TargetDecl->hasAttr<ConstAttr>()) {
       FuncAttrs.addAttribute(llvm::Attribute::ReadNone);
       FuncAttrs.addAttribute(llvm::Attribute::NoUnwind);
       // gcc specifies that 'const' functions have greater restrictions than
       // 'pure' functions, so they also cannot have infinite loops.

clang/test/CodeGen/alloc-fns-alignment.c

+// RUN: %clang_cc1 -triple x86_64-unknown-linux-gnu -emit-llvm < %s | FileCheck %s --check-prefix=ALIGN16
+// RUN: %clang_cc1 -triple x86_64-windows-msvc      -emit-llvm < %s | FileCheck %s --check-prefix=ALIGN16
+// RUN: %clang_cc1 -triple i386-apple-darwin        -emit-llvm < %s | FileCheck %s --check-prefix=ALIGN16
+// RUN: %clang_cc1 -triple i386-unknown-linux-gnu   -emit-llvm < %s | FileCheck %s --check-prefix=ALIGN8
+// RUN: %clang_cc1 -triple x86_64-unknown-linux-gnu -fno-builtin-malloc  -emit-llvm < %s  | FileCheck %s --check-prefix=NOBUILTIN-MALLOC
+// RUN: %clang_cc1 -triple x86_64-unknown-linux-gnu -fno-builtin-calloc  -emit-llvm < %s  | FileCheck %s --check-prefix=NOBUILTIN-CALLOC
+// RUN: %clang_cc1 -triple x86_64-unknown-linux-gnu -fno-builtin-realloc -emit-llvm < %s  | FileCheck %s --check-prefix=NOBUILTIN-REALLOC
+
+typedef __SIZE_TYPE__ size_t;
+
+void *malloc(size_t);
+void *calloc(size_t, size_t);
+void *realloc(void *, size_t);
+
+void *malloc_test(size_t n) {
+  return malloc(n);
+}
+
+void *calloc_test(size_t n) {
+  return calloc(1, n);
+}
+
+void *raalloc_test(void *p, size_t n) {
+  return realloc(p, n);
+}
+
+// ALIGN16: align 16 i8* @malloc
+// ALIGN16: align 16 i8* @calloc
+// ALIGN16: align 16 i8* @realloc
+// ALIGN8: align 8 i8* @malloc
+// ALIGN8: align 8 i8* @calloc
+// ALIGN8: align 8 i8* @realloc
+// NOBUILTIN-MALLOC: declare i8* @malloc
+// NOBUILTIN-CALLOC: declare i8* @calloc
+// NOBUILTIN-REALLOC: declare i8* @realloc