[llvm][MemoryBuiltins] Add alloca support to getInitialValueOfAllocation

[jmciver]

Summary

This commit is in support of future uninitialized memory handling and adds
alloca instruction support to getInitialValueOfAllocation. This unifies initial
memory state querying (both stack and heap) to a single utility function.

Mem2Reg, GVN, and NewGVN optimizations are refactored to take advantage of
alloca support in getInitialValueOfAllocation.

To support uninitialized memory as poison we are proposing that in the future
load instructions support an attribute !freeze (or alternative) which will allow
freeze poison insertions where applicable. Thus the constant emitted by
getInitialValueOfAllocation will be dependent on the allocation
function/instruction and the load instruction attributes.

[nikic]

This commit is in support of future uninitialized memory handling and adds
alloca instruction support to getInitialValueOfAllocation. This unifies initial
memory state querying (both stack and heap) to a single utility function.

Could you explain in more detail what future work you have based on this? Is this about the promotion of malloc (and similar) memory?

In any case, I don't think it's acceptable to add TLI as a required dependency for mem2reg. Alloca promotion doesn't need it, and that's what all the existing code is doing. This should at least be an optional dependency.

However, I think it would be better to directly pass the initial value to mem2reg instead (defaulting to UndefValue), rather than making it query it.

[jmciver]

@nikic as per my GSoC project I am trying, under the guidance of @nlopes, a load attribute based approach to migrating uninitialized load to poison. The first attribute that I am working on is !freeze which effectively inserts a freeze poison if the load is uninitialized. Obviously this can only be done in
optimizations that allow instruction creation. In the future I am looking to add a load instruction parameter to getInitialValueOfAllocation to allow modification of the returned constant based on the allocation function/instruction and the presence of a load attribute.

So why pack the alloca test into getInitialValueOfAllocation? The reasoning is that attribute is on a per-load instruction, but allocation could be alloca or function. I agree if the application of the load attribute were universal passing in the default value to mem2reg would work, but as we are modulating the returned constant based on individual load instruction attributes this would not work. Hence the query based approach.

As for the TLI I agree that making it required is probably not ideal. @nlopes can vouch that I thought about this :-). Two options off the top of my head are:

1. Make the TLI parameter of getInitialValueOfAllocation a pointer with defaults to nullptr.

2. Add a separated query function for alloca instructions.

The advantage to option 1 is all allocation initial state queries are handled in one place. The detractor is we have a parameter that has a default nullptr.

The advantage to option 2 is allocation functions vs alloca instruction are handled by functions that have only the required parameterizations exposed. The detractor is there will be some combinatorial overlap between the two functions.

Thoughts?

[jmciver]

Remove reliance on TLI objects where only alloca instructions are processed.

[jmciver]

Refactor AMDGPUPromoteAlloca to use getInitialValueOfAllocation.

[jmciver]

Ping

[jmciver]

Ping

[arsenm]

llvm/lib/Target/AMDGPU/AMDGPUPromoteAlloca.cpp

809–811

This is very specifically handling alloca, not any random allocation like function

[jmciver]

llvm/lib/Target/AMDGPU/AMDGPUPromoteAlloca.cpp

809–811

@arsenm thanks for the feedback. I added functionality to getInitalValueOfAllocation to handle alloca instructions specifically. This is being done as preliminary to some possible refactorizations allowing uninitialized memory to move to poison semantics. The behavior for these changes would be the same for alloca and allocation like functions.

[nikic]

@jmciver Thanks for the context. I would recommend you to put up the patch you have based on top of this, because it's pretty hard to tell whether this API design makes sense without seeing the use. I have some doubts about that, for two reasons:

• If I understand correctly, for your use case getInitialValueOfAllocation() can't just return a constant anymore, it may have to insert an instruction. Additionally, there is no longer a single "initial value", but it may wary between different loads from the same allocation. This means that the API is going to change to the point that getInitialValueOfAllocation() is no longer recognizable (and probably no longer correctly named -- it would be more materializeInitialValueOfAllocation()).
• As some of the changes in this patch show, we also have to give lifetime.start intrinsics similar treatment to allocas, but this doesn't quite fit the current API.

I think supporting allocas in getInitialValueOfAllocation() is perfectly fine, but I'm not sure this really brings you closer to what you want to do.

[jmciver]

@nikic Thanks for responding. I will get a "work in progress" patch up in the next three days.

In the API adaptation, instruction insertion is still being handled in the caller as some passes are only allowed removal and not insertion.

[jmciver]

@nikic I added this patch to a work in progress (WIP) "stack" of patches. D158352 and D158353 show what the intended progression looks like for mem2reg. I will add WIP SROA changes in the next few days.

llvm/include/llvm/Analysis/MemoryBuiltins.h

 /// doing abstract interpretation.
 std::optional<APInt> getAllocSize(
     const CallBase *CB, const TargetLibraryInfo *TLI,
     function_ref<const Value *(const Value *)> Mapper = [](const Value *V) {
       return V;
     });
 
 /// If this is a call to an allocation function that initializes memory to a
