[AA][NFC] Convert AliasResult to class containing offset for PartialAlias case.

[dfukalov]

Summary

Add an ability to store Offset between partially aliased location. Use this
storage within returned ResultAlias instead of caching it in AAQueryInfo.

[dfukalov]

llvm/include/llvm/Analysis/MemorySSA.h

304

Perhaps AliasResult should be replaced with AliasResult::Result here and in similar places in MemorySSA? @nikic, @asbirlea, what do you think?

[nikic]

llvm/include/llvm/Analysis/AliasAnalysis.h

111

Why does this ctor only initialize HasOffset?

124

I believe this is isInt<OffsetBits>(NewOffset).

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1094

aliasCheck() performs location swapping as well. I think now you need to adjust it to negate the offset if a swapped location is used.

[dfukalov]

Addressed comments.

[dfukalov]

@nikic thanks for review, and what do you think about Optional<AliasResult> - should it be refactored to Optional<AliasResult::Result> in MemorySSA?
Or, possibly, will this module use PartialAlias offsets?

llvm/include/llvm/Analysis/AliasAnalysis.h

111

Yes, it was incorrect, we should no get an uninitialized Alias field.

124

Thanks for hint!

[asbirlea]

@nikic, could you check this patch through the compiler-tracker, please?

llvm/include/llvm/Analysis/MemorySSA.h

304

Yes. Unless we have a usecase of using the PartialAlias in MemorySSA, I don't think we should have the overhead of creating new class instances for all aliasing result kept in optimized memory accesses.

[dfukalov]

llvm/include/llvm/Analysis/MemorySSA.h

304

Actually I thought about pretty ugly compositions like AliasResult(AliasResult::MayAlias). They are caused by Optional<AliasResult>. And speaking of running compiler on x86, IMHO AliasResult class overhead is not significant, at least if it is stored in Optional<>.

[dfukalov]

llvm/include/llvm/Analysis/MemorySSA.h

304

MemorySSA.diff8 KBDownload

I've attached diff with a substitution with using AliasRes = AliasResult::Result. If this option is ok, I'll update the review' patch.

[nikic]

In D98718#2632377, @asbirlea wrote:

@nikic, could you check this patch through the compiler-tracker, please?

I do see some impact from this patch: https://llvm-compile-time-tracker.com/compare.php?from=be92dcb9f679a23329d360bbc5533acc5f808d9c&to=1f10b8ef5f0243ac0a2679d6f334275471bff316&stat=instructions

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1549

Doesn't this swap the cached result? I think the intention here was to only return a swapped result, no?

1573

I think we shouldn't be swapping here, as we computed the result already in swapped order.

[dfukalov]

• Fixed swapping already cached result.
• Result bit field size set to 8 bits, Offset field initialized with zero.

[dfukalov]

In D98718#2635171, @nikic wrote:

I do see some impact from this patch: https://llvm-compile-time-tracker.com/compare.php?from=be92dcb9f679a23329d360bbc5533acc5f808d9c&to=1f10b8ef5f0243ac0a2679d6f334275471bff316&stat=instructions

I see there you experimented with 8 bits for Result and zero init for Offset field - I agree it's a good ideas.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1549

Yes, you're right, I didn't notice it modifies cache. Thanks!

1573

Result we've just put into cache is computed by aliasCheckRecursive(V1, ..., V2) with original order, but Entry was found as AAQI.AliasCache.find(Locs) for sorted pair. So here we should save the Swapped result into cache.

[dfukalov]

In D98718#2635171, @nikic wrote:

I do see some impact from this patch: https://llvm-compile-time-tracker.com/compare.php?from=be92dcb9f679a23329d360bbc5533acc5f808d9c&to=1f10b8ef5f0243ac0a2679d6f334275471bff316&stat=instructions

I ran additional tests: perf impact of the patch and perf impact of the reverting it. Here is the "cumulative" (commit patch and revert it back) difference.

Some of tests didn't get back to original values and generated noise comparable with shown average perf drop of the patch. E.g. CMakeFiles/lencod.dir/image.c.o compilation slowed down by 1.79%, but after reverting it got back by 1.28% only. CMakeFiles/lencod.dir/nalucommon.c.o slowed by 0.20% and after reverting it slowed down again by enormous 1.29%...

Then I ran image.c.o compilation locally under perf and valgrind. Perf said new compiler slowed down, but valgrind reported tiny speedup.
Btw, both of them reported second topmost self-consuming function
DenseMapBase::LookupBucketFor() mostly called from DenseMapBase::try_emplace(std::pair<> const&, AAQueryInfo::CacheEntry&&) and BasicAAResult::aliasCheck().
But again, valgrind said it became faster, perf - slower...

IMHO all of these results say that the reported impact is not significant.
What do you think?

[dfukalov]

Ping...

[dfukalov]

@nikic, @asbirlea would you please review the patch?
It blocks GVN related D95543.

