Add getMostFrequentByte and use for isBytewiseValue implementation

[vitalybuka]

Summary

getMostFrequentByte is needed to optimize emitStoresForConstant in CGDecl.cpp for pattern initialization.
It should not affect compiled code. Different algorithm but isBytewiseValue behavior should be unchanged.

From @pcc prototype for -ftrivial-auto-var-init=pattern optimizations

[vitalybuka]

Fix compilation warnings

[bjope]

What is the idea here? Just a refactoring to get rid of recursive calls? Or are you going to use the histogram for some other purposes?
(the patch is lacking description, but perhaps it's just a temporary hack an not something that is subject for submitting?)

FWIW, downstream we have 16-bit addressable units and we are tweaking isBytewiseValue to also support "16-bit bytes" in our fork. So far it has been quite simple to do such adjustments, and maybe it will be doable by using a 65536+1 entries large histogram as well.
I just got curious to what the plan is here (to understand if it is worth spending time on continuing to adapt to the upstream changes or if we simply should keep our current version that should be working for 16-bit splats).

[bjope]

llvm/lib/Analysis/ValueTracking.cpp

3204

Not sure that we are guaranteed to get Size number of zeroes here. Not unless we also add a check for DL.typeSizeEqualsStoreSize(V->getType). Consider if we for example have an i12, then only 12 bits out of 16 is known to be zero.

(this might be a bug on trunk as well, or maybe I've missed some condition somewhere regarding how this is used)

[vitalybuka]

In D64111#1568642, @bjope wrote:

What is the idea here? Just a refactoring to get rid of recursive calls? Or are you going to use the histogram for some other purposes?
(the patch is lacking description, but perhaps it's just a temporary hack an not something that is subject for submitting?)

Added comment into description, I hope to upload the patch which is going to use new function today.

FWIW, downstream we have 16-bit addressable units and we are tweaking isBytewiseValue to also support "16-bit bytes" in our fork. So far it has been quite simple to do such adjustments, and maybe it will be doable by using a 65536+1 entries large histogram as well.
I just got curious to what the plan is here (to understand if it is worth spending time on continuing to adapt to the upstream changes or if we simply should keep our current version that should be working for 16-bit splats).

I don't plan other changes in this code after this patch stack.

[bjope]

In D64111#1568670, @vitalybuka wrote:

In D64111#1568642, @bjope wrote:

What is the idea here? Just a refactoring to get rid of recursive calls? Or are you going to use the histogram for some other purposes?
(the patch is lacking description, but perhaps it's just a temporary hack an not something that is subject for submitting?)

Added comment into description, I hope to upload the patch which is going to use new function today.

FWIW, downstream we have 16-bit addressable units and we are tweaking isBytewiseValue to also support "16-bit bytes" in our fork. So far it has been quite simple to do such adjustments, and maybe it will be doable by using a 65536+1 entries large histogram as well.
I just got curious to what the plan is here (to understand if it is worth spending time on continuing to adapt to the upstream changes or if we simply should keep our current version that should be working for 16-bit splats).

I don't plan other changes in this code after this patch stack.

Ok. Thanks!

[vitalybuka]

llvm/lib/Analysis/ValueTracking.cpp

3204

yes, it's not precise, as not precise the ConstantFP handling below and isSplat(8) handling in ConstantInt
I guess it does not change behavior of IsBytewiseValueTest, and it's good enough for my future patch.

Also I think this is the best behavior for current users. If we memset zero there then we should be good. Same does not work below for (CI->getBitWidth() % 8) and for non zero initiazer, we had to give up and count it against Other.

If we count non aligned isNullValue against "Other", it will change behavior of IsBytewiseValueTest.

[eugenis]

I'm a bit worried about performance implications.
isBytewiseValue is now doing some clearly unnecessary work.
Could you sanity check that it does not affect compilation times?

llvm/lib/Analysis/ValueTracking.cpp

3170

use std::array

[jfb]

llvm/lib/Analysis/ValueTracking.cpp

3180

Should Undef count as Other? Or have its own count?

3204

I think it's worth a comment on over-estimate, but it seems fine as-is.

[vitalybuka]

llvm/lib/Analysis/ValueTracking.cpp

3180

Undef means we don't care what it's there, so we can fill we any pattern.
Other counts bytes which are different from most frequent value and will have to be fixed, e.g. after memset

[eugenis]

llvm/lib/Analysis/ValueTracking.cpp

3180

Should we count undefs separately in the histogram? It seems like it would not add any complexity or runtime cost, and the caller can just add the two number if that's what they need.

[jfb]

llvm/lib/Analysis/ValueTracking.cpp

3180

Right, it seems like we might want the following information:

• Value is one of 256 bytes were tracking.
• Value wasn't something we looked into, for X bytes.
• Value was undef.
• Value was padding (same as undef).

We can figure out some of this, but not all, from the current patch. Is it useful to know the rest? I'm not sure! I haven't inspected all uses to be able to convince myself.

[vitalybuka]

llvm/lib/Analysis/ValueTracking.cpp

3180

Right now I only use "count" and "other". Future users can easily count and return undefs and update interface if needed. But I would prefer to do so when needed. Also maybe at some point it would be useful to return entire histogram.

But I am OK to include undef if you believe it could be used soon.

llvm/include/llvm/Analysis/ValueTracking.h

class Value;
   /// 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, const DataLayout &DL);
 
+  // Result type for |getMostFrequestByte|.
+  struct MostFrequentByte {
+    MostFrequentByte(Value *Value, size_t Count, size_t Other)
+        : Value(Value), Count(Count), Other(Other) {}
+    Value *Value = nullptr;
+    size_t Count = 0;
+    size_t Other = 0;
+  };
+  /// Find most frequent byte in specified value, approximately. The current
+  /// version ignores some types and non-splat integers.
+  MostFrequentByte getMostFrequentByte(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,
                            ArrayRef<unsigned> idx_range,

llvm/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, const DataLayout &DL) {
-
-  // All byte-wide stores are splatable, even of arbitrary variables.
-  if (V->getType()->isIntegerTy(8))
-    return V;
+static struct ValueHistogram {
+  uint64_t Values[256] = {};
+  uint64_t Other = 0;
+};
 
+static void addToValueHistogram(ValueHistogram &H, Value *V,
+                                const DataLayout &DL) {
   LLVMContext &Ctx = V->getContext();
 
   // Undef don't care.
-  auto *UndefInt8 = UndefValue::get(Type::getInt8Ty(Ctx));
   if (isa<UndefValue>(V))
-    return UndefInt8;
+    return;
 
   if (auto *T = dyn_cast<SequentialType>(V->getType()))
     if (!T->getNumElements())
-      return UndefInt8;
+      return;
   if (auto *T = dyn_cast<StructType>(V->getType()))
     if (!T->getNumElements())
-      return UndefInt8;
+      return;
 
+  const uint64_t Size = DL.getTypeStoreSize(V->getType());
   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;
+    H.Other += Size;
+    return;
   }
 
   // Handle 'null' ConstantArrayZero etc.
-  if (C->isNullValue())
-    return Constant::getNullValue(Type::getInt8Ty(Ctx));
+  if (C->isNullValue()) {
+    H.Values[0] += Size;
+    return;
+  }
 
   // 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>(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), DL)
-              : nullptr;
+    if (Ty)
+      addToValueHistogram(H, ConstantExpr::getBitCast(CFP, Ty), DL);
+    else
+      H.Other += Size;
+    return;
   }
 
   // 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));
-    }
+    if (CI->getBitWidth() % 8 == 0 && CI->getValue().isSplat(8))
+      H.Values[CI->getValue().getRawData()[0] % 256] += Size;
+    else
+      H.Other += Size;
+    return;
   }
 
   if (auto *CE = dyn_cast<ConstantExpr>(C)) {
     if (CE->getOpcode() == Instruction::IntToPtr) {
       auto PS = DL.getPointerSizeInBits(
           cast<PointerType>(CE->getType())->getAddressSpace());
-      return isBytewiseValue(
+      addToValueHistogram(H,
                           ConstantExpr::getIntegerCast(CE->getOperand(0),
-                                       Type::getIntNTy(Ctx, PS), false),
+                                                       Type::getIntNTy(Ctx, PS),
+                                                       false),
                           DL);
+    } else {
+      H.Other += Size;
     }
+    return;
   }
 
-  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;
-    return nullptr;
-  };
-
   if (ConstantDataSequential *CA = dyn_cast<ConstantDataSequential>(C)) {
-    Value *Val = UndefInt8;
+    assert(CA->getNumElements());
     for (unsigned I = 0, E = CA->getNumElements(); I != E; ++I)
-      if (!(Val = Merge(Val, isBytewiseValue(CA->getElementAsConstant(I), DL))))
-        return nullptr;
-    return Val;
+      addToValueHistogram(H, CA->getElementAsConstant(I), DL);
+    return;
   }
 
   if (isa<ConstantAggregate>(C)) {
-    Value *Val = UndefInt8;
+    assert(C->getNumOperands());
     for (unsigned I = 0, E = C->getNumOperands(); I != E; ++I)
-      if (!(Val = Merge(Val, isBytewiseValue(C->getOperand(I), DL))))
-        return nullptr;
-    return Val;
+      addToValueHistogram(H, C->getOperand(I), DL);
+    return;
   }
 
   // Don't try to handle the handful of other constants.
-  return nullptr;
+  H.Other += Size;
+}
+
+Value *llvm::isBytewiseValue(Value *V, const DataLayout &DL) {
+  MostFrequentByte MFB = getMostFrequentByte(V, DL);
+  return MFB.Other ? nullptr : MFB.Value;
+}
+
+MostFrequentByte llvm::getMostFrequentByte(Value *V, const DataLayout &DL) {
+  if (V->getType()->isIntegerTy(8))
+    return {V, 1, 0};
+
+  ValueHistogram H;
+  addToValueHistogram(H, V, DL);
+
+  size_t Total =
+      std::accumulate(std::begin(H.Values), std::end(H.Values), H.Other);
+  auto I = std::max_element(std::begin(H.Values), std::end(H.Values));
+  auto Ty = Type::getInt8Ty(V->getContext());
+  if (*I) {
+    return {
+        ConstantInt::get(Ty, std::distance(std::begin(H.Values), I)),
+        *I,
+        Total - *I,
+    };
+  }
+  if (!Total)
+    return {UndefValue::get(Ty), 0, 0};
+  return {nullptr, 0, Total};
 }
 
 // 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
 // build on that.

