Change AllocType representation to be more general

[Bryce-MW]

Summary

The existing AllocType enum only allows for functions which emulate C-style allocators. The users of AllocType are generally only interested in one specific propery of the allocator. These changes don't make a difference currently but it opens future allocators that work differently. There are also some versions of operator new that take alignment values. They can not be added now because of some hardcoding of arguement positions. Which brings me to the caveat of this change which is that there are a number of places where the "like" functions are hardcoded to have arguments in specific positions. I'll add a comment with where those are. I'm happy to work on those but I wanted to hear if this new design of AllocType is even desired before I put in the effort.

[Bryce-MW]

Here are the places where there are hardcoded argument positions or other special cases that will need to be updated.

Heap-To-Stack Conversion in llvm/lib/Transforms/IPO/AttributorAttributes.cpp has hardcoded argument positions. It supports malloc, calloc, and aligned_alloc but the position of the arguments is hardcoded. Needs separate fields for allocated value (to determine if memset is needed), if the allocation is aligned (and position of alignment arg which we don't have), and the positions of the two size args. This will be a larger refactor so I will do it later.

InstCombinerImpl::annotateAnyAllocSite in llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp hardcodes which arguments it looks at and hardcodes special cases for strdup and strndup.

ObjectSizeOffsetVisitor::visitCallBase in llvm/lib/Analysis/MemoryBuiltins.cpp has special-casing for strdup and strndup. Could also possibly work on the TODO there.

For line 1005 of llvm/lib/Analysis/BasicAliasAnalysis.cpp, is inaccessiblememonly implemented? It's mentioned on the IR documentation page as if it is. This would be better than the current call which would need to have the mentioned special case put in (and we would need to require that allocation functions must have inaccessiblememonly semantics anyway). Same thing with visitCallBase in llvm/lib/Analysis/CFLGraph.h

llvm/include/llvm/Analysis/MemoryBuiltins.h

 
 /// Tests if a value is a call or invoke to a function that returns a
 /// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions).
 bool isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI,
                  bool LookThroughBitCast = false);
 
 /// Tests if a value is a call or invoke to a library function that
 /// allocates uninitialized memory (such as malloc).
+bool isUndefAllocFn(const Value *V, const TargetLibraryInfo *TLI,
+                    bool LookThroughBitCast = false);
+bool isUndefAllocFn(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-initialized memory (such as calloc).
+bool isZeroAllocFn(const Value *V, const TargetLibraryInfo *TLI,
+                   bool LookThroughBitCast = false);
+bool isZeroAllocFn(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 (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).

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
-  AlignedAllocLike   = 1<<2, // allocates with alignment; may return null
-  CallocLike         = 1<<3, // allocates + bzero
-  ReallocLike        = 1<<4, // reallocates
-  StrDupLike         = 1<<5,
+  // Because there is a bit for nullable but not never-null, it is possible to
+  // ask if a function is never null and if it is either never null or nullable.
+  // I did this because I ran out of bits and this is how the previous version
+  // of this enum worked (MallocLike acted as a subtype of OpNewLike)
+  Nullable = 1 << 0, // can return null on failed allocation (like malloc)
+
+  ArgAlign = 1 << 1,   // aligns to argument specified value (like memalign)
+  OtherAlign = 1 << 2, // alignment not based on argument
+
+  UndefAlloc = 1 << 3, // allocated memory is undefined (like malloc)
+  ZeroAlloc = 1 << 4,  // allocated memory is set to 0 (like calloc)
+  OtherAlloc = 1 << 5, // allocated memory is defined but not 0 (like strdup)
+
+  Realloc = 1 << 6,    // changes an existing allocation size (like realloc)
+  NotRealloc = 1 << 7, // doesn't reallocate memory
+
+  OpNewLike = OtherAlign | UndefAlloc | NotRealloc,
+  MallocLike = Nullable | OtherAlign | UndefAlloc | NotRealloc,
+  AlignedAllocLike = Nullable | ArgAlign | UndefAlloc | NotRealloc,
+  CallocLike = Nullable | OtherAlign | ZeroAlloc | NotRealloc,
+  ReallocLike = Nullable | OtherAlign | UndefAlloc | Realloc,
+  StrDupLike = Nullable | OtherAlign | OtherAlloc | NotRealloc,
+
   MallocOrCallocLike = MallocLike | CallocLike | AlignedAllocLike,
-  AllocLike          = MallocOrCallocLike | StrDupLike,
-  AnyAlloc           = AllocLike | ReallocLike
+  AllocLike = MallocOrCallocLike | StrDupLike,
+  AnyAlloc = AllocLike | ReallocLike,
+
+  UndefAllocFn = Nullable | ArgAlign | OtherAlign | UndefAlloc | NotRealloc,
+  ZeroAllocFn = Nullable | ArgAlign | OtherAlign | ZeroAlloc | NotRealloc,
 };
 
 struct AllocFnsTy {
   AllocType AllocTy;
   unsigned NumParams;
   // First and Second size parameters (or -1 if unused)
   int FstParam, SndParam;
 };
bool llvm::isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI,
   // it's safe to consider realloc as noalias since accessing the original
   // pointer is undefined behavior
   return isAllocationFn(V, TLI, LookThroughBitCast) ||
          hasNoAliasAttr(V, LookThroughBitCast);
 }
 
 /// Tests if a value is a call or invoke to a library function that
 /// allocates uninitialized memory (such as malloc).
