Support for library function aligned_alloc in TLI / memory builtins

[bondhugula]

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. This patch introduces aligned_alloc
in target library info and memory builtins. Subsequent ones will
make other passes aware and fix https://bugs.llvm.org/show_bug.cgi?id=44062

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 glibc malloc.

Signed-off-by: Uday Bondhugula <[e-mail]>

[bondhugula]

clang-format missed changes

[bondhugula]

Fix inadvertent format changes

llvm/include/llvm/Analysis/MemoryBuiltins.h

 /// allocates uninitialized memory (such as malloc).
 bool isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
                     bool LookThroughBitCast = false);
 bool isMallocLikeFn(const Value *V,
                     function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
                     bool LookThroughBitCast = false);
 
 /// Tests if a value is a call or invoke to a library function that
+/// allocates uninitialized memory with alignment (such as aligned_alloc).
+bool isAlignedAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
+                          bool LookThroughBitCast = false);
+bool isAlignedAllocLikeFn(
+    const Value *V, function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
+    bool LookThroughBitCast = false);
+
+/// Tests if a value is a call or invoke to a library function that
 /// allocates zero-filled memory (such as calloc).
 bool isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
                     bool LookThroughBitCast = false);
 
 /// Tests if a value is a call or invoke to a library function that
 /// allocates memory similar to malloc or calloc.
 bool isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
                             bool LookThroughBitCast = false);

llvm/include/llvm/Analysis/TargetLibraryInfo.def

 TLI_DEFINE_ENUM_INTERNAL(acoshf)
 TLI_DEFINE_STRING_INTERNAL("acoshf")
 /// long double acoshl(long double x);
 TLI_DEFINE_ENUM_INTERNAL(acoshl)
 TLI_DEFINE_STRING_INTERNAL("acoshl")
 /// long double acosl(long double x);
 TLI_DEFINE_ENUM_INTERNAL(acosl)
 TLI_DEFINE_STRING_INTERNAL("acosl")
+/// void *aligned_alloc(size_t alignment, size_t size);
+TLI_DEFINE_ENUM_INTERNAL(aligned_alloc)
+TLI_DEFINE_STRING_INTERNAL("aligned_alloc")
 /// double asin(double x);
 TLI_DEFINE_ENUM_INTERNAL(asin)
 TLI_DEFINE_STRING_INTERNAL("asin")
 /// float asinf(float x);
 TLI_DEFINE_ENUM_INTERNAL(asinf)
 TLI_DEFINE_STRING_INTERNAL("asinf")
 /// double asinh(double x);
 TLI_DEFINE_ENUM_INTERNAL(asinh)

llvm/lib/Analysis/BasicAliasAnalysis.cpp

if (!isa<Constant>(Object) && Call != Object &&
     // Early return if we improved mod ref information
     if (!isModAndRefSet(Result)) {
       if (isNoModRef(Result))
         return ModRefInfo::NoModRef;
       return IsMustAlias ? setMust(Result) : clearMust(Result);
     }
   }
 
