Track whether the size of a MemoryLocation is precise

[george.burgess.iv]

Summary

In the vast majority of cases, we hand AA precise sizes for MemoryLocations, rather than upper-bounds. BasicAA has a few checks that assume the sizes passed in are precise, which breaks down when we start passing in upper-bounds that might include conditionally-executed UB (which is what AliasSetTracker is doing right now, and which caused PR36228). The most straightforward way to fix this without penalizing AA seems to be passing an extra "I guarantee you this size is precise" bit along.

Passing this bit in a minimally invasive way appears difficult in pathological cases (read: massive sizes), and we're already sort of treating this Size as an Optional<uint64_t>, so I figured I'd wrap this up in its own type to make the properties of MemoryLocation sizes more obvious/hopefully easier to deal with.

As a natural part of this refactoring, PR36228 gets fixed.

If this lands, I will do the following cleanups (...which there's a lot of, but the majority are trivial):

• Replace all uses of MemoryLocation::UnknownSize with LocationSize::unknown() + remove MemoryLocation::UnknownSize
• Replace the various resulting Loc == LocationSize::unknown()s with the shorter, equivalent !Loc.hasValue()
• Migrate users of the implicit LocationSize(uint64_t) ctor to LocationSize::precise or LocationSize::upperBound
• Remove the LocationSize(uint64_t) ctor, which will force callers of AA APIs to reason about/be explicit about the precision of the LocationSize they're passing.

The last two bullets are the bits that I hope will prevent future bugs like this (and catch other existing ones, if any). :)

Any thoughts/comments welcome, as always.

[nlopes]

I like the direction in general. I've reviewed this patch and it LGTM (as well as the overall plan).
There are still a few corner cases we need to fix regarding the meaning of size -1, but I guess it's an orthogonal fix. Right now I don't know exactly what -1 size is: does it mean potentially access the whole object, or access the object from the current offset and potentially until the end?

include/llvm/Analysis/AliasSetTracker.h

78–81

This is changing the semantics slightly. Before it would update Size if Newsize=-1. Is this intended?

82

Access size can be zero. Is it safe to do the above? You could use the map tombstone instead perhaps?

[george.burgess.iv]

Addressed comments + tweaked mapTombstone and mapEntry so they call the hacky "direct" constructor.

[george.burgess.iv]

Thanks for the comments!

include/llvm/Analysis/AliasSetTracker.h

78–81

I don't see how it's a functionality change. If !Size.hasValue(), that's the equivalent to Size == UINT64_MAX in the old code, which would result in updates never happening. If NewSize != Size, we'll conditionally update to the greater size (with the upper-bound bit definitely set). Am I missing something?

In any case, I removed the hasValue() check here, since we should handle !hasValue() correctly in Size.combineWith(NewSize).

82

Good catch. I used the empty key since that's what we appear to use for AAInfo

[nlopes]

LGTM, but I would wait for another review due to the size of the change.

lib/Analysis/BasicAliasAnalysis.cpp

1732–1734

isPrecise() should be enough since UnknownSize() isn't precise. This pattern appears a couple more times.

[george.burgess.iv]

Addressed feedback

[george.burgess.iv]

I would wait for another review

Will do. Thanks again!

lib/Analysis/BasicAliasAnalysis.cpp

1732–1734

Good catch.

[george.burgess.iv]

Ping :)

[reames]

I am concerned that you doing too many things in one patch and that the mix of refactoring and functional changes may contain hard to spot bugs. In particular, the absence of hasValue checks in various updated logic worries me.

I strongly request that you separate a patch which simply factors out a LocationSize type with the exact same semantics as the existing code. Once landed, you can introduce the new precise concept on top of that.

include/llvm/Analysis/MemoryLocation.h

39

I think you mean: must be exactly N bytes. If not, I'm confused.

112

If the two are precise and equal, this downgrades to imprecise.

lib/Analysis/AliasSetTracker.cpp

631 ↗

(On Diff #140655)

looks like we probably need a print(OS) method on LocationSize.

lib/Analysis/BasicAliasAnalysis.cpp

1068

Don't you need to check that we have a value here?

1137

Same here.

[george.burgess.iv]

I am concerned that you doing too many things in one patch and that the mix of refactoring and functional changes may contain hard to spot bugs.

Right. I tried to reduce that as much as possible here, but it's still pretty large. :/

In particular, the absence of hasValue checks in various updated logic worries me.

Yeah, this is a casualty of the reducing mentioned above. x.hasValue() and x != MemoryLocation::Unknown are identical at the moment. While there wasn't anything too crazy WRT finding these checks (e.g. I didn't find any "well, the callers of X all verify this, ...", they can be pretty nonlocal even in a function.

I strongly request that you separate a patch which simply factors out a LocationSize type with the exact same semantics as the existing code. Once landed, you can introduce the new precise concept on top of that.

Works for me! Part one is D45581. Once we're happy with that, I'll rebase this patch on top of it. :)

include/llvm/Analysis/MemoryLocation.h

39

Yeah, I could've worded this better. I was trying to say "block of bytes that the MemoryLocation references" (e.g. a store i32 1, i32* %a implies that %a must be *at least* 4 bytes large). Will update with the rebase.

112

Shouldn't the Other == *this check handle that case?

lib/Analysis/AliasSetTracker.cpp

631 ↗

(On Diff #140655)

Added in the new patch; good call. :)

lib/Analysis/BasicAliasAnalysis.cpp

1068

There's a check near the top of the function (line 1002) for V1Size == MemoryLocation::UnknownSize || V2Size == MemoryLocation::UnknownSize. It's annoying that it's so far away, though. :/

Happy to unwrap V1Size and V2Size into unsigneds directly after the check if you think that'd be clearer.

1137

(Same function, so the above reply applies here)

[george.burgess.iv]

Rebase now that our LocationSize changes are in

lib/Analysis/BasicAliasAnalysis.cpp

1068

Happy to unwrap V1Size and V2Size into unsigneds directly after the check if you think that'd be clearer.

(I've done this across BasicAA in hopes of making things a bit clearer. Please let me know if you disagree)

1205

Not a BasicAA expert, but since I see "negative offset" and an int64_t cast here, I wanted to highlight that this LocationSize change eats the sign bit of ObjectAccessSize. I assume that ObjectAccessSize should always be positive and the int64_t cast exists just to keep the >= comparison signed, but...

[george.burgess.iv]

Ping :)

[nlopes]

lib/Analysis/MemoryDependenceAnalysis.cpp

1115

Why is it ok to ignore precision here?
If we did an alias query before with precise size, and the new one is with upper-bound, the results don't seem reusable.
(I have no clue how this function works; so I don't know if the above case can happen)

[george.burgess.iv]

Rebase + address feedback

lib/Analysis/MemoryDependenceAnalysis.cpp

1115

I was trying to keep this as close to NFC as possible, but yeah, good point.

I tried bootstrapping clang with assertions about the size either being unknown or precise, and no assertions fired, so it doesn't appear that known-but-imprecise values can reach here (or if they do, they do so very rarely).

Switched to always throwing out the cached data if the precision differs (we can do better if we know the value is now precise, too). Happy to swap to what you suggested if you feel that's better, though. Like you, I'm not super familiar with memdep...

[george.burgess.iv]

Ping :)

[george.burgess.iv]

ping :)

[reames]

This change is *still* too large to comfortably review in one pass. I *strongly encourage* you to take a look through this and take every opportunity to split off small NFC refactorings to reduce the diff length and complexity. I've highlighted a couple options for you, but there are likely others.

lib/Analysis/MemoryDependenceAnalysis.cpp

1115

This does not look NFC.

lib/Transforms/Scalar/DeadStoreElimination.cpp

352

If I'm reading this write, you can extract the majority of the mechanical updates to this function by adding the two variables to the old style code. Please do so shrink the diff. Also, make const.

[george.burgess.iv]

Shrunk the diff as requested; the few pre-commit patches required to make this build are available as one patch in https://reviews.llvm.org/D52245 .

[george.burgess.iv]

include/llvm/Analysis/AliasSetTracker.h

100

(This is a functional change if we try to call getSize() before setting a size. In my tests a few months ago, this was never done in practice, and it frankly makes no sense to me to try to get an unset size. :)

I'll bootstrap clang once more to verify that this assert isn't tripped before committing)

lib/Analysis/MemoryDependenceAnalysis.cpp

1115

You're correct; it adds a case where if the preciseness of CacheInfo->Size isn't the same as Loc.Size's, we'll throw everything out.