+bool llvm::isUndefAllocFn(const Value *V, const TargetLibraryInfo *TLI,
+                          bool LookThroughBitCast) {
+  return getAllocationData(V, UndefAllocFn, TLI, LookThroughBitCast).hasValue();
+}
+bool llvm::isUndefAllocFn(
+    const Value *V, function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
+    bool LookThroughBitCast) {
+  return getAllocationData(V, UndefAllocFn, GetTLI, LookThroughBitCast)
+      .hasValue();
+}
+
+/// Tests if a value is a call or invoke to a library function that
+/// allocates zero-initialized memory (such as calloc).
+bool llvm::isZeroAllocFn(const Value *V, const TargetLibraryInfo *TLI,
+                         bool LookThroughBitCast) {
+  return getAllocationData(V, ZeroAllocFn, TLI, LookThroughBitCast).hasValue();
+}
+bool llvm::isZeroAllocFn(
+    const Value *V, function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
+    bool LookThroughBitCast) {
+  return getAllocationData(V, ZeroAllocFn, GetTLI, LookThroughBitCast)
+      .hasValue();
+}
+
+/// Tests if a value is a call or invoke to a library function that
+/// allocates uninitialized memory (such as malloc).
 bool llvm::isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
                           bool LookThroughBitCast) {
   return getAllocationData(V, MallocLike, TLI, LookThroughBitCast).hasValue();
 }
 bool llvm::isMallocLikeFn(
     const Value *V, function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
     bool LookThroughBitCast) {
   return getAllocationData(V, MallocLike, GetTLI, LookThroughBitCast)

 }
 
 /// Tests if a value is a call or invoke to a library function that
 /// reallocates memory (e.g., realloc).
 bool llvm::isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
                      bool LookThroughBitCast) {
   return getAllocationData(V, ReallocLike, TLI, LookThroughBitCast).hasValue();
 }