llvm/unittests/Analysis/ValueTrackingTest.cpp

parseAssembly(
       "  %bbb = and i8 %bb, 254\n"
       "  %A = call i8 @llvm.usub.sat.i8(i8 %aaa, i8 %bbb)\n"
       "  ret i8 %A\n"
       "}\n"
       "declare i8 @llvm.usub.sat.i8(i8, i8)\n");
   expectKnownBits(/*zero*/ 2u, /*one*/ 0u);
 }
 
-class IsBytewiseValueTest : public ValueTrackingTest,
-                            public ::testing::WithParamInterface<
-                                std::pair<const char *, const char *>> {
+struct BytewiseValueTestInput {
+  const char *Result;
+  struct {
+    uint64_t Count;
+    uint64_t Other;
+    const char *AltResult; // use |Result| if nullptr.
+  } MFBResult;
+  const char *Input;
+};
+
+std::ostream &operator<<(std::ostream &os,
+                         const BytewiseValueTestInput &Input) {
+  return os << '"' << Input.Input << '"';
+}
+
+class BytewiseValueTest
+    : public ValueTrackingTest,
+      public ::testing::WithParamInterface<BytewiseValueTestInput> {
 protected:
+  void SetUp() override {
+    M = parseModule(std::string("@test = global ") + GetParam().Input);
+    GV = dyn_cast<GlobalVariable>(M->getNamedValue("test"));
+  }
+
+  static std::string toString(Value *V) {
+    if (!V)
+      return "";
+    std::string Buff;
+    raw_string_ostream S(Buff);
+    S << *V;
+    return S.str();
+  }
+
+  std::unique_ptr<Module> M;
+  GlobalVariable *GV = nullptr;
 };
 
-const std::pair<const char *, const char *> IsBytewiseValueTests[] = {
+const BytewiseValueTestInput BytewiseValueTests[] = {
     {
         "i8 0",
+        {8},
         "i48* null",
     },
     {
         "i8 undef",
+        {0},
         "i48* undef",
     },
     {
         "i8 0",
+        {1},
         "i8 zeroinitializer",
     },
     {
         "i8 0",
+        {1},
         "i8 0",
     },
     {
         "i8 -86",
+        {1},
         "i8 -86",
     },
     {
         "i8 -1",
+        {1},
         "i8 -1",
     },
     {
         "i8 undef",
+        {0},
         "i16 undef",
     },
     {
         "i8 0",
+        {2},
         "i16 0",
     },
     {
         "",
+        {0, 2},
         "i16 7",
     },
     {
         "i8 -86",
+        {2},
         "i16 -21846",
     },
     {
         "i8 -1",
+        {2},
         "i16 -1",
     },
     {
         "i8 0",
+        {6},
         "i48 0",
     },
     {
         "i8 -1",
+        {6},
         "i48 -1",
     },
     {
         "i8 0",
+        {7},
         "i49 0",
     },
     {
         "",
+        {0, 7},
         "i49 -1",
     },
     {
         "i8 0",
+        {2},
         "half 0xH0000",
     },
     {
         "i8 -85",
+        {2},
         "half 0xHABAB",
     },
     {
         "i8 0",
+        {4},
         "float 0.0",
     },
     {
         "i8 -1",
+        {4},
         "float 0xFFFFFFFFE0000000",
     },
     {
         "i8 0",
+        {8},
         "double 0.0",
     },
     {
         "i8 -15",
+        {8},
         "double 0xF1F1F1F1F1F1F1F1",
     },
     {
         "i8 undef",
+        {},
         "i16* undef",
     },
     {
         "i8 0",
+        {8},
         "i16* inttoptr (i64 0 to i16*)",
     },
     {
         "i8 -1",
+        {8},
         "i16* inttoptr (i64 -1 to i16*)",
     },
     {
         "i8 -86",
+        {8},
         "i16* inttoptr (i64 -6148914691236517206 to i16*)",
     },
     {
         "",
+        {0, 8},
         "i16* inttoptr (i48 -1 to i16*)",
     },
     {
         "i8 -1",
+        {8},
         "i16* inttoptr (i96 -1 to i16*)",
     },
     {
         "i8 undef",
+        {},
         "[0 x i8] zeroinitializer",
     },
     {
         "i8 undef",
+        {},
         "[0 x i8] undef",
     },
     {
         "i8 0",
+        {6},
         "[6 x i8] zeroinitializer",
     },
     {
         "i8 undef",
+        {},
         "[6 x i8] undef",
     },
     {
         "i8 1",
+        {5},
         "[5 x i8] [i8 1, i8 1, i8 1, i8 1, i8 1]",
     },
     {
         "",
+        {0, 40},
         "[5 x i64] [i64 1, i64 1, i64 1, i64 1, i64 1]",
     },
     {
         "i8 -1",
+        {40},
         "[5 x i64] [i64 -1, i64 -1, i64 -1, i64 -1, i64 -1]",
     },
     {
         "",
+        {3, 1, "i8 1"},
         "[4 x i8] [i8 1, i8 2, i8 1, i8 1]",
     },
     {
         "i8 1",
+        {3},
         "[4 x i8] [i8 1, i8 undef, i8 1, i8 1]",
     },
     {
         "i8 0",
+        {6},
         "<6 x i8> zeroinitializer",
     },
     {
         "i8 undef",
+        {},
         "<6 x i8> undef",
     },
     {
         "i8 1",
+        {5},
         "<5 x i8> <i8 1, i8 1, i8 1, i8 1, i8 1>",
     },
     {
         "",
+        {0, 40},
         "<5 x i64> <i64 1, i64 1, i64 1, i64 1, i64 1>",
     },
     {
         "i8 -1",
+        {40},
         "<5 x i64> <i64 -1, i64 -1, i64 -1, i64 -1, i64 -1>",
     },
     {
         "",
+        {3, 1, "i8 1"},
         "<4 x i8> <i8 1, i8 1, i8 2, i8 1>",
     },
     {
         "i8 5",
+        {1},
         "<2 x i8> < i8 5, i8 undef >",
     },
     {
         "i8 0",
+        {8},
         "[2 x [2 x i16]] zeroinitializer",
     },
     {
         "i8 undef",
+        {},
         "[2 x [2 x i16]] undef",
     },
     {
         "i8 -86",
+        {8},
         "[2 x [2 x i16]] [[2 x i16] [i16 -21846, i16 -21846], "
         "[2 x i16] [i16 -21846, i16 -21846]]",
     },
     {
         "",
+        {6, 2, "i8 -86"},
         "[2 x [2 x i16]] [[2 x i16] [i16 -21846, i16 -21846], "
         "[2 x i16] [i16 -21836, i16 -21846]]",
     },
     {
         "i8 undef",
+        {},
         "{ } zeroinitializer",
     },
     {
         "i8 undef",
+        {},
         "{ } undef",
     },
     {
         "i8 0",
+        {24},
         "{i8, i64, i16*} zeroinitializer",
     },
     {
         "i8 undef",
+        {},
         "{i8, i64, i16*} undef",
     },
     {
         "i8 -86",
+        {9},
         "{i8, i64, i16*} {i8 -86, i64 -6148914691236517206, i16* undef}",
     },
     {
         "",
+        {8, 1, "i8 -86"},
         "{i8, i64, i16*} {i8 86, i64 -6148914691236517206, i16* undef}",
     },
 };
 
-INSTANTIATE_TEST_CASE_P(IsBytewiseValueParamTests, IsBytewiseValueTest,
-                        ::testing::ValuesIn(IsBytewiseValueTests));
+INSTANTIATE_TEST_CASE_P(BytewiseValueParamTests, BytewiseValueTest,
+                        ::testing::ValuesIn(BytewiseValueTests));
 
-TEST_P(IsBytewiseValueTest, IsBytewiseValue) {
-  auto M = parseModule(std::string("@test = global ") + GetParam().second);
-  GlobalVariable *GV = dyn_cast<GlobalVariable>(M->getNamedValue("test"));
-  Value *Actual = isBytewiseValue(GV->getInitializer(), M->getDataLayout());
-  std::string Buff;
-  raw_string_ostream S(Buff);
-  if (Actual)
-    S << *Actual;
-  EXPECT_EQ(GetParam().first, S.str());
+TEST_P(BytewiseValueTest, IsBytewiseValue) {
+  EXPECT_EQ(GetParam().Result, toString(isBytewiseValue(GV->getInitializer(),
+                                                        M->getDataLayout())));
+}
+
+TEST_P(BytewiseValueTest, GetMostFrequentByte) {
+  auto Actual = getMostFrequentByte(GV->getInitializer(), M->getDataLayout());
+  auto Expected = GetParam().MFBResult;
+  EXPECT_EQ(Expected.Count, Actual.Count);
+  EXPECT_EQ(Expected.Other, Actual.Other);
+  EXPECT_EQ(Expected.AltResult ? Expected.AltResult : GetParam().Result,
+            toString(Actual.Value));
 }