Exclude non-integral pointers in isBytewiseValue

[cherry]

Summary

Technically, non-integral pointers "have an unspecified bitwise
representation", so they are not bytewise values. In particular,
don't use memset on those values.

[cherry]

include/llvm/Analysis/ValueTracking.h

226

Provided a default value as this function is public so it won't break external uses. External uses probably don't care about non-integral pointer anyway. (E.g. clang has one use.)

[reames]

This patch made me curious because I remembered fixing this one. Turned out that's still a patch we're carrying downstream. Oops. :(

The general approach we took here was a bit different. I don't have a strong preference, but I want to see what you think of the alternate before continuing.

The basic approach we took was two fold: 1) Disallow stores of non-integral types as "legal stores" in the sense of this file, and 2) inhibit formation of geps off of null in an non-integral address space so as to prevent formation of inttoptrs.

What do you think of the merits of the two approaches? Is there something your approach catches ours doesn't?

[cherry]

Thank you for the comment!

The basic approach we took was two fold: 1) Disallow stores of non-integral types as "legal stores" in the sense of this file,

I guess "this file" you refers is ValueTracking.cpp? But it doesn't seem to mention legal stores. There is "legal store" in LoopIdiomRecognize.cpp. But in this case it probably won't completely fix our problem, where memset could be generated in MemCpyOpt. I initially thought of fixing just MemCpyOpt. As the spec says non-integral pointers "have an unspecified bitwise representation", I turn to the current patch, which I think is more aligned with the spec.

and 2) inhibit formation of geps off of null in an non-integral address space so as to prevent formation of inttoptrs.

Sorry, I'm not sure I fully understand this. This seems a reasonable thing to do. But I'm sure how it is related to storing null values into non-integral pointer typed memory.

If you would like to share your patch, I'm happy to take a look and give it a try. Thank you!

[efriedma]

test/Transforms/MemCpyOpt/non-integral-ptr.ll

20

It's not clear to me why a memset is "wrong" here; either way, you're setting all the bits to zero. Is the issue that const0 is not actually an all-zero constant?

The LLVM null pointer constant is treated as an all-zero value in LLVM, even on targets where a null pointer constant in C would have some non-zero value. If you think that isn't appropriate, please start a thread on llvmdev; I haven't really thought it through completely, but it would probably get complicated due to the impact on various transforms like constant folding. If you need an "opaque" null pointer constant, there's probably a simpler solution: define a special global @llvm.opaque.nullptr or something like that, and make your frontend use it instead of ConstantPointerNull.

[cherry]

test/Transforms/MemCpyOpt/non-integral-ptr.ll

20

Thanks for the comment.

Generating memset isn't immediately wrong, but other parts of the optimizer, like store-to-load forwarding, may try to do further optimizations and bad things could happen. For example, it may construct an integer 0 and convert to non-integral pointer type, which fails, or do other things that invalidate the non-integral pointer semantics.

I'm not suggesting that it should have a non-zero value. It is a zero value, just cannot be converted to/from integer zero value.

Also, there is a similar test test/Transforms/LoopIdiom/non-integral-pointers.ll that checks memset is not used for non-integral pointers.

[efriedma]

include/llvm/Analysis/ValueTracking.h

226

I'd prefer not to do this; constructing a DataLayout like this is probably sort of expensive. It's not a big deal to update clang.

test/Transforms/MemCpyOpt/non-integral-ptr.ll

20

Either the bits of a null pointer can't be inspected at all, or optimizations can assume the bits are actually zero; there is no in-between state. And whichever choice is correct, changing isBytewiseValue like this doesn't help make LLVM consistent. If the bits can't be inspected, the IR shouldn't contain ConstantPointerNull, and isBytewiseValue won't be able to prove anything anyway. If the bits can be inspected, isBytewiseValue is already returning the correct answer.

That said, this doesn't really have any impact on targets which don't have non-integral pointers, so I don't really care that much about what happens here; maybe this is helpful in practice even if it isn't logically consistent.

[cherry]

include/llvm/Analysis/ValueTracking.h

226

Ok, will do.

test/Transforms/MemCpyOpt/non-integral-ptr.ll

20

I'm not sure why ConstantPointerNull implies the bits can be inspected, or why memset must be used.

