implantation example for new AliasAnalysis functions (getAddressesDistance + ModRefSameBuffer)

[atheel.ma]

Summary

just a "First" implantation , maybe need to get all common code between aliasCheck() and commonBuffCheck() to a common function

[atheel.ma]

The use is inside a target specific function:

  for (MachineMemOperand *MMOa : MIa.memoperands()) {
    for (MachineMemOperand *MMOb : MIb.memoperands()) {
      const Value *Va = MMOa->getValue();
      const Value *Vb = MMOb->getValue();
      const PseudoSourceValue *Pa = MMOa->getPseudoValue();
      const PseudoSourceValue *Pb = MMOb->getPseudoValue();

      if (Va && Vb) {
        // Ask alias analysis (if there's one available) what's going on if
        // we have access to IR values.
        assert(!Pa && !Pb && "IR vs pseudo value inconsistency");
        uint64_t Sizea = MMOa->getSize();
        uint64_t Sizeb = MMOb->getSize();

        // vpld has sometimes UnknownSize
        if ((!CII->isUsingAllBanks(MIa) && !CII->isUsingAllBanks(MIb)) &&
            (MMOa->getSize() == MemoryLocation::UnknownSize ||
             MMOb->getSize() == MemoryLocation::UnknownSize)) {
          continue;
        }

        MemoryLocation Loca = MemoryLocation(Va, Sizea, MMOa->getAAInfo());
        MemoryLocation Locb = MemoryLocation(Vb, Sizeb, MMOb->getAAInfo());
		int64_t ptr1Offset = MMOa->getPointerInfo().Offset;
		int64_t ptr2Offset = MMOb->getPointerInfo().Offset;
        if (AA->ModRefSameBuffer(Loca, ptr1Offset, Locb, ptr2Offset)) {

			Optional<int64_t> dis = AA->getAddressesDistance(Loca,
				ptr1Offset, Locb, ptr2Offset);

          if ((CII->isUsingAllBanks(MIa) || CII->isUsingAllBanks(MIb))) {
            return true;
          }
          // need to take care with dis<0 *dis%64 => ((*dis%64)+64)%64
          if (dis != None && ((*dis > 0 && Sizeb > (*dis % 64)) ||
                              (*dis < 0 && Sizea > ((*dis % 64) + 64) % 64))) {
            return true;
          }
        }
      }
    }
  }

[asbirlea]

Thank you for the implementation patch!

AFAICT this is a fairly big change, and I'd like it to get more visibility and feedback. Could you please send an RFC to llvm-dev list with a short description and links to the two patches?

I'd like to understand if there's the opportunity to improve existing AA interfaces (e.g. what's missing in aliasCheck) here versus adding new ones. There's a lot of duplicated code there.
Let's continue the discussion on llvm-dev, please.

[atheel.ma]

thanks,
mail sent to llvm-dev,
ofcurse Im aware of the "duplicated code", this is only a temporary implementation,
Okm will discuss it on llvm-dev .

[xbolva00]

Maybe add more documentation, examples how to use these new API?

include/llvm/Analysis/BasicAliasAnalysis.h

91

Fix comment, you return bool value.

[xbolva00]

include/llvm/Analysis/BasicAliasAnalysis.h

152

..common buffer queries...

153

Convert to more C++ish code via "using MyType = ..."?

lib/Analysis/BasicAliasAnalysis.cpp

625

isa<...> is enough here, no?

You can use still getParent function with "V"

757

if (!ptr)...

760

Same as above

832

Why extra if ((...))?

1745

Is this loop correct? Why start at 1? And why not "i < e"?

Anyway, range based iteration is nicer, you should chrck if possible here

for (Value *V : V1Srcs) { ... }

[atheel.ma]

Fix some comments
remove duplicated functions

[atheel.ma]

O1 == nullptr is taken from aliasCheck()
If I want to change it to !nullptr I should do it in 2 functions in a different commit
same for the loop (its correct to start from 1 because 0 was checked before... using iterator is not the best solution)

I see no body has commented on llvm-dev... any other way to get more comments?

include/llvm/Analysis/AliasAnalysis.h

enum AliasResult : uint8_t {
   /// The two locations may or may not alias. This is the least precise result.
   MayAlias,
   /// The two locations alias, but only due to a partial overlap.
   PartialAlias,
   /// The two locations precisely alias each other.
   MustAlias,
 };
 
+enum BuffUseResult {
+  /// the two locations cant use the same memory block
+  NotSameBuff = 0,
+  /// The two locations may or may not use the same memory block. This is the
+  /// least precise result.
+  MayUseSameBuff,
+  /// The two locations precisely use the same memory block.
+  MustUseSameBuff
+
+};
 /// Flags indicating whether a memory access modifies or references memory.
 ///
 /// This is no access at all, a modification, a reference, or both
 /// a modification and a reference. These are specifically structured such that
 /// they form a three bit matrix and bit-tests for 'mod' or 'ref' or 'must'
 /// work with any of the possible values.
 enum class ModRefInfo : uint8_t {
   /// Must is provided for completeness, but no routines will return only
public:
   bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false);
 
   /// A convenience wrapper around the primary \c pointsToConstantMemory
   /// interface.
   bool pointsToConstantMemory(const Value *P, bool OrLocal = false) {
     return pointsToConstantMemory(MemoryLocation(P), OrLocal);
   }
 
+  /// Checks whether the given locations points to the same buffer.
+  bool ModRefSameBuffer(const MemoryLocation &LocA, int64_t ptr1Offset,
+                        const MemoryLocation &LocB, int64_t ptr2Offset);
+
+  /// A convenience wrapper around the \c ModRefSameBuffer helper interface.
+  bool ModRefSameBuffer(const Value *V1, int64_t ptr1Offset, const Value *V2,
+                        int64_t ptr2Offset) {
+    return ModRefSameBuffer(MemoryLocation(V1), ptr1Offset, MemoryLocation(V2),
+                            ptr2Offset);
+  }
   /// @}
   //===--------------------------------------------------------------------===//
   /// \name Simple mod/ref information
   /// @{
 
   /// Get the ModRef info associated with a pointer argument of a callsite. The
   /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note
   /// that these bits do not necessarily account for the overall behavior of
   /// the function, but rather only provide additional per-argument
   /// information. This never sets ModRefInfo::Must.
   ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx);
 
   /// Return the behavior of the given call site.
   FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS);
 
   /// Return the behavior when calling the given function.
   FunctionModRefBehavior getModRefBehavior(const Function *F);
