Expose must/may alias info in MemorySSA.

[asbirlea]

Summary

Building MemorySSA gathers alias information for Defs/Uses.
Store and expose this information when optimizing uses (when building MemorySSA),
and when optimizing defs or updating uses (getClobberingMemoryAccess).
Current patch does not propagate alias information through MemoryPhis.

[• dberlin]

lib/Analysis/MemorySSA.cpp

269

It is possible for a call to must-alias a single thing, no?

297

So this is going to double the number of alias calls, unfortunately. I suspect it will make building significantly slower, since roughly *all* time is spent there.

Do you have perf numbers to say one way or the other?

(unfortunately, ->alias is not const, so it will call it again)
I think we may need to finally implement some small LRU aliasing cache or something to make this fast enough.

Or

1. Optionally pass the aliasing result into getModRefInfo, which would be a really weird API).
2. Optionally return the aliasing result from getModRefInfo, which may make more sense.

2116

I'm a little concerned about saying we must-alias the live on entry def.
It's abstractly true, but i wonder if stuff will get confusingly broken.

LiveOnEntry is really equivalent to "something before this function" not "one specific thing".

Thoughts?

[george.burgess.iv]

Thanks for the patch!

include/llvm/Analysis/MemorySSA.h

264

If we're going to call resetOptimized() outside of tests, we should probably remove this bit of the comment.

284

Should be. In isOptimized(), we check to see if OptimizedID is the ID of the defining access. If we're setting the operand to something else, we should observe a different ID.

IIRC, this was necessary to make things like RAUW work without us having to manually deoptimize everything. If that's broken somehow, we shouldn't be papering over it here.

296

Nit: Can we pack this in a PtrIntPair with MemoryInst?

lib/Analysis/MemorySSA.cpp

240

I'd mildly prefer that we return a struct { bool IsClobber, IsMustAlias; }; or similar from this instead. That way, it's more clear what we want to hand back for FoundMustAlias in all cases.

(Moreover, there are quite a few paths in this function that don't try to set FoundMustAlias. It doesn't seem that's intentional.)

292

Nit: no else after if (...) return ...;

303

Same "please make this part of the return value" nit

881

Do we need to set Q.FoundMustAlias here, as well?

2116

I was thinking this could be solved by using "Clobber" in the name instead of "Alias", but I don't know if "Clobber" would imply something else that's subtly wrong.

That said, it may be a better idea to just have passes that don't care about MustAlias vs LiveOnEntry to roll their own helper:

bool isMustAlias(const MemoryAccess *MA) {
  return MA->definingIsMustAlias() || MA->getDefiningAccess() == MSSA->getLiveOnEntryDef();
}

...So we can have isMustAlias just mean isMustAlias :)

[asbirlea]

Address most comments.

[asbirlea]

Updates - part1.

include/llvm/Analysis/MemorySSA.h

284

Got it! Removing this, keeping above comment.

lib/Analysis/MemorySSA.cpp

240

I did not mean to set it on all paths, since FoundMustAlias should not be modified for NoAlias. I missed the case when it needs to reset to May.

Updating to return pair, where isMustAlias should be ignored if !IsClobber.

269

That's true. I didn't add that because I didn't see how we would use the must info here.

If we know the call does not modify and it's a must alias, then we could consider some transformation (read: promotion). In practice, we won't promote calls, so keeping FoundMustAlias = false (i.e. may) should be conservative.
The right thing is reseting to may for calls:
if(I != MRI_NoModRef) FoundMustAlias = false;
(instead of keeping the given value).

297

Ack, looking into how to best address this one.

881

Intended to keep the default (=false) for Phis.

2116

Right now definingIsMayAlias and definingIsMustAlias are opposites. Since an optimized access skipped over NoAlias.
For optimized accesses May means "I found the defining location and it may alias this access."
For unoptimized accesses, the default is May.

I was planning to couple isOptimized() and definingIsMustAlias() to determine if a May alias was found.

Must with LOE is equivalent to "The defining access is not a MayAlias".
Perhaps I should only

• keep the definingIsMayAlias() accessor
• setDefiningToMayAlias(bool Arg) setter //Arg=false means Must or LOE

Thoughts?

[• dberlin]

lib/Analysis/MemorySSA.cpp

269

I would do the right thing for calls, IMHO, if we can.
(especially since we have to solve the double alias() call issue for other things anyway).

While LICM may not promote them, PRE definitely does (and GCC tests that it does).

This is true even through function pointers.
Here's the non-aliasing version to give you an idea (the aliasing version is longer)

double f(double a)
 {
   double b;
   double c,d;
   double (*fp) (double) __attribute__ ((const));

 double (*fp) (double) __attribute__ ((const));
   /* Partially redundant call */
   if (a < 2.0)
     {
       fp = sin;
       c = fp (a);
     }
   else
     {
       c = 1.0;
       fp = cos;
     }
   d = fp (a);
   return d + c;
 }

the fp call will get pushed into the else branch.
In the equivalent loop, we could promote it (PRE could promote it too if you let it speculate)
If we determine it is a must-alias of a single thing, we could do the same.
If we determine it's a must-alias of a set of things, we could do the same
If we determine it's a must-alias of the live on entry def, etc

[• dberlin]