As noted in the comment, I can't get an imprecise value to land here in practice. If you'd rather I put an assertion about that here instead of CacheInfo->Size.isPrecise() != Loc.Size.isPrecise(), I'm happy to do so, but the rest of this should turn into the equivalent of what was CacheInfo->Size < Loc.Size.

[reames]

Mostly minor comments. I considered giving a conditional LGTM, but decided it warranted one last round. I think this is very close to landing.

include/llvm/Analysis/MemoryLocation.h

39

Looks like this update got lost?

JFYI, I consider clarity on this point essential.

39

Can we pick a different name? Maybe: union?

This is returning a result which is conservatively correct for uses of either. combineWith doesn't make that obvious.

lib/Analysis/BasicAliasAnalysis.cpp

1671–1674

This is definitely a warranted functional change, but please add a test case which reflects the change.

1731–1732

Same testing comment here.

lib/Analysis/MemoryDependenceAnalysis.cpp

1139

This looks to have very different behaviour than previously. Unless I'm misreading nesting, you’re recomputing any time the sizes are equal which is odd.

[george.burgess.iv]

Address feedback

[george.burgess.iv]

include/llvm/Analysis/MemoryLocation.h

39

Good catch; sorry for dropping this. Please let me know if you'd like me to expand further.

lib/Analysis/BasicAliasAnalysis.cpp

1671–1674

Added tests for both of these. It's not obvious to me how to get an imprecise size when directly testing BasicAA, so I opted for unittests. I'll do the newly-added // FIXME: This is duplicated between this file and MemorySSATest. Refactor. in a follow-up commit, in the interest of keeping this diff small.

lib/Analysis/MemoryDependenceAnalysis.cpp

1139

Yeah, this is one level of nesting deeper than it was previously (it's odd to me that phab doesn't point this out). In particular, the CacheInfo->Size != Loc.Size check guards this

[reames]

include/llvm/Analysis/MemoryLocation.h

39

Reading through this again, I think we have a semantic problem here. The previous semantics of MemoryLocation was that we had a memory region which was guaranteed to be at least as large as the memory actually dereferenced. Your documented new semantics now indicate that the accessed region is *larger* than the MemLoc when that MemLoc is precise. This now means that to know whether a MemLoc is inclusive of the access we *must* check the precise bit.

I am not okay with that change.

I would be okay with either of the following:

1. Precise means "accesses exactly N bytes". (i.e. still bounded from above, but now also bounded from below with the same value)
2. We replace "precise" with a MinSize field. A memory location would then guarantee that the actual access was bounded from below by MinSize and above by Size.

I recommend (1) for the moment since I think that's what you've actually implemented. (2) would be more generic, but would be basically starting over.

[george.burgess.iv]

include/llvm/Analysis/MemoryLocation.h

39

Option one is what I was going for initially, but I see I tripped over myself a bit (mostly, the last sentence was meant to apply only to imprecise memory locations, though I made that wholly unclear :) ). Reworded.

As for #2, yeah, we can do that if there's a great need for it, but I'm happy to start with something simpler.

[reames]

LGTM w/one optional, but strongly recommended change.

include/llvm/Analysis/MemoryLocation.h

36–37

This implicit switch of all callers makes me nervous. I'm willing to trust that you've audited all the callers, but my advice (which I would follow if doing this myself) would be to submit this patch with the constructor defaulting to imprecise locations. Then, in a separate patch, flip the default. Specifically, the motivation is so that if you've missed something in your audit, most of the infrastructure can stay in tree and not need to be reverted while you debug.

[george.burgess.iv]

Woo! Thank you very much for the review (and for bearing with me in your repeated requests to minimize this patch :) ).

Since there's quite a few pieces to this, I'll probably just land it all slowly over a few days, pending our last discussion here being settled.

include/llvm/Analysis/MemoryLocation.h

36–37

I'm not sure I understand. All MemoryLocations are implicitly precise today, so the most functionality-preserving thing we can do here is to treat all of them as precise by default.

Treating them all as imprecise would certainly fix any existing, yet-to-be-reported bugs where we're passing 'imprecise' MemoryLocations around. The hope is to find those places as a part of the migration to explicitly use ::precise/::upperBound, though.

Does that make sense? Or am I missing something?

[reames]

include/llvm/Analysis/MemoryLocation.h

36–37

I think the problem is that we sometimes assume MemLocs are precise, and sometimes assume they're conservative. :)

I'm fine with you landing with either default. I defer to your judgement.

[george.burgess.iv]

Thanks again! :)

include/llvm/Analysis/AliasSetTracker.h

 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;
-    LocationSize Size = 0;
+    LocationSize Size = LocationSize::mapEmpty();
     AAMDNodes AAInfo;
 
+    // Whether the size for this record has been set at all. This makes no
+    // guarantees about the size being known.
+    bool isSizeSet() const { return Size != LocationSize::mapEmpty(); }
+
   public:
     PointerRec(Value *V)
       : Val(V), AAInfo(DenseMapInfo<AAMDNodes>::getEmptyKey()) {}
 
     Value *getValue() const { return Val; }
 
     PointerRec *getNext() const { return NextInList; }
     bool hasAliasSet() const { return AS != nullptr; }
 
     PointerRec** setPrevInList(PointerRec **PIL) {
       PrevInList = PIL;
       return &NextInList;
     }
 
     bool updateSizeAndAAInfo(LocationSize NewSize, const AAMDNodes &NewAAInfo) {
       bool SizeChanged = false;
-      if (NewSize > Size) {
-        Size = NewSize;
-        SizeChanged = true;
+      if (NewSize != Size) {
+        LocationSize OldSize = Size;
+        Size = isSizeSet() ? Size.combineWith(NewSize) : NewSize;
+        SizeChanged = OldSize != Size;
       }
 
       if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey())
         // We don't have a AAInfo yet. Set it to NewAAInfo.
         AAInfo = NewAAInfo;
       else {
         AAMDNodes Intersection(AAInfo.intersect(NewAAInfo));
         if (!Intersection) {
           // NewAAInfo conflicts with AAInfo.
           AAInfo = DenseMapInfo<AAMDNodes>::getTombstoneKey();
           return SizeChanged;
         }
         AAInfo = Intersection;
       }
       return SizeChanged;
     }
 
-    LocationSize getSize() const { return Size; }
+    LocationSize getSize() const {
+      assert(isSizeSet() && "Getting an unset size!");
+      return Size;
+    }
 
     /// Return the AAInfo, or null if there is no information or conflicting
     /// information.
     AAMDNodes getAAInfo() const {
       // If we have missing or conflicting AAInfo, return null.
       if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey() ||
           AAInfo == DenseMapInfo<AAMDNodes>::getTombstoneKey())
         return AAMDNodes();

include/llvm/Analysis/MemoryLocation.h

 class MemTransferInst;
 class MemIntrinsic;
 class AtomicMemTransferInst;
 class AtomicMemIntrinsic;
 class AnyMemTransferInst;
 class AnyMemIntrinsic;
 class TargetLibraryInfo;
 
 // Represents the size of a MemoryLocation. Logically, it's an