+  /// Return the Distance between 2 address.
+  Optional<int64_t> getAddressesDistance(const MemoryLocation &LocA,
+                                         int64_t ptr1Offset,
+                                         const MemoryLocation &LocB,
+                                         int64_t ptr2Offset);
+
+  Optional<int64_t> getAddressesDistance(const Value *V1, int64_t ptr1Offset,
+                                         const Value *V2, int64_t ptr2Offset) {
+    return getAddressesDistance(MemoryLocation(V1), ptr1Offset,
+                                MemoryLocation(V2), ptr2Offset);
+  }
 
   /// Checks if the specified call is known to never read or write memory.
   ///
   /// Note that if the call only reads from known-constant memory, it is also
   /// legal to return true. Also, calls that unwind the stack are legal for
   /// this predicate.
   ///
   /// Many optimizations (such as CSE and LICM) can be performed on such calls
public:
   virtual AliasResult alias(const MemoryLocation &LocA,
                             const MemoryLocation &LocB) = 0;
 
   /// Checks whether the given location points to constant memory, or if
   /// \p OrLocal is true whether it points to a local alloca.
   virtual bool pointsToConstantMemory(const MemoryLocation &Loc,
                                       bool OrLocal) = 0;
 
+  /// Checks whether the given locations points to the same buffer.
+  virtual bool ModRefSameBuffer(const MemoryLocation &LocA, int64_t ptr1Offset,
+                                const MemoryLocation &LocB,
+                                int64_t ptr2Offset) = 0;
   /// @}
   //===--------------------------------------------------------------------===//
   /// \name Simple mod/ref information
   /// @{
 
   /// Get the ModRef info associated with a pointer argument of a callsite. The
   /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note
   /// that these bits do not necessarily account for the overall behavior of
virtual ModRefInfo getModRefInfo(ImmutableCallSite CS,
                                    const MemoryLocation &Loc) = 0;
 
   /// 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
   virtual ModRefInfo getModRefInfo(ImmutableCallSite CS1,
                                    ImmutableCallSite CS2) = 0;
 
+  /// Return the Distance between 2 address.
+  virtual Optional<int64_t> getAddressesDistance(const MemoryLocation &LocA,
+                                                 int64_t ptr1Offset,
+                                                 const MemoryLocation &LocB,
+                                                 int64_t ptr2Offset) = 0;
   /// @}
 };
 
 /// A private class template which derives from \c Concept and wraps some other
 /// type.
 ///
 /// This models the concept by directly forwarding each interface point to the
 /// wrapped type which must implement a compatible interface. This provides