[asbirlea]

I'm running some additional tests for this patch.
Could you rebase the GVN dependent patch so I get some testing done in parallel?

[dfukalov]

I was not sure this patch will be landed so left GVN patch based on previous already landed (cached) offset storage.

In D98718#2672069, @asbirlea wrote:

Could you rebase the GVN dependent patch so I get some testing done in parallel?

Yes, sure, do you need rebase it on this change or even on updated main branch + this change?

[asbirlea]

This is good to go from my side.

[nikic]

Possibly MergeAliasResults should preserve the offset when merging two PartialAlias with the same offset?

llvm/include/llvm/Analysis/AliasAnalysis.h

93

I'd rename this to something like Type or Kind.

140

I think the AliasResult printing code should be adjusted to also print the PartialAlias offset. This will allow us to test this functionality using normal -aa-eval tests, instead of unit tests. That should be a great deal simpler when testing more complex cases.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1114

Now that the offset is part of the result, I *think* the VisitedPhiBBs check is not needed anymore, but I'm not entirely sure.

[dfukalov]

@nikic, I didn't notice your comments before push, will address your comments in different patch.

[dfukalov]

llvm/include/llvm/Analysis/AliasAnalysis.h

140

There is an issue with printing offset in -aa-eval: it prints two (aliased) values sorted lexicographically.
So the printed offset may have wrong sign regarding printed pair of values. I'm not sure how it should be printed to avoid confusion in tests... Do you have any ideas?

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1114

Actually I added this check because of comment you asked about in D95543.

[nikic]

llvm/include/llvm/Analysis/AliasAnalysis.h

140

Would just calling swap() on the AliasResult if the values are swapped not work?

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1114

I think these are different issues. The comment refers to phi translation performed by MDA and GVN. BasicAA itself does not perform phi translation.

Here, VisitedPhiBBs should already implicit take effect, in that returning PartialAlias here requires that the GEP base pointers are MustAlias. They will only be MustAlias if they pass the phi cycle reachability check. So the VisitedPhiBBs are important for the recursive check on the base pointers, but there shouldn't be a need to check it here.

llvm/include/llvm/Analysis/AliasAnalysis.h

 /// Note that these are unscoped enumerations because we would like to support
 /// implicitly testing a result for the existence of any possible aliasing with
 /// a conversion to bool, but an "enum class" doesn't support this. The
 /// canonical names from the literature are suffixed and unique anyways, and so
 /// they serve as global constants in LLVM for these results.
 ///
 /// See docs/AliasAnalysis.html for more information on the specific meanings
 /// of these values.
