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

74

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

78

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

74

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).

78

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

1716–1719

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

1716–1719

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

35

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

108

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

lib/Analysis/AliasSetTracker.cpp

631

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

lib/Analysis/BasicAliasAnalysis.cpp

1054

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

1122–1123

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

35

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.

108

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

lib/Analysis/AliasSetTracker.cpp

631

Added in the new patch; good call. :)

lib/Analysis/BasicAliasAnalysis.cpp

1054

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.

1122–1123

(Same function, so the above reply applies here)

[george.burgess.iv]

Rebase now that our LocationSize changes are in

lib/Analysis/BasicAliasAnalysis.cpp

1054

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)

1188

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

1114–1140

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

1114–1140

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

1114

This does not look NFC.

lib/Transforms/Scalar/DeadStoreElimination.cpp

342

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

98

(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

1114

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

34

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.

35

Looks like this update got lost?

JFYI, I consider clarity on this point essential.

lib/Analysis/BasicAliasAnalysis.cpp

1655–1658

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

1715–1716

Same testing comment here.

lib/Analysis/MemoryDependenceAnalysis.cpp

1138

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

35

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

lib/Analysis/BasicAliasAnalysis.cpp

1655–1658

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

1138

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

35

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

35

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

31–150

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

31–150

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

31–150

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/AliasAnalysis.h

public:
 
   /// The main low level interface to the alias analysis implementation.
   /// Returns an AliasResult indicating whether the two pointers are aliased to
   /// each other. This is the interface that must be implemented by specific
   /// alias analysis implementations.
   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB);
 
   /// A convenience wrapper around the primary \c alias interface.
-  AliasResult alias(const Value *V1, uint64_t V1Size, const Value *V2,
-                    uint64_t V2Size) {
+  AliasResult alias(const Value *V1, LocationSize V1Size, const Value *V2,
+                    LocationSize V2Size) {
     return alias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size));
   }
 
   /// A convenience wrapper around the primary \c alias interface.
   AliasResult alias(const Value *V1, const Value *V2) {
     return alias(V1, MemoryLocation::UnknownSize, V2,
                  MemoryLocation::UnknownSize);
   }
 
   /// A trivial helper function to check to see if the specified pointers are
   /// no-alias.
   bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
     return alias(LocA, LocB) == NoAlias;
   }
 
   /// A convenience wrapper around the \c isNoAlias helper interface.
-  bool isNoAlias(const Value *V1, uint64_t V1Size, const Value *V2,
-                 uint64_t V2Size) {
+  bool isNoAlias(const Value *V1, LocationSize V1Size, const Value *V2,
+                 LocationSize V2Size) {
     return isNoAlias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size));
   }
 
   /// A convenience wrapper around the \c isNoAlias helper interface.
   bool isNoAlias(const Value *V1, const Value *V2) {
     return isNoAlias(MemoryLocation(V1), MemoryLocation(V2));
   }
 
public:
   }
 
   /// getModRefInfo (for call sites) - Return information about whether
   /// a particular call site modifies or reads the specified memory location.
   ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc);
 
   /// getModRefInfo (for call sites) - A convenience wrapper.
   ModRefInfo getModRefInfo(ImmutableCallSite CS, const Value *P,
-                           uint64_t Size) {
+                           LocationSize Size) {
     return getModRefInfo(CS, MemoryLocation(P, Size));
   }
 
   /// getModRefInfo (for calls) - Return information about whether
   /// a particular call modifies or reads the specified memory location.
   ModRefInfo getModRefInfo(const CallInst *C, const MemoryLocation &Loc) {
     return getModRefInfo(ImmutableCallSite(C), Loc);
   }
 
   /// getModRefInfo (for calls) - A convenience wrapper.
-  ModRefInfo getModRefInfo(const CallInst *C, const Value *P, uint64_t Size) {
+  ModRefInfo getModRefInfo(const CallInst *C, const Value *P,
+                           LocationSize Size) {
     return getModRefInfo(C, MemoryLocation(P, Size));
   }
 
   /// getModRefInfo (for invokes) - Return information about whether
   /// a particular invoke modifies or reads the specified memory location.
   ModRefInfo getModRefInfo(const InvokeInst *I, const MemoryLocation &Loc) {
     return getModRefInfo(ImmutableCallSite(I), Loc);
   }
 
   /// getModRefInfo (for invokes) - A convenience wrapper.
-  ModRefInfo getModRefInfo(const InvokeInst *I, const Value *P, uint64_t Size) {
+  ModRefInfo getModRefInfo(const InvokeInst *I, const Value *P,
+                           LocationSize Size) {
     return getModRefInfo(I, MemoryLocation(P, Size));
   }
 
   /// getModRefInfo (for loads) - Return information about whether
   /// a particular load modifies or reads the specified memory location.
   ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc);
 
   /// getModRefInfo (for loads) - A convenience wrapper.
-  ModRefInfo getModRefInfo(const LoadInst *L, const Value *P, uint64_t Size) {
+  ModRefInfo getModRefInfo(const LoadInst *L, const Value *P,
+                           LocationSize Size) {
     return getModRefInfo(L, MemoryLocation(P, Size));
   }
 
   /// getModRefInfo (for stores) - Return information about whether
   /// a particular store modifies or reads the specified memory location.
   ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc);
 
   /// getModRefInfo (for stores) - A convenience wrapper.
-  ModRefInfo getModRefInfo(const StoreInst *S, const Value *P, uint64_t Size) {
+  ModRefInfo getModRefInfo(const StoreInst *S, const Value *P,
+                           LocationSize Size) {
     return getModRefInfo(S, MemoryLocation(P, Size));
   }
 
   /// getModRefInfo (for fences) - Return information about whether
   /// a particular store modifies or reads the specified memory location.
   ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc);
 
   /// getModRefInfo (for fences) - A convenience wrapper.
-  ModRefInfo getModRefInfo(const FenceInst *S, const Value *P, uint64_t Size) {
+  ModRefInfo getModRefInfo(const FenceInst *S, const Value *P,
+                           LocationSize Size) {
     return getModRefInfo(S, MemoryLocation(P, Size));
   }
 
   /// getModRefInfo (for cmpxchges) - Return information about whether
   /// a particular cmpxchg modifies or reads the specified memory location.
   ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX,
                            const MemoryLocation &Loc);
 
ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const Value *P,
     return getModRefInfo(RMW, MemoryLocation(P, Size));
   }
 
   /// getModRefInfo (for va_args) - Return information about whether
   /// a particular va_arg modifies or reads the specified memory location.
   ModRefInfo getModRefInfo(const VAArgInst *I, const MemoryLocation &Loc);
 
   /// getModRefInfo (for va_args) - A convenience wrapper.