-// Optional<uint64_t>, with a special UnknownSize value from `MemoryLocation`.
-using LocationSize = uint64_t;
+// Optional<uint63_t> that also carries a bit to represent whether the integer
+// it contains, N, is 'precise'. Precise, in this context, means that we know
+// that the MemoryLocation we're referencing has to be at least N bytes large.
+//
+// An example of a precise MemoryLocation is (%p, 4) in
+// store i32 0, i32* %p
+//
+// Since we know that %p must be at least 4 bytes large at this point.
+// Otherwise, we have UB. An example of an imprecise MemoryLocation is (%p, 4)
+// at the memcpy in
+//
+//   %n = select i1 %foo, i64 1, i64 4
+//   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %p, i8* %baz, i64 %n, i32 1,
+//                                        i1 false)
+//
+// ...Since we'll copy *up to* 4 bytes into %p, but we can't guarantee that
+// we'll ever actually do so.
+//
+// If asked to represent a pathologically large value, this will degrade to
+// None.
+class LocationSize {
+  enum : uint64_t {
+    Unknown = ~uint64_t(0),
+    ImpreciseBit = uint64_t(1) << 63,
+    MapEmpty = Unknown - 1,
+    MapTombstone = Unknown - 2,
+
+    // The maximum value we can represent without falling back to 'unknown'.
+    MaxValue = (MapTombstone - 1) & ~ImpreciseBit,
+  };
+
+  uint64_t Value;
+
+  // Hack to support implicit construction. This should disappear when the
+  // public LocationSize ctor goes away.
+  enum DirectConstruction { Direct };
+
+  constexpr LocationSize(uint64_t Raw, DirectConstruction): Value(Raw) {}
+
+  static_assert(Unknown & ImpreciseBit, "Unknown is imprecise by definition.");
+public:
+  // FIXME: Migrate all users to construct via either `precise` or `upperBound`,
+  // to make it more obvious at the callsite the kind of size that they're
+  // providing.
+  //
+  // Since the overwhelming majority of users of this provide precise values,
+  // this assumes the provided value is precise.
+  constexpr LocationSize(uint64_t Raw)
+      : Value(Raw > MaxValue ? Unknown : Raw) {}
+
+  static LocationSize precise(uint64_t Value) {
+    if (LLVM_UNLIKELY(Value > MaxValue))
+      return unknown();
+    return LocationSize(Value, Direct);
+  }
+
+  static LocationSize upperBound(uint64_t Value) {
+    // You can't go lower than 0, so give a precise result.
+    if (LLVM_UNLIKELY(Value == 0))
+      return precise(0);
+    if (LLVM_UNLIKELY(Value > MaxValue))
+      return unknown();
+    return LocationSize(Value | ImpreciseBit, Direct);
+  }
+
+  constexpr static LocationSize unknown() {
+    return LocationSize(Unknown, Direct);
+  }
+
+  // Sentinel values, generally used for maps.
+  constexpr static LocationSize mapTombstone() {
+    return LocationSize(MapTombstone, Direct);
+  }
+  constexpr static LocationSize mapEmpty() {
+    return LocationSize(MapEmpty, Direct);
+  }
+
+  // Returns a LocationSize that can sanely represent either `*this` or `Other`.
+  LocationSize combineWith(LocationSize Other) const {
+    if (Other == *this)
+      return *this;
+
+    if (!hasValue() || !Other.hasValue())
+      return unknown();
+
+    return upperBound(std::max(getValue(), Other.getValue()));
+  }
+
+  bool hasValue() const { return Value != Unknown; }
+  uint64_t getValue() const {
+    assert(hasValue() && "Getting value from an unknown LocationSize!");
+    return Value & ~ImpreciseBit;
+  }
+
+  // Returns whether or not this value is precise. Note that if a value is
+  // precise, it's guaranteed to not be `unknown()`.
+  bool isPrecise() const {
+    return (Value & ImpreciseBit) == 0;
+  }
+
+  bool isZero() const { return hasValue() && getValue() == 0; }
+
+  bool operator==(const LocationSize &Other) const {
+    return Value == Other.Value;
+  }
+
+  bool operator!=(const LocationSize &Other) const {
+    return !operator==(Other);
+  }
+
+  bool equalsIgnoringPrecision(const LocationSize &Other) const {
+    // Special values (unknown+map values) are distinct even without the
+    // ImpreciseBit set.
+    return (Value & ~ImpreciseBit) == (Other.Value & ~ImpreciseBit);
+  }
+
+  void print(raw_ostream &OS) const;
+
+  // Ordering operators are not provided, since it's unclear if there's only one
+  // reasonable way to compare:
+  // - values that don't exist against values that do, and
+  // - precise values to imprecise values
+
+  // Returns an opaque value that represents this LocationSize.
+  uint64_t toRaw() const { return Value; }
+};
+
+inline raw_ostream &operator<<(raw_ostream &OS, LocationSize Size) {
+  Size.print(OS);
+  return OS;
+}
 
 /// Representation for a specific memory location.
 ///
 /// This abstraction can be used to represent a specific location in memory.
 /// The goal of the location is to represent enough information to describe
 /// abstract aliasing, modification, and reference behaviors of whatever
 /// value(s) are stored in memory at the particular location.
 ///
MemoryLocation getWithoutAATags() const {
     return Copy;
   }
 
   bool operator==(const MemoryLocation &Other) const {
     return Ptr == Other.Ptr && Size == Other.Size && AATags == Other.AATags;
   }
 };
 
-// Specialize DenseMapInfo for MemoryLocation.
+// Specialize DenseMapInfo.
+template <> struct DenseMapInfo<LocationSize> {
+  static inline LocationSize getEmptyKey() {
+    return LocationSize::mapEmpty();
+  }
+  static inline LocationSize getTombstoneKey() {
+    return LocationSize::mapTombstone();
+  }
+  static unsigned getHashValue(const LocationSize &Val) {
+    return DenseMapInfo<uint64_t>::getHashValue(Val.toRaw());
+  }
+  static bool isEqual(const LocationSize &LHS, const LocationSize &RHS) {
+    return LHS == RHS;
+  }
+};
+
 template <> struct DenseMapInfo<MemoryLocation> {
   static inline MemoryLocation getEmptyKey() {
-    return MemoryLocation(DenseMapInfo<const Value *>::getEmptyKey(), 0);
+    return MemoryLocation(DenseMapInfo<const Value *>::getEmptyKey(),
+                          DenseMapInfo<LocationSize>::getEmptyKey());
   }
   static inline MemoryLocation getTombstoneKey() {
-    return MemoryLocation(DenseMapInfo<const Value *>::getTombstoneKey(), 0);
+    return MemoryLocation(DenseMapInfo<const Value *>::getTombstoneKey(),
+                          DenseMapInfo<LocationSize>::getTombstoneKey());
   }
   static unsigned getHashValue(const MemoryLocation &Val) {
     return DenseMapInfo<const Value *>::getHashValue(Val.Ptr) ^
            DenseMapInfo<LocationSize>::getHashValue(Val.Size) ^
            DenseMapInfo<AAMDNodes>::getHashValue(Val.AATags);
   }
   static bool isEqual(const MemoryLocation &LHS, const MemoryLocation &RHS) {
     return LHS == RHS;
   }
 };
 }
 
 #endif

lib/Analysis/BasicAliasAnalysis.cpp

ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS1,
 
   // The AAResultBase base class has some smarts, lets use them.
   return AAResultBase::getModRefInfo(CS1, CS2);
 }
 
 /// Provide ad-hoc rules to disambiguate accesses through two GEP operators,
 /// both having the exact same pointer operand.
 static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1,
-                                            LocationSize V1Size,
+                                            LocationSize MaybeV1Size,
                                             const GEPOperator *GEP2,
