Index: llvm/trunk/include/llvm/Analysis/AliasAnalysis.h =================================================================== --- llvm/trunk/include/llvm/Analysis/AliasAnalysis.h +++ llvm/trunk/include/llvm/Analysis/AliasAnalysis.h @@ -95,46 +95,81 @@ /// /// This is no access at all, a modification, a reference, or both /// a modification and a reference. These are specifically structured such that -/// they form a two bit matrix and bit-tests for 'mod' or 'ref' +/// they form a three bit matrix and bit-tests for 'mod' or 'ref' or 'must' /// work with any of the possible values. - enum class ModRefInfo { + /// Must is provided for completeness, but no routines will return only + /// Must today. See definition of Must below. + Must = 0, + /// The access may reference the value stored in memory, + /// a mustAlias relation was found, and no mayAlias or partialAlias found. + MustRef = 1, + /// The access may modify the value stored in memory, + /// a mustAlias relation was found, and no mayAlias or partialAlias found. + MustMod = 2, + /// The access may reference, modify or both the value stored in memory, + /// a mustAlias relation was found, and no mayAlias or partialAlias found. + MustModRef = MustRef | MustMod, /// The access neither references nor modifies the value stored in memory. - NoModRef = 0, + NoModRef = 4, /// The access may reference the value stored in memory. - Ref = 1, + Ref = NoModRef | MustRef, /// The access may modify the value stored in memory. - Mod = 2, + Mod = NoModRef | MustMod, /// The access may reference and may modify the value stored in memory. ModRef = Ref | Mod, + + /// About Must: + /// Must is set in a best effort manner. + /// We usually do not try our best to infer Must, instead it is merely + /// another piece of "free" information that is presented when available. + /// Must set means there was certainly a MustAlias found. For calls, + /// where multiple arguments are checked (argmemonly), this translates to + /// only MustAlias or NoAlias was found. + /// Must is not set for RAR accesses, even if the two locations must + /// alias. The reason is that two read accesses translate to an early return + /// of NoModRef. An additional alias check to set Must may be + /// expensive. Other cases may also not set Must(e.g. callCapturesBefore). + /// We refer to Must being *set* when the most significant bit is *cleared*. + /// Conversely we *clear* Must information by *setting* the Must bit to 1. }; LLVM_NODISCARD inline bool isNoModRef(const ModRefInfo MRI) { - return MRI == ModRefInfo::NoModRef; + return (static_cast(MRI) & static_cast(ModRefInfo::MustModRef)) == + static_cast(ModRefInfo::Must); } LLVM_NODISCARD inline bool isModOrRefSet(const ModRefInfo MRI) { - return static_cast(MRI) & static_cast(ModRefInfo::ModRef); + return static_cast(MRI) & static_cast(ModRefInfo::MustModRef); } LLVM_NODISCARD inline bool isModAndRefSet(const ModRefInfo MRI) { - return (static_cast(MRI) & static_cast(ModRefInfo::ModRef)) == - static_cast(ModRefInfo::ModRef); + return (static_cast(MRI) & static_cast(ModRefInfo::MustModRef)) == + static_cast(ModRefInfo::MustModRef); } LLVM_NODISCARD inline bool isModSet(const ModRefInfo MRI) { - return static_cast(MRI) & static_cast(ModRefInfo::Mod); + return static_cast(MRI) & static_cast(ModRefInfo::MustMod); } LLVM_NODISCARD inline bool isRefSet(const ModRefInfo MRI) { - return static_cast(MRI) & static_cast(ModRefInfo::Ref); + return static_cast(MRI) & static_cast(ModRefInfo::MustRef); +} +LLVM_NODISCARD inline bool isMustSet(const ModRefInfo MRI) { + return !(static_cast(MRI) & static_cast(ModRefInfo::NoModRef)); } LLVM_NODISCARD inline ModRefInfo setMod(const ModRefInfo MRI) { - return ModRefInfo(static_cast(MRI) | static_cast(ModRefInfo::Mod)); + return ModRefInfo(static_cast(MRI) | + static_cast(ModRefInfo::MustMod)); } LLVM_NODISCARD inline ModRefInfo setRef(const ModRefInfo MRI) { - return ModRefInfo(static_cast(MRI) | static_cast(ModRefInfo::Ref)); + return ModRefInfo(static_cast(MRI) | + static_cast(ModRefInfo::MustRef)); +} +LLVM_NODISCARD inline ModRefInfo setMust(const ModRefInfo MRI) { + return ModRefInfo(static_cast(MRI) & + static_cast(ModRefInfo::MustModRef)); } LLVM_NODISCARD inline ModRefInfo setModAndRef(const ModRefInfo MRI) { return ModRefInfo(static_cast(MRI) | - static_cast(ModRefInfo::ModRef)); + static_cast(ModRefInfo::MustModRef)); } LLVM_NODISCARD inline ModRefInfo clearMod(const ModRefInfo MRI) { return ModRefInfo(static_cast(MRI) & static_cast(ModRefInfo::Ref)); @@ -142,6 +177,10 @@ LLVM_NODISCARD inline ModRefInfo clearRef(const ModRefInfo MRI) { return ModRefInfo(static_cast(MRI) & static_cast(ModRefInfo::Mod)); } +LLVM_NODISCARD inline ModRefInfo clearMust(const ModRefInfo MRI) { + return ModRefInfo(static_cast(MRI) | + static_cast(ModRefInfo::NoModRef)); +} LLVM_NODISCARD inline ModRefInfo unionModRef(const ModRefInfo MRI1, const ModRefInfo MRI2) { return ModRefInfo(static_cast(MRI1) | static_cast(MRI2)); @@ -160,11 +199,11 @@ /// Base case is no access to memory. FMRL_Nowhere = 0, /// Access to memory via argument pointers. - FMRL_ArgumentPointees = 4, + FMRL_ArgumentPointees = 8, /// Memory that is inaccessible via LLVM IR. - FMRL_InaccessibleMem = 8, + FMRL_InaccessibleMem = 16, /// Access to any memory. - FMRL_Anywhere = 16 | FMRL_InaccessibleMem | FMRL_ArgumentPointees + FMRL_Anywhere = 32 | FMRL_InaccessibleMem | FMRL_ArgumentPointees }; /// Summary of how a function affects memory in the program. @@ -344,7 +383,7 @@ /// 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 /// the function, but rather only provide additional per-argument - /// information. + /// information. This never sets ModRefInfo::Must. ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx); /// Return the behavior of the given call site. @@ -624,6 +663,8 @@ /// or reads the specified memory location \p MemLoc before instruction \p I /// in a BasicBlock. An ordered basic block \p OBB can be used to speed up /// instruction ordering queries inside the BasicBlock containing \p I. + /// Early exits in callCapturesBefore may lead to ModRefInfo::Must not being + /// set. ModRefInfo callCapturesBefore(const Instruction *I, const MemoryLocation &MemLoc, DominatorTree *DT, OrderedBasicBlock *OBB = nullptr); Index: llvm/trunk/include/llvm/Analysis/AliasAnalysisEvaluator.h =================================================================== --- llvm/trunk/include/llvm/Analysis/AliasAnalysisEvaluator.h +++ llvm/trunk/include/llvm/Analysis/AliasAnalysisEvaluator.h @@ -35,19 +35,23 @@ int64_t FunctionCount; int64_t NoAliasCount, MayAliasCount, PartialAliasCount, MustAliasCount; int64_t NoModRefCount, ModCount, RefCount, ModRefCount; + int64_t MustCount, MustRefCount, MustModCount, MustModRefCount; public: AAEvaluator() : FunctionCount(), NoAliasCount(), MayAliasCount(), PartialAliasCount(), MustAliasCount(), NoModRefCount(), ModCount(), RefCount(), - ModRefCount() {} + ModRefCount(), MustCount(), MustRefCount(), MustModCount(), + MustModRefCount() {} AAEvaluator(AAEvaluator &&Arg) : FunctionCount(Arg.FunctionCount), NoAliasCount(Arg.NoAliasCount), MayAliasCount(Arg.MayAliasCount), PartialAliasCount(Arg.PartialAliasCount), MustAliasCount(Arg.MustAliasCount), NoModRefCount(Arg.NoModRefCount), ModCount(Arg.ModCount), RefCount(Arg.RefCount), - ModRefCount(Arg.ModRefCount) { + ModRefCount(Arg.ModRefCount), MustCount(Arg.MustCount), + MustRefCount(Arg.MustRefCount), MustModCount(Arg.MustModCount), + MustModRefCount(Arg.MustModRefCount) { Arg.FunctionCount = 0; } ~AAEvaluator(); Index: llvm/trunk/lib/Analysis/AliasAnalysis.cpp =================================================================== --- llvm/trunk/lib/Analysis/AliasAnalysis.cpp +++ llvm/trunk/lib/Analysis/AliasAnalysis.cpp @@ -133,9 +133,9 @@ } ModRefInfo AAResults::getModRefInfo(Instruction *I, ImmutableCallSite Call) { - // We may have two calls + // We may have two calls. if (auto CS = ImmutableCallSite(I)) { - // Check if the two calls modify the same memory + // Check if the two calls modify the same memory. return getModRefInfo(CS, Call); } else if (I->isFenceLike()) { // If this is a fence, just return ModRef. @@ -179,6 +179,7 @@ if (onlyAccessesArgPointees(MRB) || onlyAccessesInaccessibleOrArgMem(MRB)) { bool DoesAlias = false; + bool IsMustAlias = true; ModRefInfo AllArgsMask = ModRefInfo::NoModRef; if (doesAccessArgPointees(MRB)) { for (auto AI = CS.arg_begin(), AE = CS.arg_end(); AI != AE; ++AI) { @@ -193,6 +194,8 @@ DoesAlias = true; AllArgsMask = unionModRef(AllArgsMask, ArgMask); } + // Conservatively clear IsMustAlias unless only MustAlias is found. + IsMustAlias &= (ArgAlias == MustAlias); } } // Return NoModRef if no alias found with any argument. @@ -200,6 +203,8 @@ return ModRefInfo::NoModRef; // Logical & between other AA analyses and argument analysis. Result = intersectModRef(Result, AllArgsMask); + // If only MustAlias found above, set Must bit. + Result = IsMustAlias ? setMust(Result) : clearMust(Result); } // If Loc is a constant memory location, the call definitely could not @@ -251,6 +256,7 @@ if (onlyAccessesArgPointees(CS2B)) { ModRefInfo R = ModRefInfo::NoModRef; if (doesAccessArgPointees(CS2B)) { + bool IsMustAlias = true; for (auto I = CS2.arg_begin(), E = CS2.arg_end(); I != E; ++I) { const Value *Arg = *I; if (!Arg->getType()->isPointerTy()) @@ -274,10 +280,19 @@ ModRefInfo ModRefCS1 = getModRefInfo(CS1, CS2ArgLoc); ArgMask = intersectModRef(ArgMask, ModRefCS1); + // Conservatively clear IsMustAlias unless only MustAlias is found. + IsMustAlias &= isMustSet(ModRefCS1); + R = intersectModRef(unionModRef(R, ArgMask), Result); - if (R == Result) + if (R == Result) { + // On early exit, not all args were checked, cannot set Must. + if (I + 1 != E) + IsMustAlias = false; break; + } } + // If Alias found and only MustAlias found above, set Must bit. + R = IsMustAlias ? setMust(R) : clearMust(R); } return R; } @@ -287,6 +302,7 @@ if (onlyAccessesArgPointees(CS1B)) { ModRefInfo R = ModRefInfo::NoModRef; if (doesAccessArgPointees(CS1B)) { + bool IsMustAlias = true; for (auto I = CS1.arg_begin(), E = CS1.arg_end(); I != E; ++I) { const Value *Arg = *I; if (!Arg->getType()->isPointerTy()) @@ -303,9 +319,18 @@ (isRefSet(ArgModRefCS1) && isModSet(ModRefCS2))) R = intersectModRef(unionModRef(R, ArgModRefCS1), Result); - if (R == Result) + // Conservatively clear IsMustAlias unless only MustAlias is found. + IsMustAlias &= isMustSet(ModRefCS2); + + if (R == Result) { + // On early exit, not all args were checked, cannot set Must. + if (I + 1 != E) + IsMustAlias = false; break; + } } + // If Alias found and only MustAlias found above, set Must bit. + R = IsMustAlias ? setMust(R) : clearMust(R); } return R; } @@ -353,9 +378,13 @@ // If the load address doesn't alias the given address, it doesn't read // or write the specified memory. - if (Loc.Ptr && !alias(MemoryLocation::get(L), Loc)) - return ModRefInfo::NoModRef; - + if (Loc.Ptr) { + AliasResult AR = alias(MemoryLocation::get(L), Loc); + if (AR == NoAlias) + return ModRefInfo::NoModRef; + if (AR == MustAlias) + return ModRefInfo::MustRef; + } // Otherwise, a load just reads. return ModRefInfo::Ref; } @@ -367,15 +396,20 @@ return ModRefInfo::ModRef; if (Loc.Ptr) { + AliasResult AR = alias(MemoryLocation::get(S), Loc); // If the store address cannot alias the pointer in question, then the // specified memory cannot be modified by the store. - if (!alias(MemoryLocation::get(S), Loc)) + if (AR == 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)) return ModRefInfo::NoModRef; + + // If the store address aliases the pointer as must alias, set Must. + if (AR == MustAlias) + return ModRefInfo::MustMod; } // Otherwise, a store just writes. @@ -393,15 +427,20 @@ ModRefInfo AAResults::getModRefInfo(const VAArgInst *V, const MemoryLocation &Loc) { if (Loc.Ptr) { + AliasResult AR = alias(MemoryLocation::get(V), Loc); // If the va_arg address cannot alias the pointer in question, then the // specified memory cannot be accessed by the va_arg. - if (!alias(MemoryLocation::get(V), Loc)) + if (AR == NoAlias) return ModRefInfo::NoModRef; // If the pointer is a pointer to constant memory, then it could not have // been modified by this va_arg. if (pointsToConstantMemory(Loc)) return ModRefInfo::NoModRef; + + // If the va_arg aliases the pointer as must alias, set Must. + if (AR == MustAlias) + return ModRefInfo::MustModRef; } // Otherwise, a va_arg reads and writes. @@ -440,9 +479,17 @@ if (isStrongerThanMonotonic(CX->getSuccessOrdering())) return ModRefInfo::ModRef; - // If the cmpxchg address does not alias the location, it does not access it. - if (Loc.Ptr && !alias(MemoryLocation::get(CX), Loc)) - return ModRefInfo::NoModRef; + if (Loc.Ptr) { + AliasResult AR = alias(MemoryLocation::get(CX), Loc); + // If the cmpxchg address does not alias the location, it does not access + // it. + if (AR == NoAlias) + return ModRefInfo::NoModRef; + + // If the cmpxchg address aliases the pointer as must alias, set Must. + if (AR == MustAlias) + return ModRefInfo::MustModRef; + } return ModRefInfo::ModRef; } @@ -453,9 +500,17 @@ if (isStrongerThanMonotonic(RMW->getOrdering())) return ModRefInfo::ModRef; - // If the atomicrmw address does not alias the location, it does not access it. - if (Loc.Ptr && !alias(MemoryLocation::get(RMW), Loc)) - return ModRefInfo::NoModRef; + if (Loc.Ptr) { + AliasResult AR = alias(MemoryLocation::get(RMW), Loc); + // If the atomicrmw address does not alias the location, it does not access + // it. + if (AR == NoAlias) + return ModRefInfo::NoModRef; + + // If the atomicrmw address aliases the pointer as must alias, set Must. + if (AR == MustAlias) + return ModRefInfo::MustModRef; + } return ModRefInfo::ModRef; } @@ -493,6 +548,8 @@ unsigned ArgNo = 0; ModRefInfo R = ModRefInfo::NoModRef; + bool MustAlias = true; + // Set flag only if no May found and all operands processed. for (auto CI = CS.data_operands_begin(), CE = CS.data_operands_end(); CI != CE; ++CI, ++ArgNo) { // Only look at the no-capture or byval pointer arguments. If this @@ -503,11 +560,14 @@ ArgNo < CS.getNumArgOperands() && !CS.isByValArgument(ArgNo))) continue; + AliasResult AR = alias(MemoryLocation(*CI), MemoryLocation(Object)); // If this is a no-capture pointer argument, see if we can tell that it // is impossible to alias the pointer we're checking. If not, we have to // assume that the call could touch the pointer, even though it doesn't // escape. - if (isNoAlias(MemoryLocation(*CI), MemoryLocation(Object))) + if (AR != MustAlias) + MustAlias = false; + if (AR == NoAlias) continue; if (CS.doesNotAccessMemory(ArgNo)) continue; @@ -515,9 +575,10 @@ R = ModRefInfo::Ref; continue; } + // Not returning MustModRef since we have not seen all the arguments. return ModRefInfo::ModRef; } - return R; + return MustAlias ? setMust(R) : clearMust(R); } /// canBasicBlockModify - Return true if it is possible for execution of the Index: llvm/trunk/lib/Analysis/AliasAnalysisEvaluator.cpp =================================================================== --- llvm/trunk/lib/Analysis/AliasAnalysisEvaluator.cpp +++ llvm/trunk/lib/Analysis/AliasAnalysisEvaluator.cpp @@ -31,9 +31,13 @@ static cl::opt PrintMustAlias("print-must-aliases", cl::ReallyHidden); static cl::opt PrintNoModRef("print-no-modref", cl::ReallyHidden); -static cl::opt PrintMod("print-mod", cl::ReallyHidden); static cl::opt PrintRef("print-ref", cl::ReallyHidden); +static cl::opt PrintMod("print-mod", cl::ReallyHidden); static cl::opt PrintModRef("print-modref", cl::ReallyHidden); +static cl::opt PrintMust("print-must", cl::ReallyHidden); +static cl::opt PrintMustRef("print-mustref", cl::ReallyHidden); +static cl::opt PrintMustMod("print-mustmod", cl::ReallyHidden); +static cl::opt PrintMustModRef("print-mustmodref", cl::ReallyHidden); static cl::opt EvalAAMD("evaluate-aa-metadata", cl::ReallyHidden); @@ -262,6 +266,25 @@ F.getParent()); ++ModRefCount; break; + case ModRefInfo::Must: + PrintModRefResults("Must", PrintMust, I, Pointer, F.getParent()); + ++MustCount; + break; + case ModRefInfo::MustMod: + PrintModRefResults("Just Mod (MustAlias)", PrintMustMod, I, Pointer, + F.getParent()); + ++MustModCount; + break; + case ModRefInfo::MustRef: + PrintModRefResults("Just Ref (MustAlias)", PrintMustRef, I, Pointer, + F.getParent()); + ++MustRefCount; + break; + case ModRefInfo::MustModRef: + PrintModRefResults("Both ModRef (MustAlias)", PrintMustModRef, I, + Pointer, F.getParent()); + ++MustModRefCount; + break; } } } @@ -288,6 +311,25 @@ PrintModRefResults("Both ModRef", PrintModRef, *C, *D, F.getParent()); ++ModRefCount; break; + case ModRefInfo::Must: + PrintModRefResults("Must", PrintMust, *C, *D, F.getParent()); + ++MustCount; + break; + case ModRefInfo::MustMod: + PrintModRefResults("Just Mod (MustAlias)", PrintMustMod, *C, *D, + F.getParent()); + ++MustModCount; + break; + case ModRefInfo::MustRef: + PrintModRefResults("Just Ref (MustAlias)", PrintMustRef, *C, *D, + F.getParent()); + ++MustRefCount; + break; + case ModRefInfo::MustModRef: + PrintModRefResults("Both ModRef (MustAlias)", PrintMustModRef, *C, *D, + F.getParent()); + ++MustModRefCount; + break; } } } @@ -325,7 +367,8 @@ } // Display the summary for mod/ref analysis - int64_t ModRefSum = NoModRefCount + ModCount + RefCount + ModRefCount; + int64_t ModRefSum = NoModRefCount + RefCount + ModCount + ModRefCount + + MustCount + MustRefCount + MustModCount + MustModRefCount; if (ModRefSum == 0) { errs() << " Alias Analysis Mod/Ref Evaluator Summary: no " "mod/ref!\n"; @@ -339,10 +382,22 @@ PrintPercent(RefCount, ModRefSum); errs() << " " << ModRefCount << " mod & ref responses "; PrintPercent(ModRefCount, ModRefSum); + errs() << " " << MustCount << " must responses "; + PrintPercent(MustCount, ModRefSum); + errs() << " " << MustModCount << " must mod responses "; + PrintPercent(MustModCount, ModRefSum); + errs() << " " << MustRefCount << " must ref responses "; + PrintPercent(MustRefCount, ModRefSum); + errs() << " " << MustModRefCount << " must mod & ref responses "; + PrintPercent(MustModRefCount, ModRefSum); errs() << " Alias Analysis Evaluator Mod/Ref Summary: " << NoModRefCount * 100 / ModRefSum << "%/" << ModCount * 100 / ModRefSum << "%/" << RefCount * 100 / ModRefSum - << "%/" << ModRefCount * 100 / ModRefSum << "%\n"; + << "%/" << ModRefCount * 100 / ModRefSum << "%/" + << MustCount * 100 / ModRefSum << "%/" + << MustRefCount * 100 / ModRefSum << "%/" + << MustModCount * 100 / ModRefSum << "%/" + << MustModRefCount * 100 / ModRefSum << "%\n"; } } Index: llvm/trunk/lib/Analysis/BasicAliasAnalysis.cpp =================================================================== --- llvm/trunk/lib/Analysis/BasicAliasAnalysis.cpp +++ llvm/trunk/lib/Analysis/BasicAliasAnalysis.cpp @@ -781,6 +781,7 @@ // Optimistically assume that call doesn't touch Object and check this // assumption in the following loop. ModRefInfo Result = ModRefInfo::NoModRef; + bool IsMustAlias = true; unsigned OperandNo = 0; for (auto CI = CS.data_operands_begin(), CE = CS.data_operands_end(); @@ -802,7 +803,8 @@ // is impossible to alias the pointer we're checking. AliasResult AR = getBestAAResults().alias(MemoryLocation(*CI), MemoryLocation(Object)); - + if (AR != MustAlias) + IsMustAlias = false; // Operand doesnt alias 'Object', continue looking for other aliases if (AR == NoAlias) continue; @@ -818,13 +820,20 @@ continue; } // This operand aliases 'Object' and call reads and writes into it. + // Setting ModRef will not yield an early return below, MustAlias is not + // used further. Result = ModRefInfo::ModRef; break; } + // No operand aliases, reset Must bit. Add below if at least one aliases + // and all aliases found are MustAlias. + if (isNoModRef(Result)) + IsMustAlias = false; + // Early return if we improved mod ref information if (!isModAndRefSet(Result)) - return Result; + return IsMustAlias ? setMust(Result) : clearMust(Result); } // If the CallSite is to malloc or calloc, we can assume that it doesn't Index: llvm/trunk/lib/Analysis/GlobalsModRef.cpp =================================================================== --- llvm/trunk/lib/Analysis/GlobalsModRef.cpp +++ llvm/trunk/lib/Analysis/GlobalsModRef.cpp @@ -85,12 +85,17 @@ /// The bit that flags that this function may read any global. This is /// chosen to mix together with ModRefInfo bits. /// FIXME: This assumes ModRefInfo lattice will remain 4 bits! + /// It overlaps with ModRefInfo::Must bit! + /// FunctionInfo.getModRefInfo() masks out everything except ModRef so + /// this remains correct, but the Must info is lost. enum { MayReadAnyGlobal = 4 }; /// Checks to document the invariants of the bit packing here. - static_assert((MayReadAnyGlobal & static_cast(ModRefInfo::ModRef)) == 0, + static_assert((MayReadAnyGlobal & static_cast(ModRefInfo::MustModRef)) == + 0, "ModRef and the MayReadAnyGlobal flag bits overlap."); - static_assert(((MayReadAnyGlobal | static_cast(ModRefInfo::ModRef)) >> + static_assert(((MayReadAnyGlobal | + static_cast(ModRefInfo::MustModRef)) >> AlignedMapPointerTraits::NumLowBitsAvailable) == 0, "Insufficient low bits to store our flag and ModRef info."); @@ -125,14 +130,22 @@ return *this; } + /// This method clears MayReadAnyGlobal bit added by GlobalsAAResult to return + /// the corresponding ModRefInfo. It must align in functionality with + /// clearMust(). + ModRefInfo globalClearMayReadAnyGlobal(int I) const { + return ModRefInfo((I & static_cast(ModRefInfo::ModRef)) | + static_cast(ModRefInfo::NoModRef)); + } + /// Returns the \c ModRefInfo info for this function. ModRefInfo getModRefInfo() const { - return ModRefInfo(Info.getInt() & static_cast(ModRefInfo::ModRef)); + return globalClearMayReadAnyGlobal(Info.getInt()); } /// Adds new \c ModRefInfo for this function to its state. void addModRefInfo(ModRefInfo NewMRI) { - Info.setInt(Info.getInt() | static_cast(NewMRI)); + Info.setInt(Info.getInt() | static_cast(setMust(NewMRI))); } /// Returns whether this function may read any global variable, and we don't Index: llvm/trunk/lib/Analysis/MemoryDependenceAnalysis.cpp =================================================================== --- llvm/trunk/lib/Analysis/MemoryDependenceAnalysis.cpp +++ llvm/trunk/lib/Analysis/MemoryDependenceAnalysis.cpp @@ -647,6 +647,7 @@ // Ok, this store might clobber the query pointer. Check to see if it is // a must alias: in this case, we want to return this as a def. + // FIXME: Use ModRefInfo::Must bit from getModRefInfo call above. MemoryLocation StoreLoc = MemoryLocation::get(SI); // If we found a pointer, check if it could be the same as our pointer. @@ -690,7 +691,7 @@ // If necessary, perform additional analysis. if (isModAndRefSet(MR)) MR = AA.callCapturesBefore(Inst, MemLoc, &DT, &OBB); - switch (MR) { + switch (clearMust(MR)) { case ModRefInfo::NoModRef: // If the call has no effect on the queried pointer, just ignore it. continue; Index: llvm/trunk/test/Analysis/BasicAA/args-rets-allocas-loads.ll =================================================================== --- llvm/trunk/test/Analysis/BasicAA/args-rets-allocas-loads.ll +++ llvm/trunk/test/Analysis/BasicAA/args-rets-allocas-loads.ll @@ -308,4 +308,9 @@ ; CHECK-NEXT: 0 mod responses (0.0%) ; CHECK-NEXT: 0 ref responses (0.0%) ; CHECK-NEXT: 140 mod & ref responses (76.0%) -; CHECK-NEXT: Alias Analysis Evaluator Mod/Ref Summary: 23%/0%/0%/76% +; CHECK-NEXT: 0 must responses (0.0%) +; CHECK-NEXT: 0 must mod responses (0.0%) +; CHECK-NEXT: 0 must ref responses (0.0%) +; CHECK-NEXT: 0 must mod & ref responses (0.0%) +; CHECK-NEXT: Alias Analysis Evaluator Mod/Ref Summary: 23%/0%/0%/76%/0%/0%/0%/0% + Index: llvm/trunk/test/Analysis/BasicAA/call-attrs.ll =================================================================== --- llvm/trunk/test/Analysis/BasicAA/call-attrs.ll +++ llvm/trunk/test/Analysis/BasicAA/call-attrs.ll @@ -31,12 +31,12 @@ ret void } -; CHECK: Just Ref: Ptr: i8* %p <-> call void @readonly_attr(i8* %p) +; CHECK: Just Ref (MustAlias): Ptr: i8* %p <-> call void @readonly_attr(i8* %p) ; CHECK: Just Ref: Ptr: i8* %p <-> call void @readonly_func(i8* %p) -; CHECK: Just Mod: Ptr: i8* %p <-> call void @writeonly_attr(i8* %p) +; CHECK: Just Mod (MustAlias): Ptr: i8* %p <-> call void @writeonly_attr(i8* %p) ; CHECK: Just Mod: Ptr: i8* %p <-> call void @writeonly_func(i8* %p) ; CHECK: NoModRef: Ptr: i8* %p <-> call void @readnone_attr(i8* %p) ; CHECK: NoModRef: Ptr: i8* %p <-> call void @readnone_func(i8* %p) ; CHECK: Both ModRef: Ptr: i8* %p <-> call void @read_write(i8* %p, i8* %p, i8* %p) -; CHECK: Just Ref: Ptr: i8* %p <-> call void @func() [ "deopt"(i8* %p) ] +; CHECK: Just Ref (MustAlias): Ptr: i8* %p <-> call void @func() [ "deopt"(i8* %p) ] ; CHECK: Both ModRef: Ptr: i8* %p <-> call void @writeonly_attr(i8* %p) [ "deopt"(i8* %p) ] Index: llvm/trunk/test/Analysis/BasicAA/cs-cs-arm.ll =================================================================== --- llvm/trunk/test/Analysis/BasicAA/cs-cs-arm.ll +++ llvm/trunk/test/Analysis/BasicAA/cs-cs-arm.ll @@ -19,11 +19,11 @@ ; CHECK-LABEL: Function: test1: ; CHECK: NoAlias: i8* %p, i8* %q -; CHECK: Just Ref: Ptr: i8* %p <-> %a = call <8 x i16> @llvm.arm.neon.vld1.v8i16.p0i8(i8* %p, i32 16) +; CHECK: Just Ref (MustAlias): Ptr: i8* %p <-> %a = call <8 x i16> @llvm.arm.neon.vld1.v8i16.p0i8(i8* %p, i32 16) ; CHECK: NoModRef: Ptr: i8* %q <-> %a = call <8 x i16> @llvm.arm.neon.vld1.v8i16.p0i8(i8* %p, i32 16) ; CHECK: NoModRef: Ptr: i8* %p <-> call void @llvm.arm.neon.vst1.p0i8.v8i16(i8* %q, <8 x i16> %y, i32 16) -; CHECK: Both ModRef: Ptr: i8* %q <-> call void @llvm.arm.neon.vst1.p0i8.v8i16(i8* %q, <8 x i16> %y, i32 16) -; CHECK: Just Ref: Ptr: i8* %p <-> %b = call <8 x i16> @llvm.arm.neon.vld1.v8i16.p0i8(i8* %p, i32 16) +; CHECK: Both ModRef (MustAlias): Ptr: i8* %q <-> call void @llvm.arm.neon.vst1.p0i8.v8i16(i8* %q, <8 x i16> %y, i32 16) +; CHECK: Just Ref (MustAlias): Ptr: i8* %p <-> %b = call <8 x i16> @llvm.arm.neon.vld1.v8i16.p0i8(i8* %p, i32 16) ; CHECK: NoModRef: Ptr: i8* %q <-> %b = call <8 x i16> @llvm.arm.neon.vld1.v8i16.p0i8(i8* %p, i32 16) ; CHECK: NoModRef: %a = call <8 x i16> @llvm.arm.neon.vld1.v8i16.p0i8(i8* %p, i32 16) #{{[0-9]+}} <-> call void @llvm.arm.neon.vst1.p0i8.v8i16(i8* %q, <8 x i16> %y, i32 16) ; CHECK: NoModRef: %a = call <8 x i16> @llvm.arm.neon.vld1.v8i16.p0i8(i8* %p, i32 16) #{{[0-9]+}} <-> %b = call <8 x i16> @llvm.arm.neon.vld1.v8i16.p0i8(i8* %p, i32 16) Index: llvm/trunk/test/Analysis/BasicAA/cs-cs.ll =================================================================== --- llvm/trunk/test/Analysis/BasicAA/cs-cs.ll +++ llvm/trunk/test/Analysis/BasicAA/cs-cs.ll @@ -164,7 +164,7 @@ ; CHECK-LABEL: Function: test4: ; CHECK: NoAlias: i8* %P, i8* %Q -; CHECK: Just Mod: Ptr: i8* %P <-> tail call void @llvm.memset.p0i8.i64(i8* %P, i8 42, i64 8, i32 1, i1 false) +; CHECK: Just Mod (MustAlias): Ptr: i8* %P <-> tail call void @llvm.memset.p0i8.i64(i8* %P, i8 42, i64 8, i32 1, i1 false) ; CHECK: NoModRef: Ptr: i8* %Q <-> tail call void @llvm.memset.p0i8.i64(i8* %P, i8 42, i64 8, i32 1, i1 false) ; CHECK: Just Mod: Ptr: i8* %P <-> tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i32 1, i1 false) ; CHECK: Just Ref: Ptr: i8* %Q <-> tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i32 1, i1 false) @@ -192,6 +192,26 @@ ; CHECK: Just Mod: tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %R, i64 12, i32 1, i1 false) <-> tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i32 1, i1 false) } +define void @test5a(i8* noalias %P, i8* noalias %Q, i8* noalias %R) nounwind ssp { + tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i32 1, i1 false) + tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %R, i64 12, i32 1, i1 false) + ret void + +; CHECK-LABEL: Function: test5a: + +; CHECK: NoAlias: i8* %P, i8* %Q +; CHECK: NoAlias: i8* %P, i8* %R +; CHECK: NoAlias: i8* %Q, i8* %R +; CHECK: Just Mod: Ptr: i8* %P <-> tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i32 1, i1 false) +; CHECK: Just Ref: Ptr: i8* %Q <-> tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i32 1, i1 false) +; CHECK: NoModRef: Ptr: i8* %R <-> tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i32 1, i1 false) +; CHECK: Just Mod: Ptr: i8* %P <-> tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %R, i64 12, i32 1, i1 false) +; CHECK: NoModRef: Ptr: i8* %Q <-> tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %R, i64 12, i32 1, i1 false) +; CHECK: Just Ref: Ptr: i8* %R <-> tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %R, i64 12, i32 1, i1 false) +; CHECK: Just Mod: tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i32 1, i1 false) <-> tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %R, i64 12, i32 1, i1 false) +; CHECK: Just Mod: tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %R, i64 12, i32 1, i1 false) <-> tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %P, i8* %Q, i64 12, i32 1, i1 false) +} + define void @test6(i8* %P) #3 { call void @llvm.memset.p0i8.i64(i8* %P, i8 -51, i64 32, i32 8, i1 false) call void @a_readonly_func(i8* %P) @@ -199,7 +219,7 @@ ; CHECK-LABEL: Function: test6: -; CHECK: Just Mod: Ptr: i8* %P <-> call void @llvm.memset.p0i8.i64(i8* %P, i8 -51, i64 32, i32 8, i1 false) +; CHECK: Just Mod (MustAlias): Ptr: i8* %P <-> call void @llvm.memset.p0i8.i64(i8* %P, i8 -51, i64 32, i32 8, i1 false) ; CHECK: Just Ref: Ptr: i8* %P <-> call void @a_readonly_func(i8* %P) ; CHECK: Just Mod: call void @llvm.memset.p0i8.i64(i8* %P, i8 -51, i64 32, i32 8, i1 false) <-> call void @a_readonly_func(i8* %P) ; CHECK: Just Ref: call void @a_readonly_func(i8* %P) <-> call void @llvm.memset.p0i8.i64(i8* %P, i8 -51, i64 32, i32 8, i1 false) @@ -237,9 +257,9 @@ ; CHECK: NoModRef: Ptr: i8* %p <-> call void @an_inaccessiblememonly_func() ; CHECK: NoModRef: Ptr: i8* %q <-> call void @an_inaccessiblememonly_func() ; CHECK: NoModRef: Ptr: i8* %p <-> call void @an_inaccessibleorargmemonly_func(i8* %q) -; CHECK: Both ModRef: Ptr: i8* %q <-> call void @an_inaccessibleorargmemonly_func(i8* %q) +; CHECK: Both ModRef (MustAlias): Ptr: i8* %q <-> call void @an_inaccessibleorargmemonly_func(i8* %q) ; CHECK: NoModRef: Ptr: i8* %p <-> call void @an_argmemonly_func(i8* %q) -; CHECK: Both ModRef: Ptr: i8* %q <-> call void @an_argmemonly_func(i8* %q) +; CHECK: Both ModRef (MustAlias): Ptr: i8* %q <-> call void @an_argmemonly_func(i8* %q) ; CHECK: Just Ref: call void @a_readonly_func(i8* %p) <-> call void @an_inaccessiblememonly_func() ; CHECK: Just Ref: call void @a_readonly_func(i8* %p) <-> call void @an_inaccessibleorargmemonly_func(i8* %q) ; CHECK: Just Ref: call void @a_readonly_func(i8* %p) <-> call void @an_argmemonly_func(i8* %q) @@ -254,12 +274,34 @@ ; CHECK: Both ModRef: call void @an_inaccessibleorargmemonly_func(i8* %q) <-> call void @a_readonly_func(i8* %p) ; CHECK: Both ModRef: call void @an_inaccessibleorargmemonly_func(i8* %q) <-> call void @a_writeonly_func(i8* %q) ; CHECK: Both ModRef: call void @an_inaccessibleorargmemonly_func(i8* %q) <-> call void @an_inaccessiblememonly_func() -; CHECK: Both ModRef: call void @an_inaccessibleorargmemonly_func(i8* %q) <-> call void @an_argmemonly_func(i8* %q) +; CHECK: Both ModRef (MustAlias): call void @an_inaccessibleorargmemonly_func(i8* %q) <-> call void @an_argmemonly_func(i8* %q) ; CHECK: Both ModRef: call void @an_argmemonly_func(i8* %q) <-> call void @a_readonly_func(i8* %p) ; CHECK: Both ModRef: call void @an_argmemonly_func(i8* %q) <-> call void @a_writeonly_func(i8* %q) ; CHECK: NoModRef: call void @an_argmemonly_func(i8* %q) <-> call void @an_inaccessiblememonly_func() -; CHECK: Both ModRef: call void @an_argmemonly_func(i8* %q) <-> call void @an_inaccessibleorargmemonly_func(i8* %q) +; CHECK: Both ModRef (MustAlias): call void @an_argmemonly_func(i8* %q) <-> call void @an_inaccessibleorargmemonly_func(i8* %q) +} + +;; test that MustAlias is set for calls when no MayAlias is found. +declare void @another_argmemonly_func(i8*, i8*) #0 +define void @test8a(i8* noalias %p, i8* noalias %q) { +entry: + call void @another_argmemonly_func(i8* %p, i8* %q) + ret void + +; CHECK-LABEL: Function: test8a +; CHECK: Both ModRef: Ptr: i8* %p <-> call void @another_argmemonly_func(i8* %p, i8* %q) +; CHECK: Both ModRef: Ptr: i8* %q <-> call void @another_argmemonly_func(i8* %p, i8* %q) } +define void @test8b(i8* %p, i8* %q) { +entry: + call void @another_argmemonly_func(i8* %p, i8* %q) + ret void + +; CHECK-LABEL: Function: test8b +; CHECK: Both ModRef: Ptr: i8* %p <-> call void @another_argmemonly_func(i8* %p, i8* %q) +; CHECK: Both ModRef: Ptr: i8* %q <-> call void @another_argmemonly_func(i8* %p, i8* %q) +} + ;; test that unknown operand bundle has unknown effect to the heap define void @test9(i8* %p) { @@ -310,9 +352,9 @@ ; CHECK: NoModRef: Ptr: i8* %p <-> call void @an_inaccessiblememonly_func() #7 [ "unknown"() ] ; CHECK: NoModRef: Ptr: i8* %q <-> call void @an_inaccessiblememonly_func() #7 [ "unknown"() ] ; CHECK: NoModRef: Ptr: i8* %p <-> call void @an_inaccessibleorargmemonly_func(i8* %q) #8 [ "unknown"() ] -; CHECK: Both ModRef: Ptr: i8* %q <-> call void @an_inaccessibleorargmemonly_func(i8* %q) #8 [ "unknown"() ] +; CHECK: Both ModRef (MustAlias): Ptr: i8* %q <-> call void @an_inaccessibleorargmemonly_func(i8* %q) #8 [ "unknown"() ] ; CHECK: NoModRef: Ptr: i8* %p <-> call void @an_argmemonly_func(i8* %q) #9 [ "unknown"() ] -; CHECK: Both ModRef: Ptr: i8* %q <-> call void @an_argmemonly_func(i8* %q) #9 [ "unknown"() ] +; CHECK: Both ModRef (MustAlias): Ptr: i8* %q <-> call void @an_argmemonly_func(i8* %q) #9 [ "unknown"() ] ; CHECK: Just Ref: call void @a_readonly_func(i8* %p) #6 [ "unknown"() ] <-> call void @an_inaccessiblememonly_func() #7 [ "unknown"() ] ; CHECK: Just Ref: call void @a_readonly_func(i8* %p) #6 [ "unknown"() ] <-> call void @an_inaccessibleorargmemonly_func(i8* %q) #8 [ "unknown"() ] ; CHECK: Just Ref: call void @a_readonly_func(i8* %p) #6 [ "unknown"() ] <-> call void @an_argmemonly_func(i8* %q) #9 [ "unknown"() ] @@ -321,10 +363,10 @@ ; CHECK: NoModRef: call void @an_inaccessiblememonly_func() #7 [ "unknown"() ] <-> call void @an_argmemonly_func(i8* %q) #9 [ "unknown"() ] ; CHECK: Both ModRef: call void @an_inaccessibleorargmemonly_func(i8* %q) #8 [ "unknown"() ] <-> call void @a_readonly_func(i8* %p) #6 [ "unknown"() ] ; CHECK: Both ModRef: call void @an_inaccessibleorargmemonly_func(i8* %q) #8 [ "unknown"() ] <-> call void @an_inaccessiblememonly_func() #7 [ "unknown"() ] -; CHECK: Both ModRef: call void @an_inaccessibleorargmemonly_func(i8* %q) #8 [ "unknown"() ] <-> call void @an_argmemonly_func(i8* %q) #9 [ "unknown"() ] +; CHECK: Both ModRef (MustAlias): call void @an_inaccessibleorargmemonly_func(i8* %q) #8 [ "unknown"() ] <-> call void @an_argmemonly_func(i8* %q) #9 [ "unknown"() ] ; CHECK: Both ModRef: call void @an_argmemonly_func(i8* %q) #9 [ "unknown"() ] <-> call void @a_readonly_func(i8* %p) #6 [ "unknown"() ] ; CHECK: NoModRef: call void @an_argmemonly_func(i8* %q) #9 [ "unknown"() ] <-> call void @an_inaccessiblememonly_func() #7 [ "unknown"() ] -; CHECK: Both ModRef: call void @an_argmemonly_func(i8* %q) #9 [ "unknown"() ] <-> call void @an_inaccessibleorargmemonly_func(i8* %q) #8 [ "unknown"() ] +; CHECK: Both ModRef (MustAlias): call void @an_argmemonly_func(i8* %q) #9 [ "unknown"() ] <-> call void @an_inaccessibleorargmemonly_func(i8* %q) #8 [ "unknown"() ] } attributes #0 = { argmemonly nounwind }