[AliasAnalysis] Return NoModRef for loads from constant memory

[aeubanks]

Summary

This noticeably increases compile times [1], but is necessary for not regressing a follow-up change to DSE that saves much more compile time.

Also update some places that assumed that all loads have a corresponding MemoryUse.

[1] https://llvm-compile-time-tracker.com/compare.php?from=9dcae2f524e7bd9c6655778fb3c4c5cac05180cb&to=a4a2b62495a63516a4f782acff1b19361906546b&stat=instructions:u

[nikic]

I'm concerned that this will cause us problems in the future, e.g. if we want to do MemorySSA-based GVN, because we will no longer have MemoryUses for these loads at all, even though we may want to do load CSE on them.

llvm/lib/Analysis/AliasAnalysis.cpp

482

Should probably use Loc rather than MemoryLocation::get(L) here, just like all the other methods?

[nikic]

llvm/lib/Analysis/AliasAnalysis.cpp

482

Or I guess not, if the intention is to pick up TBAA metadata from the load itself?

[aeubanks]

In D152743#4415131, @nikic wrote:

I'm concerned that this will cause us problems in the future, e.g. if we want to do MemorySSA-based GVN, because we will no longer have MemoryUses for these loads at all, even though we may want to do load CSE on them.

why is having a MemoryUse necessary for load CSE? can't you CSE loads of the same pointer that don't have a MemoryUse?

llvm/lib/Analysis/AliasAnalysis.cpp

482

yeah exactly

[asbirlea]

In D152743#4415131, @nikic wrote:

I'm concerned that this will cause us problems in the future, e.g. if we want to do MemorySSA-based GVN, because we will no longer have MemoryUses for these loads at all, even though we may want to do load CSE on them.

I think the issue is we can no longer determine when a true read happens.
The change likely needs to go into MSSA, have the isUseTriviallyOptimizableToLiveOnEntry check done during construction outside of optimizeUses, as a mandatory "cheap enough" optimization.
Over there the method is saying "it's true you may be a reading instruction, but you're not going to be modified by anything else anyway so you're getting optimized to LoE".
GVN still needs to account for two such MemoryUses and their relation to do CSE/PRE.

llvm/lib/Analysis/AliasAnalysis.cpp

482

I think there's subtle distinction here with the Store case below. For Store, if either MemoryLocation::get(S) OR Loc are invariable, the answer is still NoModRef, because, well, it's invariable and the store cannot modify any such locations. So the getModRefInfoMask check could go before the alias check and still be correct.

For the load, you should still return Ref when MemoryLocation::get(L) == Loc, and that's given by the alias check.
Ref means "this instructions is reading". This is true when the locations are the same (or may have some overlap), it *is* reading *that* invariant location. It is not true when the locations are different.
So the alias check is needed first, and if that one cannot prove NoAlias, the conservative answer should be Ref: "the Load instruction may be reading Loc, and I don't care that it's invariant, it may still be reading it".

[aeubanks]

llvm/lib/Analysis/AliasAnalysis.cpp

482

your response mostly makes sense to me and I'll send out a patch to update MemorySSA instead, but then should this be returning Ref since it can be read from?

[aeubanks]

llvm/lib/Analysis/AliasAnalysis.cpp

482

actually the llvm docs seem to be inconsistent

https://llvm.org/docs/AliasAnalysis.html#the-getmodrefinfomask-method says that globally constant memory is NoModRef and locally constant memory is Ref, but https://llvm.org/docs/LangRef.html#representation says that pointsToConstantMemory should return true for invariant tbaa metadata, but [pointsToConstantMemory](https://github.com/llvm/llvm-project/blob/3391bdc255f1a75c59d71c7305959e84d8d5f468/llvm/include/llvm/Analysis/AliasAnalysis.h#L388) is just a wrapper around isNoModRef(getModRefInfoMask())

[nikic]

In D152743#4415526, @asbirlea wrote:

In D152743#4415131, @nikic wrote:

I'm concerned that this will cause us problems in the future, e.g. if we want to do MemorySSA-based GVN, because we will no longer have MemoryUses for these loads at all, even though we may want to do load CSE on them.

I think the issue is we can no longer determine when a true read happens.

I think it's mostly a question of allowing uniform handling: Once you work on MSSA it is convenient if all your loads/stores are represented as memory accesses. Not having MemoryUses for invariant loads doesn't fundamentally prevent doing load CSE for them, but probably makes it a good bit more awkward. (It's something of a speculative concern though, as I don't think we really have an accepted approach on how MSSA should be introduced in GVN...)

The change likely needs to go into MSSA, have the isUseTriviallyOptimizableToLiveOnEntry check done during construction outside of optimizeUses, as a mandatory "cheap enough" optimization.
Over there the method is saying "it's true you may be a reading instruction, but you're not going to be modified by anything else anyway so you're getting optimized to LoE".

I think I'd prefer this approach.

llvm/lib/Analysis/AliasAnalysis.cpp

482

ModRefInfo works in terms of memory effects. A read from globally invariant memory is not observable, and as such NoModRef. You can reorder such a read past arbitrary modifications.