AliasResult alias(const MemoryLocation &LocA,
                     const MemoryLocation &LocB) override {
     return Result.alias(LocA, LocB);
   }
 
   bool pointsToConstantMemory(const MemoryLocation &Loc,
                               bool OrLocal) override {
     return Result.pointsToConstantMemory(Loc, OrLocal);
   }
+  bool ModRefSameBuffer(const MemoryLocation &LocA, int64_t ptr1Offset,
+                        const MemoryLocation &LocB,
+                        int64_t ptr2Offset) override {
+    return Result.ModRefSameBuffer(LocA, ptr1Offset, LocB, ptr2Offset);
+  }
 
   ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) override {
     return Result.getArgModRefInfo(CS, ArgIdx);
   }
 
   FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS) override {
     return Result.getModRefBehavior(CS);
   }
 
   FunctionModRefBehavior getModRefBehavior(const Function *F) override {
     return Result.getModRefBehavior(F);
   }
 
   ModRefInfo getModRefInfo(ImmutableCallSite CS,
                            const MemoryLocation &Loc) override {
     return Result.getModRefInfo(CS, Loc);
   }
 
   ModRefInfo getModRefInfo(ImmutableCallSite CS1,
                            ImmutableCallSite CS2) override {
     return Result.getModRefInfo(CS1, CS2);
   }
+  Optional<int64_t> getAddressesDistance(const MemoryLocation &LocA,
+                                         int64_t ptr1Offset,
+                                         const MemoryLocation &LocB,
+                                         int64_t ptr2Offset) override {
+    return Result.getAddressesDistance(LocA, ptr1Offset, LocB, ptr2Offset);
+  }
 };
 
 /// A CRTP-driven "mixin" base class to help implement the function alias
 /// analysis results concept.
 ///
 /// Because of the nature of many alias analysis implementations, they often
 /// only implement a subset of the interface. This base class will attempt to
 /// implement the remaining portions of the interface in terms of simpler forms
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
       return AAR ? AAR->alias(LocA, LocB) : CurrentResult.alias(LocA, LocB);
     }
 
     bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal) {
       return AAR ? AAR->pointsToConstantMemory(Loc, OrLocal)
                  : CurrentResult.pointsToConstantMemory(Loc, OrLocal);
     }
 
+    bool ModRefSameBuffer(const MemoryLocation &LocA, int64_t ptr1Offset,
+                          const MemoryLocation &LocB, int64_t ptr2Offset) {
+      return AAR ? AAR->ModRefSameBuffer(LocA, ptr1Offset, LocB, ptr2Offset)
+                 : CurrentResult.ModRefSameBuffer(LocA, ptr1Offset, LocB,
+                                                  ptr2Offset);
+    }
     ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) {
       return AAR ? AAR->getArgModRefInfo(CS, ArgIdx) : CurrentResult.getArgModRefInfo(CS, ArgIdx);
     }
 
     FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS) {
       return AAR ? AAR->getModRefBehavior(CS) : CurrentResult.getModRefBehavior(CS);
     }
 
     FunctionModRefBehavior getModRefBehavior(const Function *F) {
       return AAR ? AAR->getModRefBehavior(F) : CurrentResult.getModRefBehavior(F);
     }
 
     ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc) {
       return AAR ? AAR->getModRefInfo(CS, Loc)
                  : CurrentResult.getModRefInfo(CS, Loc);
     }
 
     ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) {
       return AAR ? AAR->getModRefInfo(CS1, CS2) : CurrentResult.getModRefInfo(CS1, CS2);
     }
+    Optional<int64_t> getAddressesDistance(const MemoryLocation &LocA,
+                                           int64_t ptr1Offset,
+                                           const MemoryLocation &LocB,
+                                           int64_t ptr2Offset) {
+      return AAR ? AAR->getAddressesDistance(LocA, ptr1Offset, LocB, ptr2Offset)
+                 : CurrentResult.getAddressesDistance(LocA, ptr1Offset, LocB,
+                                                      ptr2Offset);
+    }
   };
 
   explicit AAResultBase() = default;
 
   // Provide all the copy and move constructors so that derived types aren't
   // constrained.
   AAResultBase(const AAResultBase &Arg) {}
   AAResultBase(AAResultBase &&Arg) {}

 public:
   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
     return MayAlias;
   }
 
   bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal) {
     return false;
   }
+  bool ModRefSameBuffer(const MemoryLocation &LocA, int64_t ptr1Offset,
+                        const MemoryLocation &LocB, int64_t ptr2Offset) {
+    return false;
+  }
 
   ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) {
     return ModRefInfo::ModRef;
   }
 
   FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS) {
     return FMRB_UnknownModRefBehavior;
   }
 
   FunctionModRefBehavior getModRefBehavior(const Function *F) {
     return FMRB_UnknownModRefBehavior;
   }
 
   ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc) {
     return ModRefInfo::ModRef;
   }
 
   ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) {
     return ModRefInfo::ModRef;
   }
