diff --git a/llvm/docs/AliasAnalysis.rst b/llvm/docs/AliasAnalysis.rst --- a/llvm/docs/AliasAnalysis.rst +++ b/llvm/docs/AliasAnalysis.rst @@ -166,9 +166,25 @@ The ``pointsToConstantMemory`` method returns true if and only if the analysis can prove that the pointer only points to unchanging memory locations -(functions, constant global variables, and the null pointer). This information -can be used to refine mod/ref information: it is impossible for an unchanging -memory location to be modified. +(functions, constant global variables, and the null pointer). The +``getModRefInfoMask`` function uses this to refine mod/ref information: it is +impossible for an unchanging memory location to be modified. + +The ``getModRefInfoMask`` method +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +The ``getModRefInfoMask`` method returns a bound on Mod/Ref information for +the supplied pointer, based on knowledge about whether the pointer points to +globally-constant memory (for which it returns ``NoModRef``) or +locally-invariant memory (for which it returns ``Ref``). Locally-invariant +memory is memory that we know is invariant for the lifetime of its SSA value, +but not necessarily for the life of the program: for example, the memory +pointed to by ``readonly`` ``noalias`` parameters is known-invariant for the +duration of the corresponding function call. Given Mod/Ref information +``MRI`` for a memory location ``Loc``, ``MRI`` can be refined with a +statement like ``MRI &= AA.getModRefInfoMask(Loc);``. Another useful idiom is +``isModSet(AA.getModRefInfoMask(Loc))``; this checks to see if the given +location can be modified at all. .. _never access memory or only read memory: diff --git a/llvm/include/llvm/Analysis/AliasAnalysis.h b/llvm/include/llvm/Analysis/AliasAnalysis.h --- a/llvm/include/llvm/Analysis/AliasAnalysis.h +++ b/llvm/include/llvm/Analysis/AliasAnalysis.h @@ -375,6 +375,18 @@ /// \name Simple mod/ref information /// @{ + /// Returns a bitmask that should be unconditionally applied to the ModRef + /// info of a memory location. This allows us to eliminate Mod and/or Ref + /// from the ModRef info based on the knowledge that the memory location + /// points to constant and/or locally-invariant memory. + ModRefInfo getModRefInfoMask(const MemoryLocation &Loc); + + /// A convenience wrapper around the primary \c getModRefInfoMask + /// interface. + ModRefInfo getModRefInfoMask(const Value *P) { + return getModRefInfoMask(MemoryLocation::getBeforeOrAfter(P)); + } + /// Get the ModRef info associated with a pointer argument of a call. The /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note /// that these bits do not necessarily account for the overall behavior of @@ -617,6 +629,7 @@ AAQueryInfo &AAQI); bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, bool OrLocal = false); + ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI); ModRefInfo getModRefInfo(Instruction *I, const CallBase *Call2, AAQueryInfo &AAQIP); ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, @@ -684,6 +697,9 @@ bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false) { return AA.pointsToConstantMemory(Loc, AAQI, OrLocal); } + ModRefInfo getModRefInfoMask(const MemoryLocation &Loc) { + return AA.getModRefInfoMask(Loc, AAQI); + } ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc) { return AA.getModRefInfo(Call, Loc, AAQI); } @@ -756,6 +772,13 @@ /// \name Simple mod/ref information /// @{ + /// Returns a bitmask that should be unconditionally applied to the ModRef + /// info of a memory location. This allows us to eliminate Mod and/or Ref from + /// the ModRef info based on the knowledge that the memory location points to + /// constant and/or locally-invariant memory. + virtual ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, + AAQueryInfo &AAQI) = 0; + /// Get the ModRef info associated with a pointer argument of a callsite. The /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note /// that these bits do not necessarily account for the overall behavior of @@ -809,6 +832,11 @@ return Result.pointsToConstantMemory(Loc, AAQI, OrLocal); } + ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, + AAQueryInfo &AAQI) override { + return Result.getModRefInfoMask(Loc, AAQI); + } + ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) override { return Result.getArgModRefInfo(Call, ArgIdx); } @@ -864,6 +892,10 @@ return false; } + ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI) { + return ModRefInfo::ModRef; + } + ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) { return ModRefInfo::ModRef; } diff --git a/llvm/include/llvm/Analysis/BasicAliasAnalysis.h b/llvm/include/llvm/Analysis/BasicAliasAnalysis.h --- a/llvm/include/llvm/Analysis/BasicAliasAnalysis.h +++ b/llvm/include/llvm/Analysis/BasicAliasAnalysis.h @@ -79,6 +79,12 @@ bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, bool OrLocal); + /// Returns a bitmask that should be unconditionally applied to the ModRef + /// info of a memory location. This allows us to eliminate Mod and/or Ref + /// from the ModRef info based on the knowledge that the memory location + /// points to constant and/or locally-invariant memory. + ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI); + /// Get the location associated with a pointer argument of a callsite. ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx); diff --git a/llvm/include/llvm/Analysis/TypeBasedAliasAnalysis.h b/llvm/include/llvm/Analysis/TypeBasedAliasAnalysis.h --- a/llvm/include/llvm/Analysis/TypeBasedAliasAnalysis.h +++ b/llvm/include/llvm/Analysis/TypeBasedAliasAnalysis.h @@ -42,6 +42,7 @@ AAQueryInfo &AAQI); bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, bool OrLocal); + ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI); MemoryEffects getMemoryEffects(const CallBase *Call, AAQueryInfo &AAQI); MemoryEffects getMemoryEffects(const Function *F); ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, diff --git a/llvm/lib/Analysis/AliasAnalysis.cpp b/llvm/lib/Analysis/AliasAnalysis.cpp --- a/llvm/lib/Analysis/AliasAnalysis.cpp +++ b/llvm/lib/Analysis/AliasAnalysis.cpp @@ -162,6 +162,26 @@ return false; } +ModRefInfo AAResults::getModRefInfoMask(const MemoryLocation &Loc) { + SimpleAAQueryInfo AAQIP(*this); + return getModRefInfoMask(Loc, AAQIP); +} + +ModRefInfo AAResults::getModRefInfoMask(const MemoryLocation &Loc, + AAQueryInfo &AAQI) { + ModRefInfo Result = ModRefInfo::ModRef; + + for (const auto &AA : AAs) { + Result &= AA->getModRefInfoMask(Loc, AAQI); + + // Early-exit the moment we reach the bottom of the lattice. + if (isNoModRef(Result)) + return ModRefInfo::NoModRef; + } + + return Result; +} + ModRefInfo AAResults::getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) { ModRefInfo Result = ModRefInfo::ModRef; @@ -253,10 +273,11 @@ Result &= ArgMR | OtherMR; - // If Loc is a constant memory location, the call definitely could not + // Apply the ModRef mask. This ensures that if Loc is a constant memory + // location, we take into account the fact that the call definitely could not // modify the memory location. - if (isModSet(Result) && pointsToConstantMemory(Loc, AAQI, /*OrLocal*/ false)) - Result &= ModRefInfo::Ref; + if (!isNoModRef(Result)) + Result &= getModRefInfoMask(Loc); return Result; } @@ -510,9 +531,11 @@ if (AR == AliasResult::NoAlias) return ModRefInfo::NoModRef; - // If the pointer is a pointer to constant memory, then it could not have - // been modified by this store. - if (pointsToConstantMemory(Loc, AAQI)) + // Examine the ModRef mask. If Mod isn't present, then return NoModRef. + // This ensures that if Loc is a constant memory location, we take into + // account the fact that the store definitely could not modify the memory + // location. + if (!isModSet(getModRefInfoMask(Loc))) return ModRefInfo::NoModRef; } @@ -529,11 +552,10 @@ ModRefInfo AAResults::getModRefInfo(const FenceInst *S, const MemoryLocation &Loc, AAQueryInfo &AAQI) { - // If we know that the location is a constant memory location, the fence - // cannot modify this location. - if (Loc.Ptr && pointsToConstantMemory(Loc, AAQI)) - return ModRefInfo::Ref; - return ModRefInfo::ModRef; + // All we know about a fence instruction is what we get from the ModRef + // mask: if Loc is a constant memory location, the fence definitely could + // not modify it. + return getModRefInfoMask(Loc); } ModRefInfo AAResults::getModRefInfo(const VAArgInst *V, diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp --- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp +++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp @@ -820,6 +820,31 @@ return false; } +ModRefInfo BasicAAResult::getModRefInfoMask(const MemoryLocation &Loc, + AAQueryInfo &AAQI) { + if (Loc.Ptr) { + // If the location points to globally-constant memory, there can be no + // visible memory effects. + if (pointsToConstantMemory(Loc, AAQI, false)) + return ModRefInfo::NoModRef; + + // If the location points to memory that is known to be invariant for + // the life of the underlying SSA value, then we can exclude Mod from + // the set of valid memory effects. + // + // An argument that is marked readonly and noalias is known to be + // invariant while that function is executing. + if (const Argument *Arg = + dyn_cast(getUnderlyingObject(Loc.Ptr))) { + if (Arg->hasNoAliasAttr() && Arg->hasAttribute(Attribute::ReadOnly)) + return ModRefInfo::Ref; + } + } + + // Otherwise, forward to the base AAResult. + return AAResultBase::getModRefInfoMask(Loc, AAQI); +} + ModRefInfo BasicAAResult::getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) { // Checking for known builtin intrinsics and target library functions. diff --git a/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp b/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp --- a/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp +++ b/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp @@ -525,7 +525,7 @@ } // Stores don't alias loads from read-only memory. - if (BatchAA.pointsToConstantMemory(LoadLoc)) + if (!isModSet(BatchAA.getModRefInfoMask(LoadLoc))) continue; // Stores depend on may/must aliased loads. diff --git a/llvm/lib/Analysis/MemorySSA.cpp b/llvm/lib/Analysis/MemorySSA.cpp --- a/llvm/lib/Analysis/MemorySSA.cpp +++ b/llvm/lib/Analysis/MemorySSA.cpp @@ -378,9 +378,10 @@ const Instruction *I) { // If the memory can't be changed, then loads of the memory can't be // clobbered. - if (auto *LI = dyn_cast(I)) + if (auto *LI = dyn_cast(I)) { return I->hasMetadata(LLVMContext::MD_invariant_load) || - AA.pointsToConstantMemory(MemoryLocation::get(LI)); + !isModSet(AA.getModRefInfoMask(MemoryLocation::get(LI))); + } return false; } diff --git a/llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp b/llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp --- a/llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp +++ b/llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp @@ -404,6 +404,17 @@ return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal); } +ModRefInfo TypeBasedAAResult::getModRefInfoMask(const MemoryLocation &Loc, + AAQueryInfo &AAQI) { + // If the location points to globally-constant memory, there can be no + // visible memory effects. + if (Loc.Ptr && pointsToConstantMemory(Loc, AAQI, false)) + return ModRefInfo::NoModRef; + + // Otherwise, forward to the base. + return AAResultBase::getModRefInfoMask(Loc, AAQI); +} + MemoryEffects TypeBasedAAResult::getMemoryEffects(const CallBase *Call, AAQueryInfo &AAQI) { if (!EnableTBAA) diff --git a/llvm/lib/Transforms/IPO/FunctionAttrs.cpp b/llvm/lib/Transforms/IPO/FunctionAttrs.cpp --- a/llvm/lib/Transforms/IPO/FunctionAttrs.cpp +++ b/llvm/lib/Transforms/IPO/FunctionAttrs.cpp @@ -143,6 +143,9 @@ // Ignore accesses to local memory. if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) return; + // Ignore accesses to memory that we know is invariant. + if (!isModSet(AAR.getModRefInfoMask(Loc))) + return; const Value *UO = getUnderlyingObject(Loc.Ptr); assert(!isa(UO) && diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp --- a/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp @@ -135,7 +135,7 @@ // If we have a store to a location which is known constant, we can conclude // that the store must be storing the constant value (else the memory // wouldn't be constant), and this must be a noop. - if (AA->pointsToConstantMemory(MI->getDest())) { + if (!isModSet(AA->getModRefInfoMask(MI->getDest()))) { // Set the size of the copy to 0, it will be deleted on the next iteration. MI->setLength(Constant::getNullValue(MI->getLength()->getType())); return MI; @@ -252,7 +252,7 @@ // If we have a store to a location which is known constant, we can conclude // that the store must be storing the constant value (else the memory // wouldn't be constant), and this must be a noop. - if (AA->pointsToConstantMemory(MI->getDest())) { + if (!isModSet(AA->getModRefInfoMask(MI->getDest()))) { // Set the size of the copy to 0, it will be deleted on the next iteration. MI->setLength(Constant::getNullValue(MI->getLength()->getType())); return MI; diff --git a/llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp b/llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp --- a/llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp @@ -128,8 +128,8 @@ // If the memintrinsic isn't using the alloca as the dest, reject it. if (U.getOperandNo() != 0) return false; - // If the source of the memcpy/move is not a constant global, reject it. - if (!AA->pointsToConstantMemory(MI->getSource())) + // If the source of the memcpy/move is not constant, reject it. + if (isModSet(AA->getModRefInfoMask(MI->getSource()))) return false; // Otherwise, the transform is safe. Remember the copy instruction. @@ -1372,7 +1372,7 @@ // If we have a store to a location which is known constant, we can conclude // that the store must be storing the constant value (else the memory // wouldn't be constant), and this must be a noop. - if (AA->pointsToConstantMemory(Ptr)) + if (!isModSet(AA->getModRefInfoMask(Ptr))) return eraseInstFromFunction(SI); // Do really simple DSE, to catch cases where there are several consecutive diff --git a/llvm/lib/Transforms/Scalar/LICM.cpp b/llvm/lib/Transforms/Scalar/LICM.cpp --- a/llvm/lib/Transforms/Scalar/LICM.cpp +++ b/llvm/lib/Transforms/Scalar/LICM.cpp @@ -1161,7 +1161,7 @@ // Loads from constant memory are always safe to move, even if they end up // in the same alias set as something that ends up being modified. - if (AA->pointsToConstantMemory(LI->getOperand(0))) + if (!isModSet(AA->getModRefInfoMask(LI->getOperand(0)))) return true; if (LI->hasMetadata(LLVMContext::MD_invariant_load)) return true; diff --git a/llvm/lib/Transforms/Scalar/LoopPredication.cpp b/llvm/lib/Transforms/Scalar/LoopPredication.cpp --- a/llvm/lib/Transforms/Scalar/LoopPredication.cpp +++ b/llvm/lib/Transforms/Scalar/LoopPredication.cpp @@ -569,7 +569,7 @@ if (const SCEVUnknown *U = dyn_cast(S)) if (const auto *LI = dyn_cast(U->getValue())) if (LI->isUnordered() && L->hasLoopInvariantOperands(LI)) - if (AA->pointsToConstantMemory(LI->getOperand(0)) || + if (!isModSet(AA->getModRefInfoMask(LI->getOperand(0))) || LI->hasMetadata(LLVMContext::MD_invariant_load)) return true; return false; diff --git a/llvm/test/Analysis/BasicAA/constant-memory.ll b/llvm/test/Analysis/BasicAA/constant-memory.ll --- a/llvm/test/Analysis/BasicAA/constant-memory.ll +++ b/llvm/test/Analysis/BasicAA/constant-memory.ll @@ -4,18 +4,16 @@ declare void @dummy() -; FIXME: This could be NoModRef ; CHECK-LABEL: Function: basic -; CHECK: Just Ref: Ptr: i32* @c <-> call void @dummy() +; CHECK: NoModRef: Ptr: i32* @c <-> call void @dummy() define void @basic(ptr %p) { call void @dummy() load i32, ptr @c ret void } -; FIXME: This could be NoModRef ; CHECK-LABEL: Function: recphi -; CHECK: Just Ref: Ptr: i32* %p <-> call void @dummy() +; CHECK: NoModRef: Ptr: i32* %p <-> call void @dummy() define void @recphi() { entry: br label %loop diff --git a/llvm/test/Analysis/BasicAA/pr18573.ll b/llvm/test/Analysis/BasicAA/pr18573.ll --- a/llvm/test/Analysis/BasicAA/pr18573.ll +++ b/llvm/test/Analysis/BasicAA/pr18573.ll @@ -8,7 +8,7 @@ declare <8 x float> @llvm.x86.avx2.gather.d.ps.256(<8 x float>, i8*, <8 x i32>, <8 x float>, i8) #0 ; Function Attrs: nounwind -define <8 x float> @foo1(i8* noalias readonly %arr.ptr, <8 x i32>* noalias readonly %vix.ptr, i8* noalias %t2.ptr) #1 { +define <8 x float> @foo1(i8* readonly %arr.ptr, <8 x i32>* noalias readonly %vix.ptr, i8* noalias %t2.ptr) #1 { allocas: %vix = load <8 x i32>, <8 x i32>* %vix.ptr, align 4 %t1.ptr = getelementptr i8, i8* %arr.ptr, i8 4 diff --git a/llvm/test/Analysis/BasicAA/readonly-noalias.ll b/llvm/test/Analysis/BasicAA/readonly-noalias.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Analysis/BasicAA/readonly-noalias.ll @@ -0,0 +1,13 @@ +; Tests that readonly noalias implies !Mod. +; +; RUN: opt < %s -passes=aa-eval -print-all-alias-modref-info 2>&1 | FileCheck %s + +declare void @foo() + +; CHECK-LABEL: Function: basic +; CHECK: NoModRef: Ptr: i32* %p <-> call void @foo() +define void @basic(ptr readonly noalias %p) { + call void @foo() + load i32, ptr %p + ret void +} diff --git a/llvm/test/Transforms/InstCombine/store.ll b/llvm/test/Transforms/InstCombine/store.ll --- a/llvm/test/Transforms/InstCombine/store.ll +++ b/llvm/test/Transforms/InstCombine/store.ll @@ -336,6 +336,14 @@ ret void } +; Delete stores to readonly noalias pointers. +define void @store_to_readonly_noalias(ptr readonly noalias %0) { +; CHECK-LABEL: @store_to_readonly_noalias( +; CHECK-NEXT: ret void + store i32 3, ptr %0, align 4 + ret void +} + !0 = !{!4, !4, i64 0} !1 = !{!"omnipotent char", !2} !2 = !{!"Simple C/C++ TBAA"} diff --git a/llvm/test/Transforms/LoopVectorize/AArch64/sve-gather-scatter.ll b/llvm/test/Transforms/LoopVectorize/AArch64/sve-gather-scatter.ll --- a/llvm/test/Transforms/LoopVectorize/AArch64/sve-gather-scatter.ll +++ b/llvm/test/Transforms/LoopVectorize/AArch64/sve-gather-scatter.ll @@ -292,7 +292,7 @@ -define void @gather_nxv4i32_ind64_stride2(float* noalias nocapture readonly %a, float* noalias nocapture readonly %b, i64 %n) #0 { +define void @gather_nxv4i32_ind64_stride2(float* noalias nocapture %a, float* noalias nocapture readonly %b, i64 %n) #0 { ; CHECK-LABEL: @gather_nxv4i32_ind64_stride2( ; CHECK-NEXT: entry: ; CHECK-NEXT: [[TMP0:%.*]] = call i64 @llvm.vscale.i64() diff --git a/llvm/test/Transforms/LoopVectorize/interleaved-accesses.ll b/llvm/test/Transforms/LoopVectorize/interleaved-accesses.ll --- a/llvm/test/Transforms/LoopVectorize/interleaved-accesses.ll +++ b/llvm/test/Transforms/LoopVectorize/interleaved-accesses.ll @@ -572,15 +572,15 @@ ; void load_gap_reverse(struct pair *P1, struct pair *P2, int X) { ; for (int i = 1023; i >= 0; i--) { ; int a = X + i; -; int b = A[i].y - i; -; B[i].x = a; +; int b = B[i].y - i; +; A[i].x = a; ; B[i].y = b; ; } ; } %pair = type { i64, i64 } -define void @load_gap_reverse(%pair* noalias nocapture readonly %P1, %pair* noalias nocapture readonly %P2, i64 %X) { +define void @load_gap_reverse(%pair* noalias nocapture %P1, %pair* noalias nocapture %P2, i64 %X) { ; CHECK-LABEL: @load_gap_reverse( ; CHECK-NEXT: entry: ; CHECK-NEXT: br i1 false, label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]