-enum AliasResult : uint8_t {
+class AliasResult {
+private:
+  static const int OffsetBits = 23;
+  static const int AliasBits = 8;
+  static_assert(AliasBits + 1 + OffsetBits <= 32,
+                "AliasResult size is intended to be 4 bytes!");
+
+  unsigned int Alias : AliasBits;
+  unsigned int HasOffset : 1;
+  signed int Offset : OffsetBits;
+
+public:
+  enum Result : uint8_t {
     /// The two locations do not alias at all.
     ///
     /// This value is arranged to convert to false, while all other values
     /// convert to true. This allows a boolean context to convert the result to
     /// a binary flag indicating whether there is the possibility of aliasing.
     NoAlias = 0,
-  /// The two locations may or may not alias. This is the least precise result.
+    /// The two locations may or may not alias. This is the least precise
+    /// result.
     MayAlias,
     /// The two locations alias, but only due to a partial overlap.
     PartialAlias,
     /// The two locations precisely alias each other.
     MustAlias,
   };
+  static_assert(MustAlias < (1 << AliasBits),
+                "Not enough bit field size for the enum!");
+
+  explicit AliasResult() = delete;
+  constexpr AliasResult(const Result &Alias)
+      : Alias(Alias), HasOffset(false), Offset(0) {}
+
+  operator Result() const { return static_cast<Result>(Alias); }
+
+  constexpr bool hasOffset() const { return HasOffset; }
+  constexpr int32_t getOffset() const {
+    assert(HasOffset && "No offset!");
+    return Offset;
+  }
+  void setOffset(int32_t NewOffset) {
+    if (isInt<OffsetBits>(NewOffset)) {
+      HasOffset = true;
+      Offset = NewOffset;
+    }
+  }
+
+  /// Helper for processing AliasResult for swapped memory location pairs.
+  void swap(bool DoSwap) {
+    if (DoSwap && hasOffset())
+      setOffset(-getOffset());
+  }
+};
+
+static_assert(sizeof(AliasResult) == 4,
+              "AliasResult size is intended to be 4 bytes!");
 
 /// << operator for AliasResult.
 raw_ostream &operator<<(raw_ostream &OS, AliasResult AR);
 
 /// Flags indicating whether a memory access modifies or references memory.
 ///
 /// 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 three bit matrix and bit-tests for 'mod' or 'ref' or 'must'
 /// work with any of the possible values.
 enum class ModRefInfo : uint8_t {

 /// query. By default, the root query is stateless and starts with a freshly
 /// constructed info object. Specific alias analyses can use this query info to
 /// store per-query state that is important for recursive or nested queries to
 /// 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 {
-  /// Storage for estimated relative offsets between two partially aliased
-  /// values. Used to optimize out redundant parts of loads/stores (in GVN/DSE).
-  /// These users cannot process quite complicated addresses (e.g. GEPs with
-  /// non-constant offsets). Used by BatchAAResults only.
-  bool CacheOffsets = false;
-  SmallDenseMap<std::pair<std::pair<const Value *, const Value *>,
-                          std::pair<uint64_t, uint64_t>>,
-                int64_t, 4>
-      ClobberOffsets;
-
 public:
   using LocPair = std::pair<AACacheLoc, AACacheLoc>;
   struct CacheEntry {
     AliasResult Result;
     /// Number of times a NoAlias assumption has been used.
     /// 0 for assumptions that have not been used, -1 for definitive results.
     int NumAssumptionUses;
     /// Whether this is a definitive (non-assumption) result.
public:
   /// How many active NoAlias assumption uses there are.
   int NumAssumptionUses = 0;
 
   /// Location pairs for which an assumption based result is currently stored.
   /// Used to remove all potentially incorrect results from the cache if an
   /// assumption is disproven.
   SmallVector<AAQueryInfo::LocPair, 4> AssumptionBasedResults;
 
-  AAQueryInfo(bool CacheOffsets = false)
-      : CacheOffsets(CacheOffsets), ClobberOffsets(), AliasCache(),
-        IsCapturedCache() {}
+  AAQueryInfo() : AliasCache(), IsCapturedCache() {}
 
   /// Create a new AAQueryInfo based on this one, but with the cache cleared.
   /// This is used for recursive queries across phis, where cache results may
   /// not be valid.
   AAQueryInfo withEmptyCache() {
     AAQueryInfo NewAAQI;
     NewAAQI.Depth = Depth;
     return NewAAQI;
   }
-
-  Optional<int64_t> getClobberOffset(const Value *Ptr1, const Value *Ptr2,
-                                     uint64_t Size1, uint64_t Size2) const {
-    assert(CacheOffsets && "Clobber offset cached in batch mode only!");
-    const bool Swapped = Ptr1 > Ptr2;
-    if (Swapped) {
-      std::swap(Ptr1, Ptr2);
-      std::swap(Size1, Size2);
-    }
-    const auto IOff = ClobberOffsets.find({{Ptr1, Ptr2}, {Size1, Size2}});
-    if (IOff != ClobberOffsets.end())
-      return Swapped ? -IOff->second : IOff->second;
-    return None;
-  }
-
-  void setClobberOffset(const Value *Ptr1, const Value *Ptr2, uint64_t Size1,
-                        uint64_t Size2, int64_t Offset) {
-    // Cache offset for batch mode only.
-    if (!CacheOffsets)
-      return;
-    if (Ptr1 > Ptr2) {
-      std::swap(Ptr1, Ptr2);
-      std::swap(Size1, Size2);
-      Offset = -Offset;
-    }
-    ClobberOffsets[{{Ptr1, Ptr2}, {Size1, Size2}}] = 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.

 /// esentially making AA work in "batch mode". The internal state cannot be
 /// cleared, so to go "out-of-batch-mode", the user must either use AAResults,
 /// or create a new BatchAAResults.
 class BatchAAResults {
   AAResults &AA;
   AAQueryInfo AAQI;
 
 public:
-  BatchAAResults(AAResults &AAR, bool CacheOffsets = false)
-      : AA(AAR), AAQI(CacheOffsets) {}
+  BatchAAResults(AAResults &AAR) : AA(AAR), AAQI() {}
   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
     return AA.alias(LocA, LocB, AAQI);
   }
   bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false) {
     return AA.pointsToConstantMemory(Loc, AAQI, OrLocal);
   }
   ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc) {
     return AA.getModRefInfo(Call, Loc, AAQI);
public:
   bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
     return alias(LocA, LocB) == AliasResult::MustAlias;
   }
   bool isMustAlias(const Value *V1, const Value *V2) {
     return alias(MemoryLocation(V1, LocationSize::precise(1)),
                  MemoryLocation(V2, LocationSize::precise(1))) ==
            AliasResult::MustAlias;
   }
-  Optional<int64_t> getClobberOffset(const MemoryLocation &LocA,
-                                     const MemoryLocation &LocB) const;
 };
 
 /// 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.

llvm/include/llvm/Analysis/AliasSetTracker.h

 #include <cstddef>
 #include <cstdint>
 #include <iterator>
 #include <vector>
 
 namespace llvm {
 
 class AAResults;
+class AliasResult;
 class AliasSetTracker;
-class BasicBlock;
-class LoadInst;
 class AnyMemSetInst;
 class AnyMemTransferInst;
+class BasicBlock;
+class LoadInst;
 class raw_ostream;
 class StoreInst;
 class VAArgInst;
 class Value;
 
-enum AliasResult : uint8_t;
-
 class AliasSet : public ilist_node<AliasSet> {
   friend class AliasSetTracker;
 
   class PointerRec {
     Value *Val;  // The pointer this record corresponds to.
     PointerRec **PrevInList = nullptr;
     PointerRec *NextInList = nullptr;
     AliasSet *AS = nullptr;

llvm/include/llvm/Analysis/MemorySSA.h

protected:
 
   // Use deleteValue() to delete a generic MemoryUseOrDef.
   ~MemoryUseOrDef() = default;
 
   void setOptimizedAccessType(Optional<AliasResult> AR) {
     OptimizedAccessAlias = AR;
   }
 
-  void setDefiningAccess(MemoryAccess *DMA, bool Optimized = false,
-                         Optional<AliasResult> AR = AliasResult::MayAlias) {
+  void setDefiningAccess(
+      MemoryAccess *DMA, bool Optimized = false,
+      Optional<AliasResult> AR = AliasResult(AliasResult::MayAlias)) {
     if (!Optimized) {
       setOperand(0, DMA);
       return;
     }
     setOptimized(DMA);
     setOptimizedAccessType(AR);
   }
 

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 {
-  if (!LocA.Size.hasValue() || !LocB.Size.hasValue())
-    return None;
-  const Value *V1 = LocA.Ptr->stripPointerCastsForAliasAnalysis();
-  const Value *V2 = LocB.Ptr->stripPointerCastsForAliasAnalysis();
-  return AAQI.getClobberOffset(V1, V2, LocA.Size.getValue(),
-                               LocB.Size.getValue());
-}
-
 bool llvm::isNoAliasCall(const Value *V) {
   if (const auto *Call = dyn_cast<CallBase>(V))
     return Call->hasRetAttr(Attribute::NoAlias);
   return false;
 }
 
 static bool isNoAliasOrByValArgument(const Value *V) {
   if (const Argument *A = dyn_cast<Argument>(V))

llvm/lib/Analysis/BasicAliasAnalysis.cpp

 AliasResult BasicAAResult::aliasGEP(
     const GEPOperator *GEP1, LocationSize V1Size,
     const Value *V2, LocationSize V2Size,
     const Value *UnderlyingV1, const Value *UnderlyingV2, AAQueryInfo &AAQI) {
   if (!V1Size.hasValue() && !V2Size.hasValue()) {
     // TODO: This limitation exists for compile-time reasons. Relax it if we
     // can avoid exponential pathological cases.
     if (!isa<GEPOperator>(V2))
-      return MayAlias;
+      return AliasResult::MayAlias;
 
     // If both accesses have unknown size, we can only check whether the base
     // objects don't alias.
     AliasResult BaseAlias = getBestAAResults().alias(
         MemoryLocation::getBeforeOrAfter(UnderlyingV1),
         MemoryLocation::getBeforeOrAfter(UnderlyingV2), AAQI);
-    return BaseAlias == NoAlias ? NoAlias : MayAlias;
+    return BaseAlias == AliasResult::NoAlias ? AliasResult::NoAlias
+                                             : AliasResult::MayAlias;
   }
 
   DecomposedGEP DecompGEP1 = DecomposeGEPExpression(GEP1, DL, &AC, DT);
   DecomposedGEP DecompGEP2 = DecomposeGEPExpression(V2, DL, &AC, DT);
 
   // Don't attempt to analyze the decomposed GEP if index scale is not a
   // compile-time constant.
   if (!DecompGEP1.HasCompileTimeConstantScale ||
AliasResult BasicAAResult::aliasGEP(
   if (DecompGEP1.Offset != 0 && DecompGEP1.VarIndices.empty()) {
     APInt &Off = DecompGEP1.Offset;
 
     // Initialize for Off >= 0 (V2 <= GEP1) case.
     const Value *LeftPtr = V2;
     const Value *RightPtr = GEP1;
     LocationSize VLeftSize = V2Size;
     LocationSize VRightSize = V1Size;
+    const bool Swapped = Off.isNegative();
 
-    if (Off.isNegative()) {
+    if (Swapped) {
       // Swap if we have the situation where:
       // +                +
       // | BaseOffset     |
       // ---------------->|
       // |-->V1Size       |-------> V2Size
       // GEP1             V2
       std::swap(LeftPtr, RightPtr);
       std::swap(VLeftSize, VRightSize);
       Off = -Off;
     }
 
     if (VLeftSize.hasValue()) {
       const uint64_t LSize = VLeftSize.getValue();
       if (Off.ult(LSize)) {
         // Conservatively drop processing if a phi was visited and/or offset is
         // too big.
+        AliasResult AR = AliasResult::PartialAlias;
         if (VisitedPhiBBs.empty() && VRightSize.hasValue() &&
-            Off.ule(INT64_MAX)) {
+            Off.ule(INT32_MAX) && (Off + VRightSize.getValue()).ule(LSize)) {
           // Memory referenced by right pointer is nested. Save the offset in
-          // cache.
-          const uint64_t RSize = VRightSize.getValue();
-          if ((Off + RSize).ule(LSize))
-            AAQI.setClobberOffset(LeftPtr, RightPtr, LSize, RSize,
-                                  Off.getSExtValue());
+          // cache. Note that originally offset estimated as GEP1-V2, but
+          // AliasResult contains the shift that represents GEP1+Offset=V2.
+          AR.setOffset(-Off.getSExtValue());
+          AR.swap(Swapped);
         }
-        return AliasResult::PartialAlias;
+        return AR;
       }
       return AliasResult::NoAlias;
     }
   }
 
   if (!DecompGEP1.VarIndices.empty()) {
     APInt GCD;
     bool AllNonNegative = DecompGEP1.Offset.isNonNegative();
AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size,
   // enough to be very rarely hit, while still being small enough to avoid
   // stack overflows.
   if (AAQI.Depth >= 512)
     return AliasResult::MayAlias;
 
   // Check the cache before climbing up use-def chains. This also terminates
   // otherwise infinitely recursive queries.
   AAQueryInfo::LocPair Locs({V1, V1Size}, {V2, V2Size});
-  if (V1 > V2)
+  const bool Swapped = V1 > V2;
+  if (Swapped)
     std::swap(Locs.first, Locs.second);
   const auto &Pair = AAQI.AliasCache.try_emplace(
       Locs, AAQueryInfo::CacheEntry{AliasResult::NoAlias, 0});
   if (!Pair.second) {
     auto &Entry = Pair.first->second;
     if (!Entry.isDefinitive()) {
       // Remember that we used an assumption.
       ++Entry.NumAssumptionUses;
       ++AAQI.NumAssumptionUses;
     }
-    return Entry.Result;
+    // Cache contains sorted {V1,V2} pairs but we should return original order.
+    auto Result = Entry.Result;
+    Result.swap(Swapped);
+    return Result;
   }
 
   int OrigNumAssumptionUses = AAQI.NumAssumptionUses;
   unsigned OrigNumAssumptionBasedResults = AAQI.AssumptionBasedResults.size();
   AliasResult Result =
       aliasCheckRecursive(V1, V1Size, V2, V2Size, AAQI, O1, O2);
 
   auto It = AAQI.AliasCache.find(Locs);
   assert(It != AAQI.AliasCache.end() && "Must be in cache");
   auto &Entry = It->second;
 
   // Check whether a NoAlias assumption has been used, but disproven.
   bool AssumptionDisproven =
       Entry.NumAssumptionUses > 0 && Result != AliasResult::NoAlias;
   if (AssumptionDisproven)
     Result = AliasResult::MayAlias;
 
   // This is a definitive result now, when considered as a root query.
   AAQI.NumAssumptionUses -= Entry.NumAssumptionUses;
   Entry.Result = Result;
+  // Cache contains sorted {V1,V2} pairs.
+  Entry.Result.swap(Swapped);
   Entry.NumAssumptionUses = -1;
 
   // If the assumption has been disproven, remove any results that may have
   // been based on this assumption. Do this after the Entry updates above to
   // avoid iterator invalidation.
   if (AssumptionDisproven)
     while (AAQI.AssumptionBasedResults.size() > OrigNumAssumptionBasedResults)
       AAQI.AliasCache.erase(AAQI.AssumptionBasedResults.pop_back_val());

llvm/lib/Analysis/MemorySSA.cpp

if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(DefInst)) {
     // (including creating MemoryAccesses for them): we just end up inventing
     // clobbers where they don't really exist at all. Please see D43269 for
     // context.
     switch (II->getIntrinsicID()) {
     case Intrinsic::invariant_start:
     case Intrinsic::invariant_end:
     case Intrinsic::assume:
     case Intrinsic::experimental_noalias_scope_decl:
-      return {false, AliasResult::NoAlias};
+      return {false, AliasResult(AliasResult::NoAlias)};
     case Intrinsic::dbg_addr:
     case Intrinsic::dbg_declare:
     case Intrinsic::dbg_label:
     case Intrinsic::dbg_value:
       llvm_unreachable("debuginfo shouldn't have associated defs!");
     default:
       break;
     }
   }
 
   if (auto *CB = dyn_cast_or_null<CallBase>(UseInst)) {
     ModRefInfo I = AA.getModRefInfo(DefInst, CB);
     AR = isMustSet(I) ? AliasResult::MustAlias : AliasResult::MayAlias;
     return {isModOrRefSet(I), AR};
   }
 
   if (auto *DefLoad = dyn_cast<LoadInst>(DefInst))
     if (auto *UseLoad = dyn_cast_or_null<LoadInst>(UseInst))
-      return {!areLoadsReorderable(UseLoad, DefLoad), AliasResult::MayAlias};
+      return {!areLoadsReorderable(UseLoad, DefLoad),
+              AliasResult(AliasResult::MayAlias)};
 
   ModRefInfo I = AA.getModRefInfo(DefInst, UseLoc);
   AR = isMustSet(I) ? AliasResult::MustAlias : AliasResult::MayAlias;
   return {isModSet(I), AR};
 }
 
 template <typename AliasAnalysisType>
 static ClobberAlias instructionClobbersQuery(MemoryDef *MD,
struct UpwardsMemoryQuery {
   bool IsCall = false;
   // The pointer location we started the query with. This will be empty if
   // IsCall is true.
   MemoryLocation StartingLoc;
   // This is the instruction we were querying about.
   const Instruction *Inst = nullptr;
   // The MemoryAccess we actually got called with, used to test local domination
   const MemoryAccess *OriginalAccess = nullptr;
-  Optional<AliasResult> AR = AliasResult::MayAlias;
+  Optional<AliasResult> AR = AliasResult(AliasResult::MayAlias);
   bool SkipSelfAccess = false;
 
   UpwardsMemoryQuery() = default;
 
   UpwardsMemoryQuery(const Instruction *Inst, const MemoryAccess *Access)
       : IsCall(isa<CallBase>(Inst)), Inst(Inst), OriginalAccess(Access) {
     if (!IsCall)
       StartingLoc = MemoryLocation::get(Inst);
walkToPhiOrClobber(DefPath &Desc, const MemoryAccess *StopAt = nullptr,
     if (!*UpwardWalkLimit) {
       *UpwardWalkLimit = 1;
       LimitAlreadyReached = true;
     }
 
     for (MemoryAccess *Current : def_chain(Desc.Last)) {
       Desc.Last = Current;
       if (Current == StopAt || Current == SkipStopAt)
-        return {Current, false, AliasResult::MayAlias};
+        return {Current, false, AliasResult(AliasResult::MayAlias)};
 
       if (auto *MD = dyn_cast<MemoryDef>(Current)) {
         if (MSSA.isLiveOnEntryDef(MD))
-          return {MD, true, AliasResult::MustAlias};
+          return {MD, true, AliasResult(AliasResult::MustAlias)};
 
         if (!--*UpwardWalkLimit)
-          return {Current, true, AliasResult::MayAlias};
+          return {Current, true, AliasResult(AliasResult::MayAlias)};
 
         ClobberAlias CA =
             instructionClobbersQuery(MD, Desc.Loc, Query->Inst, AA);
         if (CA.IsClobber)
           return {MD, true, CA.AR};
       }
     }
 
     if (LimitAlreadyReached)
       *UpwardWalkLimit = 0;
 
     assert(isa<MemoryPhi>(Desc.Last) &&
            "Ended at a non-clobber that's not a phi?");
-    return {Desc.Last, false, AliasResult::MayAlias};
+    return {Desc.Last, false, AliasResult(AliasResult::MayAlias)};
   }
 
   void addSearches(MemoryPhi *Phi, SmallVectorImpl<ListIndex> &PausedSearches,
                    ListIndex PriorNode) {
     auto UpwardDefsBegin = upward_defs_begin({Phi, Paths[PriorNode].Loc}, DT,
                                              &PerformedPhiTranslation);
     auto UpwardDefs = make_range(UpwardDefsBegin, upward_defs_end());
     for (const MemoryAccessPair &P : UpwardDefs) {
if (MSSA->isLiveOnEntryDef(DefiningAccess)) {
       StartingAccess->setOptimizedAccessType(None);
       return DefiningAccess;
     }
 
     OptimizedAccess = Walker.findClobber(DefiningAccess, Q, UpwardWalkLimit);
     StartingAccess->setOptimized(OptimizedAccess);
     if (MSSA->isLiveOnEntryDef(OptimizedAccess))
       StartingAccess->setOptimizedAccessType(None);
-    else if (Q.AR == AliasResult::MustAlias)
-      StartingAccess->setOptimizedAccessType(AliasResult::MustAlias);
+    else if (Q.AR && *Q.AR == AliasResult::MustAlias)
+      StartingAccess->setOptimizedAccessType(
+          AliasResult(AliasResult::MustAlias));
   } else
     OptimizedAccess = StartingAccess->getOptimized();
 
   LLVM_DEBUG(dbgs() << "Starting Memory SSA clobber for " << *I << " is ");
   LLVM_DEBUG(dbgs() << *StartingAccess << "\n");
   LLVM_DEBUG(dbgs() << "Optimized Memory SSA clobber for " << *I << " is ");
   LLVM_DEBUG(dbgs() << *OptimizedAccess << "\n");
 

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

isOverwrite(const Instruction *LaterI, const Instruction *EarlierI,
   // the later store was larger than the earlier store.
   if (AAR == AliasResult::MustAlias) {
     // Make sure that the Later size is >= the Earlier size.
     if (LaterSize >= EarlierSize)
       return OW_Complete;
   }
 
   // If we hit a partial alias we may have a full overwrite
-  if (AAR == AliasResult::PartialAlias) {
-    int64_t Off = AA.getClobberOffset(Later, Earlier).getValueOr(0);
-    if (Off > 0 && (uint64_t)Off + EarlierSize <= LaterSize)
+  if (AAR == AliasResult::PartialAlias && AAR.hasOffset()) {
+    int32_t Off = AAR.getOffset();
+    if (Off >= 0 && (uint64_t)Off + EarlierSize <= LaterSize)
       return OW_Complete;
   }
 
   // Check to see if the later store is to the entire object (either a global,
   // an alloca, or a byval/inalloca argument).  If so, then it clearly
   // overwrites any other store to the same object.
   const Value *P1 = Earlier.Ptr->stripPointerCasts();
   const Value *P2 = Later.Ptr->stripPointerCasts();
struct DSEState {
   DenseMap<BasicBlock *, unsigned> PostOrderNumbers;
 
   /// Keep track of instructions (partly) overlapping with killing MemoryDefs per
   /// basic block.
   DenseMap<BasicBlock *, InstOverlapIntervalsTy> IOLs;
 
   DSEState(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT,
            PostDominatorTree &PDT, const TargetLibraryInfo &TLI)
-      : F(F), AA(AA), BatchAA(AA, /*CacheOffsets =*/true), MSSA(MSSA), DT(DT),
-        PDT(PDT), TLI(TLI), DL(F.getParent()->getDataLayout()) {}
+      : F(F), AA(AA), BatchAA(AA), MSSA(MSSA), DT(DT), PDT(PDT), TLI(TLI),
+        DL(F.getParent()->getDataLayout()) {}
 
   static DSEState get(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
                       DominatorTree &DT, PostDominatorTree &PDT,
                       const TargetLibraryInfo &TLI) {
     DSEState State(F, AA, MSSA, DT, PDT, TLI);
     // Collect blocks with throwing instructions not modeled in MemorySSA and
     // alloc-like objects.
     unsigned PO = 0;

llvm/unittests/Analysis/AliasAnalysisTest.cpp

TEST_F(AliasAnalysisTest, PartialAliasOffset) {
   LLVMContext C;
   SMDiagnostic Err;
   std::unique_ptr<Module> M = parseAssemblyString(R"(
     define void @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>*
-      %L2 = load <2 x float>, <2 x float>* %i4, align 16
+      %L1 = 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
-      %L1 = load float, float* %i9, align 4
+      %L2 = load float, float* %i9, align 4
       ret void
     }
   )",
                                                   Err, C);
 
   if (!M)
     Err.print("PartialAliasOffset", errs());
 
   Function *F = M->getFunction("foo");
   const auto Loc1 = MemoryLocation::get(getInstructionByName(*F, "L1"));
-  auto Loc2 = MemoryLocation::get(getInstructionByName(*F, "L2"));
+  const auto Loc2 = MemoryLocation::get(getInstructionByName(*F, "L2"));
 
   auto &AA = getAAResults(*F);
 
-  BatchAAResults BatchAA(AA, /*CacheOffsets =*/true);
-  EXPECT_EQ(AliasResult::PartialAlias, BatchAA.alias(Loc1, Loc2));
-  EXPECT_EQ(-4, BatchAA.getClobberOffset(Loc1, Loc2).getValueOr(0));
-  EXPECT_EQ(4, BatchAA.getClobberOffset(Loc2, Loc1).getValueOr(0));
-
-  // Check that no offset returned for different size.
-  Loc2.Size = LocationSize::precise(42);
-  EXPECT_EQ(0, BatchAA.getClobberOffset(Loc1, Loc2).getValueOr(0));
+  const auto AR = AA.alias(Loc1, Loc2);
+  EXPECT_EQ(AR, AliasResult::PartialAlias);
+  EXPECT_EQ(4, AR.getOffset());
 }
 
 class AAPassInfraTest : public testing::Test {
 protected:
   LLVMContext C;
   SMDiagnostic Err;
   std::unique_ptr<Module> M;
 

llvm/unittests/Analysis/MemorySSATest.cpp

for (LoadInst *V : {LA1, LA2}) {
     EXPECT_EQ(MemUse->getOptimizedAccessType(), None)
         << "Load " << I << " doesn't have the correct alias information";
     // EXPECT_EQ expands such that if we increment I above, it won't get
     // incremented except when we try to print the error message.
     ++I;
   }
   for (LoadInst *V : {LA3, LA4}) {
     MemoryUse *MemUse = dyn_cast_or_null<MemoryUse>(MSSA.getMemoryAccess(V));
-    EXPECT_EQ(MemUse->getOptimizedAccessType(), AliasResult::MustAlias)
+    EXPECT_EQ(MemUse->getOptimizedAccessType().getValue(),
+              AliasResult::MustAlias)
         << "Load " << I << " doesn't have the correct alias information";
     // EXPECT_EQ expands such that if we increment I above, it won't get
     // incremented except when we try to print the error message.
     ++I;
   }
 }
 
 // Test Must alias for optimized defs.
else {
                            << " has Defining Access equal to Clobbering Access";
     }
     EXPECT_EQ(MemDef->isOptimized(), true)
         << "Store " << I << " was not optimized";
     if (I == 0 || I == 1)
       EXPECT_EQ(MemDef->getOptimizedAccessType(), None)
           << "Store " << I << " doesn't have the correct alias information";
     else
-      EXPECT_EQ(MemDef->getOptimizedAccessType(), AliasResult::MustAlias)
+      EXPECT_EQ(MemDef->getOptimizedAccessType().getValue(),
+                AliasResult::MustAlias)
           << "Store " << I << " doesn't have the correct alias information";
     // EXPECT_EQ expands such that if we increment I above, it won't get
     // incremented except when we try to print the error message.
     ++I;
   }
 }
 
 // Test May alias for optimized uses.
TEST_F(MemorySSATest, TestLoadMayAlias) {
   LoadInst *LB2 = B.CreateLoad(Int8, PointerB, "");
 
   setupAnalyses();
   MemorySSA &MSSA = *Analyses->MSSA;
 
   unsigned I = 0;
   for (LoadInst *V : {LA1, LB1}) {
     MemoryUse *MemUse = dyn_cast_or_null<MemoryUse>(MSSA.getMemoryAccess(V));
-    EXPECT_EQ(MemUse->getOptimizedAccessType(), AliasResult::MayAlias)
+    EXPECT_EQ(MemUse->getOptimizedAccessType().getValue(),
+              AliasResult::MayAlias)
         << "Load " << I << " doesn't have the correct alias information";
     // EXPECT_EQ expands such that if we increment I above, it won't get
     // incremented except when we try to print the error message.
     ++I;
   }
   for (LoadInst *V : {LA2, LB2}) {
     MemoryUse *MemUse = dyn_cast_or_null<MemoryUse>(MSSA.getMemoryAccess(V));
-    EXPECT_EQ(MemUse->getOptimizedAccessType(), AliasResult::MustAlias)
+    EXPECT_EQ(MemUse->getOptimizedAccessType().getValue(),
+              AliasResult::MustAlias)
         << "Load " << I << " doesn't have the correct alias information";
     // EXPECT_EQ expands such that if we increment I above, it won't get
     // incremented except when we try to print the error message.
     ++I;
   }
 }
 
 // Test May alias for optimized defs.
for (StoreInst *V : Sts)
     Walker->getClobberingMemoryAccess(V);
 
   I = 0;
   for (StoreInst *V : Sts) {
     MemoryDef *MemDef = dyn_cast_or_null<MemoryDef>(MSSA.getMemoryAccess(V));
     EXPECT_EQ(MemDef->isOptimized(), true)
         << "Store " << I << " was not optimized";
     if (I == 1 || I == 3 || I == 4)
-      EXPECT_EQ(MemDef->getOptimizedAccessType(), AliasResult::MayAlias)
+      EXPECT_EQ(MemDef->getOptimizedAccessType().getValue(),
+                AliasResult::MayAlias)
           << "Store " << I << " doesn't have the correct alias information";
     else if (I == 0 || I == 2)
       EXPECT_EQ(MemDef->getOptimizedAccessType(), None)
           << "Store " << I << " doesn't have the correct alias information";
     else
-      EXPECT_EQ(MemDef->getOptimizedAccessType(), AliasResult::MustAlias)
+      EXPECT_EQ(MemDef->getOptimizedAccessType().getValue(),
+                AliasResult::MustAlias)
           << "Store " << I << " doesn't have the correct alias information";
     // EXPECT_EQ expands such that if we increment I above, it won't get
     // incremented except when we try to print the error message.
     ++I;
   }
 }
 
 TEST_F(MemorySSATest, LifetimeMarkersAreClobbers) {
if (BB.getName() == "exit") {
           upward_defs_begin({ItA->first, ItA->second}, MSSA.getDomTree());
       // Check if the location information have been retained
       EXPECT_TRUE(ItB->second.Size.isPrecise());
       EXPECT_TRUE(ItB->second.Size.hasValue());
       EXPECT_TRUE(ItB->second.Size.getValue() == 8);
     }
   }
 }
 No newline at end of file