Merge clang's isRepeatedBytePattern with LLVM's isBytewiseValue

[jfb]

Summary

This code was in CGDecl.cpp and really belongs in LLVM's isBytewiseValue. Teach isBytewiseValue the tricks clang's isRepeatedBytePattern had, including merging undef properly, and recursing on more types.

clang part of this patch: D51752

[jfb]

As noted in D51752 I'll instead improve isBytewiseValue to do this.

[jfb]

• Augment isBytewiseValue to be as powerful as clang's version. Update code that used it to handle undef merging. This captures more memcpy patterns and can generate memcpy of undef (which selection DAG later gets rid of).

[efriedma]

lib/Analysis/ValueTracking.cpp

3127

Do you really need separate loops for ConstantVector and ConstantArray?

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

657

No test coverage for this change?

lib/Transforms/Scalar/MemCpyOptimizer.cpp

391

What's the point of changing this signature? It doesn't seem to have any effect.

[MatzeB]

LGTM once Eli approves.

lib/Analysis/ValueTracking.cpp

3046

You could move this down, closer to its first user.

3058–3063

Indeed an interesting discussion whether we should call into something like InstructionSimplify here. I agree with you that we'd rather see this handled in a separate step by whoever calls isByteWiseValue(). That way we can keep this function simple and only handle the patterns that are already simplified.

3130

not sure how valuable this comment is :)

[jfb]

• Update comments and move Ctx down a bit.

lib/Analysis/ValueTracking.cpp

3058–3063

This comment was originally at the bottom of the function, I moved it to early-exit if it's not a constant because all the subsequent code is about constants (not values).

I can drop the comment if you want?

3127

I don't think ConstantArray has getSplatValue, which I use for ConstantVector. Or are you suggesting something else?

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

657

Indeed, right now getMemSetPatternValue doesn't check for UndefValue so there's no way to trigger this line. I'm adding it opportunistically because it's obviously correct, and I added a FIXME in getMemSetPatternValue to do this.

lib/Transforms/Scalar/MemCpyOptimizer.cpp

391

If ByteVal is UndefValue then it can be merged with any other valid pattern. The below change does this. The signature change allows updating ByteVal. I could instead return a pair if you want.

[jfb]

@mehdi_amini from our discussion in D49771 I think this patch takes us partway to what you wanted (having LLVM do at least as much work as clang when it comes to generating memset). After this commits I'll look at making clang less smart, and relying on LLVM being smart instead. I want to balance compile-time versus early code quality.

[efriedma]

lib/Analysis/ValueTracking.cpp

3127

I meant you could just use the for loop for ConstantVector. Maybe a bit less efficient, but the difference is unlikely to matter.

lib/Transforms/Scalar/MemCpyOptimizer.cpp

391

Whether you use an out parameter or a pair, the value still isn't actually used by either of the callers of tryMergingIntoMemset.

Looking again, I guess technically it's used in MemCpyOptPass::processStore, but only in the case where tryMergingIntoMemset fails, so I'm guessing that isn't intentional.

[jfb]

• Remove ref param

[jfb]

lib/Analysis/ValueTracking.cpp

3127

I'd rather not since getSplatValue does exactly what we want here.

lib/Transforms/Scalar/MemCpyOptimizer.cpp

391

You're right, changed back.

[efriedma]

Missing test coverage for half.

Missing test coverage here for ConstantStruct/ConstantArray/ConstantVector, although I guess the array/struct bits are covered by the clang patch. I'd like to see some coverage for vectors with unusual element sizes, though, like <i1 x 16>.

lib/Transforms/Scalar/MemCpyOptimizer.cpp

758–759

Unnecessary change.

798

Unnecessary change.

[bjope]

This patch will conflict with my patch here: https://reviews.llvm.org/D52092

Background: In our out-of-tree target we have 16-bit-bytes (so memset/memcpy etc operate on 16-bit units). We need to patch isBytewiseValue to handle both 8-bit and 16-bit bytes (we store BitsPerByte in various places such as DataLayout, so it could be 8 or 16 depending on target). The idea with D52092 was to make it possible to check BitsPerByte in isBytewiseValue, and then convert the existing isBytewiseValue into a more general isSplatValue that should work for any given bit length (similar to isSplat in APInt.h).

Do you think it is possible to use such a design here? (I doubt that it costs too much to have a more general isSplatValue in LLVM trunk)

[jfb]

• Augment isBytewiseValue to be as powerful as clang's version. Update code that used it to handle undef merging. This captures more memcpy patterns and can generate memcpy of undef (which selection DAG later gets rid of).
• Update comments and move Ctx down a bit.
• Remove ref param
• Remove extra changes, left over from clang-format

[jfb]

I'll add more tests soon.

[jfb]

• Add a bit more testing

[jfb]

In D51751#1237272, @efriedma wrote:

