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 @@ -349,16 +349,40 @@ using AliasCacheT = SmallDenseMap; AliasCacheT AliasCache; + using OffsetPair = std::pair; + using OffsetsCacheT = SmallDenseMap; + OffsetsCacheT ClobberOffsets; + using IsCapturedCacheT = SmallDenseMap; IsCapturedCacheT IsCapturedCache; - AAQueryInfo() : AliasCache(), IsCapturedCache() {} + AAQueryInfo() : AliasCache(), ClobberOffsets(), IsCapturedCache() {} AliasResult updateResult(const LocPair &Locs, AliasResult Result) { auto It = AliasCache.find(Locs); assert(It != AliasCache.end() && "Entry must have existed"); return It->second = Result; } + + Optional getClobberOffset(OffsetPair OP) const { + const bool Swapped = OP.first > OP.second; + if (Swapped) { + std::swap(OP.first, OP.second); + } + const auto IOff = ClobberOffsets.find(OP); + if (IOff != ClobberOffsets.end()) { + return Swapped ? -IOff->second : IOff->second; + } + return None; + } + + void setClobberOffset(OffsetPair OP, int64_t Offset) { + if (OP.first > OP.second) { + std::swap(OP.first, OP.second); + Offset = -Offset; + } + ClobberOffsets[OP] = Offset; + } }; class BatchAAResults; @@ -696,7 +720,7 @@ /// Return information about whether two call sites may refer to the same set /// of memory locations. See the AA documentation for details: - /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo + /// http://llvm.org/docs/AliasAnalysis.html ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2); /// Return information about whether a particular call site modifies @@ -837,6 +861,8 @@ return alias(MemoryLocation(V1, LocationSize::precise(1)), MemoryLocation(V2, LocationSize::precise(1))) == MustAlias; } + Optional getClobberOffset(const MemoryLocation &LocA, + const MemoryLocation &LocB); }; /// Temporary typedef for legacy code that uses a generic \c AliasAnalysis @@ -903,7 +929,7 @@ /// Return information about whether two call sites may refer to the same set /// of memory locations. See the AA documentation for details: - /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo + /// http://llvm.org/docs/AliasAnalysis.html virtual ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, AAQueryInfo &AAQI) = 0; diff --git a/llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h b/llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h --- a/llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h +++ b/llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h @@ -363,6 +363,7 @@ PredIteratorCache PredCache; unsigned DefaultBlockScanLimit; + Optional ClobberOffset; public: MemoryDependenceResults(AAResults &AA, AssumptionCache &AC, @@ -468,6 +469,8 @@ /// Release memory in caches. void releaseMemory(); + Optional getClobberOffset() const { return ClobberOffset; } + private: MemDepResult getCallDependencyFrom(CallBase *Call, bool isReadOnlyCall, BasicBlock::iterator ScanIt, 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 @@ -937,6 +937,13 @@ return AAR; } +Optional BatchAAResults::getClobberOffset(const MemoryLocation &LocA, + const MemoryLocation &LocB) { + const Value *V1 = LocA.Ptr->stripPointerCastsAndInvariantGroups(); + const Value *V2 = LocB.Ptr->stripPointerCastsAndInvariantGroups(); + return AAQI.getClobberOffset({V1, V2}); +} + bool llvm::isNoAliasCall(const Value *V) { if (const auto *Call = dyn_cast(V)) return Call->hasRetAttr(Attribute::NoAlias); 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 @@ -1188,24 +1188,40 @@ // that the objects are partially overlapping. If the difference is // greater, we know they do not overlap. if (DecompGEP1.Offset != 0 && DecompGEP1.VarIndices.empty()) { - if (DecompGEP1.Offset.sge(0)) { - if (V2Size.hasValue()) { - if (DecompGEP1.Offset.ult(V2Size.getValue())) - return PartialAlias; - return NoAlias; - } - } else { - // We have the situation where: + APInt &Off = DecompGEP1.Offset; + + // Initialize for Off >= 0 (V2 <= GEP1) case. + const Value *LeftPtr = V2; + const Value *RightPtr = GEP1; + const LocationSize *VLeftSize = &V2Size; + const LocationSize *VRightSize = &V1Size; + + if (!Off.sge(0)) { + // Swap if we have the situation where: // + + // | BaseOffset | // ---------------->| // |-->V1Size |-------> V2Size // GEP1 V2 - if (V1Size.hasValue()) { - if ((-DecompGEP1.Offset).ult(V1Size.getValue())) - return PartialAlias; - return NoAlias; + std::swap(LeftPtr, RightPtr); + std::swap(VLeftSize, VRightSize); + Off = -Off; + } + + if (VLeftSize->hasValue()) { + if (Off.ult(VLeftSize->getValue())) { + // Conservatively drop processing if a phi was visited and/or offset is + // too big. + if (VisitedPhiBBs.empty() && VRightSize->hasValue() && + Off.ule(INT64_MAX)) { + // Memory refernced by right pointer is nested. Save the offset in + // cache. + if ((Off + VRightSize->getValue()).ule(VLeftSize->getValue())) + AAQI.setClobberOffset({LeftPtr, RightPtr}, Off.getSExtValue()); + } + return PartialAlias; } + return NoAlias; } } @@ -1488,10 +1504,10 @@ // have been cached earlier may no longer be valid. Perform recursive queries // with a new AAQueryInfo. AAQueryInfo NewAAQI; - AAQueryInfo *UseAAQI = BlockInserted ? &NewAAQI : &AAQI; + AAQueryInfo &UseAAQI = BlockInserted ? NewAAQI : AAQI; AliasResult Alias = aliasCheck(V2, V2Size, V2AAInfo, V1Srcs[0], PNSize, - PNAAInfo, *UseAAQI, UnderV2); + PNAAInfo, UseAAQI, UnderV2); // Early exit if the check of the first PHI source against V2 is MayAlias. // Other results are not possible. @@ -1507,8 +1523,8 @@ for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) { Value *V = V1Srcs[i]; - AliasResult ThisAlias = aliasCheck(V2, V2Size, V2AAInfo, V, PNSize, - PNAAInfo, *UseAAQI, UnderV2); + AliasResult ThisAlias = + aliasCheck(V2, V2Size, V2AAInfo, V, PNSize, PNAAInfo, UseAAQI, UnderV2); Alias = MergeAliasResults(ThisAlias, Alias); if (Alias == MayAlias) break; 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 @@ -520,16 +520,12 @@ if (R == MustAlias) return MemDepResult::getDef(Inst); -#if 0 // FIXME: Temporarily disabled. GVN is cleverly rewriting loads - // in terms of clobbering loads, but since it does this by looking - // at the clobbering load directly, it doesn't know about any - // phi translation that may have happened along the way. - // If we have a partial alias, then return this as a clobber for the // client to handle. - if (R == PartialAlias) + if (R == PartialAlias) { + ClobberOffset = BatchAA.getClobberOffset(LoadLoc, MemLoc); return MemDepResult::getClobber(Inst); -#endif + } // Random may-alias loads don't depend on each other without a // dependence. @@ -649,7 +645,7 @@ MemDepResult MemoryDependenceResults::getDependency(Instruction *QueryInst) { Instruction *ScanPos = QueryInst; - + ClobberOffset = None; // Check for a cached result MemDepResult &LocalCache = LocalDeps[QueryInst]; diff --git a/llvm/lib/Transforms/Scalar/GVN.cpp b/llvm/lib/Transforms/Scalar/GVN.cpp --- a/llvm/lib/Transforms/Scalar/GVN.cpp +++ b/llvm/lib/Transforms/Scalar/GVN.cpp @@ -991,8 +991,21 @@ // we have the first instruction in the entry block. // Can't forward from non-atomic to atomic without violating memory model. if (DepLI != LI && Address && LI->isAtomic() <= DepLI->isAtomic()) { - int Offset = - analyzeLoadFromClobberingLoad(LI->getType(), Address, DepLI, DL); + Type *LoadType = LI->getType(); + int Offset = -1; + + // If Memory Dependence Analysis reported clobber check, it was nested + // and can be extracted from DepInst result + if (DepInfo.isClobber() && + canCoerceMustAliasedValueToLoad(DepLI, LoadType, DL)) { + const auto ClobberOff = MD->getClobberOffset(); + // GVN has no deal with a negative offset. + Offset = (ClobberOff == None || ClobberOff.getValue() < 0) + ? -1 + : ClobberOff.getValue(); + } + if (Offset == -1) + Offset = analyzeLoadFromClobberingLoad(LoadType, Address, DepLI, DL); if (Offset != -1) { Res = AvailableValue::getLoad(DepLI, Offset); diff --git a/llvm/test/Transforms/GVN/partial-alias-clobber.ll b/llvm/test/Transforms/GVN/partial-alias-clobber.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/GVN/partial-alias-clobber.ll @@ -0,0 +1,19 @@ +; RUN: opt -gvn -S < %s | FileCheck %s + +; Function Attrs: nofree norecurse nounwind +define float @foo(float* %arg, i32 %i) { +bb: + %i2 = zext i32 %i to i64 + %i3 = getelementptr inbounds float, float* %arg, i64 %i2 + %i4 = bitcast float* %i3 to <2 x float>* + %i5 = load <2 x float>, <2 x float>* %i4, align 16 + %i7 = add nuw nsw i32 %i, 1 + %i8 = zext i32 %i7 to i64 + %i9 = getelementptr inbounds float, float* %arg, i64 %i8 +; CHECK-NOT: load float, float* + %i10 = load float, float* %i9, align 4 + %i16 = extractelement <2 x float> %i5, i32 0 + %i17 = fmul float %i16, %i10 + ret float %i17 +} +