-  ModRefInfo getModRefInfo(const VAArgInst *I, const Value *P, uint64_t Size) {
+  ModRefInfo getModRefInfo(const VAArgInst *I, const Value *P,
+                           LocationSize Size) {
     return getModRefInfo(I, MemoryLocation(P, Size));
   }
 
   /// getModRefInfo (for catchpads) - Return information about whether
   /// a particular catchpad modifies or reads the specified memory location.
   ModRefInfo getModRefInfo(const CatchPadInst *I, const MemoryLocation &Loc);
 
   /// getModRefInfo (for catchpads) - A convenience wrapper.
   ModRefInfo getModRefInfo(const CatchPadInst *I, const Value *P,
-                           uint64_t Size) {
+                           LocationSize Size) {
     return getModRefInfo(I, MemoryLocation(P, Size));
   }
 
   /// getModRefInfo (for catchrets) - Return information about whether
   /// a particular catchret modifies or reads the specified memory location.
   ModRefInfo getModRefInfo(const CatchReturnInst *I, const MemoryLocation &Loc);
 
   /// getModRefInfo (for catchrets) - A convenience wrapper.
   ModRefInfo getModRefInfo(const CatchReturnInst *I, const Value *P,
-                           uint64_t Size) {
+                           LocationSize Size) {
     return getModRefInfo(I, MemoryLocation(P, Size));
   }
 
   /// Check whether or not an instruction may read or write the optionally
   /// specified memory location.
   ///
   ///
   /// An instruction that doesn't read or write memory may be trivially LICM'd
case Instruction::CatchRet:
       return getModRefInfo((const CatchReturnInst *)I, Loc);
     default:
       return ModRefInfo::NoModRef;
     }
   }
 
   /// A convenience wrapper for constructing the memory location.
   ModRefInfo getModRefInfo(const Instruction *I, const Value *P,
-                           uint64_t Size) {
+                           LocationSize Size) {
     return getModRefInfo(I, MemoryLocation(P, Size));
   }
 
   /// Return information about whether a call and an instruction may refer to
   /// the same memory locations.
   ModRefInfo getModRefInfo(Instruction *I, ImmutableCallSite Call);
 
   /// Return information about whether two call sites may refer to the same set
   /// of memory locations. See the AA documentation for details:
   ///   http://llvm.org/docs/AliasAnalysis.html#ModRefInfo
   ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2);
 
   /// \brief Return information about whether a particular call site modifies
   /// or reads the specified memory location \p MemLoc before instruction \p I
   /// in a BasicBlock. An ordered basic block \p OBB can be used to speed up
   /// instruction ordering queries inside the BasicBlock containing \p I.
   /// Early exits in callCapturesBefore may lead to ModRefInfo::Must not being
   /// set.
   ModRefInfo callCapturesBefore(const Instruction *I,
                                 const MemoryLocation &MemLoc, DominatorTree *DT,
                                 OrderedBasicBlock *OBB = nullptr);
 
   /// \brief A convenience wrapper to synthesize a memory location.
   ModRefInfo callCapturesBefore(const Instruction *I, const Value *P,
-                                uint64_t Size, DominatorTree *DT,
+                                LocationSize Size, DominatorTree *DT,
                                 OrderedBasicBlock *OBB = nullptr) {
     return callCapturesBefore(I, MemoryLocation(P, Size), DT, OBB);
   }
 
   /// @}
   //===--------------------------------------------------------------------===//
   /// \name Higher level methods for querying mod/ref information.
   /// @{
 
   /// Check if it is possible for execution of the specified basic block to
   /// modify the location Loc.
   bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc);
 
   /// A convenience wrapper synthesizing a memory location.
   bool canBasicBlockModify(const BasicBlock &BB, const Value *P,
-                           uint64_t Size) {
+                           LocationSize Size) {
     return canBasicBlockModify(BB, MemoryLocation(P, Size));
   }
 
   /// Check if it is possible for the execution of the specified instructions
   /// to mod\ref (according to the mode) the location Loc.
   ///
   /// The instructions to consider are all of the instructions in the range of
   /// [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block.
   bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2,
                                  const MemoryLocation &Loc,
                                  const ModRefInfo Mode);
 
   /// A convenience wrapper synthesizing a memory location.
   bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2,