+  Optional<int64_t> getAddressesDistance(const MemoryLocation &LocA,
+                                         int64_t ptr1Offset,
+                                         const MemoryLocation &LocB,
+                                         int64_t ptr2Offset) {
+    return None;
+  }
 };
 
 /// Return true if this pointer is returned by a noalias function.
 bool isNoAliasCall(const Value *V);
 
 /// Return true if this is an argument with the noalias attribute.
 bool isNoAliasArgument(const Value *V);
 

include/llvm/Analysis/BasicAliasAnalysis.h

public:
 
   ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc);
 
   ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2);
 
   /// Chases pointers until we find a (constant global) or not.
   bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal);
 
+  /// Checks whether the given locations points to the same buffer and returns
+  // true, else returns false.
+  bool ModRefSameBuffer(const MemoryLocation &LocA, int64_t ptr1Offset,
+    const MemoryLocation &LocB, int64_t ptr2Offset);
+
+  /// Returns the distance between 2 memory location if available.
+  Optional<int64_t> getAddressesDistance(const MemoryLocation &LocA, 
+    int64_t ptr1Offset, const MemoryLocation &LocB, int64_t ptr2Offset);
   /// Get the location associated with a pointer argument of a callsite.
   ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx);
 
   /// Returns the behavior when calling the given call site.
   FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS);
 
   /// Returns the behavior when calling the given function. For use when the
   /// call site is not known.
struct DecomposedGEP {
     SmallVector<VariableGEPIndex, 4> VarIndices;
   };
 
   /// Track alias queries to guard against recursion.
   using LocPair = std::pair<MemoryLocation, MemoryLocation>;
   using AliasCacheTy = SmallDenseMap<LocPair, AliasResult, 8>;
   AliasCacheTy AliasCache;
 
+  /// Track common buffer queries to guard against recursion.
+  using MemDistancePair = std::pair<BuffUseResult, Optional<int64_t>>;
+  using CommonBufferCacheTy = SmallDenseMap<LocPair, MemDistancePair, 8>;
+  CommonBufferCacheTy CommonBufferCache;
   /// Tracks phi nodes we have visited.
   ///
   /// When interpret "Value" pointer equality as value equality we need to make
   /// sure that the "Value" is not part of a cycle. Otherwise, two uses could
   /// come from different "iterations" of a cycle and see different values for
   /// the same "Value" pointer.
   ///
   /// The following example shows the problem:
private:
   AliasResult aliasSelect(const SelectInst *SI, uint64_t SISize,
                           const AAMDNodes &SIAAInfo, const Value *V2,
                           uint64_t 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,
                          const Value *O1 = nullptr, const Value *O2 = nullptr);
