[MemorySSA] Limit clobber walks.

[asbirlea]

Summary

This patch limits all getClobberingMemoryAccess() walks to MaxCheckLimit.

[george.burgess.iv]

Thanks for this!

Would it be straightforward to have a lit test (or similar) that sets memssa-check-limit to something super low and checks that this all does what we want (e.g. walk limit is cumulative across all walks on OptimizePhis, the walker trivially obeys it, ...)

lib/Analysis/MemorySSA.cpp

557 ↗

(On Diff #191418)

nit: please remove == 0

910 ↗

(On Diff #191418)

Was this intended to be unsigned &UpwardWalkLimit? Looks like we're passing it by ref everywhere else

923 ↗

(On Diff #191418)

Would it be better to make UpwardWalkLimit a member? This entire class is a container of query-specific state anyway.

[asbirlea]

Address comments.

I updated two existing tests to take a limit of 0. Let me know if this makes sense.

[asbirlea]

format.

[george.burgess.iv]

Thanks again!

[asbirlea]

Thank you for the review!

llvm/trunk/lib/Analysis/MemorySSA.cpp

DefPath(const MemoryLocation &Loc, MemoryAccess *Init,
             Optional<ListIndex> Previous)
         : DefPath(Loc, Init, Init, Previous) {}
   };
 
   const MemorySSA &MSSA;
   AliasAnalysisType &AA;
   DominatorTree &DT;
   UpwardsMemoryQuery *Query;
+  unsigned *UpwardWalkLimit;
 
   // Phi optimization bookkeeping
   SmallVector<DefPath, 32> Paths;
   DenseSet<ConstMemoryAccessPair> VisitedPhis;
 
   /// Find the nearest def or phi that `From` can legally be optimized to.
   const MemoryAccess *getWalkTarget(const MemoryPhi *From) const {
     assert(From->getNumOperands() && "Phi with no operands?");
template <class AliasAnalysisType> class ClobberWalker {
   /// This will update Desc.Last as it walks. It will (optionally) also stop at
   /// StopAt.
   ///
   /// This does not test for whether StopAt is a clobber
   UpwardsWalkResult
   walkToPhiOrClobber(DefPath &Desc, const MemoryAccess *StopAt = nullptr,
                      const MemoryAccess *SkipStopAt = nullptr) const {
     assert(!isa<MemoryUse>(Desc.Last) && "Uses don't exist in my world");
+    assert(UpwardWalkLimit && *UpwardWalkLimit > 0 &&
+           "Need a positive walk limit");
 
     for (MemoryAccess *Current : def_chain(Desc.Last)) {
       Desc.Last = Current;
       if (Current == StopAt || Current == SkipStopAt)
         return {Current, false, MayAlias};
 
       if (auto *MD = dyn_cast<MemoryDef>(Current)) {
         if (MSSA.isLiveOnEntryDef(MD))
           return {MD, true, MustAlias};
+
+        if (!--*UpwardWalkLimit)
+          return {Current, true, MayAlias};
+
         ClobberAlias CA =
             instructionClobbersQuery(MD, Desc.Loc, Query->Inst, AA);
         if (CA.IsClobber)
           return {MD, true, CA.AR};
       }
     }
 
     assert(isa<MemoryPhi>(Desc.Last) &&
while (!PausedSearches.empty()) {
         continue;
 
       const MemoryAccess *SkipStopWhere = nullptr;
       if (Query->SkipSelfAccess && Node.Loc == Query->StartingLoc) {
         assert(isa<MemoryDef>(Query->OriginalAccess));
         SkipStopWhere = Query->OriginalAccess;
       }
 
-      UpwardsWalkResult Res = walkToPhiOrClobber(Node, /*StopAt=*/StopWhere,
+      UpwardsWalkResult Res = walkToPhiOrClobber(Node,
+                                                 /*StopAt=*/StopWhere,
                                                  /*SkipStopAt=*/SkipStopWhere);
       if (Res.IsKnownClobber) {
         assert(Res.Result != StopWhere && Res.Result != SkipStopWhere);
+
         // If this wasn't a cache hit, we hit a clobber when walking. That's a
         // failure.
         TerminatedPath Term{Res.Result, PathIndex};
         if (!MSSA.dominates(Res.Result, StopWhere))
           return Term;
 
         // Otherwise, it's a valid thing to potentially optimize to.
         Terminated.push_back(Term);

 
 public:
   ClobberWalker(const MemorySSA &MSSA, AliasAnalysisType &AA, DominatorTree &DT)
       : MSSA(MSSA), AA(AA), DT(DT) {}
 
   AliasAnalysisType *getAA() { return &AA; }
   /// Finds the nearest clobber for the given query, optimizing phis if
   /// possible.
-  MemoryAccess *findClobber(MemoryAccess *Start, UpwardsMemoryQuery &Q) {
+  MemoryAccess *findClobber(MemoryAccess *Start, UpwardsMemoryQuery &Q,
+                            unsigned &UpWalkLimit) {
     Query = &Q;
+    UpwardWalkLimit = &UpWalkLimit;
+    // Starting limit must be > 0.
+    if (!UpWalkLimit)
+      UpWalkLimit++;
 
     MemoryAccess *Current = Start;
     // This walker pretends uses don't exist. If we're handed one, silently grab
     // its def. (This has the nice side-effect of ensuring we never cache uses)
     if (auto *MU = dyn_cast<MemoryUse>(Start))
       Current = MU->getDefiningAccess();
 
     DefPath FirstDesc(Q.StartingLoc, Current, Current, None);
     // Fast path for the overly-common case (no crazy phi optimization
     // necessary)
     UpwardsWalkResult WalkResult = walkToPhiOrClobber(FirstDesc);
     MemoryAccess *Result;
     if (WalkResult.IsKnownClobber) {
       Result = WalkResult.Result;
       Q.AR = WalkResult.AR;
     } else {
       OptznResult OptRes = tryOptimizePhi(cast<MemoryPhi>(FirstDesc.Last),
                                           Current, Q.StartingLoc);
       verifyOptResult(OptRes);
       resetPhiOptznState();
       Result = OptRes.PrimaryClobber.Clobber;
     }
 
 #ifdef EXPENSIVE_CHECKS
-    if (!Q.SkipSelfAccess)
+    if (!Q.SkipSelfAccess && *UpwardWalkLimit > 0)
       checkClobberSanity(Current, Result, Q.StartingLoc, MSSA, Q, AA);
 #endif
     return Result;
   }
 };
 
 struct RenamePassData {
   DomTreeNode *DTN;
template <class AliasAnalysisType> class MemorySSA::ClobberWalkerBase {
   ClobberWalker<AliasAnalysisType> Walker;
   MemorySSA *MSSA;
 
 public:
   ClobberWalkerBase(MemorySSA *M, AliasAnalysisType *A, DominatorTree *D)
       : Walker(*M, *A, *D), MSSA(M) {}
 
   MemoryAccess *getClobberingMemoryAccessBase(MemoryAccess *,
-                                              const MemoryLocation &);
-  // Second argument (bool), defines whether the clobber search should skip the
+                                              const MemoryLocation &,
+                                              unsigned &);
+  // Third argument (bool), defines whether the clobber search should skip the
   // original queried access. If true, there will be a follow-up query searching
   // for a clobber access past "self". Note that the Optimized access is not
   // updated if a new clobber is found by this SkipSelf search. If this
   // additional query becomes heavily used we may decide to cache the result.
   // Walker instantiations will decide how to set the SkipSelf bool.
-  MemoryAccess *getClobberingMemoryAccessBase(MemoryAccess *, bool);
+  MemoryAccess *getClobberingMemoryAccessBase(MemoryAccess *, unsigned &, bool);
 };
 
 /// A MemorySSAWalker that does AA walks to disambiguate accesses. It no
 /// longer does caching on its own, but the name has been retained for the
 /// moment.
 template <class AliasAnalysisType>
 class MemorySSA::CachingWalker final : public MemorySSAWalker {
   ClobberWalkerBase<AliasAnalysisType> *Walker;
 
 public:
   CachingWalker(MemorySSA *M, ClobberWalkerBase<AliasAnalysisType> *W)
       : MemorySSAWalker(M), Walker(W) {}
   ~CachingWalker() override = default;
 
   using MemorySSAWalker::getClobberingMemoryAccess;
 
+  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA, unsigned &UWL) {
+    return Walker->getClobberingMemoryAccessBase(MA, UWL, false);
+  }
+  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
+                                          const MemoryLocation &Loc,
+                                          unsigned &UWL) {
+    return Walker->getClobberingMemoryAccessBase(MA, Loc, UWL);
+  }
+
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA) override {
-    return Walker->getClobberingMemoryAccessBase(MA, false);
+    unsigned UpwardWalkLimit = MaxCheckLimit;
+    return getClobberingMemoryAccess(MA, UpwardWalkLimit);
   }
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
                                           const MemoryLocation &Loc) override {
-    return Walker->getClobberingMemoryAccessBase(MA, Loc);
+    unsigned UpwardWalkLimit = MaxCheckLimit;
+    return getClobberingMemoryAccess(MA, Loc, UpwardWalkLimit);
   }
 
   void invalidateInfo(MemoryAccess *MA) override {
     if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA))
       MUD->resetOptimized();
   }
 };
 
 template <class AliasAnalysisType>
 class MemorySSA::SkipSelfWalker final : public MemorySSAWalker {
   ClobberWalkerBase<AliasAnalysisType> *Walker;
 
 public:
   SkipSelfWalker(MemorySSA *M, ClobberWalkerBase<AliasAnalysisType> *W)
       : MemorySSAWalker(M), Walker(W) {}
   ~SkipSelfWalker() override = default;
 
   using MemorySSAWalker::getClobberingMemoryAccess;
 
+  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA, unsigned &UWL) {
+    return Walker->getClobberingMemoryAccessBase(MA, UWL, true);
+  }
+  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
+                                          const MemoryLocation &Loc,
+                                          unsigned &UWL) {
+    return Walker->getClobberingMemoryAccessBase(MA, Loc, UWL);
+  }
+
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA) override {
-    return Walker->getClobberingMemoryAccessBase(MA, true);
+    unsigned UpwardWalkLimit = MaxCheckLimit;
+    return getClobberingMemoryAccess(MA, UpwardWalkLimit);
   }
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
                                           const MemoryLocation &Loc) override {
-    return Walker->getClobberingMemoryAccessBase(MA, Loc);
+    unsigned UpwardWalkLimit = MaxCheckLimit;
+    return getClobberingMemoryAccess(MA, Loc, UpwardWalkLimit);
   }
 
   void invalidateInfo(MemoryAccess *MA) override {
     if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA))
       MUD->resetOptimized();
   }
 };
 

 /// their defining access at the thing that actually clobbers them.  Because it
 /// is a batch walker that touches everything, it does not operate like the
 /// other walkers.  This walker is basically performing a top-down SSA renaming
 /// pass, where the version stack is used as the cache.  This enables it to be
 /// significantly more time and memory efficient than using the regular walker,
 /// which is walking bottom-up.
 class MemorySSA::OptimizeUses {
 public:
-  OptimizeUses(MemorySSA *MSSA, MemorySSAWalker *Walker, BatchAAResults *BAA,
-               DominatorTree *DT)
+  OptimizeUses(MemorySSA *MSSA, CachingWalker<BatchAAResults> *Walker,
+               BatchAAResults *BAA, DominatorTree *DT)
       : MSSA(MSSA), Walker(Walker), AA(BAA), DT(DT) {}
 
   void optimizeUses();
 
 private:
   /// This represents where a given memorylocation is in the stack.
   struct MemlocStackInfo {
     // This essentially is keeping track of versions of the stack. Whenever
struct MemlocStackInfo {
     Optional<AliasResult> AR;
   };
 
   void optimizeUsesInBlock(const BasicBlock *, unsigned long &, unsigned long &,
                            SmallVectorImpl<MemoryAccess *> &,
                            DenseMap<MemoryLocOrCall, MemlocStackInfo> &);
 
   MemorySSA *MSSA;
-  MemorySSAWalker *Walker;
+  CachingWalker<BatchAAResults> *Walker;
   BatchAAResults *AA;
   DominatorTree *DT;
 };
 
 } // end namespace llvm
 
 /// Optimize the uses in a given block This is basically the SSA renaming
 /// algorithm, with one caveat: We are able to use a single stack for all