-                                 const Value *Ptr, uint64_t Size,
+                                 const Value *Ptr, LocationSize Size,
                                  const ModRefInfo Mode) {
     return canInstructionRangeModRef(I1, I2, MemoryLocation(Ptr, Size), Mode);
   }
 
 private:
   class Concept;
 
   template <typename T> class Model;

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;
-    uint64_t Size = 0;
+    LocationSize Size = 0;
     AAMDNodes AAInfo;
 
   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(uint64_t NewSize, const AAMDNodes &NewAAInfo) {
+    bool updateSizeAndAAInfo(LocationSize NewSize, const AAMDNodes &NewAAInfo) {
       bool SizeChanged = false;
-      if (NewSize > Size) {
-        Size = NewSize;
-        SizeChanged = true;
+      if (NewSize != Size && Size.hasValue()) {
+        LocationSize OldSize = Size;
+        // Size.isZero() means that NewSize is the first meaningful Size value
+        // we're getting. Don't treat it as an upper-bound.
+        Size = Size.isZero() ? NewSize : Size.combineWith(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;
     }
 
-    uint64_t getSize() const { return Size; }
+    LocationSize getSize() const { 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();
       return AAInfo;
public:
 
     value_type &operator*() const {
       assert(CurNode && "Dereferencing AliasSet.end()!");
       return *CurNode;
     }
     value_type *operator->() const { return &operator*(); }
 
     Value *getPointer() const { return CurNode->getValue(); }
-    uint64_t getSize() const { return CurNode->getSize(); }
+    LocationSize getSize() const { return CurNode->getSize(); }
     AAMDNodes getAAInfo() const { return CurNode->getAAInfo(); }
 
     iterator& operator++() {                // Preincrement
       assert(CurNode && "Advancing past AliasSet.end()!");
       CurNode = CurNode->getNext();
       return *this;
     }
     iterator operator++(int) { // Postincrement
if (Dest != Forward) {
       Forward->dropRef(AST);
       Forward = Dest;
     }
     return Dest;
   }
 
   void removeFromTracker(AliasSetTracker &AST);
 
-  void addPointer(AliasSetTracker &AST, PointerRec &Entry, uint64_t Size,
+  void addPointer(AliasSetTracker &AST, PointerRec &Entry, LocationSize Size,
                   const AAMDNodes &AAInfo,
                   bool KnownMustAlias = false);
   void addUnknownInst(Instruction *I, AliasAnalysis &AA);
 
   void removeUnknownInst(AliasSetTracker &AST, Instruction *I) {
     bool WasEmpty = UnknownInsts.empty();
     for (size_t i = 0, e = UnknownInsts.size(); i != e; ++i)
       if (UnknownInsts[i] == I) {
         UnknownInsts[i] = UnknownInsts.back();
         UnknownInsts.pop_back();
         --i; --e;  // Revisit the moved entry.
       }
     if (!WasEmpty && UnknownInsts.empty())
       dropRef(AST);
   }
 
   void setVolatile() { Volatile = true; }
 
 public:
   /// Return true if the specified pointer "may" (or must) alias one of the
   /// members in the set.
-  bool aliasesPointer(const Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo,
-                      AliasAnalysis &AA) const;
+  bool aliasesPointer(const Value *Ptr, LocationSize Size,
+                      const AAMDNodes &AAInfo, AliasAnalysis &AA) const;
   bool aliasesUnknownInst(const Instruction *Inst, AliasAnalysis &AA) const;
 };
 
 inline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) {
   AS.print(OS);
   return OS;
 }
 
public:
   ///   1. If the instruction doesn't alias any other sets, create a new set.
   ///   2. If the instruction aliases exactly one set, add it to the set
   ///   3. If the instruction aliases multiple sets, merge the sets, and add
   ///      the instruction to the result.
   ///
   /// These methods return true if inserting the instruction resulted in the
   /// addition of a new alias set (i.e., the pointer did not alias anything).
   ///
-  void add(Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo); // Add a loc.
+  void add(Value *Ptr, LocationSize Size, const AAMDNodes &AAInfo); // Add a loc
   void add(LoadInst *LI);
   void add(StoreInst *SI);
   void add(VAArgInst *VAAI);
   void add(MemSetInst *MSI);
   void add(MemTransferInst *MTI);
   void add(Instruction *I);       // Dispatch to one of the other add methods...
   void add(BasicBlock &BB);       // Add all instructions in basic block
   void add(const AliasSetTracker &AST); // Add alias relations from another AST
   void addUnknown(Instruction *I);
 
   void clear();
 
   /// Return the alias sets that are active.
   const ilist<AliasSet> &getAliasSets() const { return AliasSets; }
 
   /// Return the alias set that the specified pointer lives in. If the New
   /// argument is non-null, this method sets the value to true if a new alias
   /// set is created to contain the pointer (because the pointer didn't alias
   /// anything).
-  AliasSet &getAliasSetForPointer(Value *P, uint64_t Size,
+  AliasSet &getAliasSetForPointer(Value *P, LocationSize Size,
                                   const AAMDNodes &AAInfo);
 
   /// Return the alias set containing the location specified if one exists,
   /// otherwise return null.
-  AliasSet *getAliasSetForPointerIfExists(const Value *P, uint64_t Size,
+  AliasSet *getAliasSetForPointerIfExists(const Value *P, LocationSize Size,
                                           const AAMDNodes &AAInfo) {
     return mergeAliasSetsForPointer(P, Size, AAInfo);
   }
 
   /// Return true if the specified instruction "may" (or must) alias one of the
   /// members in any of the sets.
   bool containsUnknown(const Instruction *I) const;
 
private:
   /// pointer if it doesn't already exist.
   AliasSet::PointerRec &getEntryFor(Value *V) {
     AliasSet::PointerRec *&Entry = PointerMap[ASTCallbackVH(V, this)];
     if (!Entry)
       Entry = new AliasSet::PointerRec(V);
     return *Entry;
   }
 
-  AliasSet &addPointer(Value *P, uint64_t Size, const AAMDNodes &AAInfo,
+  AliasSet &addPointer(Value *P, LocationSize Size, const AAMDNodes &AAInfo,
                        AliasSet::AccessLattice E);
-  AliasSet *mergeAliasSetsForPointer(const Value *Ptr, uint64_t Size,
+  AliasSet *mergeAliasSetsForPointer(const Value *Ptr, LocationSize Size,
                                      const AAMDNodes &AAInfo);
 
   /// Merge all alias sets into a single set that is considered to alias any
   /// pointer.
   AliasSet &mergeAllAliasSets();
 
   AliasSet *findAliasSetForUnknownInst(Instruction *Inst);
 };

include/llvm/Analysis/BasicAliasAnalysis.h

GetLinearExpression(const Value *V, APInt &Scale, APInt &Offset,
                       const DataLayout &DL, unsigned Depth, AssumptionCache *AC,
                       DominatorTree *DT, bool &NSW, bool &NUW);
 
   static bool DecomposeGEPExpression(const Value *V, DecomposedGEP &Decomposed,
       const DataLayout &DL, AssumptionCache *AC, DominatorTree *DT);
 
   static bool isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp,
       const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompObject,
-      uint64_t ObjectAccessSize);
+      LocationSize ObjectAccessSize);
 
   /// \brief A Heuristic for aliasGEP that searches for a constant offset
   /// between the variables.
   ///
   /// GetLinearExpression has some limitations, as generally zext(%x + 1)
   /// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression
   /// will therefore conservatively refuse to decompose these expressions.
   /// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if
   /// the addition overflows.
   bool
   constantOffsetHeuristic(const SmallVectorImpl<VariableGEPIndex> &VarIndices,
-                          uint64_t V1Size, uint64_t V2Size, int64_t BaseOffset,
-                          AssumptionCache *AC, DominatorTree *DT);
+                          LocationSize V1Size, LocationSize V2Size,
+                          int64_t BaseOffset, AssumptionCache *AC,
+                          DominatorTree *DT);
 
   bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2);
 
   void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest,
                           const SmallVectorImpl<VariableGEPIndex> &Src);
 
-  AliasResult aliasGEP(const GEPOperator *V1, uint64_t V1Size,
+  AliasResult aliasGEP(const GEPOperator *V1, LocationSize V1Size,
                        const AAMDNodes &V1AAInfo, const Value *V2,
-                       uint64_t V2Size, const AAMDNodes &V2AAInfo,
+                       LocationSize V2Size, const AAMDNodes &V2AAInfo,
                        const Value *UnderlyingV1, const Value *UnderlyingV2);
 
-  AliasResult aliasPHI(const PHINode *PN, uint64_t PNSize,
+  AliasResult aliasPHI(const PHINode *PN, LocationSize PNSize,
                        const AAMDNodes &PNAAInfo, const Value *V2,
-                       uint64_t V2Size, const AAMDNodes &V2AAInfo,
+                       LocationSize V2Size, const AAMDNodes &V2AAInfo,
                        const Value *UnderV2);
 
-  AliasResult aliasSelect(const SelectInst *SI, uint64_t SISize,
+  AliasResult aliasSelect(const SelectInst *SI, LocationSize SISize,
                           const AAMDNodes &SIAAInfo, const Value *V2,
-                          uint64_t V2Size, const AAMDNodes &V2AAInfo,
+                          LocationSize V2Size, const AAMDNodes &V2AAInfo,
                           const Value *UnderV2);
 
-  AliasResult aliasCheck(const Value *V1, uint64_t V1Size, AAMDNodes V1AATag,
-                         const Value *V2, uint64_t V2Size, AAMDNodes V2AATag,
+  AliasResult aliasCheck(const Value *V1, LocationSize V1Size,
+                         AAMDNodes V1AATag, const Value *V2,
+                         LocationSize V2Size, AAMDNodes V2AATag,
                          const Value *O1 = nullptr, const Value *O2 = nullptr);
 };
 
 /// Analysis pass providing a never-invalidated alias analysis result.
 class BasicAA : public AnalysisInfoMixin<BasicAA> {
   friend AnalysisInfoMixin<BasicAA>;
 
   static AnalysisKey Key;

include/llvm/Analysis/MemoryDependenceAnalysis.h

private:
   struct NonLocalPointerInfo {
     /// The pair of the block and the skip-first-block flag.
     BBSkipFirstBlockPair Pair;
     /// The results of the query for each relevant block.
     NonLocalDepInfo NonLocalDeps;
     /// The maximum size of the dereferences of the pointer.
     ///
     /// May be UnknownSize if the sizes are unknown.
-    uint64_t Size = MemoryLocation::UnknownSize;
+    LocationSize Size = LocationSize::unknown();
     /// The AA tags associated with dereferences of the pointer.
     ///
     /// The members may be null if there are no tags or conflicting tags.
     AAMDNodes AATags;
 
     NonLocalPointerInfo() = default;
   };
 

include/llvm/Analysis/MemoryLocation.h

 
 namespace llvm {
 
 class LoadInst;
 class StoreInst;
 class MemTransferInst;
 class MemIntrinsic;
 class TargetLibraryInfo;
 
+// Represents the size of a MemoryLocation. Logically, it's an
+// 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);
+  }
+
+  // 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;
+  }
+
+  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);
+  }
+
+  // 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
+
+  // Only public so we can use these in our DenseMapInfo specialization
+  static LocationSize mapTombstone() { return LocationSize(MapTombstone); }
+  static LocationSize mapEmpty() { return LocationSize(MapEmpty); }
+
+  // Returns an opaque value that represents this LocationSize.
+  uint64_t toRaw() const { return Value; }
+};
+
 /// 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.
 ///
 /// The primary user of this interface is LLVM's Alias Analysis, but other
 /// memory analyses such as MemoryDependence can use it as well.
public:
 
   /// The maximum size of the location, in address-units, or
   /// UnknownSize if the size is not known.
   ///
   /// Note that an unknown size does not mean the pointer aliases the entire
   /// virtual address space, because there are restrictions on stepping out of
   /// one object and into another. See
   /// http://llvm.org/docs/LangRef.html#pointeraliasing
-  uint64_t Size;
+  LocationSize Size;
 
   /// The metadata nodes which describes the aliasing of the location (each
   /// member is null if that kind of information is unavailable).
   AAMDNodes AATags;
 
   /// Return a location with information about the memory reference by the given
   /// instruction.
   static MemoryLocation get(const LoadInst *LI);
public:
   /// transfer.
   static MemoryLocation getForDest(const MemIntrinsic *MI);
 
   /// Return a location representing a particular argument of a call.
   static MemoryLocation getForArgument(ImmutableCallSite CS, unsigned ArgIdx,
                                        const TargetLibraryInfo &TLI);
 
   explicit MemoryLocation(const Value *Ptr = nullptr,
-                          uint64_t Size = UnknownSize,
+                          LocationSize Size = LocationSize::unknown(),
                           const AAMDNodes &AATags = AAMDNodes())
       : Ptr(Ptr), Size(Size), AATags(AATags) {}
 
   MemoryLocation getWithNewPtr(const Value *NewPtr) const {
     MemoryLocation Copy(*this);
     Copy.Ptr = NewPtr;
     return Copy;
   }
 
-  MemoryLocation getWithNewSize(uint64_t NewSize) const {
+  MemoryLocation getWithNewSize(LocationSize NewSize) const {
     MemoryLocation Copy(*this);
     Copy.Size = NewSize;
     return Copy;
   }
 
   MemoryLocation getWithoutAATags() const {
     MemoryLocation Copy(*this);
     Copy.AATags = AAMDNodes();
     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<uint64_t>::getHashValue(Val.Size) ^
+           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/AliasSetTracker.cpp

 }
 
 void AliasSet::removeFromTracker(AliasSetTracker &AST) {
   assert(RefCount == 0 && "Cannot remove non-dead alias set from tracker!");
   AST.removeAliasSet(this);
 }
 
 void AliasSet::addPointer(AliasSetTracker &AST, PointerRec &Entry,
-                          uint64_t Size, const AAMDNodes &AAInfo,
+                          LocationSize Size, const AAMDNodes &AAInfo,
                           bool KnownMustAlias) {
   assert(!Entry.hasAliasSet() && "Entry already in set!");
 
   // Check to see if we have to downgrade to _may_ alias.
   if (isMustAlias() && !KnownMustAlias)
     if (PointerRec *P = getSomePointer()) {
       AliasAnalysis &AA = AST.getAliasAnalysis();
       AliasResult Result =
void AliasSet::addUnknownInst(Instruction *I, AliasAnalysis &AA) {
   // FIXME: This should use mod/ref information to make this not suck so bad
   Alias = SetMayAlias;
   Access = ModRefAccess;
 }
 
 /// aliasesPointer - Return true if the specified pointer "may" (or must)
 /// alias one of the members in the set.
 ///
-bool AliasSet::aliasesPointer(const Value *Ptr, uint64_t Size,
+bool AliasSet::aliasesPointer(const Value *Ptr, LocationSize Size,
                               const AAMDNodes &AAInfo,
                               AliasAnalysis &AA) const {
   if (AliasAny)
     return true;
 
   if (Alias == SetMustAlias) {
     assert(UnknownInsts.empty() && "Illegal must alias set!");
 
void AliasSetTracker::clear() {
   AliasSets.clear();
 }
 
 
 /// mergeAliasSetsForPointer - Given a pointer, merge all alias sets that may
 /// alias the pointer. Return the unified set, or nullptr if no set that aliases
 /// the pointer was found.
 AliasSet *AliasSetTracker::mergeAliasSetsForPointer(const Value *Ptr,
-                                                    uint64_t Size,
+                                                    LocationSize Size,
                                                     const AAMDNodes &AAInfo) {
   AliasSet *FoundSet = nullptr;
   for (iterator I = begin(), E = end(); I != E;) {
     iterator Cur = I++;
     if (Cur->Forward || !Cur->aliasesPointer(Ptr, Size, AAInfo, AA)) continue;
     
     if (!FoundSet) {      // If this is the first alias set ptr can go into.
       FoundSet = &*Cur;   // Remember it.
for (iterator I = begin(), E = end(); I != E;) {
     else if (!Cur->Forward)   // Otherwise, we must merge the sets.
       FoundSet->mergeSetIn(*Cur, *this);     // Merge in contents.
   }
   return FoundSet;
 }
 
 /// getAliasSetForPointer - Return the alias set that the specified pointer
 /// lives in.
-AliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer, uint64_t Size,
+AliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer,
+                                                 LocationSize Size,
                                                  const AAMDNodes &AAInfo) {
   AliasSet::PointerRec &Entry = getEntryFor(Pointer);
 
   if (AliasAnyAS) {
     // At this point, the AST is saturated, so we only have one active alias
     // set. That means we already know which alias set we want to return, and
     // just need to add the pointer to that set to keep the data structure
     // consistent.
AliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer,
   }
   
   // Otherwise create a new alias set to hold the loaded pointer.
   AliasSets.push_back(new AliasSet());
   AliasSets.back().addPointer(*this, Entry, Size, AAInfo);
   return AliasSets.back();
 }
 
-void AliasSetTracker::add(Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo) {
+void AliasSetTracker::add(Value *Ptr, LocationSize Size,
+                          const AAMDNodes &AAInfo) {
   addPointer(Ptr, Size, AAInfo, AliasSet::NoAccess);
 }
 
 void AliasSetTracker::add(LoadInst *LI) {
   if (isStrongerThanMonotonic(LI->getOrdering())) return addUnknown(LI);
 
   AAMDNodes AAInfo;
   LI->getAAMetadata(AAInfo);
for (auto Cur : ASVector) {
 
     // Otherwise, perform the actual merge.
     AliasAnyAS->mergeSetIn(*Cur, *this);
   }
 
   return *AliasAnyAS;
 }
 
-AliasSet &AliasSetTracker::addPointer(Value *P, uint64_t Size,
+AliasSet &AliasSetTracker::addPointer(Value *P, LocationSize Size,
                                       const AAMDNodes &AAInfo,
                                       AliasSet::AccessLattice E) {
   AliasSet &AS = getAliasSetForPointer(P, Size, AAInfo);
   AS.Access |= E;
 
   if (!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold)) {
     // The AST is now saturated. From here on, we conservatively consider all
     // pointers to alias each-other.
void AliasSet::print(raw_ostream &OS) const {
   if (Forward)
     OS << " forwarding to " << (void*)Forward;
 
   if (!empty()) {
     OS << "Pointers: ";
     for (iterator I = begin(), E = end(); I != E; ++I) {
       if (I != begin()) OS << ", ";
       I.getPointer()->printAsOperand(OS << "(");
-      OS << ", " << I.getSize() << ")";
+      OS << ", " << I.getSize().toRaw() << ")";
     }
   }
   if (!UnknownInsts.empty()) {
     OS << "\n    " << UnknownInsts.size() << " Unknown instructions: ";
     for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
       if (i) OS << ", ";
       if (auto *I = getUnknownInst(i))
         I->printAsOperand(OS);

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,
-                                            uint64_t V1Size,
+                                            LocationSize V1Size,
                                             const GEPOperator *GEP2,
-                                            uint64_t V2Size,
+                                            LocationSize V2Size,
                                             const DataLayout &DL) {
   assert(GEP1->getPointerOperand()->stripPointerCastsAndBarriers() ==
              GEP2->getPointerOperand()->stripPointerCastsAndBarriers() &&
          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.
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)
+    if (V1Size.getValue() != ElementSize || V2Size.getValue() != 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))
+  if (EltsDontOverlap(V1Off, V1Size.getValue(), V2Off, V2Size.getValue()) ||
+      EltsDontOverlap(V2Off, V2Size.getValue(), V1Off, V1Size.getValue()))
     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).

 //  %f1 = getelementptr inbounds %struct, %struct.foo* %random, i32 0, i32 1
 //
 // 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, 
-      uint64_t ObjectAccessSize) {
+      const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompObject,
+      LocationSize ObjectAccessSize) {
   // If the object access size is unknown, or the GEP isn't inbounds, bail.
   if (ObjectAccessSize == MemoryLocation::UnknownSize || !GEPOp->isInBounds())
     return false;
 
   // 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're in
   // a bit more trouble: we can't count on the constant offsets that come
   // from non-struct sources, since these can be "rewound" by a negative
   // variable offset. So use only offsets that came from structs.
   int64_t GEPBaseOffset = DecompGEP.StructOffset;
   if (DecompGEP.VarIndices.empty())
     GEPBaseOffset += DecompGEP.OtherOffset;
 
-  return (GEPBaseOffset >= ObjectBaseOffset + (int64_t)ObjectAccessSize);
+  return GEPBaseOffset >=
+         ObjectBaseOffset + (int64_t)ObjectAccessSize.getValue();
 }
 
 /// 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, uint64_t V1Size,
-                                    const AAMDNodes &V1AAInfo, const Value *V2,
-                                    uint64_t V2Size, const AAMDNodes &V2AAInfo,
-                                    const Value *UnderlyingV1,
-                                    const Value *UnderlyingV2) {
+AliasResult
+BasicAAResult::aliasGEP(const GEPOperator *GEP1, LocationSize V1Size,
+                        LocationSize V2Size, const AAMDNodes &V2AAInfo,
+                        const Value *UnderlyingV1, const Value *UnderlyingV2) {
   DecomposedGEP DecompGEP1, DecompGEP2;
   bool GEP1MaxLookupReached =
     DecomposeGEPExpression(GEP1, DecompGEP1, DL, &AC, DT);
   bool GEP2MaxLookupReached =
     DecomposeGEPExpression(V2, DecompGEP2, DL, &AC, DT);
 
   int64_t GEP1BaseOffset = DecompGEP1.StructOffset + DecompGEP1.OtherOffset;
   int64_t GEP2BaseOffset = DecompGEP2.StructOffset + DecompGEP2.OtherOffset;
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 ((A == PartialAlias && B == MustAlias) ||
       (B == PartialAlias && A == MustAlias))
     return PartialAlias;
   // Otherwise, we don't know anything.
   return MayAlias;
 }
 
 /// Provides a bunch of ad-hoc rules to disambiguate a Select instruction
 /// against another.
-AliasResult BasicAAResult::aliasSelect(const SelectInst *SI, uint64_t SISize,
+AliasResult BasicAAResult::aliasSelect(const SelectInst *SI,
+                                       LocationSize SISize,
                                        const AAMDNodes &SIAAInfo,
-                                       const Value *V2, uint64_t V2Size,
+                                       const Value *V2, LocationSize V2Size,
                                        const AAMDNodes &V2AAInfo,
                                        const Value *UnderV2) {
   // If the values are Selects with the same condition, we can do a more precise
   // check: just check for aliases between the values on corresponding arms.
   if (const SelectInst *SI2 = dyn_cast<SelectInst>(V2))
     if (SI->getCondition() == SI2->getCondition()) {
       AliasResult Alias = aliasCheck(SI->getTrueValue(), SISize, SIAAInfo,
                                      SI2->getTrueValue(), V2Size, V2AAInfo);
AliasResult BasicAAResult::aliasSelect(const SelectInst *SI,
   AliasResult ThisAlias =
       aliasCheck(V2, V2Size, V2AAInfo, SI->getFalseValue(), SISize, SIAAInfo,
                  UnderV2);
   return MergeAliasResults(ThisAlias, Alias);
 }
 
 /// Provide a bunch of ad-hoc rules to disambiguate a PHI instruction against
 /// another.
-AliasResult BasicAAResult::aliasPHI(const PHINode *PN, uint64_t PNSize,
+AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize,
                                     const AAMDNodes &PNAAInfo, const Value *V2,
-                                    uint64_t V2Size, const AAMDNodes &V2AAInfo,
+                                    LocationSize V2Size,
+                                    const AAMDNodes &V2AAInfo,
                                     const Value *UnderV2) {
   // Track phi nodes we have visited. We use this information when we determine
   // value equivalence.
   VisitedPhiBBs.insert(PN->getParent());
 
   // If the values are PHIs in the same block, we can do a more precise
   // as well as efficient check: just check for aliases between the values
   // on corresponding edges.
if (Alias == MayAlias)
       break;
   }
 
   return Alias;
 }
 
 /// Provides a bunch of ad-hoc rules to disambiguate in common cases, such as
 /// array references.
-AliasResult BasicAAResult::aliasCheck(const Value *V1, uint64_t V1Size,
+AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size,
                                       AAMDNodes V1AAInfo, const Value *V2,
-                                      uint64_t V2Size, AAMDNodes V2AAInfo, 
+                                      LocationSize V2Size, AAMDNodes V2AAInfo,
                                       const Value *O1, const Value *O2) {
   // If either of the memory references is empty, it doesn't matter what the
   // pointer values are.
   if (V1Size == 0 || V2Size == 0)
     return NoAlias;
 
   // Strip off any casts if they exist.
   V1 = V1->stripPointerCastsAndBarriers();
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 != MemoryLocation::UnknownSize && V1Size.isPrecise() &&
+       isObjectSmallerThan(O2, V1Size.getValue(), DL, TLI)) ||
+      (V2Size != MemoryLocation::UnknownSize && 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 != MemoryLocation::UnknownSize && V1Size.isPrecise() &&
+        V2Size != MemoryLocation::UnknownSize && 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, uint64_t V1Size,
-    uint64_t V2Size, int64_t BaseOffset, AssumptionCache *AC,
+    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)
     return false;
 
   const VariableGEPIndex &Var0 = VarIndices[0], &Var1 = VarIndices[1];
 
   if (Var0.ZExtBits != Var1.ZExtBits || Var0.SExtBits != Var1.SExtBits ||
bool BasicAAResult::constantOffsetHeuristic(
   APInt MinDiff = V0Offset - V1Offset, Wrapped = -MinDiff;
   MinDiff = APIntOps::umin(MinDiff, Wrapped);
   uint64_t MinDiffBytes = MinDiff.getZExtValue() * std::abs(Var0.Scale);
 
   // We can't definitely say whether GEP1 is before or after V2 due to wrapping
   // arithmetic (i.e. for some values of GEP1 and V2 GEP1 < V2, and for other
   // values GEP1 > V2). We'll therefore only declare NoAlias if both V1Size and
   // V2Size can fit in the MinDiffBytes gap.
-  return V1Size + std::abs(BaseOffset) <= MinDiffBytes &&
-         V2Size + std::abs(BaseOffset) <= MinDiffBytes;
+  return V1Size.getValue() + std::abs(BaseOffset) <= MinDiffBytes &&
+         V2Size.getValue() + std::abs(BaseOffset) <= MinDiffBytes;
 }
 
 //===----------------------------------------------------------------------===//
 // BasicAliasAnalysis Pass
 //===----------------------------------------------------------------------===//
 
 AnalysisKey BasicAA::Key;
 

lib/Analysis/CFLAndersAliasAnalysis.cpp

class CFLAndersAAResult::FunctionInfo {
   AliasSummary Summary;
 
   Optional<AliasAttrs> getAttrs(const Value *) const;
 
 public:
   FunctionInfo(const Function &, const SmallVectorImpl<Value *> &,
                const ReachabilitySet &, const AliasAttrMap &);
 
-  bool mayAlias(const Value *, uint64_t, const Value *, uint64_t) const;
+  bool mayAlias(const Value *, LocationSize, const Value *, LocationSize) const;
   const AliasSummary &getAliasSummary() const { return Summary; }
 };
 
 static bool hasReadOnlyState(StateSet Set) {
   return (Set & StateSet(ReadOnlyStateMask)).any();
 }
 
 static bool hasWriteOnlyState(StateSet Set) {
CFLAndersAAResult::FunctionInfo::getAttrs(const Value *V) const {
 
   auto Itr = AttrMap.find(V);
   if (Itr != AttrMap.end())
     return Itr->second;
   return None;
 }
 
 bool CFLAndersAAResult::FunctionInfo::mayAlias(const Value *LHS,
-                                               uint64_t LHSSize,
+                                               LocationSize LHSSize,
                                                const Value *RHS,
-                                               uint64_t RHSSize) const {
+                                               LocationSize RHSSize) const {
   assert(LHS && RHS);
 
   // Check if we've seen LHS and RHS before. Sometimes LHS or RHS can be created
   // after the analysis gets executed, and we want to be conservative in those
   // cases.
   auto MaybeAttrsA = getAttrs(LHS);
   auto MaybeAttrsB = getAttrs(RHS);
   if (!MaybeAttrsA || !MaybeAttrsB)
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/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/Target/Hexagon/HexagonLoopIdiomRecognition.cpp

 static bool
 mayLoopAccessLocation(Value *Ptr, ModRefInfo Access, Loop *L,
                       const SCEV *BECount, unsigned StoreSize,
                       AliasAnalysis &AA,
                       SmallPtrSetImpl<Instruction *> &Ignored) {
   // Get the location that may be stored across the loop.  Since the access
   // is strided positively through memory, we say that the modified location
   // starts at the pointer and has infinite size.
-  uint64_t AccessSize = MemoryLocation::UnknownSize;
+  LocationSize AccessSize = MemoryLocation::UnknownSize;
 
   // If the loop iterates a fixed number of times, we can refine the access
   // size to be exactly the size of the memset, which is (BECount+1)*StoreSize
   if (const SCEVConstant *BECst = dyn_cast<SCEVConstant>(BECount))
     AccessSize = (BECst->getValue()->getZExtValue() + 1) * StoreSize;
 
   // TODO: For this to be really effective, we have to dive into the pointer
   // operand in the store.  Store to &A[i] of 100 will always return may alias

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) {
   // 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)
+  if (!Later.Size.hasValue() || !Earlier.Size.hasValue())
     return OW_Unknown;
 
+  // FIXME: Vet that this works for size upper-bounds. Seems unlikely that we'll
+  // get imprecise values here, though.
+  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) {
     // 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];
     DEBUG(dbgs() << "DSE: Partial overwrite: Earlier [" << EarlierOff << ", " <<
-                    int64_t(EarlierOff + Earlier.Size) << ") Later [" <<
-                    LaterOff << ", " << int64_t(LaterOff + Later.Size) << ")\n");
+                    int64_t(EarlierOff + EarlierSize) << ") Later [" <<
+                    LaterOff << ", " << 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)) {
       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) {
     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/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
+}