Allow None as a MemoryLocation to getModRefInfo, use it to start cleaning up interfaces and uses

[• dberlin]

Summary

Currently, we have instructions which affect memory but have no memory
location. If you call, for example, MemoryLocation::get on a fence,
it asserts. This means things specifically have to avoid that. It
also means we end up with a copy of each API, one taking a memory
location, one not.

This starts to fix that.

We add MemoryLocation::getOrNone as a new call, and reimplement the
old asserting version in terms of it.

We make MemoryLocation optional in the (Instruction, MemoryLocation)
version of getModRefInfo, and kill the old one argument version in
favor of passing None (it had one caller). Now both can handle fences
because you can just use MemoryLocation::getOrNone on an instruction
and it will return a correct answer.

We use all this to clean up part of MemorySSA that had to handle this difference.

Note that literally every actual getModRefInfo interface we have could be made private and replaced with:

getModRefInfo(Instruction, Optional<MemoryLocation>)
and
getModRefInfo(Instruction, Optional<MemoryLocation>, Instruction, Optional<MemoryLocation>)

and delegating to the right ones, if we wanted to.

I have not attempted to do this yet.

[• dberlin]

include/llvm/Analysis/AliasAnalysis.h

550

This got clang-formatted when i reformatted the function.

lib/Transforms/Utils/MemorySSA.cpp

110

Sadly, we have to implement all of this because Optional has a non-trivial destructor/etc

[dblaikie]

include/llvm/Analysis/MemoryLocation.h

71–72

omit 'else' after return ( http://llvm.org/docs/CodingStandards.html#don-t-use-else-after-a-return )

71–72

Consider a switch over the inst kind enum to reduce the work repeatedly done by dyn_cast (at least it seems like LLVM code often uses a switch over enum rather than chained dyn_cast - I don't actually know if the overhead is real)

72

This is using reference lifetime extension probably unintentionally, may be better to write it more directly as:

Optional<MemoryLocation> Loc = ...;

73–74

Optional already has the assert in it, so unless you particularly want that assert text/message, you could write this as:

return *MemoryLocation.getOrNone(Inst);

lib/Transforms/Utils/MemorySSA.cpp

146

You can write this as "return *Loc;" if you like.

149

Should this assert !IsCall?

162–163

Does !IsCall imply that Loc.hasValue() ? (or can the "None" state of Loc be used in some cases) Judging by "getLoc" I'm guessing it does imply that.

If it does imply that, then Optional's hasValue tracking is wasted space. Wonder if there's a nice abstraction that should exist for this case, but I'm not sure.

I ask partly because the use of Optional maybe makes that invariant non-obvious so a better matched abstraction may make the code easier to understand.

[• dberlin]

include/llvm/Analysis/MemoryLocation.h

71–72

So i didn't write this, and i'm happy to clean it up in a future patch, but i want to not touch it here if that's okay, as i would like the patch to change as little as possible :)

If you stare at MemoryLocation.cpp, you'll see that basically all of these are doing the same thing, and probably could stand a bit of templating.

Honestly, at this point, we may just want to make the memory instructions able to return a memorylocation in Instructions.h.
Who knows.

73–74

I was trying to duplicate the exact functionality of the existing code, but happy to change it.

lib/Transforms/Utils/MemorySSA.cpp

149

No.
Actually, we expect calls to return None here.

162–163

"If it does imply that, then Optional's hasValue tracking is wasted space. Wonder if there's a nice abstraction that should exist for this case, but I'm not sure."
Yes, it's a bit of waste space. We could have a traits that lets you reuse a bit in the thing you are making optional, and use that. That is how we do a lot of "use this thing, but storage is external" in LLVM.
But not sure it's worth it.

In reality, this entire class is working around a bit of api deficiency, IMHO.

We want ways to make "hashtable of memory locations", but calls don't have memory locations (or more accurately, they have multiple ones).

IE you really want to be able to say "the last time i saw this abstract memory area, it had this value".

But we only can do that for non-call instructions.
So either we have one mapping for calls, and none for non-calls, which ends up a different kind of ugly, or we have a class like this that tries to encapsulate the difference.

In practice, all of this should go away at some point, and we should come up with a clean API that allows mapping/caching memory locations to other things, without the current mess, because nobody should have to care about this :)

Even if that is really "MLocOrCall becomes the new MemoryLocation".

[• dberlin]

include/llvm/Analysis/MemoryLocation.h

71–72

I gave up and fixed it since it looks nicer that way anyway :)

[• dberlin]