-                                            LocationSize V2Size,
+                                            LocationSize MaybeV2Size,
                                             const DataLayout &DL) {
   assert(GEP1->getPointerOperand()->stripPointerCastsAndInvariantGroups() ==
              GEP2->getPointerOperand()->stripPointerCastsAndInvariantGroups() &&
          GEP1->getPointerOperandType() == GEP2->getPointerOperandType() &&
          "Expected GEPs with the same pointer operand");
 
   // Try to determine whether GEP1 and GEP2 index through arrays, into structs,
   // such that the struct field accesses provably cannot alias.
   // We also need at least two indices (the pointer, and the struct field).
   if (GEP1->getNumIndices() != GEP2->getNumIndices() ||
       GEP1->getNumIndices() < 2)
     return MayAlias;
 
   // If we don't know the size of the accesses through both GEPs, we can't
   // determine whether the struct fields accessed can't alias.
-  if (V1Size == MemoryLocation::UnknownSize ||
-      V2Size == MemoryLocation::UnknownSize)
+  if (MaybeV1Size == MemoryLocation::UnknownSize ||
+      MaybeV2Size == MemoryLocation::UnknownSize)
     return MayAlias;
 
+  const uint64_t V1Size = MaybeV1Size.getValue();
+  const uint64_t V2Size = MaybeV2Size.getValue();
+
   ConstantInt *C1 =
       dyn_cast<ConstantInt>(GEP1->getOperand(GEP1->getNumOperands() - 1));
   ConstantInt *C2 =
       dyn_cast<ConstantInt>(GEP2->getOperand(GEP2->getNumOperands() - 1));
 
   // If the last (struct) indices are constants and are equal, the other indices
   // might be also be dynamically equal, so the GEPs can alias.
   if (C1 && C2 && C1->getSExtValue() == C2->getSExtValue())
if (isa<SequentialType>(Ty)) {
     //
     // Because array indices greater than the number of elements are valid in
     // GEPs, unless we know the intermediate indices are identical between
     // GEP1 and GEP2 we cannot guarantee that the last indexed arrays don't
     // partially overlap. We also need to check that the loaded size matches
     // the element size, otherwise we could still have overlap.
     const uint64_t ElementSize =
         DL.getTypeStoreSize(cast<SequentialType>(Ty)->getElementType());
     if (V1Size != ElementSize || V2Size != ElementSize)
       return MayAlias;
 
     for (unsigned i = 0, e = GEP1->getNumIndices() - 1; i != e; ++i)
       if (GEP1->getOperand(i + 1) != GEP2->getOperand(i + 1))
         return MayAlias;
 
     // Now we know that the array/pointer that GEP1 indexes into and that
     // that GEP2 indexes into must either precisely overlap or be disjoint.
static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1,
   auto EltsDontOverlap = [StructSize](uint64_t V1Off, uint64_t V1Size,
                                       uint64_t V2Off, uint64_t V2Size) {
     return V1Off < V2Off && V1Off + V1Size <= V2Off &&
            ((V2Off + V2Size <= StructSize) ||
             (V2Off + V2Size - StructSize <= V1Off));
   };
 
   if (EltsDontOverlap(V1Off, V1Size, V2Off, V2Size) ||
       EltsDontOverlap(V2Off, V2Size, V1Off, V1Size))
     return NoAlias;
 
   return MayAlias;
 }
 
 // If a we have (a) a GEP and (b) a pointer based on an alloca, and the
 // beginning of the object the GEP points would have a negative offset with
 // repsect to the alloca, that means the GEP can not alias pointer (b).

 //
 // Assume %f1 and %f0 alias. Then %f1 would point into the object allocated
 // by %alloca. Since the %f1 GEP is inbounds, that means %random must also
 // point into the same object. But since %f0 points to the beginning of %alloca,
 // the highest %f1 can be is (%alloca + 3). This means %random can not be higher
 // than (%alloca - 1), and so is not inbounds, a contradiction.
 bool BasicAAResult::isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp,
       const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompObject,
-      LocationSize ObjectAccessSize) {
+      LocationSize MaybeObjectAccessSize) {
   // If the object access size is unknown, or the GEP isn't inbounds, bail.
-  if (ObjectAccessSize == MemoryLocation::UnknownSize || !GEPOp->isInBounds())
+  if (MaybeObjectAccessSize == MemoryLocation::UnknownSize ||
+      !GEPOp->isInBounds())
     return false;
 
+  const auto ObjectAccessSize = int64_t(MaybeObjectAccessSize.getValue());
+
   // We need the object to be an alloca or a globalvariable, and want to know
   // the offset of the pointer from the object precisely, so no variable
   // indices are allowed.
   if (!(isa<AllocaInst>(DecompObject.Base) ||
         isa<GlobalVariable>(DecompObject.Base)) ||
       !DecompObject.VarIndices.empty())
     return false;
 
   int64_t ObjectBaseOffset = DecompObject.StructOffset +
                              DecompObject.OtherOffset;
 
   // If the GEP has no variable indices, we know the precise offset
   // from the base, then use it. If the GEP has variable indices,
   // we can't get exact GEP offset to identify pointer alias. So return
   // false in that case.
   if (!DecompGEP.VarIndices.empty())
     return false;
   int64_t GEPBaseOffset = DecompGEP.StructOffset;
   GEPBaseOffset += DecompGEP.OtherOffset;
 
-  return (GEPBaseOffset >= ObjectBaseOffset + (int64_t)ObjectAccessSize);
+  return GEPBaseOffset >= ObjectBaseOffset + ObjectAccessSize;
 }
 
 /// Provides a bunch of ad-hoc rules to disambiguate a GEP instruction against
 /// another pointer.
 ///
 /// We know that V1 is a GEP, but we don't know anything about V2.
 /// UnderlyingV1 is GetUnderlyingObject(GEP1, DL), UnderlyingV2 is the same for
 /// V2.
 AliasResult
BasicAAResult::aliasGEP(const GEPOperator *GEP1, LocationSize V1Size,
 
   // 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 (GEP1BaseOffset != 0 && DecompGEP1.VarIndices.empty()) {
     if (GEP1BaseOffset >= 0) {
       if (V2Size != MemoryLocation::UnknownSize) {
-        if ((uint64_t)GEP1BaseOffset < V2Size)
+        if ((uint64_t)GEP1BaseOffset < V2Size.getValue())
           return PartialAlias;
         return NoAlias;
       }
     } else {
       // We have the situation where:
       // +                +
       // | BaseOffset     |
       // ---------------->|
       // |-->V1Size       |-------> V2Size
       // GEP1             V2
       // We need to know that V2Size is not unknown, otherwise we might have
       // stripped a gep with negative index ('gep <ptr>, -1, ...).
       if (V1Size != MemoryLocation::UnknownSize &&
           V2Size != MemoryLocation::UnknownSize) {
-        if (-(uint64_t)GEP1BaseOffset < V1Size)
+        if (-(uint64_t)GEP1BaseOffset < V1Size.getValue())
           return PartialAlias;
         return NoAlias;
       }
     }
   }
 
   if (!DecompGEP1.VarIndices.empty()) {
     uint64_t Modulo = 0;
if (!DecompGEP1.VarIndices.empty()) {
 
     Modulo = Modulo ^ (Modulo & (Modulo - 1));
 
     // We can compute the difference between the two addresses
     // mod Modulo. Check whether that difference guarantees that the
     // two locations do not alias.
     uint64_t ModOffset = (uint64_t)GEP1BaseOffset & (Modulo - 1);
     if (V1Size != MemoryLocation::UnknownSize &&
-        V2Size != MemoryLocation::UnknownSize && ModOffset >= V2Size &&
-        V1Size <= Modulo - ModOffset)
+        V2Size != MemoryLocation::UnknownSize &&
+        ModOffset >= V2Size.getValue() &&
+        V1Size.getValue() <= Modulo - ModOffset)
       return NoAlias;
 
     // If we know all the variables are positive, then GEP1 >= GEP1BasePtr.
     // If GEP1BasePtr > V2 (GEP1BaseOffset > 0) then we know the pointers
     // don't alias if V2Size can fit in the gap between V2 and GEP1BasePtr.
-    if (AllPositive && GEP1BaseOffset > 0 && V2Size <= (uint64_t)GEP1BaseOffset)
+    if (AllPositive && GEP1BaseOffset > 0 && V2Size.hasValue() &&
+        V2Size.getValue() <= (uint64_t)GEP1BaseOffset)
       return NoAlias;
 
     if (constantOffsetHeuristic(DecompGEP1.VarIndices, V1Size, V2Size,
                                 GEP1BaseOffset, &AC, DT))
       return NoAlias;
   }
 
   // Statically, we can see that the base objects are the same, but the
if (O1 != O2) {
     if (isEscapeSource(O1) && isNonEscapingLocalObject(O2))
       return NoAlias;
     if (isEscapeSource(O2) && isNonEscapingLocalObject(O1))
       return NoAlias;
   }
 
   // If the size of one access is larger than the entire object on the other
   // side, then we know such behavior is undefined and can assume no alias.
-  if ((V1Size != MemoryLocation::UnknownSize &&
-       isObjectSmallerThan(O2, V1Size, DL, TLI)) ||
-      (V2Size != MemoryLocation::UnknownSize &&
-       isObjectSmallerThan(O1, V2Size, DL, TLI)))
+  if ((V1Size.isPrecise() &&
+       isObjectSmallerThan(O2, V1Size.getValue(), DL, TLI)) ||
+      (V2Size.isPrecise() &&
+       isObjectSmallerThan(O1, V2Size.getValue(), DL, TLI)))
     return NoAlias;
 
   // Check the cache before climbing up use-def chains. This also terminates
   // otherwise infinitely recursive queries.
   LocPair Locs(MemoryLocation(V1, V1Size, V1AAInfo),
                MemoryLocation(V2, V2Size, V2AAInfo));
   if (V1 > V2)
     std::swap(Locs.first, Locs.second);
if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) {
     AliasResult Result =
         aliasSelect(S1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O2);
     if (Result != MayAlias)
       return AliasCache[Locs] = Result;
   }
 
   // If both pointers are pointing into the same object and one of them
   // accesses the entire object, then the accesses must overlap in some way.
   if (O1 == O2)
-    if (V1Size != MemoryLocation::UnknownSize &&
-        V2Size != MemoryLocation::UnknownSize &&
-        (isObjectSize(O1, V1Size, DL, TLI) ||
-         isObjectSize(O2, V2Size, DL, TLI)))
+    if (V1Size.isPrecise() && V2Size.isPrecise() &&
+        (isObjectSize(O1, V1Size.getValue(), DL, TLI) ||
+         isObjectSize(O2, V2Size.getValue(), DL, TLI)))
       return AliasCache[Locs] = PartialAlias;
 
   // Recurse back into the best AA results we have, potentially with refined
   // memory locations. We have already ensured that BasicAA has a MayAlias
   // cache result for these, so any recursion back into BasicAA won't loop.
   AliasResult Result = getBestAAResults().alias(Locs.first, Locs.second);
   return AliasCache[Locs] = Result;
 }