I'd reuse the type we already have to express alias results.
While you don't care about partial alias, it makes all code have the same meaning for the same thing :)

include/llvm/Analysis/MemorySSA.h

258

Why not just have definingAliasType() and use the AliasResult type here?

Then this looks like any other aliasing code.

277–282

IMHO, setDefiningAliasType(AliasResult)

281

Take an AliasResult AliasType = MayAlias)

lib/Analysis/MemorySSA.cpp

244

Just use AliasResult for the second part here.

(I'd suggest using ModRefType for the first but i believe nothing wants it right now)

[asbirlea]

Use AliasResult to store alias information with the defining type.
Use MRI_Must bit to avoid double queries to AA.

[asbirlea]

Gentle ping. Also blocked on dependent patch.

[nlopes]

The concept looks interesting to me. I'll let the experts review the patch, though (I just skimmed over it).
Out of curiosity, what are the clients you envision could use this functionality?
I can imagine that we can do store forwarding with a mustalias MemUse if stored size >= load size. Also, a mustalias MemDef can kill the previous MemDef if it has no other uses (2 stores to same location).
Are there any other uses cases? Can it be used to simplify more complex optimizations? Even better, are there missing blocks that would be needed to simplify these optimizations? (tricky question; just wondering if you have some thoughts on that).

Please excuse my academic curiosity :)

[asbirlea]

An immediate usecase I have in LICM, is in very large testcases where I want to rely on MemorySSA's threshhold for optimizing MemUses.
I need to use getDefiningAccess() on a Use and query if the result given is May_Alias or Must_Alias. If the Use is not optimized, the result will always be MayAlias. If optimized, it may be May or Must.
Alias info is needed to avoid an additional AA.alias call when creating mssa alias sets for promotion.

It can certainly be used for more complex optimizations, aliasing between MemDefs is the most interesting to me. Since in MemorySSA all stores clobber all stores (until optimized), must alias info could be used to shortcut def alias chains. AFAIK this is done for MemUses, I don't think it's done for MemDefs.

[nlopes]

In D38569#933068, @asbirlea wrote:

An immediate usecase I have in LICM, is in very large testcases where I want to rely on MemorySSA's threshhold for optimizing MemUses.
I need to use getDefiningAccess() on a Use and query if the result given is May_Alias or Must_Alias. If the Use is not optimized, the result will always be MayAlias. If optimized, it may be May or Must.
Alias info is needed to avoid an additional AA.alias call when creating mssa alias sets for promotion.

It can certainly be used for more complex optimizations, aliasing between MemDefs is the most interesting to me. Since in MemorySSA all stores clobber all stores (until optimized), must alias info could be used to shortcut def alias chains. AFAIK this is done for MemUses, I don't think it's done for MemDefs.

Cool, makes sense. Thank you!
Nuno

[asbirlea]

Rebase after ModRefInfo and MemorySSA changes.

[asbirlea]

API change and review ping.

[asbirlea]

clang-format

[george.burgess.iv]

Overall approach looks good to me. Just a few naming/refactoring nits and I'm happy to stamp this. Sorry for taking so long to get back to it

include/llvm/Analysis/MemorySSA.h

258

Is this the type of the defining access, or of the optimized access? (They're identical for Uses, but not for Defs) I assume it's the latter, but if not, the rest of this comment is just noise. :)

In a perfect world, I think the right thing here would be to hide this and have the walker return it as part of getClobberingMemoryAccess(). I also realize that we have workarounds in place because MSSA's walker takes ~forever in some cases, so this 'ideal' API probably won't work so well yet. :(

So, as a compromise, might it be good to rename this getOptimizedAccessType(), with a comment that it might disappear and become part of the walker's return value instead?

277–282

Continuing with my assumption that AliasWithDefining is talking about the optimized access, can we rename to setOptimizedAccessType?

296

ping :)

lib/Analysis/MemorySSA.cpp

255

Nit: parens are redundant

530

Nit: no else after a return

2086

Nit: reflow this comment to 80-cols, please. (In vim, gq will do what you want. Otherwise, joining the lines + running clang-tidy should split it up properly.)

2116

(So... I had "That WFM. If we decide to go that way, please also add a comment explaining what it means if definingIsMayAlias returns false." that I never submitted. Is this thread still relevant? I don't see definingIsMayAlias anywhere but here...)

unittests/Analysis/MemorySSA.cpp

1067

Nit: it looks like (?) we're iterating over the same list in the same order in the other two loops. Can we pop it in a local array or initializer_list or something, then use that as the container for these loops?

[asbirlea]

Address comments.

[asbirlea]

include/llvm/Analysis/MemorySSA.h

296

Done, using 3 bits, 2 for AliasResult and 1 for None.

lib/Analysis/MemorySSA.cpp

2116

I used dberlin's advice to "use the AliasResult type", so the only accessor now is definingAccessType() renamed to getOptimizedAccessType(). This returns an AliasResult. The setter also gets an AliasResult.
Per offline discussion, updated to use an Optional<AliasResult>, where None is used when the optimized access is LiveOnEntry.

[george.burgess.iv]

A bundle of nitpicks for you. LGTM assuming those get addressed.

Thanks for working on this!

include/llvm/Analysis/MemorySSA.h

298

nit: newFunctionsShouldStartWithALowerCaseLetter :)

298

nit: static?

301