-  // If the call is to malloc or calloc, we can assume that it doesn't
+  // If the call is malloc/calloc like, we can assume that it doesn't
   // modify any IR visible value.  This is only valid because we assume these
   // routines do not read values visible in the IR.  TODO: Consider special
   // casing realloc and strdup routines which access only their arguments as
   // well.  Or alternatively, replace all of this with inaccessiblememonly once
   // that's implemented fully.
   if (isMallocOrCallocLikeFn(Call, &TLI)) {
     // Be conservative if the accessed pointer may alias the allocation -
     // fallback to the generic handling below.

llvm/lib/Analysis/MemoryBuiltins.cpp

 #include <iterator>
 #include <utility>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "memory-builtins"
 
 enum AllocType : uint8_t {
   OpNewLike          = 1<<0, // allocates; never returns null
   MallocLike         = 1<<1 | OpNewLike, // allocates; may return null
-  CallocLike         = 1<<2, // allocates + bzero
-  ReallocLike        = 1<<3, // reallocates
-  StrDupLike         = 1<<4,
-  MallocOrCallocLike = MallocLike | CallocLike,
-  AllocLike          = MallocLike | CallocLike | StrDupLike,
+  AlignedAllocLike   = 1<<2, // allocates with alignment; may return null
+  CallocLike         = 1<<3, // allocates + bzero
+  ReallocLike        = 1<<4, // reallocates
+  StrDupLike         = 1<<5,
+  MallocOrCallocLike = MallocLike | CallocLike | AlignedAllocLike,
+  AllocLike          = MallocOrCallocLike | StrDupLike,
   AnyAlloc           = AllocLike | ReallocLike
 };
 
 struct AllocFnsTy {
   AllocType AllocTy;
   unsigned NumParams;
   // First and Second size parameters (or -1 if unused)
   int FstParam, SndParam;
 };
 
 // FIXME: certain users need more information. E.g., SimplifyLibCalls needs to
 // know which functions are nounwind, noalias, nocapture parameters, etc.
 static const std::pair<LibFunc, AllocFnsTy> AllocationFnData[] = {
   {LibFunc_malloc,              {MallocLike,  1, 0,  -1}},
   {LibFunc_valloc,              {MallocLike,  1, 0,  -1}},
   {LibFunc_Znwj,                {OpNewLike,   1, 0,  -1}}, // new(unsigned int)
   {LibFunc_ZnwjRKSt9nothrow_t,  {MallocLike,  2, 0,  -1}}, // new(unsigned int, nothrow)
   {LibFunc_ZnwjSt11align_val_t, {OpNewLike,   2, 0,  -1}}, // new(unsigned int, align_val_t)
   {LibFunc_ZnwjSt11align_val_tRKSt9nothrow_t, // new(unsigned int, align_val_t, nothrow)
                                 {MallocLike,  3, 0,  -1}},
   {LibFunc_Znwm,                {OpNewLike,   1, 0,  -1}}, // new(unsigned long)
   {LibFunc_ZnwmRKSt9nothrow_t,  {MallocLike,  2, 0,  -1}}, // new(unsigned long, nothrow)
static const std::pair<LibFunc, AllocFnsTy> AllocationFnData[] = {
   {LibFunc_msvc_new_int,         {OpNewLike,   1, 0,  -1}}, // new(unsigned int)
   {LibFunc_msvc_new_int_nothrow, {MallocLike,  2, 0,  -1}}, // new(unsigned int, nothrow)
   {LibFunc_msvc_new_longlong,         {OpNewLike,   1, 0,  -1}}, // new(unsigned long long)
   {LibFunc_msvc_new_longlong_nothrow, {MallocLike,  2, 0,  -1}}, // new(unsigned long long, nothrow)
   {LibFunc_msvc_new_array_int,         {OpNewLike,   1, 0,  -1}}, // new[](unsigned int)
   {LibFunc_msvc_new_array_int_nothrow, {MallocLike,  2, 0,  -1}}, // new[](unsigned int, nothrow)
   {LibFunc_msvc_new_array_longlong,         {OpNewLike,   1, 0,  -1}}, // new[](unsigned long long)
   {LibFunc_msvc_new_array_longlong_nothrow, {MallocLike,  2, 0,  -1}}, // new[](unsigned long long, nothrow)
+  {LibFunc_aligned_alloc,       {AlignedAllocLike, 2, 1,  -1}},
   {LibFunc_calloc,              {CallocLike,  2, 0,   1}},
   {LibFunc_realloc,             {ReallocLike, 2, 1,  -1}},
   {LibFunc_reallocf,            {ReallocLike, 2, 1,  -1}},
   {LibFunc_strdup,              {StrDupLike,  1, -1, -1}},
   {LibFunc_strndup,             {StrDupLike,  2, 1,  -1}}
   // TODO: Handle "int posix_memalign(void **, size_t, size_t)"
 };
 

 bool llvm::isMallocLikeFn(
     const Value *V, function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
     bool LookThroughBitCast) {
   return getAllocationData(V, MallocLike, GetTLI, LookThroughBitCast)
       .hasValue();
 }
 
 /// Tests if a value is a call or invoke to a library function that
+/// allocates uninitialized memory with alignment (such as aligned_alloc).
+bool llvm::isAlignedAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
+                                bool LookThroughBitCast) {
+  return getAllocationData(V, AlignedAllocLike, TLI, LookThroughBitCast)
+      .hasValue();
+}
+bool llvm::isAlignedAllocLikeFn(
+    const Value *V, function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
+    bool LookThroughBitCast) {
+  return getAllocationData(V, AlignedAllocLike, GetTLI, LookThroughBitCast)
+      .hasValue();
+}
+
+/// Tests if a value is a call or invoke to a library function that
 /// allocates zero-filled memory (such as calloc).
 bool llvm::isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
                           bool LookThroughBitCast) {
   return getAllocationData(V, CallocLike, TLI, LookThroughBitCast).hasValue();
 }
 
 /// Tests if a value is a call or invoke to a library function that
 /// allocates memory similar to malloc or calloc.