In the documentation it says non-integral pointers "have an unspecified bitwise representation". If the zero value of non-integral pointer, unlike all other values, has a defined bitwise representation, it probably need to be documented this way, although it looks weird to me. Maybe @reames could help clarify the semantics.

Thanks.

[cherry]

include/llvm/Analysis/ValueTracking.h

226

Done.

[cherry]

Hello. Is there anything I can do for this to proceed? Thank you!

[efriedma]

I'm okay with this, I guess... but someone more familiar with non-integral pointers in practice should approve.

Also, it would be nice to fix LangRef to clarify the interaction of non-integral pointers with a known bit-pattern.

[cherry]

Also, it would be nice to fix LangRef to clarify the interaction of non-integral pointers with a known bit-pattern.

Added a clarification about the zero value. Thanks.

[reames]

After taking a look at this again, I remain unconvinced of the need for this patch. In particular, I took your test case and ran it against our downstream copy, and discovered my previous comment was incorrect. We actually *don't* prevent the transform you're preventing here. I'm getting a strong sense that this is working around a deeper problem, and we need to figure out what that deeper problem is before going forward.

Just to check the obvious, you're not trying to use a non-zero value for null are you? If so, then this patch *is* warranted, but is definitely not anywhere near sufficient to resolve the whole problem.

test/Transforms/MemCpyOpt/non-integral-ptr.ll

20

A bit of background here.

For all practical GCs I know of, even relocating and compacting GCs, the bit pattern of null is in fact zero, and remains zero throughout the GC cycle.

As such, we've chosen to take a practical approach where an non-integral address space pointer value has an unspecified value, but we've baked in null as the zero pattern in a few spots.

As Eli points out, the optimize makes it practically hard to describe an address space for which the null value is not zero. We can describe an AS where null is dereferenceable, but not one where null != 0.

</end background>

docs/LangRef.rst

 -------------------------
 
 Note: non-integral pointer types are a work in progress, and they should be
 considered experimental at this time.
 
 LLVM IR optionally allows the frontend to denote pointers in certain address
 spaces as "non-integral" via the :ref:`datalayout string<langref_datalayout>`.
 Non-integral pointer types represent pointers that have an *unspecified* bitwise
-representation; that is, the integral representation may be target dependent or
-unstable (not backed by a fixed integer).
+representation (including the null value); that is, the integral representation
+may be target dependent or unstable (not backed by a fixed integer).
 
 ``inttoptr`` instructions converting integers to non-integral pointer types are
 ill-typed, and so are ``ptrtoint`` instructions converting values of
 non-integral pointer types to integers.  Vector versions of said instructions
 are ill-typed as well.
 
 .. _globalvars:
 

include/llvm/Analysis/ValueTracking.h

class Value;
   bool SignBitMustBeZero(const Value *V, const TargetLibraryInfo *TLI);
 
   /// If the specified value can be set by repeating the same byte in memory,
   /// return the i8 value that it is represented with. This is true for all i8
   /// values obviously, but is also true for i32 0, i32 -1, i16 0xF0F0, double
   /// 0.0 etc. If the value can't be handled with a repeated byte store (e.g.
   /// i16 0x1234), return null. If the value is entirely undef and padding,
   /// return undef.
-  Value *isBytewiseValue(Value *V);
+  Value *isBytewiseValue(Value *V, const DataLayout &DL);
 
   /// Given an aggregrate and an sequence of indices, see if the scalar value
   /// indexed is already around as a register, for example if it were inserted
   /// directly into the aggregrate.
   ///
   /// If InsertBefore is not null, this function will duplicate (modified)
   /// insertvalues when a part of a nested struct is extracted.
   Value *FindInsertedValue(Value *V,

lib/Analysis/ValueTracking.cpp

for (unsigned i = 0; i != NumElts; ++i) {
     auto *CElt = dyn_cast<ConstantFP>(Elt);
     if (!CElt || CElt->isNaN())
       return false;
   }
   // All elements were confirmed not-NaN or undefined.
   return true;
 }
 
