Use getMostFrequentByte to decide if should used memset+stores

[vitalybuka]

Summary

Previous implementation handled only memsets to zero.
This patch keeps behavior as close as possible to the original.
In followup patches I'll resolve TODOs and update/add tests.

Significantly changed part of @pcc prototype for -ftrivial-auto-var-init=pattern optimizations

[vitalybuka]

Reverted debug logging

[jfb]

clang/lib/CodeGen/CGDecl.cpp

865

You should update the return value to Optional<Value*> where the non-None return is the bytewise value.

873

I'm not sure I understand what this bit does. If something isn't a bytewise value then we now automatically assume it can be stored to with a single store. That's not necessarily true. I think you need to drop BWInit || from here, and conditionalize this entire branch with if (BWInit) instead (so, an && on it all).

888

The recursion now allows different values for BWInit on each sub-element.

895

What does this new loop do? It'll only ever go around the loop once.

[vitalybuka]

undo some behavior change

[vitalybuka]

rebase

[vitalybuka]

clang/lib/CodeGen/CGDecl.cpp

865

Why?
We already know value which was used for memset, now we just counting additional store/memsets

873

If value is bytewise, we will emit BWInit

888

yes

895

it counts number of stores used by elements
similar look we had in canEmitInitWithFewStoresAfterBZero

[vitalybuka]

clang/lib/CodeGen/CGDecl.cpp

873

If value is bytewise, we will emit BWInit

If value is bytewise, we will emit memset, which we can count as one store.
It's not always true that memset costs as a single store. However this is a heuristic, as the limit 6 itself.

Here I try to keep behavior close to original for zeroes.
In future patches I'd like to try to remove this function and use just "density" ((count memset bytes that match initializer)/(full size of initializer)). This will be simpler, should work good enough for exiting cases, and cover new cases with large initializers where 6 is not enough,

clang/lib/CodeGen/CGDecl.cpp

if (accessedByInit && lifetime == Qualifiers::OCL_Strong) {
     EmitStoreOfScalar(value, lvalue, /* isInitialization */ true);
     EmitARCRelease(oldValue, ARCImpreciseLifetime);
     return;
   }
 
   EmitStoreOfScalar(value, lvalue, /* isInitialization */ true);
 }
 