Missing test coverage for half.

Missing test coverage here for ConstantStruct/ConstantArray/ConstantVector, although I guess the array/struct bits are covered by the clang patch. I'd like to see some coverage for vectors with unusual element sizes, though, like <i1 x 16>.

I added some tests. Indeed the clang-side test/CodeGenCXX/auto-var-init.cpp already exercises a bunch of this.

[efriedma]

test/Transforms/MemCpyOpt/memcpy-to-memset.ll

54 ↗

(On Diff #166377)

You're not really testing any interesting codepaths with a constant zero? We just hit the "isNullValue()" early exit.

[jfb]

test/Transforms/MemCpyOpt/memcpy-to-memset.ll

54 ↗

(On Diff #166377)

It's the only interesting codepath for i1 though. Unless you're saying that we should add handling for i1 in isBytewiseValue?

[jfb]

test/Transforms/MemCpyOpt/memcpy-to-memset.ll

54 ↗

(On Diff #166377)

To be clear, this is where we return nullptr for all other i1:

// 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;
    return ConstantInt::get(Ctx, CI->getValue().trunc(8));
  }
}

[efriedma]

test/Transforms/MemCpyOpt/memcpy-to-memset.ll

54 ↗

(On Diff #166377)

Well, an improved isBytewiseValue could theoretically handle it... but I guess it's probably not worth bothering, at least for now. But better to have some test coverage so we it's clear what isn't handled.

[jfb]

• Test i1, show it isn't handled.

[jfb]

Added the negative test.

[efriedma]

LGTM

[vitalybuka]

lib/Analysis/ValueTracking.cpp

3127

@jfb This vector processing does not handle undefs correctly. I'd like to fix that with D64031

include/llvm/Analysis/ValueTracking.h

class Value;
   ///   x > +0 --> true
   ///   x < -0 --> false
   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.
+  /// i16 0x1234), return null. If the value is entirely undef and padding,
+  /// return undef.
   Value *isBytewiseValue(Value *V);
 
   /// 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.

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;
 }
 
-/// 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.
 Value *llvm::isBytewiseValue(Value *V) {
+
   // All byte-wide stores are splatable, even of arbitrary variables.
-  if (V->getType()->isIntegerTy(8)) return V;
+  if (V->getType()->isIntegerTy(8))
+    return V;
+
+  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 (!C) {
+    // Conceptually, we could handle things like:
+    //   %a = zext i8 %X to i16
+    //   %b = shl i16 %a, 8
+    //   %c = or i16 %a, %b
+    // but until there is an example that actually needs this, it doesn't seem
+    // worth worrying about.
+    return nullptr;
+  }
 
   // Handle 'null' ConstantArrayZero etc.
-  if (Constant *C = dyn_cast<Constant>(V))
-    if (C->isNullValue())
-      return Constant::getNullValue(Type::getInt8Ty(V->getContext()));
+    return Constant::getNullValue(Type::getInt8Ty(Ctx));
 
-  // Constant float and double values can be handled as integer values if the
+  // Constant floating-point values can be handled as integer values if the
   // corresponding integer value is "byteable".  An important case is 0.0.
-  if (ConstantFP *CFP = dyn_cast<ConstantFP>(V)) {
-    if (CFP->getType()->isFloatTy())
-      V = ConstantExpr::getBitCast(CFP, Type::getInt32Ty(V->getContext()));
-    if (CFP->getType()->isDoubleTy())
-      V = ConstantExpr::getBitCast(CFP, Type::getInt64Ty(V->getContext()));
+  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;
   }
 
   // We can handle constant integers that are multiple of 8 bits.
-  if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
+  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;
-      return ConstantInt::get(V->getContext(), CI->getValue().trunc(8));
+      return ConstantInt::get(Ctx, CI->getValue().trunc(8));
     }
   }
 
-  // A ConstantDataArray/Vector is splatable if all its members are equal and
-  // also splatable.
-  if (ConstantDataSequential *CA = dyn_cast<ConstantDataSequential>(V)) {
-    Value *Elt = CA->getElementAsConstant(0);
-    Value *Val = isBytewiseValue(Elt);
-    if (!Val)
-      return nullptr;
+  auto Merge = [&](Value *LHS, Value *RHS) -> Value * {
+    if (LHS == RHS)
+      return LHS;
+    if (!LHS || !RHS)
+      return nullptr;
+    if (LHS == UndefInt8)
+      return RHS;
+    if (RHS == UndefInt8)
+      return LHS;
+  };
 
-    for (unsigned I = 1, E = CA->getNumElements(); I != E; ++I)
-      if (CA->getElementAsConstant(I) != Elt)
+  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)))))
         return nullptr;