Nit: (int)OAR.getValueOr(4);? Or does that require awkward casting? If it does need additional casting, I'm happy with this as-is.

304

Same casing + static nits

305

Should this accept 6 and 7? I thought the values were {May,Must,Partial,No}Alias (for 0-3) and None (for 4)

307

Nit: if (

lib/Analysis/MemorySSA.cpp

2116

SGTM.

[asbirlea]

Address comments.

include/llvm/Analysis/MemorySSA.h

301

The value given as OR is expected to be of the same type inside the Optional, in this case AliasResult. I think it's not a casting issue, but a correctness one; casting the 4 to AliasResult is UB.
Leaving as is, but please correct me if I'm wrong.

[george.burgess.iv]

include/llvm/Analysis/MemorySSA.h

301

Ick, yeah, good call. WFM!

[asbirlea]

Thank you very much for the review!

include/llvm/Analysis/MemorySSA.h

public:
   }
 
   // Sadly, these have to be public because they are needed in some of the
   // iterators.
   inline bool isOptimized() const;
   inline MemoryAccess *getOptimized() const;
   inline void setOptimized(MemoryAccess *);
 
+  bool definingAccessMayAlias() const { return !isMustAlias; }
+
+  bool definingAccessMustAlias() const { return isMustAlias; }
+
   /// \brief Reset the ID of what this MemoryUse was optimized to, causing it to
   /// be rewalked by the walker if necessary.
   /// This really should only be called by tests.
   inline void resetOptimized();
 
 protected:
   friend class MemorySSA;
   friend class MemorySSAUpdater;
 
   MemoryUseOrDef(LLVMContext &C, MemoryAccess *DMA, unsigned Vty,
                  DeleteValueTy DeleteValue, Instruction *MI, BasicBlock *BB)
       : MemoryAccess(C, Vty, DeleteValue, BB, 1), MemoryInst(MI) {
     setDefiningAccess(DMA);
   }
 
-  void setDefiningAccess(MemoryAccess *DMA, bool Optimized = false) {
+  void setDefiningToMayAlias() { isMustAlias = false; }
+
+  void setDefiningToMustAlias() { isMustAlias = true; }
+
+  void setDefiningAccess(MemoryAccess *DMA, bool Optimized = false,
+                         bool IsMustAlias = false) {
     if (!Optimized) {
+      // FIXME: is this redundant?
+      resetOptimized();
+      setDefiningToMayAlias();
       setOperand(0, DMA);
       return;
     }
+    isMustAlias = IsMustAlias;
     setOptimized(DMA);
   }
 
 private:
   Instruction *MemoryInst;
+  bool isMustAlias;
 };
 
 template <>
 struct OperandTraits<MemoryUseOrDef>
     : public FixedNumOperandTraits<MemoryUseOrDef, 1> {};
 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryUseOrDef, MemoryAccess)
 
 /// \brief Represents read-only accesses to memory
 ///
 /// In particular, the set of Instructions that will be represented by
 /// MemoryUse's is exactly the set of Instructions for which
 /// AliasAnalysis::getModRefInfo returns "Ref".
 class MemoryUse final : public MemoryUseOrDef {
 public:
   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess);
 
   MemoryUse(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB)
       : MemoryUseOrDef(C, DMA, MemoryUseVal, deleteMe, MI, BB) {}
 

lib/Analysis/MemorySSA.cpp

static Reorderability getLoadReorderability(const LoadInst *Use,
   if (SeqCstUse || MayClobberIsAcquire)
     return Reorderability::Never;
   return Result;
 }
 
 static bool instructionClobbersQuery(MemoryDef *MD,
                                      const MemoryLocation &UseLoc,
                                      const Instruction *UseInst,
-                                     AliasAnalysis &AA) {
+                                     AliasAnalysis &AA, bool &FoundMustAlias) {
   Instruction *DefInst = MD->getMemoryInst();
   assert(DefInst && "Defining instruction not actually an instruction");
   ImmutableCallSite UseCS(UseInst);
 
   if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(DefInst)) {
     // These intrinsics will show up as affecting memory, but they are just
     // markers.
+    bool isMustAlias;
     switch (II->getIntrinsicID()) {
     case Intrinsic::lifetime_start:
       if (UseCS)
         return false;
-      return AA.isMustAlias(MemoryLocation(II->getArgOperand(1)), UseLoc);
+      isMustAlias =
+          AA.isMustAlias(MemoryLocation(II->getArgOperand(1)), UseLoc);
+      if (isMustAlias)
+        FoundMustAlias = true;
+      return isMustAlias;
     case Intrinsic::lifetime_end:
     case Intrinsic::invariant_start:
     case Intrinsic::invariant_end:
     case Intrinsic::assume:
       return false;
     default:
       break;
     }
   }
 
   if (UseCS) {
     ModRefInfo I = AA.getModRefInfo(DefInst, UseCS);
     return I != MRI_NoModRef;
   }
 
   if (auto *DefLoad = dyn_cast<LoadInst>(DefInst)) {
     if (auto *UseLoad = dyn_cast<LoadInst>(UseInst)) {
       switch (getLoadReorderability(UseLoad, DefLoad)) {
       case Reorderability::Always:
         return false;
       case Reorderability::Never:
         return true;
       case Reorderability::IfNoAlias:
-        return !AA.isNoAlias(UseLoc, MemoryLocation::get(DefLoad));
+        AliasResult AResult = AA.alias(MemoryLocation::get(DefLoad), UseLoc);
+        if (AResult == MustAlias)
+          FoundMustAlias = true;
+        return AResult != NoAlias;
       }
     }
   }
 