-/// Decide whether we can emit the non-zero parts of the specified initializer
-/// with equal or fewer than NumStores scalar stores.
-static bool canEmitInitWithFewStoresAfterBZero(llvm::Constant *Init,
-                                               unsigned &NumStores) {
-  // Zero and Undef never requires any extra stores.
-  if (isa<llvm::ConstantAggregateZero>(Init) ||
-      isa<llvm::ConstantPointerNull>(Init) ||
-      isa<llvm::UndefValue>(Init))
+/// Decide whether we can emit the non-pattern parts of the specified
+/// initializer with equal or fewer than NumStores scalar stores.
+static bool canEmitStoresForInitAfterMemset(CodeGenModule &CGM,
+                                            llvm::Constant *Init,
+                                            llvm::Value *Pattern,
+  assert(Pattern);
+  llvm::Value *BWInit = isBytewiseValue(Init, CGM.getDataLayout());
+  if (BWInit && (BWInit == Pattern || isa<llvm::UndefValue>(BWInit)))
     return true;
-  if (isa<llvm::ConstantInt>(Init) || isa<llvm::ConstantFP>(Init) ||
+  if (BWInit || isa<llvm::ConstantInt>(Init) || isa<llvm::ConstantFP>(Init) ||
       isa<llvm::ConstantVector>(Init) || isa<llvm::BlockAddress>(Init) ||
-      isa<llvm::ConstantExpr>(Init))
-    return Init->isNullValue() || NumStores--;
-
-  // See if we can emit each element.
-  if (isa<llvm::ConstantArray>(Init) || isa<llvm::ConstantStruct>(Init)) {
-    for (unsigned i = 0, e = Init->getNumOperands(); i != e; ++i) {
-      llvm::Constant *Elt = cast<llvm::Constant>(Init->getOperand(i));
-      if (!canEmitInitWithFewStoresAfterBZero(Elt, NumStores))
-        return false;
-    }
-    return true;
+      isa<llvm::ConstantExpr>(Init) || isa<llvm::GlobalValue>(Init)) {
+    // Single store or memset.
+    return NumStores--;
   }
 
   if (llvm::ConstantDataSequential *CDS =
           dyn_cast<llvm::ConstantDataSequential>(Init)) {
     for (unsigned i = 0, e = CDS->getNumElements(); i != e; ++i) {
       llvm::Constant *Elt = CDS->getElementAsConstant(i);
-      if (!canEmitInitWithFewStoresAfterBZero(Elt, NumStores))
+      if (!canEmitStoresForInitAfterMemset(CGM, Elt, Pattern, NumStores))
         return false;
     }
     return true;
   }
 
+  for (unsigned i = 0, e = Init->getNumOperands(); i != e; ++i) {
+    llvm::Constant *Elt = cast<llvm::Constant>(Init->getOperand(i));
+    if (!canEmitStoresForInitAfterMemset(CGM, Elt, Pattern, NumStores))
+      return false;
+    return true;
+  }
+
   // Anything else is hard and scary.
   return false;
 }
 
-/// For inits that canEmitInitWithFewStoresAfterBZero returned true for, emit
+/// For inits that canEmitStoresForInitAfterMemset returned true for, emit
 /// the scalar stores that would be required.
-static void emitStoresForInitAfterBZero(CodeGenModule &CGM,
-                                        llvm::Constant *Init, Address Loc,
-                                        bool isVolatile, CGBuilderTy &Builder) {
-  assert(!Init->isNullValue() && !isa<llvm::UndefValue>(Init) &&
-         "called emitStoresForInitAfterBZero for zero or undef value.");
-
+static void emitStoresForInitAfterMemset(CodeGenModule &CGM,
+                                         llvm::Constant *Init,
+                                         Address ParentLoc, int IdxInParent,
+                                         llvm::Value *Pattern, bool isVolatile,
+                                         CGBuilderTy &Builder) {
+  assert(Pattern);
+  llvm::Value *BWInit = isBytewiseValue(Init, CGM.getDataLayout());
+  if (BWInit && (BWInit == Pattern || isa<llvm::UndefValue>(BWInit)))
+    return;
+  Address Loc =
+      IdxInParent < 0
+          ? Builder.CreateElementBitCast(ParentLoc, Init->getType())
+          : Builder.CreateConstInBoundsGEP2_32(ParentLoc, 0, IdxInParent);
   if (isa<llvm::ConstantInt>(Init) || isa<llvm::ConstantFP>(Init) ||
       isa<llvm::ConstantVector>(Init) || isa<llvm::BlockAddress>(Init) ||
-      isa<llvm::ConstantExpr>(Init)) {
+      isa<llvm::ConstantExpr>(Init) || isa<llvm::GlobalValue>(Init)) {
     Builder.CreateStore(Init, Loc, isVolatile);
     return;
   }
 
+  if (BWInit) {
+    auto *SizeVal = llvm::ConstantInt::get(
+        CGM.IntPtrTy, CGM.getDataLayout().getTypeStoreSize(Init->getType()));
+    Builder.CreateMemSet(Loc, BWInit, SizeVal, isVolatile);
+    return;
+  }
+
   if (llvm::ConstantDataSequential *CDS =
           dyn_cast<llvm::ConstantDataSequential>(Init)) {
     for (unsigned i = 0, e = CDS->getNumElements(); i != e; ++i) {
       llvm::Constant *Elt = CDS->getElementAsConstant(i);
-
-      // If necessary, get a pointer to the element and emit it.
-      if (!Elt->isNullValue() && !isa<llvm::UndefValue>(Elt))
-        emitStoresForInitAfterBZero(
-            CGM, Elt, Builder.CreateConstInBoundsGEP2_32(Loc, 0, i), isVolatile,
+      emitStoresForInitAfterMemset(CGM, Elt, Loc, i, Pattern, isVolatile,
                                    Builder);
     }
     return;
   }
-
   assert((isa<llvm::ConstantStruct>(Init) || isa<llvm::ConstantArray>(Init)) &&
          "Unknown value type!");
 
   for (unsigned i = 0, e = Init->getNumOperands(); i != e; ++i) {
     llvm::Constant *Elt = cast<llvm::Constant>(Init->getOperand(i));
-
-    // If necessary, get a pointer to the element and emit it.
-    if (!Elt->isNullValue() && !isa<llvm::UndefValue>(Elt))
-      emitStoresForInitAfterBZero(CGM, Elt,
-                                  Builder.CreateConstInBoundsGEP2_32(Loc, 0, i),
-                                  isVolatile, Builder);
+    emitStoresForInitAfterMemset(CGM, Elt, Loc, i, Pattern, isVolatile,
+                                 Builder);
   }
 }
 
-/// Decide whether we should use bzero plus some stores to initialize a local
-/// variable instead of using a memcpy from a constant global.  It is beneficial
-/// to use bzero if the global is all zeros, or mostly zeros and large.
-static bool shouldUseBZeroPlusStoresToInitialize(llvm::Constant *Init,
-                                                 uint64_t GlobalSize) {
-  // If a global is all zeros, always use a bzero.
-  if (isa<llvm::ConstantAggregateZero>(Init)) return true;
-
-  // If a non-zero global is <= 32 bytes, always use a memcpy.  If it is large,
-  // do it if it will require 6 or fewer scalar stores.
-  // TODO: Should budget depends on the size?  Avoiding a large global warrants
-  // plopping in more stores.
-  unsigned StoreBudget = 6;
-  uint64_t SizeLimit = 32;
+/// Decide whether we should use memset to initialize a local variable instead
+/// of using a memcpy from a constant global.
+static llvm::Value *shouldUseMemSetToInitialize(CodeGenModule &CGM,
+                                                llvm::Constant *Init,
+  llvm::MostFrequentByte MFB =
+      llvm::getMostFrequentByte(Init, CGM.getDataLayout());
 
-  return GlobalSize > SizeLimit &&
-         canEmitInitWithFewStoresAfterBZero(Init, StoreBudget);
+  if (0) {
+    // TODO: Use this branch and remove 'else'. Now we can do that for any
+    // value, but it requires tests updates, so I'll enable it in a separate
+    // patch.
+    if (MFB.Value && !MFB.Other)
+      return MFB.Value;
+  } else {
+    if (isa<llvm::ConstantAggregateZero>(Init)) {
+      assert(MFB.Value);
+      assert(!MFB.Other);
+      return MFB.Value;
+    }
   }
 
-/// Decide whether we should use memset to initialize a local variable instead
-/// of using a memcpy from a constant global. Assumes we've already decided to
-/// not user bzero.
-/// FIXME We could be more clever, as we are for bzero above, and generate
-///       memset followed by stores. It's unclear that's worth the effort.
-static llvm::Value *shouldUseMemSetToInitialize(llvm::Constant *Init,
-                                                uint64_t GlobalSize,
-                                                const llvm::DataLayout &DL) {
+  // TODO: Tweak these constants or use "density".
   uint64_t SizeLimit = 32;
   if (GlobalSize <= SizeLimit)
     return nullptr;
-  return llvm::isBytewiseValue(Init, DL);
+
+  // TODO: Remove. It's here just to keep behavior.
+  if (MFB.Other && MFB.Value &&
+      MFB.Value != llvm::ConstantInt::get(CGM.Int8Ty, 0))
+    return nullptr;
+
+  if (!MFB.Value) {
+    // We don't know most frequent byte, we may still completely initialize it
+    // with small number of stores.
+    // TODO: Use llvm::UndefValue::get. If we get here and later we decide
+    // that number of stores is small enough to use memset+store then store are
+    // going to replace entire bzeroed range. With UndefValue we can skip that
+    // bogus memset. I will do that as a separate patch.
+    MFB.Value = llvm::ConstantInt::get(CGM.Int8Ty, 0);
+  }
+
+  unsigned StoreBudget = 6;
+  return canEmitStoresForInitAfterMemset(CGM, Init, MFB.Value, StoreBudget)
+             ? MFB.Value
+             : nullptr;
 }
 
 /// Decide whether we want to split a constant structure or array store into a
 /// sequence of its fields' stores. This may cost us code size and compilation
 /// speed, but plays better with store optimizations.
 static bool shouldSplitConstantStore(CodeGenModule &CGM,
                                      uint64_t GlobalByteSize) {
   // Don't break things that occupy more than one cacheline.
if (canDoSingleStore) {
     Builder.CreateStore(constant, Loc, isVolatile);
     return;
   }
 
   auto *SizeVal = llvm::ConstantInt::get(CGM.IntPtrTy, ConstantSize);
 
   // If the initializer is all or mostly the same, codegen with bzero / memset
   // then do a few stores afterward.
-  if (shouldUseBZeroPlusStoresToInitialize(constant, ConstantSize)) {
-    Builder.CreateMemSet(Loc, llvm::ConstantInt::get(CGM.Int8Ty, 0), SizeVal,
-                         isVolatile);
-
-    bool valueAlreadyCorrect =
-        constant->isNullValue() || isa<llvm::UndefValue>(constant);
-    if (!valueAlreadyCorrect) {
-      Loc = Builder.CreateBitCast(Loc, Ty->getPointerTo(Loc.getAddressSpace()));
-      emitStoresForInitAfterBZero(CGM, constant, Loc, isVolatile, Builder);
-    }
-    return;
-  }
-
-  // If the initializer is a repeated byte pattern, use memset.
-  llvm::Value *Pattern =
-      shouldUseMemSetToInitialize(constant, ConstantSize, CGM.getDataLayout());
-  if (Pattern) {
-    uint64_t Value = 0x00;
-    if (!isa<llvm::UndefValue>(Pattern)) {
-      const llvm::APInt &AP = cast<llvm::ConstantInt>(Pattern)->getValue();
-      assert(AP.getBitWidth() <= 8);
-      Value = AP.getLimitedValue();
-    }
-    Builder.CreateMemSet(Loc, llvm::ConstantInt::get(CGM.Int8Ty, Value), SizeVal,
-                         isVolatile);
+  if (llvm::Value *Pattern =
+          shouldUseMemSetToInitialize(CGM, constant, ConstantSize)) {
+    if (!isa<llvm::UndefValue>(Pattern))
+      Builder.CreateMemSet(Loc, Pattern, SizeVal, isVolatile);
+    emitStoresForInitAfterMemset(CGM, constant, Loc, -1, Pattern, isVolatile,
+                                 Builder);
     return;
   }
 
   // If the initializer is small, use a handful of stores.
   if (shouldSplitConstantStore(CGM, ConstantSize)) {
     if (auto *STy = dyn_cast<llvm::StructType>(Ty)) {
       // FIXME: handle the case when STy != Loc.getElementType().
       if (STy == Loc.getElementType()) {