[Loads] Handle simple cases with same base pointer with constant offsets in FindAvailableLoadedValue when AA is null.

[hjyamauchi]

Summary

This will help with devirtualization (store forwarding with vtable pointers in
the presence of other stores into members in the constructor.) During inlining,
we don't have AA.

[hjyamauchi]

This is split off of D69591.

[hjyamauchi]

Any comment?

[davidxl]

BasicAA is stateless and should be available and used here to disambiguate.

[hjyamauchi]

I believe if I request AA in Inliner.cpp and pass it down to FindAvailableLoadedValue through tryPromoteCall (D71308), it would work without this patch.

Is it okay to assume that a) the AA is BasicAA and b) BasicAA is stateless since the AA interface is more generic? Is there a way to condition this logic on those conditions?

[hjyamauchi]

Rebased.

[davidxl]

llvm/lib/Analysis/Loads.cpp

479

can you guard the change with

if (!AA) {
}

as we AA, it will be unnecessary.

[hjyamauchi]

Address comment. PTAL.

[davidxl]

lgtm

[lebedev.ri]

(just passing-by remark)

In D71307#1792951, @yamauchi wrote:

I believe if I request AA in Inliner.cpp and pass it down to FindAvailableLoadedValue through tryPromoteCall (D71308), it would work without this patch.

Is it okay to assume that a) the AA is BasicAA and b) BasicAA is stateless since the AA interface is more generic? Is there a way to condition this logic on those conditions?

Perhaps it may be more productive to explain why this This is a simple form of alias analysis. *has* to exist?
Why can't, as suggested, BasicAA be used? What goes wrong if BasicAA is used?

[hjyamauchi]

To repeat/expand my question above,..

As I understand, it'd be possible to get the AA from the pass manager from the inline pass, but the AA interface is abstract and the inline pass can't assume what AA implementations they are (which is up to the pass manager setup) and they are stateless BasicAA (otherwise we'd need to invalidate/update stateful AA which is hard to do during (complex) inlining transformations and there's no guarantee that BasicAA will stay stateless in the future.) Is there a way to specifically request BasicAA and only it and that it must be stateless? The current proposed approach is to have this "simple form of alias analysis" to handle enough of the aliasing around a C++ constructor call for this missed inlining case.

[xbolva00]

In D71307#1827040, @lebedev.ri wrote:

(just passing-by remark)

In D71307#1792951, @yamauchi wrote:

I believe if I request AA in Inliner.cpp and pass it down to FindAvailableLoadedValue through tryPromoteCall (D71308), it would work without this patch.

Is it okay to assume that a) the AA is BasicAA and b) BasicAA is stateless since the AA interface is more generic? Is there a way to condition this logic on those conditions?

Perhaps it may be more productive to explain why this This is a simple form of alias analysis. *has* to exist?
Why can't, as suggested, BasicAA be used? What goes wrong if BasicAA is used?

I agree, it is quite bad to reinvent simple alias analysis here. If this is really a way to go, maybe move this code to own function?

[davidxl]

As other commented, please extract the code into its own function also add the support when AA is available ( as other parts of the function does).

[hjyamauchi]

Done.

[xbolva00]

Thanks

[xbolva00]

llvm/lib/Analysis/Loads.cpp

487

