[AA] Cache (optionally) estimated PartialAlias offsets.

[dfukalov]

Summary

For the cases of two clobbering loads and one loaded object is fully contained
in the second BasicAAResult::aliasGEP returns just PartialAlias that
is actually more common case of partial overlap, it doesn't say anything about
actual overlapping sizes.

AA users such as GVN and DSE have no functionality to estimate aliasing of GEPs
with non-constant offsets. The change stores estimated relative offsets so they
can be used further.

[nikic]

llvm/lib/Analysis/AliasAnalysis.cpp

950

Why is it okay to treat the offset symmetrically? I'd expect the offset either be negative if swapped, or be not defined at all, depending on the contract of this function is supposed to be (probably needs a doc comment).

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1494

Why do you use a separate VisitedPhi flag, rather than checking !VisitedPhiBBs.empty(), as we do elsewhere?

This kind of flag breaks BatchAA, because it will leak across queries.

llvm/lib/Analysis/CaptureTracking.cpp

417 ↗

(On Diff #312734)

This looks unrelated, land separately?

[dfukalov]

Rebased, change reworked as requested.

[dfukalov]

llvm/lib/Analysis/AliasAnalysis.cpp

950

My thought was to mark "undefined" offset as -1 and store pointers in pairs in "positive offset" order. It was based on GVN ability to use positive offset only for clobbering.
But you're right, it is more effective to store pointers pairs in cache in the same way as it is implemented for AliasCache.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1494

Thanks, good catch, missed this leak.

[dfukalov]

Ping...

[dfukalov]

Ping...

[dfukalov]

Ping. I'm going to submit the change on Friday if no objections are observed.

[lebedev.ri]

This should probably be split up into BasicAA (+unit test), MemoryDependenceAnalysis(?), and GVN patches.

[fhahn]

IIUC this is similar to the handling of partial overwrites in DSE (https://github.com/llvm/llvm-project/blob/master/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp#L548)?

If so, could we just generalize the helper there, rather than threading this through the different caches from BasicAA to GVN? Yes, we have to do some extra work in GVN, but there would be no need to maintain a cached value not used by other clients, it will work with any AA implementations returning partial alias & there will be no extra work when moving away from MemDepAnalysis.

[dfukalov]

In D93529#2504303, @fhahn wrote:

IIUC this is similar to the handling of partial overwrites in DSE (https://github.com/llvm/llvm-project/blob/master/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp#L548)?

If so, could we just generalize the helper there, rather than threading this through the different caches from BasicAA to GVN? Yes, we have to do some extra work in GVN, but there would be no need to maintain a cached value not used by other clients, it will work with any AA implementations returning partial alias & there will be no extra work when moving away from MemDepAnalysis.

GVN has similar partial aliased memory objects functionality in https://github.com/llvm/llvm-project/blob/master/llvm/lib/Transforms/Utils/VNCoercion.cpp but it has the same issue: they use GetPointerBaseWithConstantOffset() and give up in a case when GEP offset is not constant (please refer the trivial test case in the patch). But BasicAA has an ability to go further and prove partial alias plus estimate overlapping offsets. It seems all these operations (including PHIs processing) should not be re-applied in an AA user.

The issue was masked for different targets because usually vector types are splitted before GVN so it's just see MustAlias parts of vectors and successfully eliminate them.
Actually current DSE fails with the same pattern of stores, I planned to fix it after the patch.

I'm going to split the change by Roman request and update the description to clarify these circumstances.

[dfukalov]

AA part of the splitted patch.

[asbirlea]

Adding this only seems to make sense when using BatchAA.
Could we restrict populating this cache? e.g. extend AAQueryInfo constructor to take bool BatchMode = false, and set it to true for BatchAA. Then update the get/set methods to first check this (check in the setter and assert in the getter).

llvm/include/llvm/Analysis/AliasAnalysis.h

352

Document (add comments) what this cache stores, and its purpose.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1217

referenced

[dfukalov]

Comments addressed.

[dfukalov]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1217

Thanks!

[asbirlea]

Thanks! Diff looks reasonable to me, but I'd like to see the use case changes as well. Could you (re-)upload a concrete use case as dependent patch?
One reason I have in mind is we may want to concretely enable this caching solely for a particular BatchAA instance, i.e. pass true to BatchAA and change the meaning in AAQI from BatchMode to CacheOffsets (and, same as now, only allow BatchAA to set this bool). Then only pass true at the BatchAA callsites where it will be used.

llvm/include/llvm/Analysis/AliasAnalysis.h

350

complicated

364

only

[nikic]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1219

I'm not sure this code is the right place to perform these access size checks. Consider the case where BatchAA is queried for the same pointers with different location sizes in a row. The first query is such that they are PartialAlias and the LocationSize fits into the larger access. The second one is also PartialAlias, but does not fit. In this case, the getClobberOffset() API will still return a result though, and a caller may incorrectly assume that the access is nested based on this check, even though it isn't.

[dfukalov]

Added memory sizes to map key, BatchAA can be created without caching.

[dfukalov]

In D93529#2517400, @asbirlea wrote:

... Could you (re-)upload a concrete use case as dependent patch?

I've just created D95543 with the test for upcoming changes in GVN. It is actually the same code as one used in unit test in this patch.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1219

Thanks for good point! Added sizes to cache key, updated test to check that offset is returned only for exact the same set of two pointers and two sizes.

[dfukalov]

Gentle ping...

[dfukalov]

Ping...

[dfukalov]

Ping...

[dfukalov]

@asbirlea, @nikic, would you please take a look at the updated patch?

[nikic]

I think the proper solution here would be to change AliasResult into a class that carries both the type of the result and an offset for PartialAlias (probably of reduced width), rather than making this information available via a cache side channel.

That would be a larger change though, and I'm okay with doing this in the meantime to make some progress.

llvm/include/llvm/Analysis/AliasAnalysis.h

374

nit: Unnecessary braces.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1197

No need to use pointer for LocationSize, the type is okay to copy.

1199

nit: Off.isNegative()

1212

nit: auto -> uint64_t. Type is not obvious from context.

llvm/unittests/Analysis/AliasAnalysisTest.cpp

323 ↗

(On Diff #319634)

Wrong test :)

[dfukalov]

Rebased, addressed comments.

llvm/include/llvm/Analysis/AliasAnalysis.h

 /// avoid recomputing. To enable preserving this state across multiple queries
 /// where safe (due to the IR not changing), use a `BatchAAResults` wrapper.
 /// The information stored in an `AAQueryInfo` is currently limitted to the
 /// caches used by BasicAA, but can further be extended to fit other AA needs.
 class AAQueryInfo {
 public:
   using LocPair = std::pair<MemoryLocation, MemoryLocation>;
   using AliasCacheT = SmallDenseMap<LocPair, AliasResult, 8>;
   AliasCacheT AliasCache;
 
+  using OffsetPair = std::pair<const Value *, const Value *>;
+  using OffsetsCacheT = SmallDenseMap<OffsetPair, int64_t, 8>;
+  OffsetsCacheT ClobberOffsets;
+
   using IsCapturedCacheT = SmallDenseMap<const Value *, bool, 8>;
   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<int64_t> 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;
 
 class AAResults {
 public:
   // Make these results default constructable and movable. We have to spell
   // these out because MSVC won't synthesize them.
public:
   }
 
   /// Return information about whether a call and an instruction may refer to
   /// the same memory locations.
   ModRefInfo getModRefInfo(Instruction *I, const CallBase *Call);
 
   /// 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
   /// or reads the specified memory location \p MemLoc before instruction \p I
   /// in a BasicBlock.
   /// Early exits in callCapturesBefore may lead to ModRefInfo::Must not being
   /// set.
   ModRefInfo callCapturesBefore(const Instruction *I,
public:
   }
   bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
     return alias(LocA, LocB) == MustAlias;
   }
   bool isMustAlias(const Value *V1, const Value *V2) {
     return alias(MemoryLocation(V1, LocationSize::precise(1)),
                  MemoryLocation(V2, LocationSize::precise(1))) == MustAlias;
   }
+  Optional<int64_t> getClobberOffset(const MemoryLocation &LocA,
+                                     const MemoryLocation &LocB);
 };
 
 /// Temporary typedef for legacy code that uses a generic \c AliasAnalysis
 /// pointer or reference.
 using AliasAnalysis = AAResults;
 
 /// A private abstract base class describing the concept of an individual alias
 /// analysis implementation.
public:
   /// getModRefInfo (for call sites) - Return information about whether
   /// a particular call site modifies or reads the specified memory location.
   virtual ModRefInfo getModRefInfo(const CallBase *Call,
                                    const MemoryLocation &Loc,
                                    AAQueryInfo &AAQI) = 0;
 
   /// 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;
 
   /// @}
 };
 
 /// A private class template which derives from \c Concept and wraps some other
 /// type.

llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h

private:
   AAResults &AA;
   AssumptionCache ∾
   const TargetLibraryInfo &TLI;
   DominatorTree &DT;
   PhiValues &PV;
   PredIteratorCache PredCache;
 
   unsigned DefaultBlockScanLimit;
+  Optional<int64_t> ClobberOffset;
 
 public:
   MemoryDependenceResults(AAResults &AA, AssumptionCache &AC,
                           const TargetLibraryInfo &TLI, DominatorTree &DT,
                           PhiValues &PV, unsigned DefaultBlockScanLimit)
       : AA(AA), AC(AC), TLI(TLI), DT(DT), PV(PV),
         DefaultBlockScanLimit(DefaultBlockScanLimit) {}
 
public:
   /// store the same value and NonLocal which indicate that non-local Def was
   /// found, which can be retrieved by calling getNonLocalPointerDependency
   /// with the same queried instruction.
   MemDepResult getInvariantGroupPointerDependency(LoadInst *LI, BasicBlock *BB);
 
   /// Release memory in caches.
   void releaseMemory();
 
+  Optional<int64_t> getClobberOffset() const { return ClobberOffset; }
+
 private:
   MemDepResult getCallDependencyFrom(CallBase *Call, bool isReadOnlyCall,
                                      BasicBlock::iterator ScanIt,
                                      BasicBlock *BB);
   bool getNonLocalPointerDepFromBB(Instruction *QueryInst,
                                    const PHITransAddr &Pointer,
                                    const MemoryLocation &Loc, bool isLoad,
                                    BasicBlock *BB,

llvm/lib/Analysis/AliasAnalysis.cpp

if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
     AAR.addAAResult(WrapperPass->getResult());
   if (auto *WrapperPass = P.getAnalysisIfAvailable<ExternalAAWrapperPass>())
     if (WrapperPass->CB)
       WrapperPass->CB(P, F, AAR);
 
   return AAR;
 }
 
+Optional<int64_t> 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<CallBase>(V))
     return Call->hasRetAttr(Attribute::NoAlias);
   return false;
 }
 
 bool llvm::isNoAliasArgument(const Value *V) {
   if (const Argument *A = dyn_cast<Argument>(V))
     return A->hasNoAliasAttr();
   return false;
 }
 