llvm/lib/Analysis/TargetLibraryInfo.cpp

bool TargetLibraryInfoImpl::isValidProtoForLibFunc(const FunctionType &FTy,
   case LibFunc_rename:
     return (NumParams >= 2 && FTy.getParamType(0)->isPointerTy() &&
             FTy.getParamType(1)->isPointerTy());
   case LibFunc_readlink:
     return (NumParams >= 2 && FTy.getParamType(0)->isPointerTy() &&
             FTy.getParamType(1)->isPointerTy());
   case LibFunc_write:
     return (NumParams == 3 && FTy.getParamType(1)->isPointerTy());
+  case LibFunc_aligned_alloc:
+    return (NumParams == 2 && FTy.getReturnType()->isPointerTy());
   case LibFunc_bcopy:
   case LibFunc_bcmp:
     return (NumParams == 3 && FTy.getParamType(0)->isPointerTy() &&
             FTy.getParamType(1)->isPointerTy());
   case LibFunc_bzero:
     return (NumParams == 2 && FTy.getParamType(0)->isPointerTy());
   case LibFunc_calloc:
     return (NumParams == 2 && FTy.getReturnType()->isPointerTy());

llvm/lib/Transforms/Utils/BuildLibCalls.cpp

case LibFunc_readlink:
     Changed |= setDoesNotCapture(F, 1);
     Changed |= setOnlyReadsMemory(F, 0);
     return Changed;
   case LibFunc_write:
     // May throw; "write" is a valid pthread cancellation point.
     Changed |= setDoesNotCapture(F, 1);
     Changed |= setOnlyReadsMemory(F, 1);
     return Changed;
+  case LibFunc_aligned_alloc:
+    Changed |= setDoesNotThrow(F);
+    Changed |= setRetDoesNotAlias(F);
+    return Changed;
   case LibFunc_bcopy:
     Changed |= setDoesNotThrow(F);
     Changed |= setDoesNotCapture(F, 0);
     Changed |= setDoesNotCapture(F, 1);
     Changed |= setOnlyReadsMemory(F, 0);
     return Changed;
   case LibFunc_bcmp:
     Changed |= setDoesNotThrow(F);

llvm/test/Transforms/DeadStoreElimination/simple.ll

;
   store i32 %DEAD2, i32 addrspace(1)* %P
   call void @test13f( )
   store i32 0, i32 addrspace(1)* %P
   ret i32 addrspace(1)* %P
 }
 
 declare noalias i8* @malloc(i32)
 declare noalias i8* @calloc(i32, i32)