+  BuffUseResult commonBufferPHI(const PHINode *PN, uint64_t PNSize,
+                             const AAMDNodes &PNAAInfo, int64_t ptr1Offset,
+                             const Value *V2, uint64_t V2Size, 
+                             const AAMDNodes &V2AAInfo, int64_t ptr2Offset, 
+                             const Value *UnderV2, 
+                             Optional<int64_t>& LocDistance);
+
+  BuffUseResult commonBufferSelect(const SelectInst *SI, uint64_t SISize,
+                               const AAMDNodes &SIAAInfo, int64_t ptr1Offset, 
+                               const Value *V2, uint64_t V2Size,
+                               const AAMDNodes &V2AAInfo, int64_t ptr2Offset,
+                               const Value *UnderV2, Optional<int64_t>& LocDistance);
+
+  BuffUseResult ModRefSameBufferCheck(const Value *V1, uint64_t V1Size,
+    AAMDNodes V1AAInfo, int64_t ptr1Offset, const Value *V2, uint64_t V2Size,
+    AAMDNodes V2AAInfo, int64_t ptr2Offset, Optional<int64_t>& LocDistance,
+    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;
 

lib/Analysis/AliasAnalysis.cpp

bool AAResults::pointsToConstantMemory(const MemoryLocation &Loc,
                                        bool OrLocal) {
   for (const auto &AA : AAs)
     if (AA->pointsToConstantMemory(Loc, OrLocal))
       return true;
 
   return false;
 }
 
+bool AAResults::ModRefSameBuffer(const MemoryLocation &LocA, int64_t ptr1Offset,
+                                 const MemoryLocation &LocB,
+                                 int64_t ptr2Offset) {
+  for (const auto &AA : AAs)
+    if (AA->ModRefSameBuffer(LocA, ptr1Offset, LocB, ptr2Offset))
+      return true;
+
+  return false;
+}
+
+Optional<int64_t> AAResults::getAddressesDistance(const MemoryLocation &LocA,
+                                                  int64_t ptr1Offset,
+                                                  const MemoryLocation &LocB,
+                                                  int64_t ptr2Offset) {
+  for (const auto &AA : AAs) {
+    Optional<int64_t> res =
+        AA->getAddressesDistance(LocA, ptr1Offset, LocB, ptr2Offset);
+    if (res != None)
+      return res;
+  }
+
+  return None;
+}
 ModRefInfo AAResults::getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) {
   ModRefInfo Result = ModRefInfo::ModRef;
 
   for (const auto &AA : AAs) {
     Result = intersectModRef(Result, AA->getArgModRefInfo(CS, ArgIdx));
 
     // Early-exit the moment we reach the bottom of the lattice.
     if (isNoModRef(Result))

lib/Analysis/BasicAliasAnalysis.cpp

bool BasicAAResult::pointsToConstantMemory(const MemoryLocation &Loc,
   } while (!Worklist.empty() && --MaxLookup);
 
   Visited.clear();
   return Worklist.empty();
 }
 
 /// Returns the behavior when calling the given call site.
 FunctionModRefBehavior BasicAAResult::getModRefBehavior(ImmutableCallSite CS) {
   if (CS.doesNotAccessMemory())
     // Can't do better than this.
     return FMRB_DoesNotAccessMemory;
 
   FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior;
 
   // If the callsite knows it only reads memory, don't return worse
   // than that.
   if (CS.onlyReadsMemory())
static bool notDifferentParent(const Value *O1, const Value *O2) {
 
   const Function *F1 = getParent(O1);
   const Function *F2 = getParent(O2);
 
   return !F1 || !F2 || F1 == F2;
 }
 #endif
 
+bool BasicAAResult::ModRefSameBuffer(const MemoryLocation &LocA, 
+  int64_t ptr1Offset, const MemoryLocation &LocB, int64_t ptr2Offset) {
+  assert(notDifferentParent(LocA.Ptr, LocB.Ptr) &&
+    "ModRefSameBuffer doesn't support interprocedural queries.");
+
+  Optional<int64_t> LocDistance;
+  BuffUseResult sameBuff =
+      ModRefSameBufferCheck(LocA.Ptr, LocA.Size, LocA.AATags, ptr1Offset,
+      LocB.Ptr, LocB.Size, LocB.AATags, ptr2Offset, LocDistance);
+  return sameBuff == MustUseSameBuff;
+}
+
+Optional<int64_t>
+BasicAAResult::getAddressesDistance(const MemoryLocation &LocA,
+  int64_t ptr1Offset, const MemoryLocation &LocB, int64_t ptr2Offset) {
+  // LocA-LocB
+  Optional<int64_t> LocDistance;
+  BuffUseResult sameBuff =
+      ModRefSameBufferCheck(LocA.Ptr, LocA.Size, LocA.AATags, ptr1Offset, 
+      LocB.Ptr, LocB.Size, LocB.AATags, ptr2Offset, LocDistance);
+
+  return LocDistance;
+}
+
+/// Returns pointer to the buffer if given locations points to the same buffer.
+//  else return nullptr.
+BuffUseResult BasicAAResult::ModRefSameBufferCheck(
+    const Value *V1, uint64_t V1Size, AAMDNodes V1AAInfo, int64_t ptr1Offset,
+  const Value *V2, uint64_t V2Size, AAMDNodes V2AAInfo, int64_t ptr2Offset,
+  Optional<int64_t> &LocDistance, 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 NotSameBuff;
+
+  // Strip off any casts if they exist.
+  V1 = V1->stripPointerCasts();
+  V2 = V2->stripPointerCasts();
+
+  // If V1 or V2 is undef, the result is nullptr.
+  if (isa<UndefValue>(V1) || isa<UndefValue>(V2))
+    return NotSameBuff;
+
+  // Are we checking for alias of the same value?
+  // Because we look 'through' phi nodes, we could look at "Value" pointers from
+  // different iterations. We must therefore make sure that this is not the
+  // case. The function isValueEqualInPotentialCycles ensures that this cannot
+  // happen by looking at the visited phi nodes and making sure they cannot
+  // reach the value.
+  /*//atheelm: need to support this
+  if (isValueEqualInPotentialCycles(V1, V2)) {
+          return MustUseSameBuff;
+  }*/
+
+  // Figure out what objects these things are pointing to if we can.
+  if (O1 == nullptr)
+    O1 = GetUnderlyingObject(V1, DL, MaxLookupSearchDepth);
+
+  if (O2 == nullptr)
+    O2 = GetUnderlyingObject(V2, DL, MaxLookupSearchDepth);
+
+  // Null values in the default address space don't point to any object
+  if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O1))
+    if (CPN->getType()->getAddressSpace() == 0)
+      return NotSameBuff;
+  if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O2))
+    if (CPN->getType()->getAddressSpace() == 0)
+      return NotSameBuff;
+
+  if (O1 != O2) {
+    // If V1/V2 point to two different objects, we know that
+    // they are not using the same buffer.
+    if (isIdentifiedObject(O1) && isIdentifiedObject(O2))
+      return NotSameBuff;
+
+    // Constant pointers can't alias with non-const isIdentifiedObject objects.
+    if ((isa<Constant>(O1) && isIdentifiedObject(O2) && !isa<Constant>(O2)) ||
+        (isa<Constant>(O2) && isIdentifiedObject(O1) && !isa<Constant>(O1)))
+      return NotSameBuff;
+
+    // Function arguments can't alias with things that are known to be
+    // unambigously identified at the function level.
+    if ((isa<Argument>(O1) && isIdentifiedFunctionLocal(O2)) ||
+        (isa<Argument>(O2) && isIdentifiedFunctionLocal(O1)))
+      return NotSameBuff;
+
+    // Most objects can't alias null.
+    if ((isa<ConstantPointerNull>(O2) && isKnownNonNull(O1)) ||
+        (isa<ConstantPointerNull>(O1) && isKnownNonNull(O2)))
+      return NotSameBuff;
+
+    // If one pointer is the result of a call/invoke or load and the other is a
+    // non-escaping local object within the same function, then we know the
+    // object couldn't escape to a point where the call could return it.
+    //
+    // Note that if the pointers are in different functions, there are a
+    // variety of complications. A call with a nocapture argument may still
+    // temporary store the nocapture argument's value in a temporary memory
+    // location if that memory location doesn't escape. Or it may pass a
+    // nocapture value to other functions as long as they don't capture it.
+    if (isEscapeSource(O1) && isNonEscapingLocalObject(O2))
+      return NotSameBuff;
+    if (isEscapeSource(O2) && isNonEscapingLocalObject(O1))
+      return NotSameBuff;
+  }
+
+  // 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);
+  std::pair<CommonBufferCacheTy::iterator, bool> Pair =
+      CommonBufferCache.insert(
+          std::make_pair(Locs, MemDistancePair(MayUseSameBuff, None)));
+  if (!Pair.second) {
+    LocDistance = (Pair.first->second.second);
+    return Pair.first->second.first;
+  }
+
+  // FIXME: This isn't aggressively handling alias(GEP, PHI) for example: if the
+  // GEP can't simplify, we don't even look at the PHI cases.
+  if (!isa<GEPOperator>(V1) && isa<GEPOperator>(V2)) {
+    std::swap(V1, V2);
+    std::swap(V1Size, V2Size);
+    std::swap(O1, O2);
+    std::swap(V1AAInfo, V2AAInfo);
+  std::swap(ptr1Offset, ptr2Offset);
+  }
+
+  if (O1 == O2) {
+    const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1);
+    const GEPOperator *GV2 = dyn_cast<GEPOperator>(V2);
+    if (GV1 && GV2) {
+      DecomposedGEP DecompGEP1, DecompGEP2;
+      bool GEP1MaxLookupReached =
+          DecomposeGEPExpression(GV1, DecompGEP1, DL, &AC, DT);
+      bool GEP2MaxLookupReached =
+          DecomposeGEPExpression(V2, DecompGEP2, DL, &AC, DT);
+
+      int64_t GEP1BaseOffset =
+          DecompGEP1.StructOffset + DecompGEP1.OtherOffset + ptr1Offset;
+      int64_t GEP2BaseOffset =
+          DecompGEP2.StructOffset + DecompGEP2.OtherOffset + ptr2Offset;
+      LocDistance = GEP2BaseOffset - GEP1BaseOffset;
+      CommonBufferCache[Locs] = MemDistancePair(MustUseSameBuff, LocDistance);
+      return MustUseSameBuff;
+    } else if (GV1) {
+
+      BuffUseResult R = ModRefSameBufferCheck(
+          O1, MemoryLocation::UnknownSize, AAMDNodes(), ptr1Offset, V2,
+          MemoryLocation::UnknownSize, V2AAInfo, ptr2Offset, LocDistance, nullptr, O2);
+      if (R != MayUseSameBuff) {
+        CommonBufferCache[Locs] = MemDistancePair(MustUseSameBuff, LocDistance);
+        return R;
+      }
+    }
+
+    if (isa<PHINode>(V2) && !isa<PHINode>(V1)) {
+      std::swap(V1, V2);
+      std::swap(O1, O2);
+      std::swap(V1Size, V2Size);
+      std::swap(V1AAInfo, V2AAInfo);
+    std::swap(ptr1Offset, ptr2Offset);
+    }
+    if (const PHINode *PN = dyn_cast<PHINode>(V1)) {
+      BuffUseResult Result = commonBufferPHI(PN, V1Size, V1AAInfo, ptr1Offset,V2, V2Size,
+                                             V2AAInfo, ptr2Offset, O2, LocDistance);
+      if (Result != MayUseSameBuff) {
+        CommonBufferCache[Locs] = MemDistancePair(Result, LocDistance);
+        return Result;
+      }
+    }
+
+    if (isa<SelectInst>(V2) && !isa<SelectInst>(V1)) {
+      std::swap(V1, V2);
+      std::swap(O1, O2);
+      std::swap(V1Size, V2Size);
+      std::swap(V1AAInfo, V2AAInfo);
+    std::swap(ptr1Offset, ptr2Offset);
+    }
+    if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) {
+      BuffUseResult Result = commonBufferSelect(S1, V1Size, V1AAInfo,
+      ptr1Offset, V2, V2Size, V2AAInfo, ptr2Offset, O2, LocDistance);
+      if (Result != MayUseSameBuff) {
+        CommonBufferCache[Locs] = MemDistancePair(Result, LocDistance);
+        return Result;
+      }
+    }
+    CommonBufferCache[Locs] = MemDistancePair(MustUseSameBuff, None);
+    return MustUseSameBuff;
+  }
+  CommonBufferCache[Locs] = MemDistancePair(NotSameBuff, None);
+  return NotSameBuff;
+}
+
 AliasResult BasicAAResult::alias(const MemoryLocation &LocA,
                                  const MemoryLocation &LocB) {
   assert(notDifferentParent(LocA.Ptr, LocB.Ptr) &&
          "BasicAliasAnalysis doesn't support interprocedural queries.");
 
   // If we have a directly cached entry for these locations, we have recursed
   // through this once, so just return the cached results. Notably, when this
   // happens, we don't clear the cache.
if (A == B)
     return A;
   // A mix of PartialAlias and MustAlias is PartialAlias.
   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.
+BuffUseResult BasicAAResult::commonBufferSelect(const SelectInst *SI, uint64_t SISize,
+  const AAMDNodes &SIAAInfo, int64_t ptr1Offset, const Value *V2,
+  uint64_t V2Size, const AAMDNodes &V2AAInfo, int64_t ptr2Offset,
+  const Value *UnderV2, Optional<int64_t>& LocDistance) {
+  // 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()) {
+      BuffUseResult Alias = ModRefSameBufferCheck(SI->getTrueValue(), SISize, SIAAInfo,
+        ptr1Offset, SI2->getTrueValue(), V2Size, V2AAInfo, ptr2Offset, LocDistance);
+      if (Alias != MayUseSameBuff)
+        return Alias;
+      BuffUseResult ThisAlias =
+        ModRefSameBufferCheck(SI->getFalseValue(), SISize, SIAAInfo,
+          ptr1Offset, SI2->getFalseValue(), V2Size, V2AAInfo,
+          ptr2Offset, LocDistance);
+      return ThisAlias;
+    }
+
+  // If both arms of the Select node NoAlias or MustAlias V2, then returns
+  // NoAlias / MustAlias. Otherwise, returns MayAlias.
+  BuffUseResult Alias =
+    ModRefSameBufferCheck(V2, V2Size, V2AAInfo, ptr1Offset, SI->getTrueValue(),
+      SISize, SIAAInfo, ptr2Offset, LocDistance, UnderV2);
+  if (Alias != MayUseSameBuff)
+    return Alias;
+
+  BuffUseResult ThisAlias =
+    ModRefSameBufferCheck(V2, V2Size, V2AAInfo, ptr1Offset,
+      SI->getFalseValue(), SISize, SIAAInfo, ptr2Offset,
+      LocDistance, UnderV2);
+  return ThisAlias;
+}
+
+/// Provide a bunch of ad-hoc rules to disambiguate a PHI instruction against
+/// another.
+BuffUseResult BasicAAResult::commonBufferPHI(const PHINode *PN, uint64_t PNSize,
+  const AAMDNodes &PNAAInfo, int64_t ptr1Offset, const Value *V2,
+  uint64_t V2Size, const AAMDNodes &V2AAInfo, int64_t ptr2Offset, 
+  const Value *UnderV2, Optional<int64_t>& LocDistance) {
+  // 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 (const PHINode *PN2 = dyn_cast<PHINode>(V2))
+    if (PN2->getParent() == PN->getParent()) {
+      LocPair Locs(MemoryLocation(PN, PNSize, PNAAInfo),
+        MemoryLocation(V2, V2Size, V2AAInfo));
+      if (PN > V2)
+        std::swap(Locs.first, Locs.second);
+      // Analyse the PHIs' inputs under the assumption that the PHIs are
+      // NoAlias.
+      // If the PHIs are May/MustAlias there must be (recursively) an input
+      // operand from outside the PHIs' cycle that is MayAlias/MustAlias or
+      // there must be an operation on the PHIs within the PHIs' value cycle
+      // that causes a MayAlias.
+      // Pretend the phis do not alias.
+      const Value* Alias = nullptr;
+      assert(CommonBufferCache.count(Locs) &&
+        "There must exist an entry for the phi node");
+
+      for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
+        BuffUseResult ThisAlias =
+          ModRefSameBufferCheck(PN->getIncomingValue(i), PNSize, PNAAInfo,
+            ptr1Offset, PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)),
+            V2Size, V2AAInfo, ptr2Offset, LocDistance);
+        if (ThisAlias != MayUseSameBuff) {
+          return ThisAlias;
+        }
+      }
+
+    }
+
+  SmallPtrSet<Value *, 4> UniqueSrc;
+  SmallVector<Value *, 4> V1Srcs;
+  bool isRecursive = false;
+  for (Value *PV1 : PN->incoming_values()) {
+    if (isa<PHINode>(PV1))
+      // If any of the source itself is a PHI, return MayUseSameBuff conservatively
+      // to avoid compile time explosion. The worst possible case is if both
+      // sides are PHI nodes. In which case, this is O(m x n) time where 'm'
+      // and 'n' are the number of PHI sources.
+      return MayUseSameBuff;
+
+    if (EnableRecPhiAnalysis)
+      if (GEPOperator *PV1GEP = dyn_cast<GEPOperator>(PV1)) {
+        // Check whether the incoming value is a GEP that advances the pointer
+        // result of this PHI node (e.g. in a loop). If this is the case, we
+        // would recurse and always get a MayUseSameBuff. Handle this case specially
+        // below.
+        if (PV1GEP->getPointerOperand() == PN && PV1GEP->getNumIndices() == 1 &&
+          isa<ConstantInt>(PV1GEP->idx_begin())) {
+          isRecursive = true;
+          continue;
+        }
+      }
+
+    if (UniqueSrc.insert(PV1).second)
+      V1Srcs.push_back(PV1);
+  }
+
+  // If this PHI node is recursive, set the size of the accessed memory to
+  // unknown to represent all the possible values the GEP could advance the
+  // pointer to.
+  if (isRecursive)
+    PNSize = MemoryLocation::UnknownSize;
+
+  BuffUseResult Alias =
+    ModRefSameBufferCheck(V2, V2Size, V2AAInfo, ptr1Offset, V1Srcs[0],
+      PNSize, PNAAInfo, ptr2Offset, LocDistance, UnderV2);
+
+  // Early exit if the check of the first PHI source against V2 is MayUseSameBuff.
+  // Other results are not possible.
+  if (Alias != MayUseSameBuff)
+    return Alias;
+
+  // If all sources of the PHI node NotSameBuff or MustUseSameBuff V2, then returns
+  // NotSameBuff / MustUseSameBuff. Otherwise, returns MayUseSameBuff.
+  for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) {
+    Value *V = V1Srcs[i];
+
+    BuffUseResult ThisAlias =
+      ModRefSameBufferCheck(V2, V2Size, V2AAInfo, ptr1Offset, V, PNSize,
+        PNAAInfo, ptr2Offset, LocDistance, UnderV2);
+    if (ThisAlias != MayUseSameBuff)
+      return ThisAlias;
+
+    return NotSameBuff;
+  }
+  return NotSameBuff;
+}
 
 /// Provides a bunch of ad-hoc rules to disambiguate a Select instruction
 /// against another.
 AliasResult BasicAAResult::aliasSelect(const SelectInst *SI, uint64_t SISize,
                                        const AAMDNodes &SIAAInfo,
                                        const Value *V2, uint64_t V2Size,
                                        const AAMDNodes &V2AAInfo,
                                        const Value *UnderV2) {