for (unsigned i = 0, e = Src.size(); i != e; ++i) {
     if (Scale) {
       VariableGEPIndex Entry = {V, ZExtBits, SExtBits, -Scale};
       Dest.push_back(Entry);
     }
   }
 }
 
 bool BasicAAResult::constantOffsetHeuristic(
-    const SmallVectorImpl<VariableGEPIndex> &VarIndices, LocationSize V1Size,
-    LocationSize V2Size, int64_t BaseOffset, AssumptionCache *AC,
-    DominatorTree *DT) {
-  if (VarIndices.size() != 2 || V1Size == MemoryLocation::UnknownSize ||
-      V2Size == MemoryLocation::UnknownSize)
+    const SmallVectorImpl<VariableGEPIndex> &VarIndices,
+    LocationSize MaybeV1Size, LocationSize MaybeV2Size, int64_t BaseOffset,
+    AssumptionCache *AC, DominatorTree *DT) {
+  if (VarIndices.size() != 2 || MaybeV1Size == MemoryLocation::UnknownSize ||
+      MaybeV2Size == MemoryLocation::UnknownSize)
     return false;
 
+  const uint64_t V1Size = MaybeV1Size.getValue();
+  const uint64_t V2Size = MaybeV2Size.getValue();
+
   const VariableGEPIndex &Var0 = VarIndices[0], &Var1 = VarIndices[1];
 
   if (Var0.ZExtBits != Var1.ZExtBits || Var0.SExtBits != Var1.SExtBits ||
       Var0.Scale != -Var1.Scale)
     return false;
 
   unsigned Width = Var1.V->getType()->getIntegerBitWidth();
 

lib/Analysis/CFLAndersAliasAnalysis.cpp

auto RangePair = std::equal_range(Itr->second.begin(), Itr->second.end(),
                                       OffsetValue{RHS, 0}, Comparator);
 
     if (RangePair.first != RangePair.second) {
       // Be conservative about UnknownSize
       if (LHSSize == MemoryLocation::UnknownSize ||
           RHSSize == MemoryLocation::UnknownSize)
         return true;
 
+      assert(LHSSize.getValue() <= INT64_MAX &&
+             RHSSize.getValue() <= INT64_MAX &&
+             "INT64_MAX is less than a uint63_t's max?");
+
       for (const auto &OVal : make_range(RangePair)) {
         // Be conservative about UnknownOffset
         if (OVal.Offset == UnknownOffset)
           return true;
 
         // We know that LHS aliases (RHS + OVal.Offset) if the control flow
         // reaches here. The may-alias query essentially becomes integer
         // range-overlap queries over two ranges [OVal.Offset, OVal.Offset +
         // LHSSize) and [0, RHSSize).
 
-        // Try to be conservative on super large offsets
-        if (LLVM_UNLIKELY(LHSSize > INT64_MAX || RHSSize > INT64_MAX))
-          return true;
-
-        auto LHSStart = OVal.Offset;
+        int64_t LHSStart = OVal.Offset;
         // FIXME: Do we need to guard against integer overflow?
-        auto LHSEnd = OVal.Offset + static_cast<int64_t>(LHSSize);
-        auto RHSStart = 0;
-        auto RHSEnd = static_cast<int64_t>(RHSSize);
+        int64_t LHSEnd = OVal.Offset + static_cast<int64_t>(LHSSize.getValue());
+        int64_t RHSStart = 0;
+        auto RHSEnd = static_cast<int64_t>(RHSSize.getValue());
         if (LHSEnd > RHSStart && LHSStart < RHSEnd)
           return true;
       }
     }
   }
 
   return false;
 }

lib/Analysis/MemoryDependenceAnalysis.cpp