-Value *llvm::isBytewiseValue(Value *V) {
+// Whether a type contains non-integral pointer.
+static bool containsNonIntegralPointer(Type *T, const DataLayout &DL) {
+  if (DL.getNonIntegralAddressSpaces().empty())
+    return false;
+
+  switch (T->getTypeID()) {
+  case Type::PointerTyID:
+    return DL.isNonIntegralPointerType(T);
+  case Type::ArrayTyID:
+    return containsNonIntegralPointer(T->getArrayElementType(), DL);
+  case Type::VectorTyID:
+    return containsNonIntegralPointer(T->getVectorElementType(), DL);
+  case Type::StructTyID: {
+    for (unsigned I = 0, N = T->getStructNumElements(); I < N; ++I)
+      if (containsNonIntegralPointer(T->getStructElementType(I), DL))
+        return true;
+    return false;
+  }
+  default:
+    return false;
+  }
+}
+
+Value *llvm::isBytewiseValue(Value *V, const DataLayout &DL) {
 
   // All byte-wide stores are splatable, even of arbitrary variables.
   if (V->getType()->isIntegerTy(8))
     return V;
 
+  // The bit pattern of non-integral pointer is technically undefined.
+  if (containsNonIntegralPointer(V->getType(), DL))
+    return nullptr;
+
   LLVMContext &Ctx = V->getContext();
 
   // Undef don't care.
   auto *UndefInt8 = UndefValue::get(Type::getInt8Ty(Ctx));
   if (isa<UndefValue>(V))
     return UndefInt8;
 
   Constant *C = dyn_cast<Constant>(V);
if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
     Type *Ty = nullptr;
     if (CFP->getType()->isHalfTy())
       Ty = Type::getInt16Ty(Ctx);
     else if (CFP->getType()->isFloatTy())
       Ty = Type::getInt32Ty(Ctx);
     else if (CFP->getType()->isDoubleTy())
       Ty = Type::getInt64Ty(Ctx);
     // Don't handle long double formats, which have strange constraints.
-    return Ty ? isBytewiseValue(ConstantExpr::getBitCast(CFP, Ty)) : nullptr;
+    return Ty ? isBytewiseValue(ConstantExpr::getBitCast(CFP, Ty), DL) : nullptr;
   }
 
   // We can handle constant integers that are multiple of 8 bits.
   if (ConstantInt *CI = dyn_cast<ConstantInt>(C)) {
     if (CI->getBitWidth() % 8 == 0) {
       assert(CI->getBitWidth() > 8 && "8 bits should be handled above!");
       if (!CI->getValue().isSplat(8))
         return nullptr;
auto Merge = [&](Value *LHS, Value *RHS) -> Value * {
     if (RHS == UndefInt8)
       return LHS;
     return nullptr;
   };
 
   if (ConstantDataSequential *CA = dyn_cast<ConstantDataSequential>(C)) {
     Value *Val = UndefInt8;
     for (unsigned I = 0, E = CA->getNumElements(); I != E; ++I)
-      if (!(Val = Merge(Val, isBytewiseValue(CA->getElementAsConstant(I)))))
+      if (!(Val = Merge(Val, isBytewiseValue(CA->getElementAsConstant(I), DL))))
         return nullptr;
     return Val;
   }
 
   if (isa<ConstantVector>(C)) {
     Constant *Splat = cast<ConstantVector>(C)->getSplatValue();
-    return Splat ? isBytewiseValue(Splat) : nullptr;
+    return Splat ? isBytewiseValue(Splat, DL) : nullptr;
   }
 
   if (isa<ConstantArray>(C) || isa<ConstantStruct>(C)) {
     Value *Val = UndefInt8;
     for (unsigned I = 0, E = C->getNumOperands(); I != E; ++I)
-      if (!(Val = Merge(Val, isBytewiseValue(C->getOperand(I)))))
+      if (!(Val = Merge(Val, isBytewiseValue(C->getOperand(I), DL))))
         return nullptr;
     return Val;
   }
 
   // Don't try to handle the handful of other constants.
   return nullptr;
 }
 

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

if (!isa<SCEVConstant>(StoreEv->getOperand(1)))
     return LegalStoreKind::None;
 
   // See if the store can be turned into a memset.
 
   // If the stored value is a byte-wise value (like i32 -1), then it may be
   // turned into a memset of i8 -1, assuming that all the consecutive bytes
   // are stored.  A store of i32 0x01020304 can never be turned into a memset,
   // but it can be turned into memset_pattern if the target supports it.
-  Value *SplatValue = isBytewiseValue(StoredVal);
+  Value *SplatValue = isBytewiseValue(StoredVal, *DL);
   Constant *PatternValue = nullptr;
 
   // Note: memset and memset_pattern on unordered-atomic is yet not supported
   bool UnorderedAtomic = SI->isUnordered() && !SI->isSimple();
 
   // If we're allowed to form a memset, and the stored value would be
   // acceptable for memset, use it.
   if (!UnorderedAtomic && HasMemset && SplatValue &&
if (FirstStride == FirstStoreSize || -FirstStride == FirstStoreSize) {
       Heads.insert(SL[i]);
       continue;
     }
 
     Value *FirstSplatValue = nullptr;
     Constant *FirstPatternValue = nullptr;
 
     if (For == ForMemset::Yes)
-      FirstSplatValue = isBytewiseValue(FirstStoredVal);
+      FirstSplatValue = isBytewiseValue(FirstStoredVal, *DL);
     else
       FirstPatternValue = getMemSetPatternValue(FirstStoredVal, DL);
 
     assert((FirstSplatValue || FirstPatternValue) &&
            "Expected either splat value or pattern value.");
 
     IndexQueue.clear();
     // If a store has multiple consecutive store candidates, search Stores
for (auto &k : IndexQueue) {
       if (FirstStride != SecondStride)
         continue;
 
       Value *SecondStoredVal = SL[k]->getValueOperand();
       Value *SecondSplatValue = nullptr;
       Constant *SecondPatternValue = nullptr;
 
       if (For == ForMemset::Yes)
-        SecondSplatValue = isBytewiseValue(SecondStoredVal);
+        SecondSplatValue = isBytewiseValue(SecondStoredVal, *DL);
       else
         SecondPatternValue = getMemSetPatternValue(SecondStoredVal, DL);
 
       assert((SecondSplatValue || SecondPatternValue) &&
              "Expected either splat value or pattern value.");
 
       if (isConsecutiveAccess(SL[i], SL[k], *DL, *SE, false)) {
         if (For == ForMemset::Yes) {

 
 /// processLoopStridedStore - We see a strided store of some value.  If we can
 /// transform this into a memset or memset_pattern in the loop preheader, do so.
 bool LoopIdiomRecognize::processLoopStridedStore(
     Value *DestPtr, unsigned StoreSize, unsigned StoreAlignment,
     Value *StoredVal, Instruction *TheStore,
     SmallPtrSetImpl<Instruction *> &Stores, const SCEVAddRecExpr *Ev,
     const SCEV *BECount, bool NegStride, bool IsLoopMemset) {
-  Value *SplatValue = isBytewiseValue(StoredVal);
+  Value *SplatValue = isBytewiseValue(StoredVal, *DL);
   Constant *PatternValue = nullptr;
 
   if (!SplatValue)
     PatternValue = getMemSetPatternValue(StoredVal, DL);
 
   assert((SplatValue || PatternValue) &&
          "Expected either splat value or pattern value.");
 

lib/Transforms/Scalar/MemCpyOptimizer.cpp

if (!isa<StoreInst>(BI) && !isa<MemSetInst>(BI)) {
       continue;
     }
 
     if (StoreInst *NextStore = dyn_cast<StoreInst>(BI)) {
       // If this is a store, see if we can merge it in.
       if (!NextStore->isSimple()) break;
 
       // Check to see if this stored value is of the same byte-splattable value.
-      Value *StoredByte = isBytewiseValue(NextStore->getOperand(0));
+      Value *StoredByte = isBytewiseValue(NextStore->getOperand(0), DL);
       if (isa<UndefValue>(ByteVal) && StoredByte)
         ByteVal = StoredByte;
       if (ByteVal != StoredByte)
         break;
 
       // Check to see if this store is to a constant offset from the start ptr.
       int64_t Offset;
       if (!IsPointerOffset(StartPtr, NextStore->getPointerOperand(), Offset,
bool MemCpyOptPass::processStore(StoreInst *SI, BasicBlock::iterator &BBI) {
 
   // There are two cases that are interesting for this code to handle: memcpy
   // and memset.  Right now we only handle memset.
 
   // Ensure that the value being stored is something that can be memset'able a
   // byte at a time like "0" or "-1" or any width, as well as things like
   // 0xA0A0A0A0 and 0.0.
   auto *V = SI->getOperand(0);
-  if (Value *ByteVal = isBytewiseValue(V)) {
+  if (Value *ByteVal = isBytewiseValue(V, DL)) {
     if (Instruction *I = tryMergingIntoMemset(SI, SI->getPointerOperand(),
                                               ByteVal)) {
       BBI = I->getIterator(); // Don't invalidate iterator.
       return true;
     }
 
     // If we have an aggregate, we try to promote it to memset regardless
     // of opportunity for merging as it can expose optimization opportunities
bool MemCpyOptPass::processMemCpy(MemCpyInst *M) {
 
   // If the source and destination of the memcpy are the same, then zap it.
   if (M->getSource() == M->getDest()) {
     MD->removeInstruction(M);
     M->eraseFromParent();
     return false;
   }
 
+  const DataLayout &DL = M->getModule()->getDataLayout();
+
   // If copying from a constant, try to turn the memcpy into a memset.
   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(M->getSource()))
     if (GV->isConstant() && GV->hasDefinitiveInitializer())
-      if (Value *ByteVal = isBytewiseValue(GV->getInitializer())) {
+      if (Value *ByteVal = isBytewiseValue(GV->getInitializer(), DL)) {
         IRBuilder<> Builder(M);
         Builder.CreateMemSet(M->getRawDest(), ByteVal, M->getLength(),
                              M->getDestAlignment(), false);
         MD->removeInstruction(M);
         M->eraseFromParent();
         ++NumCpyToSet;
         return true;
       }

test/Transforms/MemCpyOpt/non-integral-ptr.ll

+; RUN: opt -memcpyopt -S < %s | FileCheck %s
+
+; Check that non-integral pointer writes are not optimized to memset.
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
+target triple = "x86_64-unknown-linux-gnu"
+
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture, i64, i1) nounwind
+
+@x = global i8 addrspace(1)* zeroinitializer
+@const0 = private constant i8 addrspace(1)* null
+
+define void @test_memcpy() {
+  ; CHECK-LABEL: test_memcpy
+  ; CHECK: @llvm.memcpy
+  ; CHECK-NOT: @llvm.memset
+  %1 = bitcast i8 addrspace(1)** @x to i8*
+  %2 = bitcast i8 addrspace(1)** @const0 to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 8 %1, i8* align 8 %2, i64 8, i1 false)
+  ret void
+}
+
+@y = global [3 x i8 addrspace(1)*] zeroinitializer
+
+define void @test_aggregate() {
+  ; CHECK-LABEL: test_aggregate
+  ; CHECK: store
+  ; CHECK-NOT: @llvm.memset
+  store [3 x i8 addrspace(1)*] zeroinitializer, [3 x i8 addrspace(1)*]* @y
+  ret void
+}

unittests/Analysis/ValueTrackingTest.cpp

parseAssembly(
       "  %aaa = or i16 %aa, 3840\n"
       "  %bbb = or i16 %bb, 3840\n"
       "  %A = call i16 @llvm.fshl.i16(i16 %aaa, i16 %bbb, i16 0)\n"
       "  ret i16 %A\n"
       "}\n"
       "declare i16 @llvm.fshl.i16(i16, i16, i16)\n");
   expectKnownBits(/*zero*/ 15u, /*one*/ 3840u);
 }
+
+TEST(ValueTracking, IsBytewiseValueNonIntegral) {
+  StringRef Assembly = "%t = type { i64, i64 addrspace(10)* }"
+                       "@x = private constant i64 addrspace(10)* null"
+                       "@y = private constant [3 x i64 addrspace(10)*] zeroinitializer"
+                       "@z = private constant %t zeroinitializer";
+
+  LLVMContext Context;
+  SMDiagnostic Error;
+  auto M = parseAssemblyString(Assembly, Error, Context);
+  assert(M && "Bad assembly?");
+
+  // Set address space 10 as non-integral.
+  std::string DLStr = M->getDataLayoutStr();
+  if (!DLStr.empty())
+    DLStr += "-";
+  DLStr += "ni:10";
+  DataLayout DL(DLStr);
+  M->setDataLayout(DL);
+
+  GlobalValue *X = M->getNamedValue("x");
+  assert(X && "Bad assembly?");
+  EXPECT_FALSE(isBytewiseValue(X, DL));
+
+  GlobalValue *Y = M->getNamedValue("y");
+  assert(Y && "Bad assembly?");
+  EXPECT_FALSE(isBytewiseValue(Y, DL));
+
+  GlobalValue *Z = M->getNamedValue("z");
+  assert(Z && "Bad assembly?");
+  EXPECT_FALSE(isBytewiseValue(Z, DL));
+}