-/// fixed value, return said value in the requested type.  Otherwise, return
-/// nullptr.
+/// fixed value, return said value in the requested type. If this is a call to
+/// alloca instruction the returned value is undef. Otherwise, return nullptr.
 Constant *getInitialValueOfAllocation(const Value *V,
                                       const TargetLibraryInfo *TLI,
                                       Type *Ty);
 
 /// If a function is part of an allocation family (e.g.
 /// malloc/realloc/calloc/free), return the identifier for its family
 /// of functions.
 std::optional<StringRef> getAllocationFamily(const Value *I,

llvm/lib/Analysis/MemoryBuiltins.cpp

llvm::getAllocSize(const CallBase *CB, const TargetLibraryInfo *TLI,
   if (Overflow)
     return std::nullopt;
   return Size;
 }
 
 Constant *llvm::getInitialValueOfAllocation(const Value *V,
                                             const TargetLibraryInfo *TLI,
                                             Type *Ty) {
+  if (isa<AllocaInst>(V))
+    return UndefValue::get(Ty);
+
   auto *Alloc = dyn_cast<CallBase>(V);
   if (!Alloc)
     return nullptr;
 
   // malloc are uninitialized (undef)
   if (getAllocationData(Alloc, MallocOrOpNewLike, TLI).has_value())
     return UndefValue::get(Ty);
 

llvm/lib/Target/AMDGPU/AMDGPUPromoteAlloca.cpp

 
 #include "AMDGPU.h"
 #include "GCNSubtarget.h"
 #include "Utils/AMDGPUBaseInfo.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/InstSimplifyFolder.h"
 #include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/IntrinsicsAMDGPU.h"
 #include "llvm/IR/IntrinsicsR600.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Pass.h"
bool AMDGPUPromoteAllocaImpl::tryPromoteAllocaToVector(AllocaInst &Alloca) {
   LLVM_DEBUG(dbgs() << "  Converting alloca to vector " << *AllocaTy << " -> "
                     << *VectorTy << '\n');
   const unsigned VecStoreSize = DL->getTypeStoreSize(VectorTy);
 
   // Alloca is uninitialized memory. Imitate that by making the first value
   // undef.
   SSAUpdater Updater;
   Updater.Initialize(VectorTy, "promotealloca");
-  Updater.AddAvailableValue(Alloca.getParent(), UndefValue::get(VectorTy));
+  Updater.AddAvailableValue(
+      Alloca.getParent(),
+      getInitialValueOfAllocation(&Alloca, nullptr, VectorTy));
 
   // First handle the initial worklist.
   SmallVector<LoadInst *, 4> DeferredLoads;
   forEachWorkListItem(WorkList, [&](Instruction *I) {
     BasicBlock *BB = I->getParent();
     // On the first pass, we only take values that are trivially known, i.e.
     // where AddAvailableValue was already called in this block.
     Value *Result = promoteAllocaUserToVector(

llvm/lib/Transforms/Scalar/GVN.cpp

LLVM_DEBUG(
         dbgs() << " is clobbered by " << *DepInst << '\n';);
     if (ORE->allowExtraAnalysis(DEBUG_TYPE))
       reportMayClobberedLoad(Load, DepInfo, DT, ORE);
 
     return std::nullopt;
   }
   assert(DepInfo.isDef() && "follows from above");
 
-  // Loading the alloca -> undef.
   // Loading immediately after lifetime begin -> undef.
-  if (isa<AllocaInst>(DepInst) || isLifetimeStart(DepInst))
+  if (isLifetimeStart(DepInst))
     return AvailableValue::get(UndefValue::get(Load->getType()));
 
+  // In addition to allocator function calls this includes loading the alloca ->
+  // undef.
   if (Constant *InitVal =
           getInitialValueOfAllocation(DepInst, TLI, Load->getType()))
     return AvailableValue::get(InitVal);
 
   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

if (auto *DepSI = dyn_cast<StoreInst>(DepInst)) {
     }
   }
 
   // All of the below are only true if the loaded pointer is produced
   // 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)) {
-    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 (auto *II = dyn_cast<IntrinsicInst>(DepInst)) {
     if (II->getIntrinsicID() == Intrinsic::lifetime_start)
       return createConstantExpression(UndefValue::get(LoadType));
-  } else if (auto *InitVal =
-                 getInitialValueOfAllocation(DepInst, TLI, LoadType))
-      return createConstantExpression(InitVal);
+  }
+  // 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.
+  else if (auto *InitVal = getInitialValueOfAllocation(DepInst, TLI, LoadType))
 
   return nullptr;
 }
 
 const Expression *NewGVN::performSymbolicLoadEvaluation(Instruction *I) const {
   auto *LI = cast<LoadInst>(I);
 
   // We can eliminate in favor of non-simple loads, but we won't be able to

llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp

 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/IteratedDominanceFrontier.h"
+#include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DIBuilder.h"
 #include "llvm/IR/DebugInfo.h"
 #include "llvm/IR/Dominators.h"
for (User *U : make_early_inc_range(AI->users())) {
     StoresByIndexTy::iterator I = llvm::lower_bound(
         StoresByIndex,
         std::make_pair(LoadIdx, static_cast<StoreInst *>(nullptr)),
         less_first());
     Value *ReplVal;
     if (I == StoresByIndex.begin()) {
       if (StoresByIndex.empty())
         // If there are no stores, the load takes the undef value.
-        ReplVal = UndefValue::get(LI->getType());
+        ReplVal = getInitialValueOfAllocation(AI, nullptr, LI->getType());
       else
         // There is no store before this load, bail out (load may be affected
         // by the following stores - see main comment).
         return false;
     } else {
       // Otherwise, there was a store before this load, the load takes its
       // value.
       ReplVal = std::prev(I)->second->getOperand(0);