[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

524

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

524

This check looks fundamentally incompatible with opaque pointers.

[nikic]

llvm/lib/Analysis/Loads.cpp

524

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

524

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

524

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

524

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 that the current implementations is incomplete and
+/// unsound. It does not reject all invalid cases yet and will be made stricter
+/// in the future.
+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");
+
+  if (auto *C = dyn_cast<Constant>(B)) {
+    return C->isNullValue() ||
+           isDereferenceablePointer(B, Ty->getPointerElementType(), DL, CtxI);
+  }
+
+  return true;
+}