+declare noalias i8* @aligned_alloc(i32, i32)
+declare void @free(i8*)
 
 
 define void @test14(i32* %Q) {
 ; CHECK-LABEL: @test14(
 ; CHECK-NEXT:    ret void
 ;
   %P = alloca i32
   %DEAD = load i32, i32* %Q
   store i32 %DEAD, i32* %P
   ret void
 
 }
 
+; Dead store on an aligned_alloc: should know that %M doesn't alias with %A.
+define i32 @test14a(i8* %M, i8 %value) {
+; CHECK-LABEL: @test14a(
+; CHECK-NOT: store
+; CHECK:     ret i32 0
+;
+  %A = tail call i8* @aligned_alloc(i32 32, i32 1024)
+  store i8 %value, i8* %A
+  tail call void @free(i8* %A)
+  ret i32 0
+}
 
 ; PR8701
 
 ;; Fully dead overwrite of memcpy.
 define void @test15(i8* %P, i8* %Q) nounwind ssp {
 ; CHECK-LABEL: @test15(
 ; CHECK-NEXT:    tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* [[P:%.*]], i8* [[Q:%.*]], i64 12, i1 false)
 ; CHECK-NEXT:    ret void

llvm/unittests/Analysis/TargetLibraryInfoTest.cpp

parseAssembly(
       "declare i32 @abs(i32)\n"
       "declare i32 @access(i8*, i32)\n"
       "declare double @acos(double)\n"
       "declare float @acosf(float)\n"
       "declare double @acosh(double)\n"
       "declare float @acoshf(float)\n"
       "declare x86_fp80 @acoshl(x86_fp80)\n"
       "declare x86_fp80 @acosl(x86_fp80)\n"
+      "declare i8* @aligned_alloc(i64, i64)\n"
       "declare double @asin(double)\n"
       "declare float @asinf(float)\n"
       "declare double @asinh(double)\n"
       "declare float @asinhf(float)\n"
       "declare x86_fp80 @asinhl(x86_fp80)\n"
       "declare x86_fp80 @asinl(x86_fp80)\n"
       "declare double @atan(double)\n"
       "declare double @atan2(double, double)\n"
parseAssembly(
       "declare float @exp10f(float)\n"
       "declare x86_fp80 @exp10l(x86_fp80)\n"
 
       // These printf variants have the same prototype as the non-'i' versions.
       "declare i32 @fiprintf(%struct*, i8*, ...)\n"
       "declare i32 @iprintf(i8*, ...)\n"
       "declare i32 @siprintf(i8*, i8*, ...)\n"
 
       // __small_printf variants have the same prototype as the non-'i' versions.
       "declare i32 @__small_fprintf(%struct*, i8*, ...)\n"
       "declare i32 @__small_printf(i8*, ...)\n"
       "declare i32 @__small_sprintf(i8*, i8*, ...)\n"
 
       "declare i32 @htonl(i32)\n"
       "declare i16 @htons(i16)\n"
       "declare i32 @ntohl(i32)\n"
       "declare i16 @ntohs(i16)\n"
parseAssembly(
       "declare double @__log_finite(double)\n"
       "declare float @__logf_finite(float)\n"
       "declare x86_fp80 @__logl_finite(x86_fp80)\n"
       "declare double @__pow_finite(double, double)\n"
       "declare float @__powf_finite(float, float)\n"
       "declare x86_fp80 @__powl_finite(x86_fp80, x86_fp80)\n"
       "declare double @__sinh_finite(double)\n"
       "declare float @__sinhf_finite(float)\n"
       "declare x86_fp80 @__sinhl_finite(x86_fp80)\n"
       );
 
   for (unsigned FI = 0; FI != LibFunc::NumLibFuncs; ++FI) {
     LibFunc LF = (LibFunc)FI;
     // Make sure everything is available; we're not testing target defaults.
     TLII.setAvailable(LF);
     Function *F = M->getFunction(TLI.getName(LF));
     EXPECT_TRUE(isLibFunc(F, LF));
   }
 }