+    return Val;
+  }
+
+  if (isa<ConstantVector>(C)) {
+    Constant *Splat = cast<ConstantVector>(C)->getSplatValue();
+    return Splat ? isBytewiseValue(Splat) : 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)))))
+        return nullptr;
     return Val;
   }
 
-  // Conceptually, we could handle things like:
-  //   %a = zext i8 %X to i16
-  //   %b = shl i16 %a, 8
-  //   %c = or i16 %a, %b
-  // but until there is an example that actually needs this, it doesn't seem
-  // worth worrying about.
+  // Don't try to handle the handful of other constants.
   return nullptr;
 }
 
 // This is the recursive version of BuildSubAggregate. It takes a few different
 // arguments. Idxs is the index within the nested struct From that we are
 // looking at now (which is of type IndexedType). IdxSkip is the number of
 // indices from Idxs that should be left out when inserting into the resulting
 // struct. To is the result struct built so far, new insertvalue instructions

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

 
 /// getMemSetPatternValue - If a strided store of the specified value is safe to
 /// turn into a memset_pattern16, return a ConstantArray of 16 bytes that should
 /// be passed in.  Otherwise, return null.
 ///
 /// Note that we don't ever attempt to use memset_pattern8 or 4, because these
 /// just replicate their input array and then pass on to memset_pattern16.
 static Constant *getMemSetPatternValue(Value *V, const DataLayout *DL) {
+  // FIXME: This could check for UndefValue because it can be merged into any
+  // other valid pattern.
+
   // If the value isn't a constant, we can't promote it to being in a constant
   // array.  We could theoretically do a store to an alloca or something, but
   // that doesn't seem worthwhile.
   Constant *C = dyn_cast<Constant>(V);
   if (!C)
     return nullptr;
 
   // Only handle simple values that are a power of two bytes in size.
for (auto &k : IndexQueue) {
       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) {
+          if (isa<UndefValue>(FirstSplatValue))
+            FirstSplatValue = SecondSplatValue;
           if (FirstSplatValue != SecondSplatValue)
             continue;
         } else {
+          if (isa<UndefValue>(FirstPatternValue))
+            FirstPatternValue = SecondPatternValue;
           if (FirstPatternValue != SecondPatternValue)
             continue;
         }
         Tails.insert(SL[k]);
         Heads.insert(SL[i]);
         ConsecutiveChain[SL[i]] = SL[k];
         break;
       }

lib/Transforms/Scalar/MemCpyOptimizer.cpp