+  Optional<MemoryLocation> DefLoc = MemoryLocation::getOrNone(DefInst);
+  if (DefLoc == None)
+    return AA.getModRefInfo(DefInst, UseLoc) & MRI_Mod;
+  else {
+    AliasResult AResult = AA.alias(DefLoc.getValue(), UseLoc);
+    if (AResult == MustAlias)
+      FoundMustAlias = true;
+    // Must return if location is modified, not AResult != NoAlias;
     return AA.getModRefInfo(DefInst, UseLoc) & MRI_Mod;
   }
+}
 
 static bool instructionClobbersQuery(MemoryDef *MD, const MemoryUseOrDef *MU,
                                      const MemoryLocOrCall &UseMLOC,
-                                     AliasAnalysis &AA) {
+                                     AliasAnalysis &AA, bool &FoundMustAlias) {
   // FIXME: This is a temporary hack to allow a single instructionClobbersQuery
   // to exist while MemoryLocOrCall is pushed through places.
   if (UseMLOC.IsCall)
     return instructionClobbersQuery(MD, MemoryLocation(), MU->getMemoryInst(),
-                                    AA);
-  return instructionClobbersQuery(MD, UseMLOC.getLoc(), MU->getMemoryInst(),
-                                  AA);
+                                    AA, FoundMustAlias);
+  return instructionClobbersQuery(MD, UseMLOC.getLoc(), MU->getMemoryInst(), AA,
+                                  FoundMustAlias);
 }
 
 // Return true when MD may alias MU, return false otherwise.
 bool MemorySSAUtil::defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU,
                                         AliasAnalysis &AA) {
-  return instructionClobbersQuery(MD, MU, MemoryLocOrCall(MU), AA);
+  bool FoundMustAlias;
+  return instructionClobbersQuery(MD, MU, MemoryLocOrCall(MU), AA,
+                                  FoundMustAlias);
 }
 
 namespace {
 
 struct UpwardsMemoryQuery {
   // True if our original query started off as a call
   bool IsCall = false;
   // The pointer location we started the query with. This will be empty if
   // IsCall is true.
   MemoryLocation StartingLoc;
   // This is the instruction we were querying about.
   const Instruction *Inst = nullptr;
   // The MemoryAccess we actually got called with, used to test local domination
   const MemoryAccess *OriginalAccess = nullptr;
+  bool FoundMustAlias = false;
 
   UpwardsMemoryQuery() = default;
 
   UpwardsMemoryQuery(const Instruction *Inst, const MemoryAccess *Access)
       : IsCall(ImmutableCallSite(Inst)), Inst(Inst), OriginalAccess(Access) {
     if (!IsCall)
       StartingLoc = MemoryLocation::get(Inst);
   }
checkClobberSanity(MemoryAccess *Start, MemoryAccess *ClobberAt,
 
   if (MSSA.isLiveOnEntryDef(Start)) {
     assert(MSSA.isLiveOnEntryDef(ClobberAt) &&
            "liveOnEntry must clobber itself");
     return;
   }
 
   bool FoundClobber = false;
+  bool FoundMustAlias;
   DenseSet<MemoryAccessPair> VisitedPhis;
   SmallVector<MemoryAccessPair, 8> Worklist;
   Worklist.emplace_back(Start, StartLoc);
   // Walk all paths from Start to ClobberAt, while looking for clobbers. If one
   // is found, complain.
   while (!Worklist.empty()) {
     MemoryAccessPair MAP = Worklist.pop_back_val();
     // All we care about is that nothing from Start to ClobberAt clobbers Start.
     // We learn nothing from revisiting nodes.
     if (!VisitedPhis.insert(MAP).second)
       continue;
 
     for (MemoryAccess *MA : def_chain(MAP.first)) {
       if (MA == ClobberAt) {
         if (auto *MD = dyn_cast<MemoryDef>(MA)) {
           // instructionClobbersQuery isn't essentially free, so don't use `|=`,
           // since it won't let us short-circuit.
           //
           // Also, note that this can't be hoisted out of the `Worklist` loop,
           // since MD may only act as a clobber for 1 of N MemoryLocations.
-          FoundClobber =
-              FoundClobber || MSSA.isLiveOnEntryDef(MD) ||
-              instructionClobbersQuery(MD, MAP.second, Query.Inst, AA);
+          FoundClobber = FoundClobber || MSSA.isLiveOnEntryDef(MD) ||
+                         instructionClobbersQuery(MD, MAP.second, Query.Inst,
+                                                  AA, FoundMustAlias);
         }
         break;
       }
 
       // We should never hit liveOnEntry, unless it's the clobber.
       assert(!MSSA.isLiveOnEntryDef(MA) && "Hit liveOnEntry before clobber?");
 
       if (auto *MD = dyn_cast<MemoryDef>(MA)) {
         (void)MD;
-        assert(!instructionClobbersQuery(MD, MAP.second, Query.Inst, AA) &&
+        assert(!instructionClobbersQuery(MD, MAP.second, Query.Inst, AA,
+                                         FoundMustAlias) &&
                "Found clobber before reaching ClobberAt!");
         continue;
       }
 
       assert(isa<MemoryPhi>(MA));
       Worklist.append(upward_defs_begin({MA, MAP.second}), upward_defs_end());
     }
   }
while ((Node = Node->getIDom())) {
         return &*Defs->rbegin();
     }
     return Result;
   }
 
   /// Result of calling walkToPhiOrClobber.
   struct UpwardsWalkResult {
     /// The "Result" of the walk. Either a clobber, the last thing we walked, or
-    /// both.
+    /// both. Include alias info when clobber found.
     MemoryAccess *Result;
     bool IsKnownClobber;
+    bool FoundMustAlias;
   };
 
   /// Walk to the next Phi or Clobber in the def chain starting at Desc.Last.
   /// 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 {
     assert(!isa<MemoryUse>(Desc.Last) && "Uses don't exist in my world");
 
+    bool FoundMustAlias = false;
     for (MemoryAccess *Current : def_chain(Desc.Last)) {
       Desc.Last = Current;
       if (Current == StopAt)
-        return {Current, false};
+        return {Current, false, FoundMustAlias};
 
       if (auto *MD = dyn_cast<MemoryDef>(Current))
         if (MSSA.isLiveOnEntryDef(MD) ||
-            instructionClobbersQuery(MD, Desc.Loc, Query->Inst, AA))
-          return {MD, true};
+            instructionClobbersQuery(MD, Desc.Loc, Query->Inst, AA,
+                                     FoundMustAlias))
+          return {MD, true, FoundMustAlias};
     }
 
     assert(isa<MemoryPhi>(Desc.Last) &&
            "Ended at a non-clobber that's not a phi?");
-    return {Desc.Last, false};
+    return {Desc.Last, false, false};
   }
 
   void addSearches(MemoryPhi *Phi, SmallVectorImpl<ListIndex> &PausedSearches,
                    ListIndex PriorNode) {
     auto UpwardDefs = make_range(upward_defs_begin({Phi, Paths[PriorNode].Loc}),
                                  upward_defs_end());
     for (const MemoryAccessPair &P : UpwardDefs) {
       PausedSearches.push_back(Paths.size());
MemoryAccess *findClobber(MemoryAccess *Start, UpwardsMemoryQuery &Q) {
 
     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.FoundMustAlias = WalkResult.FoundMustAlias;
     } else {
       OptznResult OptRes = tryOptimizePhi(cast<MemoryPhi>(FirstDesc.Last),
                                           Current, Q.StartingLoc);
       verifyOptResult(OptRes);
       resetPhiOptznState();
       Result = OptRes.PrimaryClobber.Clobber;
     }
 
 #ifdef EXPENSIVE_CHECKS
     checkClobberSanity(Current, Result, Q.StartingLoc, MSSA, Q, AA);
 #endif
     return Result;
   }
 
struct MemlocStackInfo {
     // the place the last stack walk ended.
     // Note: Correctness depends on this being initialized to 0, which densemap
     // does
     unsigned long LowerBound;
     const BasicBlock *LowerBoundBlock;
     // This is where the last walk for this memory location ended.
     unsigned long LastKill;
     bool LastKillValid;
+    bool MustAlias;
   };
 
   void optimizeUsesInBlock(const BasicBlock *, unsigned long &, unsigned long &,
                            SmallVectorImpl<MemoryAccess *> &,
                            DenseMap<MemoryLocOrCall, MemlocStackInfo> &);
 
   MemorySSA *MSSA;
   MemorySSAWalker *Walker;
for (MemoryAccess &MA : *Accesses) {
     auto *MU = dyn_cast<MemoryUse>(&MA);
     if (!MU) {
       VersionStack.push_back(&MA);
       ++StackEpoch;
       continue;
     }
 
     if (isUseTriviallyOptimizableToLiveOnEntry(*AA, MU->getMemoryInst())) {
-      MU->setDefiningAccess(MSSA->getLiveOnEntryDef(), true);
+      MU->setDefiningAccess(MSSA->getLiveOnEntryDef(), true, true);
       continue;
     }
 
     MemoryLocOrCall UseMLOC(MU);
     auto &LocInfo = LocStackInfo[UseMLOC];
     // If the pop epoch changed, it means we've removed stuff from top of
     // stack due to changing blocks. We may have to reset the lower bound or
     // last kill info.
if (LocInfo.PopEpoch != PopEpoch) {
       // new things on the stack, because we've checked everything before.  In
       // this case, the lower bound of things to check remains the same.
       LocInfo.PopEpoch = PopEpoch;
       LocInfo.StackEpoch = StackEpoch;
     }
     if (!LocInfo.LastKillValid) {
       LocInfo.LastKill = VersionStack.size() - 1;
       LocInfo.LastKillValid = true;
+      LocInfo.MustAlias = false;
     }
 
     // At this point, we should have corrected last kill and LowerBound to be
     // in bounds.
     assert(LocInfo.LowerBound < VersionStack.size() &&
            "Lower bound out of range");
     assert(LocInfo.LastKill < VersionStack.size() &&
            "Last kill info out of range");
while (UpperBound > LocInfo.LowerBound) {
 
       MemoryDef *MD = cast<MemoryDef>(VersionStack[UpperBound]);
       // If the lifetime of the pointer ends at this instruction, it's live on
       // entry.
       if (!UseMLOC.IsCall && lifetimeEndsAt(MD, UseMLOC.getLoc(), *AA)) {
         // Reset UpperBound to liveOnEntryDef's place in the stack
         UpperBound = 0;
         FoundClobberResult = true;
+        LocInfo.MustAlias = true;
         break;
       }
-      if (instructionClobbersQuery(MD, MU, UseMLOC, *AA)) {
+      if (instructionClobbersQuery(MD, MU, UseMLOC, *AA, LocInfo.MustAlias)) {
         FoundClobberResult = true;
         break;
       }
       --UpperBound;
     }
+
+    // Note: Phis always have MustAlias set to false ATM.
+
     // At the end of this loop, UpperBound is either a clobber, or lower bound
     // PHI walking may cause it to be < LowerBound, and in fact, < LastKill.
     if (FoundClobberResult || UpperBound < LocInfo.LastKill) {
-      MU->setDefiningAccess(VersionStack[UpperBound], true);
       // We were last killed now by where we got to
+      if (MSSA->isLiveOnEntryDef(VersionStack[UpperBound]))
+        LocInfo.MustAlias = true;
+      MU->setDefiningAccess(VersionStack[UpperBound], true, LocInfo.MustAlias);
       LocInfo.LastKill = UpperBound;
     } else {
       // Otherwise, we checked all the new ones, and now we know we can get to
       // LastKill.
-      MU->setDefiningAccess(VersionStack[LocInfo.LastKill], true);
+      MU->setDefiningAccess(VersionStack[LocInfo.LastKill], true,
+                            LocInfo.MustAlias);
     }
     LocInfo.LowerBound = VersionStack.size() - 1;
     LocInfo.LowerBoundBlock = BB;
   }
 }
 
 /// Optimize uses to point to their actual clobbering definitions.
 void MemorySSA::OptimizeUses::optimizeUses() {

 MemoryAccess *
 MemorySSA::CachingWalker::getClobberingMemoryAccess(MemoryAccess *MA) {
   auto *StartingAccess = dyn_cast<MemoryUseOrDef>(MA);
   // If this is a MemoryPhi, we can't do anything.
   if (!StartingAccess)
     return MA;
 
   // If this is an already optimized use or def, return the optimized result.
-  // Note: Currently, we do not store the optimized def result because we'd need
-  // a separate field, since we can't use it as the defining access.
+  // Note: Currently, we store the optimized def result in
+  // a separate field, since we can't use the defining access.
   if (auto *MUD = dyn_cast<MemoryUseOrDef>(StartingAccess))
     if (MUD->isOptimized())
       return MUD->getOptimized();
 
   const Instruction *I = StartingAccess->getMemoryInst();
   UpwardsMemoryQuery Q(I, StartingAccess);
   // We can't sanely do anything with a fences, they conservatively
   // clobber all memory, and have no locations to get pointers from to
   // try to disambiguate.
   if (!Q.IsCall && I->isFenceLike())
     return StartingAccess;
 
   if (isUseTriviallyOptimizableToLiveOnEntry(*MSSA->AA, I)) {
     MemoryAccess *LiveOnEntry = MSSA->getLiveOnEntryDef();
-    if (auto *MUD = dyn_cast<MemoryUseOrDef>(StartingAccess))
+    if (auto *MUD = dyn_cast<MemoryUseOrDef>(StartingAccess)) {
       MUD->setOptimized(LiveOnEntry);
+      MUD->setDefiningToMustAlias();
+    }
     return LiveOnEntry;
   }
 
   // Start with the thing we already think clobbers this location
   MemoryAccess *DefiningAccess = StartingAccess->getDefiningAccess();
 
   // 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))
+  if (MSSA->isLiveOnEntryDef(DefiningAccess)) {
+    if (auto *MUD = dyn_cast<MemoryUseOrDef>(StartingAccess)) {
+      MUD->setOptimized(DefiningAccess);
+      MUD->setDefiningToMustAlias();
+    }
     return DefiningAccess;
+  }
 
   MemoryAccess *Result = getClobberingMemoryAccess(DefiningAccess, Q);
   DEBUG(dbgs() << "Starting Memory SSA clobber for " << *I << " is ");
   DEBUG(dbgs() << *DefiningAccess << "\n");
   DEBUG(dbgs() << "Final Memory SSA clobber for " << *I << " is ");
   DEBUG(dbgs() << *Result << "\n");
-  if (auto *MUD = dyn_cast<MemoryUseOrDef>(StartingAccess))
+
+  if (auto *MUD = dyn_cast<MemoryUseOrDef>(StartingAccess)) {
     MUD->setOptimized(Result);
+    if (MSSA->isLiveOnEntryDef(Result) || Q.FoundMustAlias)
+      MUD->setDefiningToMustAlias();
+  }
 
   return Result;
 }
 
 MemoryAccess *
 DoNothingMemorySSAWalker::getClobberingMemoryAccess(MemoryAccess *MA) {
   if (auto *Use = dyn_cast<MemoryUseOrDef>(MA))
     return Use->getDefiningAccess();

unittests/Analysis/MemorySSA.cpp

TEST_F(MemorySSATest, Irreducible) {
   MemorySSAUpdater Updater(&MSSA);
   // Create the load memory acccess
   LoadInst *LoadInst = B.CreateLoad(FirstArg);
   MemoryUse *LoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(
       LoadInst, nullptr, AfterLoopBB, MemorySSA::Beginning));
   Updater.insertUse(LoadAccess);
   MSSA.verifyMemorySSA();
 }
+
+// Test Must alias for optimized uses
+TEST_F(MemorySSATest, TestLoadMustAlias) {
+  F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),
+                       GlobalValue::ExternalLinkage, "F", &M);
+  B.SetInsertPoint(BasicBlock::Create(C, "", F));
+  Type *Int8 = Type::getInt8Ty(C);
+  Value *AllocaA = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");
+  Value *AllocaB = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "B");
+
+  B.CreateStore(ConstantInt::get(Int8, 1), AllocaB);
+  // Check load from LOE
+  LoadInst *LA1 = B.CreateLoad(AllocaA, "");
+  // Check load alias cached for second load
+  LoadInst *LA2 = B.CreateLoad(AllocaA, "");
+
+  B.CreateStore(ConstantInt::get(Int8, 1), AllocaA);
+  // Check load from store/def
+  LoadInst *LA3 = B.CreateLoad(AllocaA, "");
+  // Check load alias cached for second load
+  LoadInst *LA4 = B.CreateLoad(AllocaA, "");
+
+  setupAnalyses();
+  MemorySSA &MSSA = *Analyses->MSSA;
+
+  unsigned I = 0;
+  for (LoadInst *V : {LA1, LA2, LA3, LA4}) {
+    MemoryUse *MemUse = dyn_cast_or_null<MemoryUse>(MSSA.getMemoryAccess(V));
+    EXPECT_EQ(MemUse->definingAccessMustAlias(), true)
+        << "Load " << I << " doesn't have the correct alias information";
+    // EXPECT_EQ expands such that if we increment I above, it won't get
+    // incremented except when we try to print the error message.
+    ++I;
+  }
+}
+
+// Test Must alias for optimized defs.
+TEST_F(MemorySSATest, TestStoreMustAlias) {
+  F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),
+                       GlobalValue::ExternalLinkage, "F", &M);
+  B.SetInsertPoint(BasicBlock::Create(C, "", F));
+  Type *Int8 = Type::getInt8Ty(C);
+  Value *AllocaA = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");
+  Value *AllocaB = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "B");
+  StoreInst *SA1 = B.CreateStore(ConstantInt::get(Int8, 1), AllocaA);
+  StoreInst *SB1 = B.CreateStore(ConstantInt::get(Int8, 1), AllocaB);
+  StoreInst *SA2 = B.CreateStore(ConstantInt::get(Int8, 2), AllocaA);
+  StoreInst *SB2 = B.CreateStore(ConstantInt::get(Int8, 2), AllocaB);
+  StoreInst *SA3 = B.CreateStore(ConstantInt::get(Int8, 3), AllocaA);
+  StoreInst *SB3 = B.CreateStore(ConstantInt::get(Int8, 3), AllocaB);
+
+  setupAnalyses();
+  MemorySSA &MSSA = *Analyses->MSSA;
+  MemorySSAWalker *Walker = Analyses->Walker;
+
+  unsigned I = 0;
+  for (StoreInst *V : {SA1, SB1, SA2, SB2, SA3, SB3}) {
+    MemoryDef *MemDef = dyn_cast_or_null<MemoryDef>(MSSA.getMemoryAccess(V));
+    EXPECT_EQ(MemDef->isOptimized(), false)
+        << "Store " << I << " is optimized from the start?";
+    EXPECT_EQ(MemDef->definingAccessMustAlias(), false)
+        << "Store " << I
+        << " has correct alias information before being optimized?";
+    if (V == SA1)
+      Walker->getClobberingMemoryAccess(V);
+    else {
+      MemoryAccess *Def = MemDef->getDefiningAccess();
+      MemoryAccess *Clob = Walker->getClobberingMemoryAccess(V);
+      EXPECT_NE(Def, Clob) << "Store " << I
+                           << " has Defining Access equal to Clobbering Access";
+    }
+    EXPECT_EQ(MemDef->isOptimized(), true)
+        << "Store " << I << " was not optimized";
+    EXPECT_EQ(MemDef->definingAccessMustAlias(), true)
+        << "Store " << I << " doesn't have the correct alias information";
+    // EXPECT_EQ expands such that if we increment I above, it won't get
+    // incremented except when we try to print the error message.
+    ++I;
+  }
+}
+
+// Test May alias for optimized uses.
+TEST_F(MemorySSATest, TestLoadMayAlias) {
+  F = Function::Create(FunctionType::get(B.getVoidTy(),
+                                         {B.getInt8PtrTy(), B.getInt8PtrTy()},
+                                         false),
+                       GlobalValue::ExternalLinkage, "F", &M);
+  B.SetInsertPoint(BasicBlock::Create(C, "", F));
+  Type *Int8 = Type::getInt8Ty(C);
+  auto *ArgIt = F->arg_begin();
+  Argument *PointerA = &*ArgIt;
+  Argument *PointerB = &*(++ArgIt);
+  B.CreateStore(ConstantInt::get(Int8, 1), PointerB);
+  LoadInst *LA1 = B.CreateLoad(PointerA, "");
+  B.CreateStore(ConstantInt::get(Int8, 0), PointerA);
+  LoadInst *LB1 = B.CreateLoad(PointerB, "");
+  B.CreateStore(ConstantInt::get(Int8, 0), PointerA);
+  LoadInst *LA2 = B.CreateLoad(PointerA, "");
+  B.CreateStore(ConstantInt::get(Int8, 0), PointerB);
+  LoadInst *LB2 = B.CreateLoad(PointerB, "");
+
+  setupAnalyses();
+  MemorySSA &MSSA = *Analyses->MSSA;
+
+  unsigned I = 0;
+  for (LoadInst *V : {LA1, LB1}) {
+    MemoryUse *MemUse = dyn_cast_or_null<MemoryUse>(MSSA.getMemoryAccess(V));
+    EXPECT_EQ(MemUse->definingAccessMayAlias(), true)
+        << "Load " << I << " doesn't have the correct alias information";
+    // EXPECT_EQ expands such that if we increment I above, it won't get
+    // incremented except when we try to print the error message.
+    ++I;
+  }
+  for (LoadInst *V : {LA2, LB2}) {
+    MemoryUse *MemUse = dyn_cast_or_null<MemoryUse>(MSSA.getMemoryAccess(V));
+    EXPECT_EQ(MemUse->definingAccessMayAlias(), false)
+        << "Load " << I << " doesn't have the correct alias information";
+    // EXPECT_EQ expands such that if we increment I above, it won't get
+    // incremented except when we try to print the error message.
+    ++I;
+  }
+}
+
+// Test May alias for optimized defs.
+TEST_F(MemorySSATest, TestStoreMayAlias) {
+  F = Function::Create(FunctionType::get(B.getVoidTy(),
+                                         {B.getInt8PtrTy(), B.getInt8PtrTy()},
+                                         false),
+                       GlobalValue::ExternalLinkage, "F", &M);
+  B.SetInsertPoint(BasicBlock::Create(C, "", F));
+  Type *Int8 = Type::getInt8Ty(C);
+  auto *ArgIt = F->arg_begin();
+  Argument *PointerA = &*ArgIt;
+  Argument *PointerB = &*(++ArgIt);
+  Value *AllocaC = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "C");
+  // Store into arg1, must alias because it's LOE => must
+  StoreInst *SA1 = B.CreateStore(ConstantInt::get(Int8, 0), PointerA);
+  // Store into arg2, may alias store to arg1 => may
+  StoreInst *SB1 = B.CreateStore(ConstantInt::get(Int8, 1), PointerB);
+  // Store into aloca, no alias with args, so must alias LOE => must
+  StoreInst *SC1 = B.CreateStore(ConstantInt::get(Int8, 2), AllocaC);
+  // Store into arg1, may alias store to arg2 => may
+  StoreInst *SA2 = B.CreateStore(ConstantInt::get(Int8, 3), PointerA);
+  // Store into arg2, may alias store to arg1 => may
+  StoreInst *SB2 = B.CreateStore(ConstantInt::get(Int8, 4), PointerB);
+  // Store into aloca, no alias with args, so must alias SC1 => must
+  StoreInst *SC2 = B.CreateStore(ConstantInt::get(Int8, 5), AllocaC);
+  // Store into arg2, must alias store to arg2 => must
+  StoreInst *SB3 = B.CreateStore(ConstantInt::get(Int8, 6), PointerB);
+
+  setupAnalyses();
+  MemorySSA &MSSA = *Analyses->MSSA;
+  MemorySSAWalker *Walker = Analyses->Walker;
+
+  unsigned I = 0;
+  for (StoreInst *V : {SA1, SB1, SC1, SA2, SB2, SC2, SB3}) {
+    MemoryDef *MemDef = dyn_cast_or_null<MemoryDef>(MSSA.getMemoryAccess(V));
+    EXPECT_EQ(MemDef->isOptimized(), false)
+        << "Store " << I << " is optimized from the start?";
+    EXPECT_EQ(MemDef->definingAccessMustAlias(), false)
+        << "Store " << I
+        << " has correct alias information before being optimized?";
+    ++I;
+  }
+
+  for (StoreInst *V : {SA1, SB1, SC1, SA2, SB2, SC2, SB3})
+    Walker->getClobberingMemoryAccess(V);
+
+  I = 0;
+  for (StoreInst *V : {SA1, SB1, SC1, SA2, SB2, SC2, SB3}) {
+    MemoryDef *MemDef = dyn_cast_or_null<MemoryDef>(MSSA.getMemoryAccess(V));
+    EXPECT_EQ(MemDef->isOptimized(), true)
+        << "Store " << I << " was not optimized";
+    if (I == 1 || I == 3 || I == 4)
+      EXPECT_EQ(MemDef->definingAccessMayAlias(), true)
+          << "Store " << I << " doesn't have the correct alias information";
+    else
+      EXPECT_EQ(MemDef->definingAccessMustAlias(), true)
+          << "Store " << I << " doesn't have the correct alias information";
+    // EXPECT_EQ expands such that if we increment I above, it won't get
+    // incremented except when we try to print the error message.
+    ++I;
+  }
+}