llvm/lib/Analysis/BasicAliasAnalysis.cpp

AliasResult BasicAAResult::aliasGEP(
   if (DecompGEP1.Offset == 0 && DecompGEP1.VarIndices.empty())
     return MustAlias;
 
   // If there is a constant difference between the pointers, but the difference
   // is less than the size of the associated memory object, then we know
   // 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 NoAlias;
     }
   }
 
   if (!DecompGEP1.VarIndices.empty()) {
     APInt GCD;
     bool AllNonNegative = DecompGEP1.Offset.isNonNegative();
     bool AllNonPositive = DecompGEP1.Offset.isNonPositive();
     for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) {
if (V1Srcs.empty())
     return MayAlias;
 
   // If this PHI node is recursive, indicate that the pointer may be moved
   // across iterations. We can only prove NoAlias if different underlying
   // objects are involved.
   if (isRecursive)
     PNSize = LocationSize::beforeOrAfterPointer();
 
   // In the recursive alias queries below, we may compare values from two
   // different loop iterations. Keep track of visited phi blocks, which will
   // be used when determining value equivalence.
   bool BlockInserted = VisitedPhiBBs.insert(PN->getParent()).second;
   auto _ = make_scope_exit([&]() {
     if (BlockInserted)
       VisitedPhiBBs.erase(PN->getParent());
   });
 
   // If we inserted a block into VisitedPhiBBs, alias analysis results that
   // 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.
   if (Alias == MayAlias)
     return MayAlias;
   // With recursive phis we cannot guarantee that MustAlias/PartialAlias will
   // remain valid to all elements and needs to conservatively return MayAlias.
   if (isRecursive && Alias != NoAlias)
     return MayAlias;
 
   // If all sources of the PHI node NoAlias or MustAlias V2, then returns
   // NoAlias / MustAlias. Otherwise, returns MayAlias.
   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;
   }
 
   return Alias;
 }
 