-
-/// Tests if a functions is a call or invoke to a library function that
-/// reallocates memory (e.g., realloc).
 bool llvm::isReallocLikeFn(const Function *F, const TargetLibraryInfo *TLI) {
   return getAllocationDataForFunction(F, ReallocLike, TLI).hasValue();
 }
 
 /// Tests if a value is a call or invoke to a library function that
 /// allocates memory and throws if an allocation failed (e.g., new).
 bool llvm::isOpNewLikeFn(const Value *V, const TargetLibraryInfo *TLI,
                      bool LookThroughBitCast) {

llvm/lib/Transforms/IPO/Attributor.cpp

bool AA::isDynamicallyUnique(Attributor &A, const AbstractAttribute &QueryingAA,
   return NoRecurseAA.isAssumedNoRecurse();
 }
 
 Constant *AA::getInitialValueForObj(Value &Obj, Type &Ty,
                                     const TargetLibraryInfo *TLI) {
   if (isa<AllocaInst>(Obj))
     return UndefValue::get(&Ty);
   if (isNoAliasFn(&Obj, TLI)) {
-    if (isMallocLikeFn(&Obj, TLI) || isAlignedAllocLikeFn(&Obj, TLI))
+    if (isUndefAllocFn(&Obj, TLI))
       return UndefValue::get(&Ty);
-    if (isCallocLikeFn(&Obj, TLI))
+    if (isZeroAllocFn(&Obj, TLI))
       return Constant::getNullValue(&Ty);
     return nullptr;
   }
   auto *GV = dyn_cast<GlobalVariable>(&Obj);
   if (!GV || !GV->hasLocalLinkage())
     return nullptr;
   if (!GV->hasInitializer())
     return UndefValue::get(&Ty);

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

else
       return false;
 
     if (!isRemovable(DefI))
       return false;
 
     if (StoredConstant && StoredConstant->isNullValue()) {
       auto *DefUOInst = dyn_cast<Instruction>(DefUO);
       if (DefUOInst) {
-        if (isCallocLikeFn(DefUOInst, &TLI)) {
+        if (isZeroAllocFn(DefUOInst, &TLI)) {
           auto *UnderlyingDef =
               cast<MemoryDef>(MSSA.getMemoryAccess(DefUOInst));
           // If UnderlyingDef is the clobbering access of Def, no instructions
           // between them can modify the memory location.
           auto *ClobberDef =
               MSSA.getSkipSelfWalker()->getClobberingMemoryAccess(Def);
           return UnderlyingDef == ClobberDef;
         }

llvm/lib/Transforms/Scalar/GVN.cpp

if (DepInfo.isClobber()) {
     if (ORE->allowExtraAnalysis(DEBUG_TYPE))
       reportMayClobberedLoad(Load, DepInfo, DT, ORE);
 
     return false;
   }
   assert(DepInfo.isDef() && "follows from above");
 
   // Loading the allocation -> undef.
-  if (isa<AllocaInst>(DepInst) || isMallocLikeFn(DepInst, TLI) ||
-      isAlignedAllocLikeFn(DepInst, TLI) ||
+  if (isa<AllocaInst>(DepInst) || isUndefAllocFn(DepInst, TLI) ||
       // Loading immediately after lifetime begin -> undef.
       isLifetimeStart(DepInst)) {
     Res = AvailableValue::get(UndefValue::get(Load->getType()));
     return true;
   }
 
   // Loading from calloc (which zero initializes memory) -> zero
-  if (isCallocLikeFn(DepInst, TLI)) {
+  if (isZeroAllocFn(DepInst, TLI)) {
     Res = AvailableValue::get(Constant::getNullValue(Load->getType()));
     return true;
   }
 
   if (StoreInst *S = dyn_cast<StoreInst>(DepInst)) {
     // Reject loads and stores that are to the same address but are of
     // different types if we have to. If the stored value is convertable to
     // the loaded value, we can reuse it.

llvm/lib/Transforms/Scalar/NewGVN.cpp

NewGVN::performSymbolicLoadCoercion(Type *LoadType, Value *LoadPtr,
   // by the dependent instruction.
   if (LoadPtr != lookupOperandLeader(DepInst) &&
       !AA->isMustAlias(LoadPtr, DepInst))
     return nullptr;
   // If this load really doesn't depend on anything, then we must be loading an
   // undef value.  This can happen when loading for a fresh allocation with no
   // intervening stores, for example.  Note that this is only true in the case
   // that the result of the allocation is pointer equal to the load ptr.
-  if (isa<AllocaInst>(DepInst) || isMallocLikeFn(DepInst, TLI) ||
-      isAlignedAllocLikeFn(DepInst, TLI)) {
+  if (isa<AllocaInst>(DepInst) || isUndefAllocFn(DepInst, TLI)) {
     return createConstantExpression(UndefValue::get(LoadType));
   }
   // If this load occurs either right after a lifetime begin,
   // then the loaded value is undefined.
   else if (auto *II = dyn_cast<IntrinsicInst>(DepInst)) {
     if (II->getIntrinsicID() == Intrinsic::lifetime_start)
       return createConstantExpression(UndefValue::get(LoadType));
   }
-  // If this load follows a calloc (which zero initializes memory),
-  // then the loaded value is zero
-  else if (isCallocLikeFn(DepInst, TLI)) {
+  // If this load follows an allocation that returns zeroed memory
+  else if (isZeroAllocFn(DepInst, TLI)) {
     return createConstantExpression(Constant::getNullValue(LoadType));
   }
 
   return nullptr;
 }
 
 const Expression *NewGVN::performSymbolicLoadEvaluation(Instruction *I) const {
   auto *LI = cast<LoadInst>(I);