Returning NoModRef is fine (from a legality perspective) if either Loc or MemoryLocation::get(L) is globally invariant.

pointsToConstantMemory() is a legacy method with conservative behavior -- it should probably be replaced with getModRefInfoMask() that check the effects that are relevant for the transform.

[aeubanks]

llvm/lib/Analysis/AliasAnalysis.cpp

482

but loads with invariant tbaa metadata are not typically globally invariant right? the first doc says that corresponds to Ref, but the second doc says that it's ok to return NoModRef for this tbaa metadata

[nikic]

llvm/lib/Analysis/AliasAnalysis.cpp

482

Invariant TBAA metadata requires global invariance, NoModRef is correct.

[aeubanks]

llvm/lib/Analysis/AliasAnalysis.cpp

482

ah ok, although then I don't know what that'd be used for then if it required global invariance

anyway, https://reviews.llvm.org/D152859 for the MemorySSA change

llvm/lib/Analysis/AliasAnalysis.cpp

ModRefInfo AAResults::getModRefInfo(const LoadInst *L,
 
   // If the load address doesn't alias the given address, it doesn't read
   // or write the specified memory.
   if (Loc.Ptr) {
     AliasResult AR = alias(MemoryLocation::get(L), Loc, AAQI, L);
     if (AR == AliasResult::NoAlias)
       return ModRefInfo::NoModRef;
   }
+
+  // If the load is from constant memory, it doesn't mod/ref anything.
+  if (!isRefSet(getModRefInfoMask(MemoryLocation::get(L))))
+    return ModRefInfo::NoModRef;
+
   // Otherwise, a load just reads.
   return ModRefInfo::Ref;
 }
 
 ModRefInfo AAResults::getModRefInfo(const StoreInst *S,
                                     const MemoryLocation &Loc,
                                     AAQueryInfo &AAQI) {
   // Be conservative in the face of atomic.

llvm/lib/Target/AMDGPU/Utils/AMDGPUMemoryUtils.cpp

if (checkNoAlias(dyn_cast<AtomicCmpXchgInst>(DefInst)) ||
       checkNoAlias(dyn_cast<AtomicRMWInst>(DefInst)))
     return false;
 
   return true;
 }
 
 bool isClobberedInFunction(const LoadInst *Load, MemorySSA *MSSA,
                            AAResults *AA) {
+  if (!MSSA->getMemoryAccess(Load))
+    return false;
   MemorySSAWalker *Walker = MSSA->getWalker();
   SmallVector<MemoryAccess *> WorkList{Walker->getClobberingMemoryAccess(Load)};
   SmallSet<MemoryAccess *, 8> Visited;
   MemoryLocation Loc(MemoryLocation::get(Load));
 
   LLVM_DEBUG(dbgs() << "Checking clobbering of: " << *Load << '\n');
 
   // Start with a nearest dominating clobbering access, it will be either

llvm/lib/Transforms/Scalar/GVN.cpp

auto *NewLoad =
                      Load->getSyncScopeID(), UnavailableBlock->getTerminator());
     NewLoad->setDebugLoc(Load->getDebugLoc());
     if (MSSAU) {
       auto *MSSA = MSSAU->getMemorySSA();
       // Get the defining access of the original load or use the load if it is a
       // MemoryDef (e.g. because it is volatile). The inserted loads are
       // guaranteed to load from the same definition.
       auto *LoadAcc = MSSA->getMemoryAccess(Load);
+      if (LoadAcc) {
         auto *DefiningAcc =
             isa<MemoryDef>(LoadAcc) ? LoadAcc : LoadAcc->getDefiningAccess();
         auto *NewAccess = MSSAU->createMemoryAccessInBB(
             NewLoad, DefiningAcc, NewLoad->getParent(),
             MemorySSA::BeforeTerminator);
         if (auto *NewDef = dyn_cast<MemoryDef>(NewAccess))
           MSSAU->insertDef(NewDef, /*RenameUses=*/true);
         else
           MSSAU->insertUse(cast<MemoryUse>(NewAccess), /*RenameUses=*/true);
       }
+    }
 
     // Transfer the old load's AA tags to the new load.
     AAMDNodes Tags = Load->getAAMetadata();
     if (Tags)
       NewLoad->setAAMetadata(Tags);
 
     if (auto *MD = Load->getMetadata(LLVMContext::MD_invariant_load))
       NewLoad->setMetadata(LLVMContext::MD_invariant_load, MD);

llvm/lib/Transforms/Scalar/NewGVN.cpp

if (!LI->isSimple())
     return nullptr;
 
   Value *LoadAddressLeader = lookupOperandLeader(LI->getPointerOperand());
   // Load of undef is UB.
   if (isa<UndefValue>(LoadAddressLeader))
     return createConstantExpression(PoisonValue::get(LI->getType()));
   MemoryAccess *OriginalAccess = getMemoryAccess(I);
   MemoryAccess *DefiningAccess =
