Make FindAvailableLoadedValue TBAA aware

[thopre]

Summary

FindAvailableLoadedValue() relies on FindAvailablePtrLoadStore() to run
the alias analysis when searching for an equivalent value. However,
FindAvailablePtrLoadStore() calls the alias analysis framework with a
memory location for the load constructed from an address and a size,
which thus lacks TBAA metadata info. This commit modifies
FindAvailablePtrLoadStore() to accept an optional memory location as
parameter to allow FindAvailableLoadedValue() to create it based on the
load instruction, which would then have TBAA metadata info attached.

[thopre]

Note: the test added in this commit currently fails because of https://reviews.llvm.org/D99022 (issue reported in https://reviews.llvm.org/D99022#2644973).

[nikic]

llvm/include/llvm/Analysis/Loads.h

167–168

Why make it optional? The only None use seems to be in JumpThreading, and we should be able to pass a location there as well.

(Could also drop the Ptr argument if it's required, as the memory location includes the pointer.)

[nikic]

Looks fine conceptually. I'd recommend dropping the dependency on the LoopRotate patch and testing this via InstCombine instead, which uses this in a much more direct way.

[jdoerfert]

llvm/include/llvm/Analysis/Loads.h

167–168

+1, you can always make a MemoryLocation from a pointer anyway.

[lebedev.ri]

This seems like a worthwhile change regardless of LoopRotate.
Can you perhaps add a test for one of the passes that already use FindAvailableLoadedValue()?

[thopre]

• Make patch standalone
• Add InstCombine testcase
• Fix naming of function while modifying parameters
• Make MemoryLocation mandatory

[lebedev.ri]

llvm/test/Transforms/InstCombine/load-no-aliasing.ll

1

Please precommit using llvm/utils/update_test_checks.py

[nikic]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

1394

The AATags have already been extracted above (before the loop), so there should be no need to do so again here.

llvm/test/Transforms/InstCombine/load-no-aliasing.ll

1

The -evaluate-aa-metadata flag here is not needed -- this is used for directly printing modref information, not for normal transformation tests.

[thopre]

• Remove redundant AAAATags
• Rebase on committed baseline testcase
• Remove -evaluate-aa-metadata

llvm/test/Transforms/InstCombine/load-no-aliasing.ll

1

Sorry I only saw that after committing.

[nikic]

LGTM

llvm/include/llvm/Analysis/Loads.h

 
 class AAResults;
 class DataLayout;
 class DominatorTree;
 class Instruction;
 class LoadInst;
 class Loop;
 class MDNode;
+class MemoryLocation;
 class ScalarEvolution;
 class TargetLibraryInfo;
 
 /// Return true if this is always a dereferenceable pointer. If the context
 /// instruction is specified perform context-sensitive analysis and return true
 /// if the pointer is dereferenceable at the specified instruction.
 bool isDereferenceablePointer(const Value *V, Type *Ty,
                               const DataLayout &DL,

 
 /// Scan backwards to see if we have the value of the given pointer available
 /// locally within a small number of instructions.
 ///
 /// You can use this function to scan across multiple blocks: after you call
 /// this function, if ScanFrom points at the beginning of the block, it's safe
 /// to continue scanning the predecessors.
 ///
-/// \param Ptr The pointer we want the load and store to originate from.
+/// \param Loc The location we want the load and store to originate from.
 /// \param AccessTy The access type of the pointer.
 /// \param AtLeastAtomic Are we looking for at-least an atomic load/store ? In
 /// case it is false, we can return an atomic or non-atomic load or store. In
 /// case it is true, we need to return an atomic load or store.
 /// \param ScanBB The basic block to scan.
 /// \param [in,out] ScanFrom The location to start scanning from. When this
 /// function returns, it points at the last instruction scanned.
 /// \param MaxInstsToScan The maximum number of instructions to scan. If this
 /// is zero, the whole block will be scanned.
 /// \param AA Optional pointer to alias analysis, to make the scan more
 /// precise.
 /// \param [out] IsLoadCSE Whether the returned value is a load from the same
 /// location in memory, as opposed to the value operand of a store.
 ///
 /// \returns The found value, or nullptr if no value is found.
-Value *FindAvailablePtrLoadStore(Value *Ptr, Type *AccessTy, bool AtLeastAtomic,
-                                 BasicBlock *ScanBB,
+Value *findAvailablePtrLoadStore(const MemoryLocation &Loc, Type *AccessTy,
+                                 bool AtLeastAtomic, BasicBlock *ScanBB,
                                  BasicBlock::iterator &ScanFrom,
                                  unsigned MaxInstsToScan, AAResults *AA,
                                  bool *IsLoadCSE, unsigned *NumScanedInst);
 
 /// Returns true if a pointer value \p A can be replace with another pointer
 /// value \B if they are deemed equal through some means (e.g. information from
 /// conditions).
 /// NOTE: the current implementations is incomplete and unsound. It does not
 /// reject all invalid cases yet, but will be made stricter in the future. In
 /// particular this means returning true means unknown if replacement is safe.
 bool canReplacePointersIfEqual(Value *A, Value *B, const DataLayout &DL,
                                Instruction *CtxI);
 }
 
 #endif

llvm/lib/Analysis/Loads.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumeBundleQueries.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
+#include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/GlobalAlias.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/IntrinsicInst.h"
Value *llvm::FindAvailableLoadedValue(LoadInst *Load,
                                       BasicBlock::iterator &ScanFrom,
                                       unsigned MaxInstsToScan,
                                       AAResults *AA, bool *IsLoad,
                                       unsigned *NumScanedInst) {
   // Don't CSE load that is volatile or anything stronger than unordered.
   if (!Load->isUnordered())
     return nullptr;
 
-  return FindAvailablePtrLoadStore(
-      Load->getPointerOperand(), Load->getType(), Load->isAtomic(), ScanBB,
-      ScanFrom, MaxInstsToScan, AA, IsLoad, NumScanedInst);
+  MemoryLocation Loc = MemoryLocation::get(Load);
+  return findAvailablePtrLoadStore(Loc, Load->getType(), Load->isAtomic(),
+                                   ScanBB, ScanFrom, MaxInstsToScan, AA, IsLoad,
+                                   NumScanedInst);
 }
 
 // Check if the load and the store have the same base, constant offsets and
 // non-overlapping access ranges.
-static bool AreNonOverlapSameBaseLoadAndStore(
-    Value *LoadPtr, Type *LoadTy, Value *StorePtr, Type *StoreTy,
+static bool areNonOverlapSameBaseLoadAndStore(const Value *LoadPtr,
+                                              Type *LoadTy,
+                                              const Value *StorePtr,
+                                              Type *StoreTy,
                                               const DataLayout &DL) {
   APInt LoadOffset(DL.getTypeSizeInBits(LoadPtr->getType()), 0);
   APInt StoreOffset(DL.getTypeSizeInBits(StorePtr->getType()), 0);
-  Value *LoadBase = LoadPtr->stripAndAccumulateConstantOffsets(
+  const Value *LoadBase = LoadPtr->stripAndAccumulateConstantOffsets(
       DL, LoadOffset, /* AllowNonInbounds */ false);
-  Value *StoreBase = StorePtr->stripAndAccumulateConstantOffsets(
+  const Value *StoreBase = StorePtr->stripAndAccumulateConstantOffsets(
       DL, StoreOffset, /* AllowNonInbounds */ false);
   if (LoadBase != StoreBase)
     return false;
   auto LoadAccessSize = LocationSize::precise(DL.getTypeStoreSize(LoadTy));
   auto StoreAccessSize = LocationSize::precise(DL.getTypeStoreSize(StoreTy));
   ConstantRange LoadRange(LoadOffset,
                           LoadOffset + LoadAccessSize.toRaw());
   ConstantRange StoreRange(StoreOffset,
                            StoreOffset + StoreAccessSize.toRaw());
   return LoadRange.intersectWith(StoreRange).isEmptySet();
 }
 
-static Value *getAvailableLoadStore(Instruction *Inst, Value *Ptr,
+static Value *getAvailableLoadStore(Instruction *Inst, const Value *Ptr,
                                     Type *AccessTy, bool AtLeastAtomic,
                                     const DataLayout &DL, bool *IsLoadCSE) {
   // If this is a load of Ptr, the loaded value is available.
   // (This is true even if the load is volatile or atomic, although
   // those cases are unlikely.)
   if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
     // We can value forward from an atomic to a non-atomic, but not the
     // other way around.
if (CastInst::isBitOrNoopPointerCastable(Val->getType(), AccessTy, DL)) {
         *IsLoadCSE = false;
       return Val;
     }
   }
 
   return nullptr;
 }
 
-Value *llvm::FindAvailablePtrLoadStore(Value *Ptr, Type *AccessTy,
-                                       bool AtLeastAtomic, BasicBlock *ScanBB,
-                                       BasicBlock::iterator &ScanFrom,
-                                       unsigned MaxInstsToScan,
-                                       AAResults *AA, bool *IsLoadCSE,
-                                       unsigned *NumScanedInst) {
+Value *llvm::findAvailablePtrLoadStore(
+    const MemoryLocation &Loc, Type *AccessTy, bool AtLeastAtomic,
+    BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan,
+    AAResults *AA, bool *IsLoadCSE, unsigned *NumScanedInst) {
   if (MaxInstsToScan == 0)
     MaxInstsToScan = ~0U;
 
   const DataLayout &DL = ScanBB->getModule()->getDataLayout();
-  Value *StrippedPtr = Ptr->stripPointerCasts();
+  const Value *StrippedPtr = Loc.Ptr->stripPointerCasts();
 
   while (ScanFrom != ScanBB->begin()) {
     // We must ignore debug info directives when counting (otherwise they
     // would affect codegen).
     Instruction *Inst = &*--ScanFrom;
     if (isa<DbgInfoIntrinsic>(Inst))
       continue;
 
while (ScanFrom != ScanBB->begin()) {
 
     --ScanFrom;
 
     if (Value *Available = getAvailableLoadStore(Inst, StrippedPtr, AccessTy,
                                                  AtLeastAtomic, DL, IsLoadCSE))
       return Available;
 
     // Try to get the store size for the type.
-    auto AccessSize = LocationSize::precise(DL.getTypeStoreSize(AccessTy));
-
     if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
       Value *StorePtr = SI->getPointerOperand()->stripPointerCasts();
 
       // If both StrippedPtr and StorePtr reach all the way to an alloca or
       // global and they are different, ignore the store. This is a trivial form
       // of alias analysis that is important for reg2mem'd code.
       if ((isa<AllocaInst>(StrippedPtr) || isa<GlobalVariable>(StrippedPtr)) &&
           (isa<AllocaInst>(StorePtr) || isa<GlobalVariable>(StorePtr)) &&
           StrippedPtr != StorePtr)
         continue;
 
       if (!AA) {
         // When AA isn't available, but if the load and the store have the same
         // base, constant offsets and non-overlapping access ranges, ignore the
         // store. This is a simple form of alias analysis that is used by the
         // inliner. FIXME: use BasicAA if possible.
-        if (AreNonOverlapSameBaseLoadAndStore(
-                Ptr, AccessTy, SI->getPointerOperand(),
+        if (areNonOverlapSameBaseLoadAndStore(
+                Loc.Ptr, AccessTy, SI->getPointerOperand(),
                 SI->getValueOperand()->getType(), DL))
           continue;
       } else {
         // If we have alias analysis and it says the store won't modify the
         // loaded value, ignore the store.
-        if (!isModSet(AA->getModRefInfo(SI, StrippedPtr, AccessSize)))
+        if (!isModSet(AA->getModRefInfo(SI, Loc)))
           continue;
       }
 
       // Otherwise the store that may or may not alias the pointer, bail out.
       ++ScanFrom;
       return nullptr;
     }
 
     // If this is some other instruction that may clobber Ptr, bail out.
     if (Inst->mayWriteToMemory()) {
       // If alias analysis claims that it really won't modify the load,
       // ignore it.
-      if (AA && !isModSet(AA->getModRefInfo(Inst, StrippedPtr, AccessSize)))
+      if (AA && !isModSet(AA->getModRefInfo(Inst, Loc)))
         continue;
 
       // May modify the pointer, bail out.
       ++ScanFrom;
       return nullptr;
     }
   }
 
for (Instruction &Inst : make_range(++Load->getReverseIterator(),
 
     if (Inst.mayWriteToMemory())
       MustNotAliasInsts.push_back(&Inst);
   }
 
   // If we found an available value, ensure that the instructions in between
   // did not modify the memory location.
   if (Available) {
-    auto AccessSize = LocationSize::precise(DL.getTypeStoreSize(AccessTy));
+    MemoryLocation Loc = MemoryLocation::get(Load);
     for (Instruction *Inst : MustNotAliasInsts)
-      if (isModSet(AA.getModRefInfo(Inst, StrippedPtr, AccessSize)))
+      if (isModSet(AA.getModRefInfo(Inst, Loc)))
         return nullptr;
   }
 
   return Available;
 }
 
 bool llvm::canReplacePointersIfEqual(Value *A, Value *B, const DataLayout &DL,
                                      Instruction *CtxI) {

llvm/lib/Transforms/Scalar/JumpThreading.cpp

 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/DomTreeUpdater.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/GuardUtils.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
for (BasicBlock *PredBB : predecessors(LoadBB)) {
     unsigned NumScanedInst = 0;
     Value *PredAvailable = nullptr;
     // NOTE: We don't CSE load that is volatile or anything stronger than
     // unordered, that should have been checked when we entered the function.
     assert(LoadI->isUnordered() &&
            "Attempting to CSE volatile or atomic loads");
     // If this is a load on a phi pointer, phi-translate it and search
     // for available load/store to the pointer in predecessors.
-    Value *Ptr = LoadedPtr->DoPHITranslation(LoadBB, PredBB);
-    PredAvailable = FindAvailablePtrLoadStore(
-        Ptr, LoadI->getType(), LoadI->isAtomic(), PredBB, BBIt,
-        DefMaxInstsToScan, AA, &IsLoadCSE, &NumScanedInst);
+    Type *AccessTy = LoadI->getType();
+    const auto &DL = LoadI->getModule()->getDataLayout();
+    MemoryLocation Loc(LoadedPtr->DoPHITranslation(LoadBB, PredBB),
+                       LocationSize::precise(DL.getTypeStoreSize(AccessTy)),
+                       AATags);
+    PredAvailable = findAvailablePtrLoadStore(Loc, AccessTy, LoadI->isAtomic(),
+                                              PredBB, BBIt, DefMaxInstsToScan,
+                                              AA, &IsLoadCSE, &NumScanedInst);
 
     // If PredBB has a single predecessor, continue scanning through the
     // single predecessor.
     BasicBlock *SinglePredBB = PredBB;
     while (!PredAvailable && SinglePredBB && BBIt == SinglePredBB->begin() &&
            NumScanedInst < DefMaxInstsToScan) {
       SinglePredBB = SinglePredBB->getSinglePredecessor();
       if (SinglePredBB) {
         BBIt = SinglePredBB->end();
-        PredAvailable = FindAvailablePtrLoadStore(
-            Ptr, LoadI->getType(), LoadI->isAtomic(), SinglePredBB, BBIt,
+        PredAvailable = findAvailablePtrLoadStore(
+            Loc, AccessTy, LoadI->isAtomic(), SinglePredBB, BBIt,
             (DefMaxInstsToScan - NumScanedInst), AA, &IsLoadCSE,
             &NumScanedInst);
       }
     }
 
     if (!PredAvailable) {
       OneUnavailablePred = PredBB;
       continue;

llvm/test/Transforms/InstCombine/load-no-aliasing.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -tbaa -evaluate-aa-metadata -instcombine -S < %s | FileCheck %s
+; RUN: opt -tbaa -instcombine -S < %s | FileCheck %s
 
 ; Check that load to load forwarding works with non aliasing store inbetween.
 define i32 @test_load_store_load_combine(i32*, float*) {
 ; CHECK-LABEL: @test_load_store_load_combine(
 ; CHECK-NEXT:    [[A:%.*]] = load i32, i32* [[TMP0:%.*]], align 4, !tbaa [[TBAA0:![0-9]+]]
 ; CHECK-NEXT:    [[F:%.*]] = sitofp i32 [[A]] to float
 ; CHECK-NEXT:    store float [[F]], float* [[TMP1:%.*]], align 4, !tbaa [[TBAA4:![0-9]+]]
-; CHECK-NEXT:    [[B:%.*]] = load i32, i32* [[TMP0]], align 4, !tbaa [[TBAA0]]
-; CHECK-NEXT:    ret i32 [[B]]
+; CHECK-NEXT:    ret i32 [[A]]
 ;
   %a = load i32, i32* %0, align 4, !tbaa !0
   %f = sitofp i32 %a to float
   store float %f, float* %1, align 4, !tbaa !4
   %b = load i32, i32* %0, align 4, !tbaa !0
   ret i32 %b
 }
 
 !0 = !{!1, !1, i64 0}
 !1 = !{!"int", !2, i64 0}
 !2 = !{!"omnipotent char", !3, i64 0}
 !3 = !{!"Simple C++ TBAA"}
 !4 = !{!5, !5, i64 0}
 !5 = !{!"float", !2, i64 0}