else {

?

[hjyamauchi]

llvm/lib/Analysis/Loads.cpp

487

Do you mean it'd be good to combine the two if statements?

if (!AA) {
  // ...
  if (AreNonOverlapSameBaseLoadAndStore(..))
    continue;
} else {
  // ...
  if (!isModSet(AA->getModRefInfo(SI, StrippedPtr, AccessSize)))
    continue;
}

[xbolva00]

llvm/lib/Analysis/Loads.cpp

487

Yes

(optional, if you like, do so)

[hjyamauchi]

Address comment (combine the if statements).

llvm/lib/Analysis/Loads.cpp

Value *llvm::FindAvailableLoadedValue(LoadInst *Load,
   if (!Load->isUnordered())
     return nullptr;
 
   return FindAvailablePtrLoadStore(
       Load->getPointerOperand(), 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,
+    const DataLayout &DL) {
+  APInt LoadOffset(DL.getTypeSizeInBits(LoadPtr->getType()), 0);
+  APInt StoreOffset(DL.getTypeSizeInBits(StorePtr->getType()), 0);
+  Value *LoadBase = LoadPtr->stripAndAccumulateConstantOffsets(
+      DL, LoadOffset, /* AllowNonInbounds */ false);
+  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();
+}
+
 Value *llvm::FindAvailablePtrLoadStore(Value *Ptr, Type *AccessTy,
                                        bool AtLeastAtomic, BasicBlock *ScanBB,
                                        BasicBlock::iterator &ScanFrom,
                                        unsigned MaxInstsToScan,
                                        AliasAnalysis *AA, bool *IsLoadCSE,
                                        unsigned *NumScanedInst) {
   if (MaxInstsToScan == 0)
     MaxInstsToScan = ~0U;
if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
       // 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(),
+                SI->getValueOperand()->getType(), DL))
+          continue;
+      }
+
       // If we have alias analysis and it says the store won't modify the loaded
       // value, ignore the store.
       if (AA && !isModSet(AA->getModRefInfo(SI, StrippedPtr, AccessSize)))
         continue;
 
       // Otherwise the store that may or may not alias the pointer, bail out.
       ++ScanFrom;
       return nullptr;
     }

llvm/unittests/Analysis/CMakeLists.txt

add_llvm_unittest(AnalysisTests
   CaptureTrackingTest.cpp
   CFGTest.cpp
   CGSCCPassManagerTest.cpp
   DivergenceAnalysisTest.cpp
   DomTreeUpdaterTest.cpp
   GlobalsModRefTest.cpp
   IVDescriptorsTest.cpp
   LazyCallGraphTest.cpp
+  LoadsTest.cpp
   LoopInfoTest.cpp
   MemoryBuiltinsTest.cpp
   MemorySSATest.cpp
   OrderedBasicBlockTest.cpp
   OrderedInstructionsTest.cpp
   PhiValuesTest.cpp
   ProfileSummaryInfoTest.cpp
   ScalarEvolutionTest.cpp

llvm/unittests/Analysis/LoadsTest.cpp

+//===- LoadsTest.cpp - local load analysis unit tests ---------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/Loads.h"
+#include "llvm/AsmParser/Parser.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Support/SourceMgr.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {
+  SMDiagnostic Err;
+  std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);
+  if (!Mod)
+    Err.print("AnalysisTests", errs());
+  return Mod;
+}
+
+TEST(LoadsTest, FindAvailableLoadedValueSameBasePtrConstantOffsetsNullAA) {
+  LLVMContext C;
+  std::unique_ptr<Module> M = parseIR(C,
+                                      R"IR(
+%class = type <{ i32, i32 }>
+
+define i32 @f() {
+entry:
+  %o = alloca %class
+  %f1 = getelementptr inbounds %class, %class* %o, i32 0, i32 0
+  store i32 42, i32* %f1
+  %f2 = getelementptr inbounds %class, %class* %o, i32 0, i32 1
+  store i32 43, i32* %f2
+  %v = load i32, i32* %f1
+  ret i32 %v
+}
+)IR");
+  auto *GV = M->getNamedValue("f");
+  ASSERT_TRUE(GV);
+  auto *F = dyn_cast<Function>(GV);
+  ASSERT_TRUE(F);
+  Instruction *Inst = &F->front().front();
+  auto *AI = dyn_cast<AllocaInst>(Inst);
+  ASSERT_TRUE(AI);
+  Inst = &*++F->front().rbegin();
+  auto *LI = dyn_cast<LoadInst>(Inst);
+  ASSERT_TRUE(LI);
+  BasicBlock::iterator BBI(LI);
+  Value *Loaded = FindAvailableLoadedValue(
+      LI, LI->getParent(), BBI, 0, nullptr, nullptr);
+  ASSERT_TRUE(Loaded);
+  auto *CI = dyn_cast<ConstantInt>(Loaded);
+  ASSERT_TRUE(CI);
+  ASSERT_TRUE(CI->equalsInt(42));
+}