[Loads] Add canReplacePointersIfEqual helper.

[fhahn]

Summary

This patch adds an initial, incomeplete and unsound implementation of
canReplacePointersIfEqual to check if a pointer value A can be replaced
by another pointer value B, that are deemed to be equivalent through
some means (e.g. information from conditions).

Note that is in general not sound to blindly replace pointers based on
equality, for example if they are based on different underlying objects.

LLVM's memory model is not completely settled as of now; see
https://bugs.llvm.org/show_bug.cgi?id=34548 for a more detailed
discussion.

The initial version of canReplacePointersIfEqual only rejects a very
specific case: replacing a pointer with a constant expression that is
not dereferenceable. Such a replacement is problematic and can be
restricted relatively easily without impacting most code. Using it to
limit replacements in GVN/SCCP/CVP only results in small differences in
7 programs out of MultiSource/SPEC2000/SPEC2006 on X86 with -O3 -flto.

This patch is supposed to be an initial step to improve the current
situation and the helper should be made stricter in the future. But this
will require careful analysis of the impact on performance.

[fhahn]

Directly take DataLayout as argument, as CtxI can be null.

[efriedma]

llvm/include/llvm/Analysis/Loads.h

161

Maybe make this note a little louder: put NOTE in all caps, at the beginning of a new paragraph.

llvm/lib/Analysis/Loads.cpp

515

This check is full of holes... but I guess it's a good thing if we can start marking the places in transforms where this matters without worrying too much about the initial performance impact.

[nikic]

llvm/lib/Analysis/Loads.cpp

515

This check looks fundamentally incompatible with opaque pointers.

[nikic]

llvm/lib/Analysis/Loads.cpp

515

Maybe just check derefability of a single byte, instead of the pointer element type?

[fhahn]

Made the language a bit louder, also add note to canReplacePointersIfEqual definition.

[fhahn]

llvm/lib/Analysis/Loads.cpp

515

This check is full of holes... but I guess it's a good thing if we can start marking the places in transforms where this matters without worrying too much about the initial performance impact.

Yes, I added a note. The holes are intentional, to avoid causing too many issues at once and allowing us to gradually tighten the restrictions. FWIW if you require both pointers to be dereferenceable, there are binary changes in ~50 programs out of MultiSource/SPEC2000/SPEC2006, so not too terrible either. But it's probably better to take things in steps.

This check looks fundamentally incompatible with opaque pointers.
Maybe just check derefability of a single byte, instead of the pointer element type?

That might work, but we probably should do this for all uses of isDereferenceablePointer, potentially as follow-up?

[nikic]

llvm/lib/Analysis/Loads.cpp

515

That might work, but we probably should do this for all uses of isDereferenceablePointer, potentially as follow-up?

To be clear, the problem is not in the isDereferenceablePointer() API, but in the way it is used in this specific case. Other uses of this API correctly pass in a load type, not a pointer element type. As you do not have access to a load type here, checking for a single byte seems like the best you can do.

[fhahn]

Use isDereferenceableAndAlignedPointer directly and pass size of 1.

[fhahn]

llvm/lib/Analysis/Loads.cpp

515

Oh right, I missed that the type is actually only used to get the size. Changed to use isDereferenceableAndAlignedPointer directly.

[aqjune]

Hi, I agree this is is a desirable direction.
Should we have a unit test for this function?

[fhahn]

In D85524#2232554, @aqjune wrote:

Hi, I agree this is is a desirable direction.
Should we have a unit test for this function?

That seems like a good idea, I added a unit test, which also contains a note that the current implementation is incomplete. I also extended the note in the header to state that returning true currently means unknown if they can be replaced.

[aqjune]

LGTM

llvm/include/llvm/Analysis/Loads.h

166

Would it be better if it starts with CanReplace...?

[fhahn]

Thanks!

llvm/include/llvm/Analysis/Loads.h

166

I think https://llvm.org/docs/CodingStandards.html#name-types-functions-variables-and-enumerators-properly suggests starting function names with lowercases. The functions in this file seem to mix both upper and lower case first characters. Given that I think it is slightly better to go with the suggestion in the docs. But I am happy to change post-commit if I am missing something and upper case would be better!

llvm/include/llvm/Analysis/Loads.h

 /// 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,
                                  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

if (Inst->mayWriteToMemory()) {
       return nullptr;
     }
   }
 
   // Got to the start of the block, we didn't find it, but are done for this
   // block.
   return nullptr;
 }
+
+bool llvm::canReplacePointersIfEqual(Value *A, Value *B, const DataLayout &DL,
+                                     Instruction *CtxI) {
+  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.
+  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(A->getType()), 1);
+    return C->isNullValue() ||
+           isDereferenceableAndAlignedPointer(B, Align(1), OneByte, DL, CtxI);
+  }
+
+  return true;
+}

llvm/unittests/Analysis/LoadsTest.cpp

)IR");
   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));
 }
+
+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) {
+  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");
+  auto &DL = M->getDataLayout();
+  auto *GV = M->getNamedValue("f");
+  ASSERT_TRUE(GV);
+  auto *F = dyn_cast<Function>(GV);
+  ASSERT_TRUE(F);
+
+  // 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();
+  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));
+
+  ++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));
+}