[Loads] Return false in canReplacePointersIfEqual helper for non-aliasing pointers

[mnadeem]

Summary

As suggested in https://discourse.llvm.org/t/gvn-aa-c-should-we-propagate-equalities-for-noalias-pointers/68107

[aqjune]

Looks good to me in high level, but I suggest waiting for one more accept since I haven't been working with the LLVM codebase for a while.

[nikic]

I don't think this is the correct check to do, and I also don't particularly want to introduce AA queries for this. The correct check is whether getUnderlyingObject(A) == getUnderlyingObject(B), in reasonable approximation. (There are more cases that are safe, e.g. a null pointer can be replaced with anything, but they are probably not very useful.)

I believe that if we actually want to fix this class of problems (which goes beyond GVN), we should fix it properly, and that starts with using the right predicate so we get a correct idea of the performance regressions we should expect.

[mnadeem]

Ported all changes to the patch I previously added as the child revision.

llvm/include/llvm/Analysis/Loads.h

 
 /// 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);
+                               Instruction *CtxI, AAResults *AA = nullptr);
 }
 
 #endif

llvm/lib/Analysis/Loads.cpp

for (Instruction *Inst : MustNotAliasInsts)
       if (isModSet(AA.getModRefInfo(Inst, Loc)))
         return nullptr;
   }
 
   return Available;
 }
 
 bool llvm::canReplacePointersIfEqual(Value *A, Value *B, const DataLayout &DL,
-                                     Instruction *CtxI) {
+                                     Instruction *CtxI, AAResults *AA) {
   Type *Ty = A->getType();
   assert(Ty == B->getType() && Ty->isPointerTy() &&
          "values must have matching pointer types");
 
   // NOTE: The checks in the function are incomplete and currently miss illegal
   // cases! The current implementation is a starting point and the
   // implementation should be made stricter over time.
+
+  // Do not replace pointers if they are known noalias.
+  if (AA && AA->alias(A, B) == AliasResult::NoAlias)
+    return false;
+
   if (auto *C = dyn_cast<Constant>(B)) {
     // Do not allow replacing a pointer with a constant pointer, unless it is
     // either null or at least one byte is dereferenceable.
     APInt OneByte(DL.getPointerTypeSizeInBits(Ty), 1);
     return C->isNullValue() ||
            isDereferenceableAndAlignedPointer(B, Align(1), OneByte, DL, CtxI);
   }
 
   return true;
 }

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/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/BasicAliasAnalysis.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/AsmParser/Parser.h"
 #include "llvm/IR/Constants.h"
+#include "llvm/IR/Dominators.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;
 
TEST(LoadsTest, CanReplacePointersIfEqual) {
   LLVMContext C;
   std::unique_ptr<Module> M = parseIR(C,
                                       R"IR(
 @y = common global [1 x i32] zeroinitializer, align 4
 @x = common global [1 x i32] zeroinitializer, align 4
 
 declare void @use(i32*)
 
-define void @f(i32* %p) {
+define void @f(i32* %p, i32* noalias %p1) {
   call void @use(i32* getelementptr inbounds ([1 x i32], [1 x i32]* @y, i64 0, i64 0))
   call void @use(i32* getelementptr inbounds (i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @x, i64 0, i64 0), i64 1))
   ret void
 }
 )IR");
   const auto &DL = M->getDataLayout();
   auto *GV = M->getNamedValue("f");
   ASSERT_TRUE(GV);
   auto *F = dyn_cast<Function>(GV);
   ASSERT_TRUE(F);
 
+  DominatorTree DT(*F);
+  TargetLibraryInfoImpl TLII;
+  TargetLibraryInfo TLI(TLII);
+  AssumptionCache AC(*F);
+  AAResults AA(TLI);
+  BasicAAResult BAA(DL, *F, TLI, AC, &DT);
+  AA.addAAResult(BAA);
+
   // NOTE: the implementation of canReplacePointersIfEqual is incomplete.
   // Currently the only the cases it returns false for are really sound and
   // returning true means unknown.
   Value *P = &*F->arg_begin();
+  Value *NoAliasPtr = F->getArg(1);
+
   auto InstIter = F->front().begin();
   Value *ConstDerefPtr = *cast<CallInst>(&*InstIter)->arg_begin();
   // ConstDerefPtr is a constant pointer that is provably de-referenceable. We
   // can replace an arbitrary pointer with it.
   EXPECT_TRUE(canReplacePointersIfEqual(P, ConstDerefPtr, DL, nullptr));
 
+  // Do not replace pointers if they are known noalias.
+  EXPECT_FALSE(
+      canReplacePointersIfEqual(NoAliasPtr, ConstDerefPtr, DL, nullptr, &AA));
+  EXPECT_FALSE(
+      canReplacePointersIfEqual(ConstDerefPtr, NoAliasPtr, DL, nullptr, &AA));
+  EXPECT_FALSE(canReplacePointersIfEqual(P, NoAliasPtr, DL, nullptr, &AA));
+  EXPECT_FALSE(canReplacePointersIfEqual(NoAliasPtr, P, DL, nullptr, &AA));
+
   ++InstIter;
   Value *ConstUnDerefPtr = *cast<CallInst>(&*InstIter)->arg_begin();
   // ConstUndDerefPtr is a constant pointer that is provably not
   // de-referenceable. We cannot replace an arbitrary pointer with it.
   EXPECT_FALSE(
       canReplacePointersIfEqual(ConstDerefPtr, ConstUnDerefPtr, DL, nullptr));
 }