bool MemoryDependenceResults::getNonLocalPointerDepFromBB(
   // already have one.
   std::pair<CachedNonLocalPointerInfo::iterator, bool> Pair =
       NonLocalPointerDeps.insert(std::make_pair(CacheKey, InitialNLPI));
   NonLocalPointerInfo *CacheInfo = &Pair.first->second;
 
   // If we already have a cache entry for this CacheKey, we may need to do some
   // work to reconcile the cache entry and the current query.
   if (!Pair.second) {
-    if (CacheInfo->Size < Loc.Size) {
+    if (!CacheInfo->Size.equalsIgnoringPrecision(Loc.Size)) {
+      // For our purposes, unknown size > all others.
+      bool CachedSizeIsGreater;
+      if (CacheInfo->Size.hasValue() != Loc.Size.hasValue()) {
+        CachedSizeIsGreater = Loc.Size.hasValue();
+      } else {
+        assert(CacheInfo->Size.hasValue() && Loc.Size.hasValue() &&
+               "Unequal sizes, but both are None?");
+        CachedSizeIsGreater = CacheInfo->Size.getValue() > Loc.Size.getValue();
+      }
+
+      if (!CachedSizeIsGreater) {
         // The query's Size is greater than the cached one. Throw out the
         // cached data and proceed with the query at the greater size.
         CacheInfo->Pair = BBSkipFirstBlockPair();
         CacheInfo->Size = Loc.Size;
         for (auto &Entry : CacheInfo->NonLocalDeps)
           if (Instruction *Inst = Entry.getResult().getInst())
             RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey);
         CacheInfo->NonLocalDeps.clear();
-    } else if (CacheInfo->Size > Loc.Size) {
+      } else {
         // This query's Size is less than the cached one. Conservatively restart
         // the query using the greater size.
         return getNonLocalPointerDepFromBB(
             QueryInst, Pointer, Loc.getWithNewSize(CacheInfo->Size), isLoad,
             StartBB, Result, Visited, SkipFirstBlock);
       }
+    }
 
     // If the query's AATags are inconsistent with the cached one,
     // conservatively throw out the cached data and restart the query with
     // no tag if needed.
     if (CacheInfo->AATags != Loc.AATags) {
       if (CacheInfo->AATags) {
         CacheInfo->Pair = BBSkipFirstBlockPair();
         CacheInfo->AATags = AAMDNodes();

lib/Analysis/MemoryLocation.cpp

 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Type.h"
 using namespace llvm;
 
+void LocationSize::print(raw_ostream &OS) const {
+  OS << "LocationSize::";
+  if (*this == unknown())
+    OS << "unknown";
+  else if (*this == mapEmpty())
+    OS << "mapEmpty";
+  else if (*this == mapTombstone())
+    OS << "mapTombstone";
+  else if (isPrecise())
+    OS << "precise(" << getValue() << ')';
+  else
+    OS << "upperBound(" << getValue() << ')';
+}
+
 MemoryLocation MemoryLocation::get(const LoadInst *LI) {
   AAMDNodes AATags;
   LI->getAAMetadata(AATags);
   const auto &DL = LI->getModule()->getDataLayout();
 
   return MemoryLocation(LI->getPointerOperand(),
                         DL.getTypeStoreSize(LI->getType()), AATags);
 }

lib/Analysis/ScalarEvolutionAliasAnalysis.cpp

 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 using namespace llvm;
 
 AliasResult SCEVAAResult::alias(const MemoryLocation &LocA,
                                 const MemoryLocation &LocB) {
   // If either of the memory references is empty, it doesn't matter what the
   // pointer values are. This allows the code below to ignore this special
   // case.
-  if (LocA.Size == 0 || LocB.Size == 0)
+  if (LocA.Size.isZero() || LocB.Size.isZero())
     return NoAlias;
 
   // This is SCEVAAResult. Get the SCEVs!
   const SCEV *AS = SE.getSCEV(const_cast<Value *>(LocA.Ptr));
   const SCEV *BS = SE.getSCEV(const_cast<Value *>(LocB.Ptr));
 
   // If they evaluate to the same expression, it's a MustAlias.
   if (AS == BS)
     return MustAlias;
 
   // If something is known about the difference between the two addresses,
   // see if it's enough to prove a NoAlias.
-  if (SE.getEffectiveSCEVType(AS->getType()) ==
+  if (LocA.Size.hasValue() && LocB.Size.hasValue() &&
+      SE.getEffectiveSCEVType(AS->getType()) ==
           SE.getEffectiveSCEVType(BS->getType())) {
     unsigned BitWidth = SE.getTypeSizeInBits(AS->getType());
-    APInt ASizeInt(BitWidth, LocA.Size);
-    APInt BSizeInt(BitWidth, LocB.Size);
+    APInt ASizeInt(BitWidth, LocA.Size.getValue());
+    APInt BSizeInt(BitWidth, LocB.Size.getValue());
 
     // Compute the difference between the two pointers.
     const SCEV *BA = SE.getMinusSCEV(BS, AS);
 
     // Test whether the difference is known to be great enough that memory of
     // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
     // are non-zero, which is special-cased above.
     if (ASizeInt.ule(SE.getUnsignedRange(BA).getUnsignedMin()) &&

lib/Transforms/Scalar/DeadStoreElimination.cpp

 static OverwriteResult isOverwrite(const MemoryLocation &Later,
                                    const MemoryLocation &Earlier,
                                    const DataLayout &DL,
                                    const TargetLibraryInfo &TLI,
                                    int64_t &EarlierOff, int64_t &LaterOff,
                                    Instruction *DepWrite,
                                    InstOverlapIntervalsTy &IOL,
                                    AliasAnalysis &AA) {
-  // If we don't know the sizes of either access, then we can't do a comparison.
-  if (Later.Size == MemoryLocation::UnknownSize ||
-      Earlier.Size == MemoryLocation::UnknownSize)
+  // FIXME: Vet that this works for size upper-bounds. Seems unlikely that we'll
+  // get imprecise values here, though (except for unknown sizes).
+  if (!Later.Size.isPrecise() || !Earlier.Size.isPrecise())
     return OW_Unknown;
 
+  uint64_t LaterSize = Later.Size.getValue();
+  uint64_t EarlierSize = Earlier.Size.getValue();
+
   const Value *P1 = Earlier.Ptr->stripPointerCasts();
   const Value *P2 = Later.Ptr->stripPointerCasts();
 
   // If the start pointers are the same, we just have to compare sizes to see if
   // the later store was larger than the earlier store.
   if (P1 == P2 || AA.isMustAlias(P1, P2)) {
     // Make sure that the Later size is >= the Earlier size.
-    if (Later.Size >= Earlier.Size)
+    if (LaterSize >= EarlierSize)
       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 *UO1 = GetUnderlyingObject(P1, DL),
               *UO2 = GetUnderlyingObject(P2, DL);
 
   // If we can't resolve the same pointers to the same object, then we can't
   // analyze them at all.
   if (UO1 != UO2)
     return OW_Unknown;
 
   // If the "Later" store is to a recognizable object, get its size.
   uint64_t ObjectSize = getPointerSize(UO2, DL, TLI);
   if (ObjectSize != MemoryLocation::UnknownSize)
-    if (ObjectSize == Later.Size && ObjectSize >= Earlier.Size)
+    if (ObjectSize == LaterSize && ObjectSize >= EarlierSize)
       return OW_Complete;
 
   // Okay, we have stores to two completely different pointers.  Try to
   // decompose the pointer into a "base + constant_offset" form.  If the base
   // pointers are equal, then we can reason about the two stores.
   EarlierOff = 0;
   LaterOff = 0;
   const Value *BP1 = GetPointerBaseWithConstantOffset(P1, EarlierOff, DL);
static OverwriteResult isOverwrite(const MemoryLocation &Later,
   // 2. The earlier store has an offset greater than the later offset, but which
   //    still lies completely within the later store.
   //
   //        |--earlier--|
   //    |-----  later  ------|
   //
   // We have to be careful here as *Off is signed while *.Size is unsigned.
   if (EarlierOff >= LaterOff &&
-      Later.Size >= Earlier.Size &&
-      uint64_t(EarlierOff - LaterOff) + Earlier.Size <= Later.Size)
+      LaterSize >= EarlierSize &&
+      uint64_t(EarlierOff - LaterOff) + EarlierSize <= LaterSize)
     return OW_Complete;
 
   // We may now overlap, although the overlap is not complete. There might also
   // be other incomplete overlaps, and together, they might cover the complete
   // earlier write.
   // Note: The correctness of this logic depends on the fact that this function
   // is not even called providing DepWrite when there are any intervening reads.
   if (EnablePartialOverwriteTracking &&
-      LaterOff < int64_t(EarlierOff + Earlier.Size) &&
-      int64_t(LaterOff + Later.Size) >= EarlierOff) {
+      LaterOff < int64_t(EarlierOff + EarlierSize) &&
+      int64_t(LaterOff + LaterSize) >= EarlierOff) {
 
     // Insert our part of the overlap into the map.
     auto &IM = IOL[DepWrite];
     LLVM_DEBUG(dbgs() << "DSE: Partial overwrite: Earlier [" << EarlierOff
-                      << ", " << int64_t(EarlierOff + Earlier.Size)
+                      << ", " << int64_t(EarlierOff + EarlierSize)
                       << ") Later [" << LaterOff << ", "
-                      << int64_t(LaterOff + Later.Size) << ")\n");
+                      << int64_t(LaterOff + LaterSize) << ")\n");
 
     // Make sure that we only insert non-overlapping intervals and combine
     // adjacent intervals. The intervals are stored in the map with the ending
     // offset as the key (in the half-open sense) and the starting offset as
     // the value.
-    int64_t LaterIntStart = LaterOff, LaterIntEnd = LaterOff + Later.Size;
+    int64_t LaterIntStart = LaterOff, LaterIntEnd = LaterOff + LaterSize;
 
     // Find any intervals ending at, or after, LaterIntStart which start
     // before LaterIntEnd.
     auto ILI = IM.lower_bound(LaterIntStart);
     if (ILI != IM.end() && ILI->second <= LaterIntEnd) {
       // This existing interval is overlapped with the current store somewhere
       // in [LaterIntStart, LaterIntEnd]. Merge them by erasing the existing
       // intervals and adjusting our start and end.
if (ILI != IM.end() && ILI->second <= LaterIntEnd) {
         ILI = IM.erase(ILI);
       }
     }
 
     IM[LaterIntEnd] = LaterIntStart;
 
     ILI = IM.begin();
     if (ILI->second <= EarlierOff &&
-        ILI->first >= int64_t(EarlierOff + Earlier.Size)) {
+        ILI->first >= int64_t(EarlierOff + EarlierSize)) {
       LLVM_DEBUG(dbgs() << "DSE: Full overwrite from partials: Earlier ["
                         << EarlierOff << ", "
-                        << int64_t(EarlierOff + Earlier.Size)
+                        << int64_t(EarlierOff + EarlierSize)
                         << ") Composite Later [" << ILI->second << ", "
                         << ILI->first << ")\n");
       ++NumCompletePartials;
       return OW_Complete;
     }
   }
 
   // Check for an earlier store which writes to all the memory locations that
   // the later store writes to.
   if (EnablePartialStoreMerging && LaterOff >= EarlierOff &&
-      int64_t(EarlierOff + Earlier.Size) > LaterOff &&
-      uint64_t(LaterOff - EarlierOff) + Later.Size <= Earlier.Size) {
+      int64_t(EarlierOff + EarlierSize) > LaterOff &&
+      uint64_t(LaterOff - EarlierOff) + LaterSize <= EarlierSize) {
     LLVM_DEBUG(dbgs() << "DSE: Partial overwrite an earlier load ["
                       << EarlierOff << ", "
-                      << int64_t(EarlierOff + Earlier.Size)
+                      << int64_t(EarlierOff + EarlierSize)
                       << ") by a later store [" << LaterOff << ", "
-                      << int64_t(LaterOff + Later.Size) << ")\n");
+                      << int64_t(LaterOff + LaterSize) << ")\n");
     // TODO: Maybe come up with a better name?
     return OW_PartialEarlierWithFullLater;
   }
 
   // Another interesting case is if the later store overwrites the end of the
   // earlier store.
   //
   //      |--earlier--|
   //                |--   later   --|
   //
   // In this case we may want to trim the size of earlier to avoid generating
   // writes to addresses which will definitely be overwritten later
   if (!EnablePartialOverwriteTracking &&
-      (LaterOff > EarlierOff && LaterOff < int64_t(EarlierOff + Earlier.Size) &&
-       int64_t(LaterOff + Later.Size) >= int64_t(EarlierOff + Earlier.Size)))
+      (LaterOff > EarlierOff && LaterOff < int64_t(EarlierOff + EarlierSize) &&
+       int64_t(LaterOff + LaterSize) >= int64_t(EarlierOff + EarlierSize)))
     return OW_End;
 
   // Finally, we also need to check if the later store overwrites the beginning
   // of the earlier store.
   //
   //                |--earlier--|
   //      |--   later   --|
   //
   // In this case we may want to move the destination address and trim the size
   // of earlier to avoid generating writes to addresses which will definitely
   // be overwritten later.
   if (!EnablePartialOverwriteTracking &&
-      (LaterOff <= EarlierOff && int64_t(LaterOff + Later.Size) > EarlierOff)) {
-    assert(int64_t(LaterOff + Later.Size) <
-               int64_t(EarlierOff + Earlier.Size) &&
+      (LaterOff <= EarlierOff && int64_t(LaterOff + LaterSize) > EarlierOff)) {
+    assert(int64_t(LaterOff + LaterSize) < int64_t(EarlierOff + EarlierSize) &&
            "Expect to be handled as OW_Complete");
     return OW_Begin;
   }
   // Otherwise, they don't completely overlap.
   return OW_Unknown;
 }
 
 /// If 'Inst' might be a self read (i.e. a noop copy of a

 static bool removePartiallyOverlappedStores(AliasAnalysis *AA,
                                             const DataLayout &DL,
                                             InstOverlapIntervalsTy &IOL) {
   bool Changed = false;
   for (auto OI : IOL) {
     Instruction *EarlierWrite = OI.first;
     MemoryLocation Loc = getLocForWrite(EarlierWrite);
     assert(isRemovable(EarlierWrite) && "Expect only removable instruction");
-    assert(Loc.Size != MemoryLocation::UnknownSize && "Unexpected mem loc");
+    auto EarlierSize = int64_t(Loc.Size.getValue());
 
     const Value *Ptr = Loc.Ptr->stripPointerCasts();
     int64_t EarlierStart = 0;
-    int64_t EarlierSize = int64_t(Loc.Size);
     GetPointerBaseWithConstantOffset(Ptr, EarlierStart, DL);
     OverlapIntervalsTy &IntervalMap = OI.second;
     Changed |=
         tryToShortenEnd(EarlierWrite, IntervalMap, EarlierStart, EarlierSize);
     if (IntervalMap.empty())
       continue;
     Changed |=
         tryToShortenBegin(EarlierWrite, IntervalMap, EarlierStart, EarlierSize);
while (InstDep.isDef() || InstDep.isClobber()) {
           InstDep = MD->getDependency(Inst);
           continue;
         } else if ((OR == OW_End && isShortenableAtTheEnd(DepWrite)) ||
                    ((OR == OW_Begin &&
                      isShortenableAtTheBeginning(DepWrite)))) {
           assert(!EnablePartialOverwriteTracking && "Do not expect to perform "
                                                     "when partial-overwrite "
                                                     "tracking is enabled");
-          int64_t EarlierSize = DepLoc.Size;
-          int64_t LaterSize = Loc.Size;
+          // The overwrite result is known, so these must be known, too.
+          int64_t EarlierSize = DepLoc.Size.getValue();
+          int64_t LaterSize = Loc.Size.getValue();
           bool IsOverwriteEnd = (OR == OW_End);
           MadeChange |= tryToShorten(DepWrite, DepWriteOffset, EarlierSize,
                                     InstWriteOffset, LaterSize, IsOverwriteEnd);
         } else if (EnablePartialStoreMerging &&
                    OR == OW_PartialEarlierWithFullLater) {
           auto *Earlier = dyn_cast<StoreInst>(DepWrite);
           auto *Later = dyn_cast<StoreInst>(Inst);
           if (Earlier && isa<ConstantInt>(Earlier->getValueOperand()) &&

test/Analysis/AliasSet/intrinsics.ll

 ; RUN: opt -basicaa -print-alias-sets -S -o - < %s 2>&1 | FileCheck %s
 
 ; CHECK: Alias sets for function 'test1':
 ; CHECK: Alias Set Tracker: 2 alias sets for 2 pointer values.
-; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %a, 1)
+; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %a, LocationSize::precise(1))
 ; CHECK-NOT: 1 Unknown instruction
-; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %b, 1)
+; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %b, LocationSize::precise(1))
 define void @test1(i32 %c) {
 entry:
   %a = alloca i8, align 1
   %b = alloca i8, align 1
   store i8 1, i8* %a, align 1
   %cond1 = icmp ne i32 %c, 0
   call void @llvm.assume(i1 %cond1)
   store i8 1, i8* %b, align 1
   ret void
 }
 
 declare void @llvm.assume(i1)

test/Analysis/AliasSet/memtransfer.ll

 ; RUN: opt -basicaa -print-alias-sets -S -o - < %s 2>&1 | FileCheck %s
 
 @s = global i8 1, align 1
 @d = global i8 2, align 1
 
 ; CHECK: Alias sets for function 'test1':
 ; CHECK: Alias Set Tracker: 3 alias sets for 4 pointer values.
-; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %a, 1)
+; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %a, LocationSize::precise(1))
 ; CHECK-NOT:    1 Unknown instructions
-; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 2] may alias, Mod/Ref   Pointers: (i8* %s, 1), (i8* %d, 1)
-; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %b, 1)
+; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 2] may alias, Mod/Ref   Pointers: (i8* %s, LocationSize::precise(1)), (i8* %d, LocationSize::precise(1))
+; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %b, LocationSize::precise(1))
 define void @test1(i8* %s, i8* %d) {
 entry:
   %a = alloca i8, align 1
   %b = alloca i8, align 1
   store i8 1, i8* %a, align 1
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %d, i8* %s, i64 1, i1 false)
   store i8 1, i8* %b, align 1
   ret void
 }
 
 ; CHECK: Alias sets for function 'test2':
 ; CHECK: Alias Set Tracker: 3 alias sets for 4 pointer values.
-; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %a, 1)
+; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %a, LocationSize::precise(1))
 ; CHECK-NOT:    1 Unknown instructions
-; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 2] may alias, Mod/Ref   [volatile] Pointers: (i8* %s, 1), (i8* %d, 1)
-; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %b, 1)
+; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 2] may alias, Mod/Ref   [volatile] Pointers: (i8* %s, LocationSize::precise(1)), (i8* %d, LocationSize::precise(1))
+; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %b, LocationSize::precise(1))
 define void @test2(i8* %s, i8* %d) {
 entry:
   %a = alloca i8, align 1
   %b = alloca i8, align 1
   store i8 1, i8* %a, align 1
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %d, i8* %s, i64 1, i1 true)
   store i8 1, i8* %b, align 1
   ret void
 }
 
 ; CHECK: Alias sets for function 'test3':
 ; CHECK: Alias Set Tracker: 3 alias sets for 4 pointer values.
-; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %a, 1)
+; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %a, LocationSize::precise(1))
 ; CHECK-NOT:    1 Unknown instructions
-; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 2] may alias, Mod/Ref   Pointers: (i8* %s, 1), (i8* %d, 1)
-; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %b, 1)
+; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 2] may alias, Mod/Ref   Pointers: (i8* %s, LocationSize::precise(1)), (i8* %d, LocationSize::precise(1))
+; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %b, LocationSize::precise(1))
 define void @test3(i8* %s, i8* %d) {
 entry:
   %a = alloca i8, align 1
   %b = alloca i8, align 1
   store i8 1, i8* %a, align 1
   call void @llvm.memmove.p0i8.p0i8.i64(i8* %d, i8* %s, i64 1, i1 false)
   store i8 1, i8* %b, align 1
   ret void
 }
 
 ; CHECK: Alias sets for function 'test4':
 ; CHECK: Alias Set Tracker: 3 alias sets for 4 pointer values.
-; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %a, 1)
+; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %a, LocationSize::precise(1))
 ; CHECK-NOT:    1 Unknown instructions
-; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 2] may alias, Mod/Ref   [volatile] Pointers: (i8* %s, 1), (i8* %d, 1)
-; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %b, 1)
+; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 2] may alias, Mod/Ref   [volatile] Pointers: (i8* %s, LocationSize::precise(1)), (i8* %d, LocationSize::precise(1))
+; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %b, LocationSize::precise(1))
 define void @test4(i8* %s, i8* %d) {
 entry:
   %a = alloca i8, align 1
   %b = alloca i8, align 1
   store i8 1, i8* %a, align 1
   call void @llvm.memmove.p0i8.p0i8.i64(i8* %d, i8* %s, i64 1, i1 true)
   store i8 1, i8* %b, align 1
   ret void
 }
 
 ; CHECK: Alias sets for function 'test5':
 ; CHECK: Alias Set Tracker: 2 alias sets for 2 pointer values.
-; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod/Ref   Pointers: (i8* %a, 1)
-; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %b, 1)
+; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod/Ref   Pointers: (i8* %a, LocationSize::precise(1))
+; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %b, LocationSize::precise(1))
 define void @test5() {
 entry:
   %a = alloca i8, align 1
   %b = alloca i8, align 1
   store i8 1, i8* %a, align 1
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %b, i8* %a, i64 1, i1 false)
   store i8 1, i8* %b, align 1
   ret void
 }
 
 ; CHECK: Alias sets for function 'test6':
 ; CHECK: Alias Set Tracker: 2 alias sets for 2 pointer values.
-; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod/Ref   Pointers: (i8* %a, 1)
-; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %b, 1)
+; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod/Ref   Pointers: (i8* %a, LocationSize::precise(1))
+; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %b, LocationSize::precise(1))
 define void @test6() {
 entry:
   %a = alloca i8, align 1
   %b = alloca i8, align 1
   store i8 1, i8* %a, align 1
   call void @llvm.memmove.p0i8.p0i8.i64(i8* %b, i8* %a, i64 1, i1 false)
   store i8 1, i8* %b, align 1
   ret void
 }
 
 ; CHECK: Alias sets for function 'test7':
 ; CHECK: Alias Set Tracker: 2 alias sets for 2 pointer values.
-; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod/Ref   Pointers: (i8* %a, 1)
-; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod/Ref   Pointers: (i8* %b, 1)
+; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod/Ref   Pointers: (i8* %a, LocationSize::precise(1))
+; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod/Ref   Pointers: (i8* %b, LocationSize::precise(1))
 define void @test7() {
 entry:
   %a = alloca i8, align 1
   %b = alloca i8, align 1
   store i8 1, i8* %a, align 1
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %b, i8* %a, i64 1, i1 false)
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %a, i8* %b, i64 1, i1 false)
   store i8 1, i8* %b, align 1
   ret void
 }
 
 declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture writeonly, i8* nocapture readonly, i64, i1)
 declare void @llvm.memmove.p0i8.p0i8.i64(i8* nocapture, i8* nocapture readonly, i64, i1)

test/Analysis/AliasSet/saturation.ll

 ; RUN: opt -basicaa -print-alias-sets -alias-set-saturation-threshold=2 -S -o - < %s 2>&1 | FileCheck %s --check-prefix=CHECK --check-prefix=NOSAT
 ; RUN: opt -basicaa -print-alias-sets -alias-set-saturation-threshold=1 -S -o - < %s 2>&1 | FileCheck %s --check-prefix=CHECK --check-prefix=SAT
 
 ; CHECK-LABEL: 'allmust'
-; CHECK: AliasSet[{{.*}}, 1] must alias, Mod Pointers: (i32* %a, 4)
-; CHECK: AliasSet[{{.*}}, 1] must alias, Mod Pointers: (i32* %b, 4)
-; CHECK: AliasSet[{{.*}}, 1] must alias, Mod Pointers: (i32* %c, 4)
-; CHECK: AliasSet[{{.*}}, 1] must alias, Mod Pointers: (i32* %d, 4)
+; CHECK: AliasSet[{{.*}}, 1] must alias, Mod Pointers: (i32* %a, LocationSize::precise(4))
+; CHECK: AliasSet[{{.*}}, 1] must alias, Mod Pointers: (i32* %b, LocationSize::precise(4))
+; CHECK: AliasSet[{{.*}}, 1] must alias, Mod Pointers: (i32* %c, LocationSize::precise(4))
+; CHECK: AliasSet[{{.*}}, 1] must alias, Mod Pointers: (i32* %d, LocationSize::precise(4))
 define void @allmust() {
   %a = alloca i32
   %b = alloca i32
   %c = alloca i32
   %d = alloca i32
   store i32 1, i32* %a
   store i32 2, i32* %b
   store i32 3, i32* %c
   store i32 4, i32* %d
   ret void
 }
 
 ; CHECK-LABEL :'mergemay'
-; NOSAT: AliasSet[{{.*}}, 2] may alias, Mod Pointers: (i32* %a, 4), (i32* %a1, 4)
-; NOSAT: AliasSet[{{.*}}, 1] must alias, Mod Pointers: (i32* %b, 4)
+; NOSAT: AliasSet[{{.*}}, 2] may alias, Mod Pointers: (i32* %a, LocationSize::precise(4)), (i32* %a1, LocationSize::precise(4))
+; NOSAT: AliasSet[{{.*}}, 1] must alias, Mod Pointers: (i32* %b, LocationSize::precise(4))
 ; SAT: AliasSet[{{.*}}, 2] may alias, Mod forwarding to 0x[[FWD:[0-9a-f]*]]
 ; SAT: AliasSet[{{.*}}, 1] must alias, Mod forwarding to 0x[[FWD]]
-; SAT: AliasSet[0x[[FWD]], 2] may alias, Mod/Ref Pointers: (i32* %a, 4), (i32* %a1, 4), (i32* %b, 4)
+; SAT: AliasSet[0x[[FWD]], 2] may alias, Mod/Ref Pointers: (i32* %a, LocationSize::precise(4)), (i32* %a1, LocationSize::precise(4)), (i32* %b, LocationSize::precise(4))
 define void @mergemay(i32 %k) {
   %a = alloca i32
   %b = alloca i32
   store i32 1, i32* %a
   store i32 2, i32* %b
   %a1 = getelementptr i32, i32 *%a, i32 %k
   store i32 2, i32* %a1  
   ret void
 }
 
 ; CHECK-LABEL: 'mergemust'
-; NOSAT: AliasSet[{{.*}}, 1] must alias, Mod Pointers: (i32* %a, 4)
-; NOSAT: AliasSet[{{.*}}, 1] must alias, Mod Pointers: (i32* %b, 4)
-; NOSAT: AliasSet[{{.*}}, 2] may alias,  Mod Pointers: (i32* %c, 4), (i32* %d, 4)
+; NOSAT: AliasSet[{{.*}}, 1] must alias, Mod Pointers: (i32* %a, LocationSize::precise(4))
+; NOSAT: AliasSet[{{.*}}, 1] must alias, Mod Pointers: (i32* %b, LocationSize::precise(4))
+; NOSAT: AliasSet[{{.*}}, 2] may alias,  Mod Pointers: (i32* %c, LocationSize::precise(4)), (i32* %d, LocationSize::precise(4))
 ; SAT: AliasSet[{{.*}}, 1] must alias, Mod forwarding to 0x[[FWD:[0-9a-f]*]]
 ; SAT: AliasSet[{{.*}}, 1] must alias, Mod forwarding to 0x[[FWD]]
 ; SAT: AliasSet[{{.*}}, 2] may alias,  Mod forwarding to 0x[[FWD]]
-; SAT: AliasSet[0x[[FWD]], 3] may alias, Mod/Ref Pointers: (i32* %a, 4), (i32* %b, 4), (i32* %c, 4), (i32* %d, 4)
+; SAT: AliasSet[0x[[FWD]], 3] may alias, Mod/Ref Pointers: (i32* %a, LocationSize::precise(4)), (i32* %b, LocationSize::precise(4)), (i32* %c, LocationSize::precise(4)), (i32* %d, LocationSize::precise(4))
 define void @mergemust(i32* %c, i32* %d) {
   %a = alloca i32
   %b = alloca i32
   store i32 1, i32* %a
   store i32 2, i32* %b
   store i32 3, i32* %c
   store i32 4, i32* %d
   ret void
 }

test/Transforms/LICM/pr36228.ll

+; RUN: opt -S -licm -o - %s | FileCheck %s
+;
+; Be sure that we don't hoist loads incorrectly if a loop has conditional UB.
+; See PR36228.
+
+declare void @check(i8)
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8*, i8*, i64, i32, i1)
+
+; CHECK-LABEL: define void @buggy
+define void @buggy(i8* %src, i1* %kOne) {
+entry:
+  %dst = alloca [1 x i8], align 1
+  %0 = getelementptr inbounds [1 x i8], [1 x i8]* %dst, i64 0, i64 0
+  store i8 42, i8* %0, align 1
+  %src16 = bitcast i8* %src to i16*
+  %srcval = load i16, i16* %src16
+  br label %while.cond
+
+while.cond:                                       ; preds = %if.end, %entry
+  %dp.0 = phi i8* [ %0, %entry ], [ %dp.1, %if.end ]
+  %1 = load volatile i1, i1* %kOne, align 4
+  br i1 %1, label %if.else, label %if.then
+
+if.then:                                          ; preds = %while.cond
+  store i8 9, i8* %dp.0, align 1
+  br label %if.end
+
+if.else:                                          ; preds = %while.cond
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dp.0, i8* %src, i64 2, i32 1, i1 false)
+  %dp.new = getelementptr inbounds i8, i8* %dp.0, i64 1
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  %dp.1 = phi i8* [ %dp.0, %if.then ], [ %dp.new, %if.else ]
+  ; CHECK: %2 = load i8, i8* %0
+  %2 = load i8, i8* %0, align 1
+  ; CHECK-NEXT: call void @check(i8 %2)
+  call void @check(i8 %2)
+  br label %while.cond
+}