• Update for review comments

[davide]

Some nits inline.

include/llvm/Analysis/AliasAnalysis.h

530–544

can you use static_cast<> here instead (and if you feel motivated change the surrounding statements to do the same)?

include/llvm/Analysis/MemoryLocation.h

19–20

Unsorted.

[asbirlea]

FYI, patch should also update:
unittests/Analysis/AliasAnalysisTest.cpp:193-204

include/llvm/Analysis/AliasAnalysis.h

 //    MustAlias at the same time. The current API can only return one result,
 //    though this is rarely a problem in practice.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_ALIASANALYSIS_H
 #define LLVM_ANALYSIS_ALIASANALYSIS_H
 
+#include "llvm/ADT/Optional.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 
 namespace llvm {
 class BasicAAResult;
public:
   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) {
     return getModRefInfo(I, MemoryLocation(P, Size));
   }
 
-  /// Check whether or not an instruction may read or write memory (without
-  /// regard to a specific location).
+  /// 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
+  /// for example.
   ///
   /// For function calls, this delegates to the alias-analysis specific
-  /// call-site mod-ref behavior queries. Otherwise it delegates to the generic
-  /// mod ref information query without a location.
-  ModRefInfo getModRefInfo(const Instruction *I) {
+  /// call-site mod-ref behavior queries. Otherwise it delegates to specific
+  /// helpers above.
+  ModRefInfo getModRefInfo(const Instruction *I,
+                           const Optional<MemoryLocation> &OptLoc) {
+    if (OptLoc == None) {
       if (auto CS = ImmutableCallSite(I)) {
         auto MRB = getModRefBehavior(CS);
         if ((MRB & MRI_ModRef) == MRI_ModRef)
           return MRI_ModRef;
         if (MRB & MRI_Ref)
           return MRI_Ref;
         if (MRB & MRI_Mod)
           return MRI_Mod;
         return MRI_NoModRef;
       }
-
-    return getModRefInfo(I, MemoryLocation());
     }
-
-  /// Check whether or not an instruction may read or write the specified
-  /// memory location.
-  ///
-  /// An instruction that doesn't read or write memory may be trivially LICM'd
-  /// for example.
-  ///
-  /// This primarily delegates to specific helpers above.
-  ModRefInfo getModRefInfo(const Instruction *I, const MemoryLocation &Loc) {
+    const MemoryLocation &Loc = OptLoc.getValueOr(MemoryLocation());
     switch (I->getOpcode()) {
-    case Instruction::VAArg:  return getModRefInfo((const VAArgInst*)I, Loc);
-    case Instruction::Load:   return getModRefInfo((const LoadInst*)I,  Loc);
-    case Instruction::Store:  return getModRefInfo((const StoreInst*)I, Loc);
-    case Instruction::Fence:  return getModRefInfo((const FenceInst*)I, Loc);
+    case Instruction::VAArg:
+      return getModRefInfo((const VAArgInst *)I, Loc);
+    case Instruction::Load:
+      return getModRefInfo((const LoadInst *)I, Loc);
+    case Instruction::Store:
+      return getModRefInfo((const StoreInst *)I, Loc);
+    case Instruction::Fence:
+      return getModRefInfo((const FenceInst *)I, Loc);
     case Instruction::AtomicCmpXchg:
-      return getModRefInfo((const AtomicCmpXchgInst*)I, Loc);
+      return getModRefInfo((const AtomicCmpXchgInst *)I, Loc);
     case Instruction::AtomicRMW:
-      return getModRefInfo((const AtomicRMWInst*)I, Loc);
-    case Instruction::Call:   return getModRefInfo((const CallInst*)I,  Loc);
-    case Instruction::Invoke: return getModRefInfo((const InvokeInst*)I,Loc);
+      return getModRefInfo((const AtomicRMWInst *)I, Loc);
+    case Instruction::Call:
+      return getModRefInfo((const CallInst *)I, Loc);
+    case Instruction::Invoke:
+      return getModRefInfo((const InvokeInst *)I, Loc);
     case Instruction::CatchPad:
       return getModRefInfo((const CatchPadInst *)I, Loc);
     case Instruction::CatchRet:
       return getModRefInfo((const CatchReturnInst *)I, Loc);
     default:
       return MRI_NoModRef;
     }
   }
 
   /// A convenience wrapper for constructing the memory location.
   ModRefInfo getModRefInfo(const Instruction *I, const Value *P,
                            uint64_t Size) {
     return getModRefInfo(I, MemoryLocation(P, Size));
   }

include/llvm/Analysis/MemoryLocation.h

 /// These are used both by the Alias Analysis infrastructure and more
 /// specialized memory analysis layers.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_MEMORYLOCATION_H
 #define LLVM_ANALYSIS_MEMORYLOCATION_H
 
+#include "llvm/ADT/Optional.h"
 #include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Metadata.h"
 
 namespace llvm {
 
 class LoadInst;
 class StoreInst;
 class MemTransferInst;
public:
 
   /// Return a location with information about the memory reference by the given
   /// instruction.
   static MemoryLocation get(const LoadInst *LI);
   static MemoryLocation get(const StoreInst *SI);
   static MemoryLocation get(const VAArgInst *VI);
   static MemoryLocation get(const AtomicCmpXchgInst *CXI);
   static MemoryLocation get(const AtomicRMWInst *RMWI);
   static MemoryLocation get(const Instruction *Inst) {
-    if (auto *I = dyn_cast<LoadInst>(Inst))
-      return get(I);
-    else if (auto *I = dyn_cast<StoreInst>(Inst))
-      return get(I);
-    else if (auto *I = dyn_cast<VAArgInst>(Inst))
-      return get(I);
-    else if (auto *I = dyn_cast<AtomicCmpXchgInst>(Inst))
-      return get(I);
-    else if (auto *I = dyn_cast<AtomicRMWInst>(Inst))
-      return get(I);
-    llvm_unreachable("unsupported memory instruction");
+    return *MemoryLocation::getOrNone(Inst);
+  }
+  static Optional<MemoryLocation> getOrNone(const Instruction *Inst) {
+    switch (Inst->getOpcode()) {
+    case Instruction::Load:
+      return get(cast<LoadInst>(Inst));
+    case Instruction::Store:
+      return get(cast<StoreInst>(Inst));
+    case Instruction::VAArg:
+      return get(cast<VAArgInst>(Inst));
+    case Instruction::AtomicCmpXchg:
+      return get(cast<AtomicCmpXchgInst>(Inst));
+    case Instruction::AtomicRMW:
+      return get(cast<AtomicRMWInst>(Inst));
+    default:
+      return None;
+    }
   }
 
   /// Return a location representing the source of a memory transfer.
   static MemoryLocation getForSource(const MemTransferInst *MTI);
 
   /// Return a location representing the destination of a memory set or
   /// transfer.
   static MemoryLocation getForDest(const MemIntrinsic *MI);

lib/Transforms/Scalar/MemCpyOptimizer.cpp

static bool moveUp(AliasAnalysis &AA, StoreInst *SI, Instruction *P,
   // Lifted callsites.
   SmallVector<ImmutableCallSite, 8> CallSites;
 
   const MemoryLocation LoadLoc = MemoryLocation::get(LI);
 
   for (auto I = --SI->getIterator(), E = P->getIterator(); I != E; --I) {
     auto *C = &*I;
 
-    bool MayAlias = AA.getModRefInfo(C) != MRI_NoModRef;
+    bool MayAlias = AA.getModRefInfo(C, None) != MRI_NoModRef;
 
     bool NeedLift = false;
     if (Args.erase(C))
       NeedLift = true;
     else if (MayAlias) {
       NeedLift = llvm::any_of(MemLocs, [C, &AA](const MemoryLocation &ML) {
         return AA.getModRefInfo(C, ML);
       });

lib/Transforms/Utils/MemorySSA.cpp

 /// For example, this class is used as a densemap key in the use optimizer.
 class MemoryLocOrCall {
 public:
   MemoryLocOrCall() : IsCall(false) {}
   MemoryLocOrCall(MemoryUseOrDef *MUD)
       : MemoryLocOrCall(MUD->getMemoryInst()) {}
   MemoryLocOrCall(const MemoryUseOrDef *MUD)
       : MemoryLocOrCall(MUD->getMemoryInst()) {}
+  ~MemoryLocOrCall() {}
+  MemoryLocOrCall(const MemoryLocOrCall &MLOC) {
+    if (IsCall)
+      CS = MLOC.CS;
+    else
+      Loc = MLOC.Loc;
+  }
+
+  MemoryLocOrCall &operator=(const MemoryLocOrCall &MLOC) {
+    if (IsCall)
+      CS = MLOC.CS;
+    else
+      Loc = MLOC.Loc;
+    return *this;
+  }
 
   MemoryLocOrCall(Instruction *Inst) {
     if (ImmutableCallSite(Inst)) {
       IsCall = true;
       CS = ImmutableCallSite(Inst);
     } else {
       IsCall = false;
-      // There is no such thing as a memorylocation for a fence inst, and it is
-      // unique in that regard.
-      if (!isa<FenceInst>(Inst))
-        Loc = MemoryLocation::get(Inst);
+      Loc = MemoryLocation::getOrNone(Inst);
     }
   }
 
   explicit MemoryLocOrCall(const MemoryLocation &Loc)
       : IsCall(false), Loc(Loc) {}
 
   bool IsCall;
   ImmutableCallSite getCS() const {
     assert(IsCall);
     return CS;
   }
-  MemoryLocation getLoc() const {
+  const MemoryLocation &getLoc() const {
     assert(!IsCall);
-    return Loc;
+    return *Loc;
   }
 
+  const Optional<MemoryLocation> &getLocOrNone() const { return Loc; }
+
   bool operator==(const MemoryLocOrCall &Other) const {
     if (IsCall != Other.IsCall)
       return false;
 
     if (IsCall)
       return CS.getCalledValue() == Other.CS.getCalledValue();
     return Loc == Other.Loc;
   }
 
 private:
   union {
     ImmutableCallSite CS;
-    MemoryLocation Loc;
+    Optional<MemoryLocation> Loc;
   };
 };
 }
 
 namespace llvm {
 template <> struct DenseMapInfo<MemoryLocOrCall> {
   static inline MemoryLocOrCall getEmptyKey() {
     return MemoryLocOrCall(DenseMapInfo<MemoryLocation>::getEmptyKey());
static Reorderability getLoadReorderability(const LoadInst *Use,
   bool MayClobberIsAcquire = isAtLeastOrStrongerThan(MayClobber->getOrdering(),
                                                      AtomicOrdering::Acquire);
   if (SeqCstUse || MayClobberIsAcquire)
     return Reorderability::Never;
   return Result;
 }
 
 static bool instructionClobbersQuery(MemoryDef *MD,
-                                     const MemoryLocation &UseLoc,
+                                     const Optional<MemoryLocation> &UseLoc,
                                      const Instruction *UseInst,
                                      AliasAnalysis &AA) {
   Instruction *DefInst = MD->getMemoryInst();
   assert(DefInst && "Defining instruction not actually an instruction");
 
   if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(DefInst)) {
     // These intrinsics will show up as affecting memory, but they are just
     // markers.
static bool instructionClobbersQuery(MemoryDef *MD,
   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));
+        return !AA.isNoAlias(UseLoc.getValue(), MemoryLocation::get(DefLoad));
       }
     }
   }
 
   return AA.getModRefInfo(DefInst, UseLoc) & MRI_Mod;
 }
 
-static bool instructionClobbersQuery(MemoryDef *MD, const MemoryUseOrDef *MU,
-                                     const MemoryLocOrCall &UseMLOC,
-                                     AliasAnalysis &AA) {
-  // 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);
-}
-
 // 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);
+  return instructionClobbersQuery(
+      MD, MemoryLocation::getOrNone(MU->getMemoryInst()), MU->getMemoryInst(),
+      AA);
 }
 }
 
 namespace {
 struct UpwardsMemoryQuery {
   // True if our original query started off as a call
   bool IsCall;
   // The pointer location we started the query with. This will be empty if
while (UpperBound > LocInfo.LowerBound) {
       // 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;
         break;
       }
-      if (instructionClobbersQuery(MD, MU, UseMLOC, *AA)) {
+      if (instructionClobbersQuery(MD, UseMLOC.getLocOrNone(),
+                                   MU->getMemoryInst(), *AA)) {
         FoundClobberResult = true;
         break;
       }
       --UpperBound;
     }
     // 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) {
MemoryUseOrDef *MemorySSA::createNewAccess(Instruction *I) {
   // that it writes arbitrarily. Ignore that fake memory dependency here.
   // FIXME: Replace this special casing with a more accurate modelling of
   // assume's control dependency.
   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
     if (II->getIntrinsicID() == Intrinsic::assume)
       return nullptr;
 
   // Find out what affect this instruction has on memory.
-  ModRefInfo ModRef = AA->getModRefInfo(I);
+  ModRefInfo ModRef = AA->getModRefInfo(I, None);
   bool Def = bool(ModRef & MRI_Mod);
   bool Use = bool(ModRef & MRI_Ref);
 
   // It's possible for an instruction to not modify memory at all. During
   // construction, we ignore them.
   if (!Def && !Use)
     return nullptr;