-      MSSAWalker->getClobberingMemoryAccess(OriginalAccess);
+      OriginalAccess ? MSSAWalker->getClobberingMemoryAccess(OriginalAccess)
+                     : MSSA->getLiveOnEntryDef();
 
   if (!MSSA->isLiveOnEntryDef(DefiningAccess)) {
     if (auto *MD = dyn_cast<MemoryDef>(DefiningAccess)) {
       Instruction *DefiningInst = MD->getMemoryInst();
       // If the defining instruction is not reachable, replace with poison.
       if (!ReachableBlocks.count(DefiningInst->getParent()))
         return createConstantExpression(PoisonValue::get(LI->getType()));
       // This will handle stores and memory insts.  We only do if it the
       // defining access has a different type, or it is a pointer produced by
       // certain memory operations that cause the memory to have a fixed value
       // (IE things like calloc).
       if (const auto *CoercionResult =
               performSymbolicLoadCoercion(LI->getType(), LoadAddressLeader, LI,
                                           DefiningInst, DefiningAccess))
         return CoercionResult;
     }
   }
 
   const auto *LE = createLoadExpression(LI->getType(), LoadAddressLeader, LI,
                                         DefiningAccess);
   // If our MemoryLeader is not our defining access, add a use to the
   // MemoryLeader, so that we get reprocessed when it changes.
-  if (LE->getMemoryLeader() != DefiningAccess)
+  if (OriginalAccess && LE->getMemoryLeader() != DefiningAccess)
     addMemoryUsers(LE->getMemoryLeader(), OriginalAccess);
   return LE;
 }
 
 NewGVN::ExprResult
 NewGVN::performSymbolicPredicateInfoEvaluation(IntrinsicInst *I) const {
   auto *PI = PredInfo->getPredicateInfoFor(I);
   if (!PI)

llvm/test/Analysis/MemorySSA/constant-memory.ll

-; RUN: opt -aa-pipeline=basic-aa -passes='print<memoryssa>' -verify-memoryssa < %s 2>&1 | FileCheck %s
+; RUN: opt -aa-pipeline=basic-aa -passes='print<memoryssa>' -verify-memoryssa < %s 2>&1 | FileCheck %s --implicit-check-not=MemoryUse
 ;
-; Things that BasicAA can prove points to constant memory should be
-; liveOnEntry, as well.
+; Things that BasicAA can prove points to constant memory should not have MemoryAccesses.
 
 declare void @clobberAllTheThings()
 
 @str = private unnamed_addr constant [2 x i8] c"hi"
 
 define i8 @foo() {
 ; CHECK: 1 = MemoryDef(liveOnEntry)
 ; CHECK-NEXT: call void @clobberAllTheThings()
   call void @clobberAllTheThings()
-; CHECK: MemoryUse(liveOnEntry)
-; CHECK-NEXT: %1 = load i8
   %1 = load i8, ptr @str, align 1
   %2 = getelementptr [2 x i8], ptr @str, i64 0, i64 1
-; CHECK: MemoryUse(liveOnEntry)
-; CHECK-NEXT: %3 = load i8
   %3 = load i8, ptr %2, align 1
   %4 = add i8 %1, %3
   ret i8 %4
 }
 
 define i8 @select(i1 %b) {
   %1 = alloca i8, align 1
 ; CHECK: 1 = MemoryDef(liveOnEntry)

llvm/test/Analysis/MemorySSA/ptr-const-mem.ll

-; RUN: opt -aa-pipeline=basic-aa -passes='print<memoryssa>' -verify-memoryssa -disable-output -memssa-check-limit=0 < %s 2>&1 | FileCheck %s
-target datalayout = "e-p:32:32-p1:64:64-p2:64:64-p3:32:32-p4:64:64-p5:32:32-i64:64-v16:16-v24:32-v32:32-v48:64-v96:128-v192:256-v256:256-v512:512-v1024:1024-v2048:2048-n32:64"
-target triple = "amdgcn"
-
-@g4 = external unnamed_addr constant i8, align 1
-
-define signext i8 @cmp_constant(ptr %q, i8 %v) local_unnamed_addr {
-entry:
-
-  store i8 %v, ptr %q, align 1
-; CHECK: 1 = MemoryDef(liveOnEntry)
-; CHECK-NEXT: store i8 %v, ptr %q, align 1
-
-  %0 = load i8, ptr @g4, align 1
-; Make sure that this load is liveOnEntry just based on the fact that @g4 is
-; constant memory.
-; CHECK: MemoryUse(liveOnEntry)
-; CHECK-NEXT: load i8, ptr @g4, align 1
-
-  ret i8 %0
-}
-

llvm/test/Transforms/GVN/mssa-constant-mem.ll

+; RUN: opt -passes='require<memoryssa>,gvn' -S < %s
+
+; check this doesn't crash
+
+@global = external constant i64
+
+declare void @foo(i64)
+
+define void @f() {
+bb:
+  br i1 true, label %bb2, label %bb1
+
+bb1:
+  %load = load i64, ptr @global
+  br label %bb2
+
+bb2:
+  %load3 = load i64, ptr @global
+  call void @foo(i64 %load3)
+  ret void
+}