if (UpperBound - LocInfo.LowerBound > MaxCheckLimit) {
                         << UpperBound - LocInfo.LowerBound
                         << " stores to disambiguate\n");
       // Because we did not walk, LastKill is no longer valid, as this may
       // have been a kill.
       LocInfo.LastKillValid = false;
       continue;
     }
     bool FoundClobberResult = false;
+    unsigned UpwardWalkLimit = MaxCheckLimit;
     while (UpperBound > LocInfo.LowerBound) {
       if (isa<MemoryPhi>(VersionStack[UpperBound])) {
         // For phis, use the walker, see where we ended up, go there
-        Instruction *UseInst = MU->getMemoryInst();
-        MemoryAccess *Result = Walker->getClobberingMemoryAccess(UseInst);
+        MemoryAccess *Result =
+            Walker->getClobberingMemoryAccess(MU, UpwardWalkLimit);
         // We are guaranteed to find it or something is wrong
         while (VersionStack[UpperBound] != Result) {
           assert(UpperBound != 0);
           --UpperBound;
         }
         FoundClobberResult = true;
         break;
       }

 
 /// Walk the use-def chains starting at \p StartingAccess and find
 /// the MemoryAccess that actually clobbers Loc.
 ///
 /// \returns our clobbering memory access
 template <typename AliasAnalysisType>
 MemoryAccess *
 MemorySSA::ClobberWalkerBase<AliasAnalysisType>::getClobberingMemoryAccessBase(
-    MemoryAccess *StartingAccess, const MemoryLocation &Loc) {
+    MemoryAccess *StartingAccess, const MemoryLocation &Loc,
+    unsigned &UpwardWalkLimit) {
   if (isa<MemoryPhi>(StartingAccess))
     return StartingAccess;
 
   auto *StartingUseOrDef = cast<MemoryUseOrDef>(StartingAccess);
   if (MSSA->isLiveOnEntryDef(StartingUseOrDef))
     return StartingUseOrDef;
 
   Instruction *I = StartingUseOrDef->getMemoryInst();
MemorySSA::ClobberWalkerBase<AliasAnalysisType>::getClobberingMemoryAccessBase(
 
   // Unlike the other function, do not walk to the def of a def, because we are
   // handed something we already believe is the clobbering access.
   // We never set SkipSelf to true in Q in this method.
   MemoryAccess *DefiningAccess = isa<MemoryUse>(StartingUseOrDef)
                                      ? StartingUseOrDef->getDefiningAccess()
                                      : StartingUseOrDef;
 
-  MemoryAccess *Clobber = Walker.findClobber(DefiningAccess, Q);
+  MemoryAccess *Clobber =
+      Walker.findClobber(DefiningAccess, Q, UpwardWalkLimit);
   LLVM_DEBUG(dbgs() << "Starting Memory SSA clobber for " << *I << " is ");
   LLVM_DEBUG(dbgs() << *StartingUseOrDef << "\n");
   LLVM_DEBUG(dbgs() << "Final Memory SSA clobber for " << *I << " is ");
   LLVM_DEBUG(dbgs() << *Clobber << "\n");
   return Clobber;
 }
 
 template <typename AliasAnalysisType>
 MemoryAccess *
 MemorySSA::ClobberWalkerBase<AliasAnalysisType>::getClobberingMemoryAccessBase(
-    MemoryAccess *MA, bool SkipSelf) {
+    MemoryAccess *MA, unsigned &UpwardWalkLimit, bool SkipSelf) {
   auto *StartingAccess = dyn_cast<MemoryUseOrDef>(MA);
   // If this is a MemoryPhi, we can't do anything.
   if (!StartingAccess)
     return MA;
 
   bool IsOptimized = false;
 
   // If this is an already optimized use or def, return the optimized result.
if (!IsOptimized) {
     // At this point, DefiningAccess may be the live on entry def.
     // If it is, we will not get a better result.
     if (MSSA->isLiveOnEntryDef(DefiningAccess)) {
       StartingAccess->setOptimized(DefiningAccess);
       StartingAccess->setOptimizedAccessType(None);
       return DefiningAccess;
     }
 
-    OptimizedAccess = Walker.findClobber(DefiningAccess, Q);
+    OptimizedAccess = Walker.findClobber(DefiningAccess, Q, UpwardWalkLimit);
     StartingAccess->setOptimized(OptimizedAccess);
     if (MSSA->isLiveOnEntryDef(OptimizedAccess))
       StartingAccess->setOptimizedAccessType(None);
     else if (Q.AR == MustAlias)
       StartingAccess->setOptimizedAccessType(MustAlias);
   } else
     OptimizedAccess = StartingAccess->getOptimized();
 
   LLVM_DEBUG(dbgs() << "Starting Memory SSA clobber for " << *I << " is ");
   LLVM_DEBUG(dbgs() << *StartingAccess << "\n");
   LLVM_DEBUG(dbgs() << "Optimized Memory SSA clobber for " << *I << " is ");
   LLVM_DEBUG(dbgs() << *OptimizedAccess << "\n");
 
   MemoryAccess *Result;
   if (SkipSelf && isa<MemoryPhi>(OptimizedAccess) &&
-      isa<MemoryDef>(StartingAccess)) {
+      isa<MemoryDef>(StartingAccess) && UpwardWalkLimit) {
     assert(isa<MemoryDef>(Q.OriginalAccess));
     Q.SkipSelfAccess = true;
-    Result = Walker.findClobber(OptimizedAccess, Q);
+    Result = Walker.findClobber(OptimizedAccess, Q, UpwardWalkLimit);
   } else
     Result = OptimizedAccess;
 
   LLVM_DEBUG(dbgs() << "Result Memory SSA clobber [SkipSelf = " << SkipSelf);
   LLVM_DEBUG(dbgs() << "] for " << *I << " is " << *Result << "\n");
 
   return Result;
 }

llvm/trunk/test/Analysis/MemorySSA/optimize-use.ll

-; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s
-; RUN: opt -aa-pipeline=basic-aa -passes='print<memoryssa>,verify<memoryssa>' -disable-output < %s 2>&1 | FileCheck %s
+; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s --check-prefixes=CHECK,NOLIMIT
+; RUN: opt -memssa-check-limit=0 -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s --check-prefixes=CHECK,LIMIT
+; RUN: opt -aa-pipeline=basic-aa -passes='print<memoryssa>,verify<memoryssa>' -disable-output < %s 2>&1 | FileCheck %s --check-prefixes=CHECK,NOLIMIT
+; RUN: opt -memssa-check-limit=0 -aa-pipeline=basic-aa -passes='print<memoryssa>,verify<memoryssa>' -disable-output < %s 2>&1 | FileCheck %s --check-prefixes=CHECK,LIMIT
 
 ; Function Attrs: ssp uwtable
 define i32 @main() {
 entry:
 ; CHECK: 1 = MemoryDef(liveOnEntry)
 ; CHECK-NEXT:   %call = call noalias i8* @_Znwm(i64 4)
   %call = call noalias i8* @_Znwm(i64 4)
   %0 = bitcast i8* %call to i32*
 ; CHECK: 2 = MemoryDef(1)
 ; CHECK-NEXT:   %call1 = call noalias i8* @_Znwm(i64 4)
   %call1 = call noalias i8* @_Znwm(i64 4)
   %1 = bitcast i8* %call1 to i32*
 ; CHECK: 3 = MemoryDef(2)
 ; CHECK-NEXT:   store i32 5, i32* %0, align 4
   store i32 5, i32* %0, align 4
 ; CHECK: 4 = MemoryDef(3)
 ; CHECK-NEXT:   store i32 7, i32* %1, align 4
   store i32 7, i32* %1, align 4
-; CHECK: MemoryUse(3) MustAlias
-; CHECK-NEXT:   %2 = load i32, i32* %0, align 4
+; NOLIMIT: MemoryUse(3) MustAlias
+; NOLIMIT-NEXT:   %2 = load i32, i32* %0, align 4
+; LIMIT: MemoryUse(4) MayAlias
+; LIMIT-NEXT:   %2 = load i32, i32* %0, align 4
   %2 = load i32, i32* %0, align 4
-; CHECK: MemoryUse(4) MustAlias
-; CHECK-NEXT:   %3 = load i32, i32* %1, align 4
+; NOLIMIT: MemoryUse(4) MustAlias
+; NOLIMIT-NEXT:   %3 = load i32, i32* %1, align 4
+; LIMIT: MemoryUse(4) MayAlias
+; LIMIT-NEXT:   %3 = load i32, i32* %1, align 4
   %3 = load i32, i32* %1, align 4
-; CHECK: MemoryUse(3) MustAlias
-; CHECK-NEXT:   %4 = load i32, i32* %0, align 4
+; NOLIMIT: MemoryUse(3) MustAlias
+; NOLIMIT-NEXT:   %4 = load i32, i32* %0, align 4
+; LIMIT: MemoryUse(4) MayAlias
+; LIMIT-NEXT:   %4 = load i32, i32* %0, align 4
   %4 = load i32, i32* %0, align 4
-; CHECK: MemoryUse(4) MustAlias
-; CHECK-NEXT:   %5 = load i32, i32* %1, align 4
+; NOLIMIT: MemoryUse(4) MustAlias
+; NOLIMIT-NEXT:   %5 = load i32, i32* %1, align 4
+; LIMIT: MemoryUse(4) MayAlias
+; LIMIT-NEXT:   %5 = load i32, i32* %1, align 4
   %5 = load i32, i32* %1, align 4
   %add = add nsw i32 %3, %5
   ret i32 %add
 }
 
+
 declare noalias i8* @_Znwm(i64)

llvm/trunk/test/Analysis/MemorySSA/phi-translation.ll

-; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s
-; RUN: opt -aa-pipeline=basic-aa -passes='print<memoryssa>,verify<memoryssa>' -disable-output < %s 2>&1 | FileCheck %s
+; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s --check-prefixes=CHECK,NOLIMIT
+; RUN: opt -memssa-check-limit=0 -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s --check-prefixes=CHECK,LIMIT
+; RUN: opt -aa-pipeline=basic-aa -passes='print<memoryssa>,verify<memoryssa>' -disable-output < %s 2>&1 | FileCheck %s --check-prefixes=CHECK,NOLIMIT
+; RUN: opt -memssa-check-limit=0 -aa-pipeline=basic-aa -passes='print<memoryssa>,verify<memoryssa>' -disable-output < %s 2>&1 | FileCheck %s --check-prefixes=CHECK,LIMIT
 
 ; %ptr can't alias %local, so we should be able to optimize the use of %local to
 ; point to the store to %local.
 ; CHECK-LABEL: define void @check
 define void @check(i8* %ptr, i1 %bool) {
 entry:
   %local = alloca i8, align 1
 ; CHECK: 1 = MemoryDef(liveOnEntry)
 ; CHECK-NEXT: store i8 0, i8* %local, align 1
   store i8 0, i8* %local, align 1
   br i1 %bool, label %if.then, label %if.end
 
 if.then:
   %p2 = getelementptr inbounds i8, i8* %ptr, i32 1
 ; CHECK: 2 = MemoryDef(1)
 ; CHECK-NEXT: store i8 0, i8* %p2, align 1
   store i8 0, i8* %p2, align 1
   br label %if.end
 
 if.end:
 ; CHECK: 3 = MemoryPhi({entry,1},{if.then,2})
-; CHECK: MemoryUse(1)
-; CHECK-NEXT: load i8, i8* %local, align 1
+; NOLIMIT: MemoryUse(1) MayAlias
+; NOLIMIT-NEXT: load i8, i8* %local, align 1
+; LIMIT: MemoryUse(3) MayAlias
+; LIMIT-NEXT: load i8, i8* %local, align 1
   load i8, i8* %local, align 1
   ret void
 }
 
 ; CHECK-LABEL: define void @check2
 define void @check2(i1 %val1, i1 %val2, i1 %val3) {
 entry:
   %local = alloca i8, align 1

 ; CHECK-NEXT: store i8 4, i8* %local2
   store i8 4, i8* %local2
   br label %phi.1
 
 phi.1:
 ; Order matters here; phi.2 needs to come before phi.3, because that's the order
 ; they're visited in.
 ; CHECK: 6 = MemoryPhi({phi.2,4},{phi.3,3})
-; CHECK: MemoryUse(1)
-; CHECK-NEXT: load i8, i8* %local
+; NOLIMIT: MemoryUse(1) MayAlias
+; NOLIMIT-NEXT: load i8, i8* %local
+; LIMIT: MemoryUse(6) MayAlias
+; LIMIT-NEXT: load i8, i8* %local
   load i8, i8* %local
   ret void
 }
 
 ; CHECK-LABEL: define void @cross_phi
 define void @cross_phi(i8* noalias %p1, i8* noalias %p2) {
 ; CHECK: 1 = MemoryDef(liveOnEntry)
 ; CHECK-NEXT: store i8 0, i8* %p1
   store i8 0, i8* %p1
-; CHECK: MemoryUse(1)
-; CHECK-NEXT: load i8, i8* %p1
+; NOLIMIT: MemoryUse(1) MustAlias
+; NOLIMIT-NEXT: load i8, i8* %p1
+; LIMIT: MemoryUse(1) MayAlias
+; LIMIT-NEXT: load i8, i8* %p1
   load i8, i8* %p1
   br i1 undef, label %a, label %b
 
 a:
 ; CHECK: 2 = MemoryDef(1)
 ; CHECK-NEXT: store i8 0, i8* %p2
   store i8 0, i8* %p2
   br i1 undef, label %c, label %d

 ; CHECK: 7 = MemoryPhi({a,2},{b,3})
 ; CHECK: 5 = MemoryDef(7)
 ; CHECK-NEXT: store i8 3, i8* %p2
   store i8 3, i8* %p2
   br label %e
 
 e:
 ; 8 = MemoryPhi({c,4},{d,5})
-; CHECK: MemoryUse(1)
-; CHECK-NEXT: load i8, i8* %p1
+; NOLIMIT: MemoryUse(1) MustAlias
+; NOLIMIT-NEXT: load i8, i8* %p1
+; LIMIT: MemoryUse(8) MayAlias
+; LIMIT-NEXT: load i8, i8* %p1
   load i8, i8* %p1
   ret void
 }
 
 ; CHECK-LABEL: define void @looped
 define void @looped(i8* noalias %p1, i8* noalias %p2) {
 ; CHECK: 1 = MemoryDef(liveOnEntry)
 ; CHECK-NEXT: store i8 0, i8* %p1
; CHECK-NEXT: store i8 1, i8* %p2
   store i8 1, i8* %p2
   br label %loop.3
 
 loop.3:
 ; CHECK: 7 = MemoryPhi({loop.1,2},{loop.2,3})
 ; CHECK: 4 = MemoryDef(7)
 ; CHECK-NEXT: store i8 2, i8* %p2
   store i8 2, i8* %p2
-; CHECK: MemoryUse(1)
-; CHECK-NEXT: load i8, i8* %p1
+; NOLIMIT: MemoryUse(1) MayAlias
+; NOLIMIT-NEXT: load i8, i8* %p1
+; LIMIT: MemoryUse(4) MayAlias
+; LIMIT-NEXT: load i8, i8* %p1
   load i8, i8* %p1
   br i1 undef, label %loop.2, label %loop.1
 }
 
 ; CHECK-LABEL: define void @looped_visitedonlyonce
 define void @looped_visitedonlyonce(i8* noalias %p1, i8* noalias %p2) {
   br label %while.cond
 

 if.then2:
 ; CHECK: 2 = MemoryDef(1)
 ; CHECK-NEXT: store i8 1, i8* %p2
   store i8 1, i8* %p2
   br label %if.end
 
 if.end:
 ; CHECK: 4 = MemoryPhi({while.cond,5},{if.then,1},{if.then2,2})
-; CHECK: MemoryUse(4)
+; CHECK: MemoryUse(4) MayAlias
 ; CHECK-NEXT: load i8, i8* %p1
   load i8, i8* %p1
 ; CHECK: 3 = MemoryDef(4)
 ; CHECK-NEXT: store i8 2, i8* %p2
   store i8 2, i8* %p2
-; CHECK: MemoryUse(4)
-; CHECK-NEXT: load i8, i8* %p1
+; NOLIMIT: MemoryUse(4) MayAlias
+; NOLIMIT-NEXT: load i8, i8* %p1
+; LIMIT: MemoryUse(3) MayAlias
+; LIMIT-NEXT: load i8, i8* %p1
   load i8, i8* %p1
   br label %while.cond
 }