llvm/lib/Analysis/MemoryDependenceAnalysis.cpp

if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
       if (isLoad) {
         if (R == NoAlias)
           continue;
 
         // Must aliased loads are defs of each other.
         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.
         continue;
       }
 
       // Stores don't depend on other no-aliased accesses.
       if (R == NoAlias)
MemDepResult MemoryDependenceResults::getSimplePointerDependencyFrom(
   // unknown, otherwise it is non-local.
   if (BB != &BB->getParent()->getEntryBlock())
     return MemDepResult::getNonLocal();
   return MemDepResult::getNonFuncLocal();
 }
 
 MemDepResult MemoryDependenceResults::getDependency(Instruction *QueryInst) {
   Instruction *ScanPos = QueryInst;
-
+  ClobberOffset = None;
   // Check for a cached result
   MemDepResult &LocalCache = LocalDeps[QueryInst];
 
   // If the cached entry is non-dirty, just return it.  Note that this depends
   // on MemDepResult's default constructing to 'dirty'.
   if (!LocalCache.isDirty())
     return LocalCache;
 

llvm/lib/Transforms/Scalar/GVN.cpp

if (DepInfo.isClobber()) {
     //    load i32* P
     //    load i8* (P+1)
     // if we have this, replace the later with an extraction from the former.
     if (LoadInst *DepLI = dyn_cast<LoadInst>(DepInst)) {
       // If this is a clobber and L is the first instruction in its block, then
       // 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);
           return true;
         }
       }
     }
 

llvm/test/Transforms/GVN/partial-alias-clobber.ll

+; 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
+}
+