INITIALIZE_PASS_END(MemCpyOptLegacyPass, "memcpyopt", "MemCpy Optimization",
                     false, false)
 
 /// When scanning forward over instructions, we look for some other patterns to
 /// fold away. In particular, this looks for stores to neighboring locations of
 /// memory. If it sees enough consecutive ones, it attempts to merge them
 /// together into a memcpy/memset.
 Instruction *MemCpyOptPass::tryMergingIntoMemset(Instruction *StartInst,
                                                  Value *StartPtr,
                                                  Value *ByteVal) {
   const DataLayout &DL = StartInst->getModule()->getDataLayout();
 
   // Okay, so we now have a single store that can be splatable.  Scan to find
   // all subsequent stores of the same value to offset from the same pointer.
   // Join these together into ranges, so we can decide whether contiguous blocks
   // are stored.
   MemsetRanges Ranges(DL);
 
   BasicBlock::iterator BI(StartInst);
   for (++BI; !BI->isTerminator(); ++BI) {
     if (!isa<StoreInst>(BI) && !isa<MemSetInst>(BI)) {
       // If the instruction is readnone, ignore it, otherwise bail out.  We
       // don't even allow readonly here because we don't want something like:
       // A[1] = 2; strlen(A); A[2] = 2; -> memcpy(A, ...); strlen(A).
       if (BI->mayWriteToMemory() || BI->mayReadFromMemory())
         break;
       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.
-      if (ByteVal != isBytewiseValue(NextStore->getOperand(0)))
+      Value *StoredByte = isBytewiseValue(NextStore->getOperand(0));
+      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,
                            DL))
         break;
 
bool MemCpyOptPass::processStore(StoreInst *SI, BasicBlock::iterator &BBI) {
   // 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 (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
     // in subsequent passes.
     auto *T = V->getType();
     if (T->isAggregateType()) {

 
 bool MemCpyOptPass::processMemSet(MemSetInst *MSI, BasicBlock::iterator &BBI) {
   // See if there is another memset or store neighboring this memset which
   // allows us to widen out the memset to do a single larger store.
   if (isa<ConstantInt>(MSI->getLength()) && !MSI->isVolatile())
     if (Instruction *I = tryMergingIntoMemset(MSI, MSI->getDest(),
                                               MSI->getValue())) {
       BBI = I->getIterator(); // Don't invalidate iterator.
       return true;
     }
   return false;
 }
 
 /// Takes a memcpy and a call that it depends on,
 /// and checks for the possibility of a call slot optimization by having
 /// the call write its result directly into the destination of the memcpy.
 bool MemCpyOptPass::performCallSlotOptzn(Instruction *cpy, Value *cpyDest,

test/Transforms/MemCpyOpt/fca2memcpy.ll

 ; CHECK-NEXT: ret void
   %1 = load %S, %S* %src
   %2 = load %S, %S* %src
   store %S %1, %S* %dst
   store %S %2, %S* %dst
   ret void
 }
 
-; If the store address is computed ina complex manner, make
+; If the store address is computed in a complex manner, make
 ; sure we lift the computation as well if needed and possible.
 define void @addrproducer(%S* %src, %S* %dst) {
-; CHECK-LABEL: addrproducer
-; CHECK: %dst2 = getelementptr %S, %S* %dst, i64 1
-; CHECK: call void @llvm.memmove.p0i8.p0i8.i64
-; CHECK-NEXT: store %S undef, %S* %dst
+; CHECK-LABEL: addrproducer(
+; CHECK-NEXT: %[[DSTCAST:[0-9]+]] = bitcast %S* %dst to i8*
+; CHECK-NEXT: %dst2 = getelementptr %S, %S* %dst, i64 1
+; CHECK-NEXT: %[[DST2CAST:[0-9]+]] = bitcast %S* %dst2 to i8*
+; CHECK-NEXT: %[[SRCCAST:[0-9]+]] = bitcast %S* %src to i8*
+; CHECK-NEXT: call void @llvm.memmove.p0i8.p0i8.i64(i8* align 8 %[[DST2CAST]], i8* align 8 %[[SRCCAST]], i64 16, i1 false)
+; CHECK-NEXT: call void @llvm.memset.p0i8.i64(i8* align 8 %[[DSTCAST]], i8 undef, i64 16, i1 false)
 ; CHECK-NEXT: ret void
   %1 = load %S, %S* %src
   store %S undef, %S* %dst
   %dst2 = getelementptr %S , %S* %dst, i64 1
   store %S %1, %S* %dst2
   ret void
 }
 
 define void @aliasaddrproducer(%S* %src, %S* %dst, i32* %dstidptr) {
-; CHECK-LABEL: aliasaddrproducer
+; CHECK-LABEL: aliasaddrproducer(
+; CHECK-NEXT: %[[SRC:[0-9]+]] = load %S, %S* %src
+; CHECK-NEXT: %[[DSTCAST:[0-9]+]] = bitcast %S* %dst to i8*
+; CHECK-NEXT: call void @llvm.memset.p0i8.i64(i8* align 8 %[[DSTCAST]], i8 undef, i64 16, i1 false)
+; CHECK-NEXT: %dstindex = load i32, i32* %dstidptr
+; CHECK-NEXT: %dst2 = getelementptr %S, %S* %dst, i32 %dstindex
+; CHECK-NEXT: store %S %[[SRC]], %S* %dst2
+; CHECK-NEXT: ret void
   %1 = load %S, %S* %src
   store %S undef, %S* %dst
   %dstindex = load i32, i32* %dstidptr
   %dst2 = getelementptr %S , %S* %dst, i32 %dstindex
   store %S %1, %S* %dst2
   ret void
 }
 
 define void @noaliasaddrproducer(%S* %src, %S* noalias %dst, i32* noalias %dstidptr) {
-; CHECK-LABEL: noaliasaddrproducer
+; CHECK-LABEL: noaliasaddrproducer(
+; CHECK-NEXT: %[[SRCCAST:[0-9]+]] = bitcast %S* %src to i8*
+; CHECK-NEXT: %[[LOADED:[0-9]+]] = load i32, i32* %dstidptr
+; CHECK-NEXT: %dstindex = or i32 %[[LOADED]], 1
+; CHECK-NEXT: %dst2 = getelementptr %S, %S* %dst, i32 %dstindex
+; CHECK-NEXT: %[[DST2CAST:[0-9]+]] = bitcast %S* %dst2 to i8*
+; CHECK-NEXT: %[[SRCCAST2:[0-9]+]] = bitcast %S* %src to i8*
+; CHECK-NEXT: call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 8 %[[DST2CAST]], i8* align 8 %[[SRCCAST2]], i64 16, i1 false)
+; CHECK-NEXT: call void @llvm.memset.p0i8.i64(i8* align 8 %[[SRCCAST]], i8 undef, i64 16, i1 false)
+; CHECK-NEXT: ret void
   %1 = load %S, %S* %src
   store %S undef, %S* %src
   %2 = load i32, i32* %dstidptr
   %dstindex = or i32 %2, 1
   %dst2 = getelementptr %S , %S* %dst, i32 %dstindex
   store %S %1, %S* %dst2
   ret void
 }