[InstCombine] Fold memchr of sequences of same characters

[msebor]

Summary

This change enhances the memchr library function handler to fold calls with one or two consecutive sequences of the same character, analogously to the corresponding feature recently added to the memrchr handler (D123631). Rather than just one sequence as for memrchr, this one handles also two sequences in order to also benefit strchr.

Tested on x86_64-linux by building Clang and running make check-all.

[nikic]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

307

Unrelated change (in strchr rather than memchr)?

1058

As far as I can tell EndOff doesn't actually get used later, it's only used for the substr(), so I'm not sure why this code is changing rather than only being moved.

I think in https://reviews.llvm.org/D123472 the wrong version of the patch ended up being committed, I remember there being a static substr() function for this purpose, but it doesn't seem to be present on main.

1069

I don't think this is correct for the case where N is variable. Let's say we have S = "12", C = 2 and N = 1 (known only at runtime). The correct result for this is null. I believe your code would return S + 1.

There doesn't seem to be test coverage for this case (variable N with two runs -- there's only one with three runs).

llvm/test/Transforms/InstCombine/memchr-6.ll

19 ↗

(On Diff #432440)

Why does this one not fold?

53 ↗

(On Diff #432440)

Unrelated: There's a canonicalization opportunity here to convert C1 ? X : (C2 ? X : Y) to (C1 ? true : C2) ? X : Y` (or vice versa, but I'd consider logical or more canonical here).

[msebor]

• Add a substr helper function and call it.
• Remove a spurious change to LibCallSimplifier::optimizeStrChr.
• Add a missing conditional and a test case for it.

[msebor]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

1058

Yes, I must have committed a prior version of the patch.

1069

Good catch! I've added the missing conditional and a test case for it.

(For what it's worth, plain C runtime tests would help spot these mistakes sooner.)

llvm/test/Transforms/InstCombine/memchr-6.ll

19 ↗

(On Diff #432440)

Because a00000 has no initializer getConstantDataArrayInfo returns a null Slice.Array that getConstantStringInfo then fails for. I've added a comment to the test.

I thought I'd handled it D125114 but apparently it needs another enhancement. I can take care of it in a followup.

53 ↗

(On Diff #432440)

I've reworked the conditional a bit and I'm not sure I see this opportunity there anymore but let me know if I missed it.

[nikic]

LGTM

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

1058

I'd suggest landing the substr() function as a separate NFC patch, as it's not directly related to this one (and we'd want to replace the other usages at the same time as well).

llvm/test/Transforms/InstCombine/memchr-6.ll

19 ↗

(On Diff #432440)

Hrm, that would probably also require an API change, because we don't have any already allocated string we could create a StringRef to.

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

 static Value *copyFlags(const CallInst &Old, Value *New) {
   assert(!Old.isMustTailCall() && "do not copy musttail call flags");
   assert(!Old.isNoTailCall() && "do not copy notail call flags");
   if (auto *NewCI = dyn_cast_or_null<CallInst>(New))
     NewCI->setTailCallKind(Old.getTailCallKind());
   return New;
 }
 
+// Helper to avoid truncating the length if size_t is 32-bits.
+static StringRef substr(StringRef Str, uint64_t Len) {
+  return Len >= Str.size() ? Str : Str.substr(0, Len);
+}
+
 //===----------------------------------------------------------------------===//
 // String and Memory Library Call Optimizations
 //===----------------------------------------------------------------------===//
 
 Value *LibCallSimplifier::optimizeStrCat(CallInst *CI, IRBuilderBase &B) {
   // Extract some information from the instruction
   Value *Dst = CI->getArgOperand(0);
   Value *Src = CI->getArgOperand(1);
Value *LibCallSimplifier::optimizeStrChr(CallInst *CI, IRBuilderBase &B) {
   Function *Callee = CI->getCalledFunction();
   FunctionType *FT = Callee->getFunctionType();
   Value *SrcStr = CI->getArgOperand(0);
   annotateNonNullNoUndefBasedOnAccess(CI, 0);
 
   // If the second operand is non-constant, see if we can compute the length
   // of the input string and turn this into memchr.
   ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
   if (!CharC) {
     uint64_t Len = GetStringLength(SrcStr);
     if (Len)
       annotateDereferenceableBytes(CI, 0, Len);
     else
       return nullptr;
     if (!FT->getParamType(1)->isIntegerTy(32)) // memchr needs i32.
       return nullptr;
 
Value *LibCallSimplifier::optimizeStrNCmp(CallInst *CI, IRBuilderBase &B) {
 
   StringRef Str1, Str2;
   bool HasStr1 = getConstantStringInfo(Str1P, Str1);
   bool HasStr2 = getConstantStringInfo(Str2P, Str2);
 
   // strncmp(x, y)  -> cnst  (if both x and y are constant strings)
   if (HasStr1 && HasStr2) {
     // Avoid truncating the 64-bit Length to 32 bits in ILP32.
-    StringRef::size_type MinLen1 = std::min((uint64_t)Str1.size(), Length);
-    StringRef::size_type MinLen2 = std::min((uint64_t)Str2.size(), Length);
-    StringRef SubStr1 = Str1.substr(0, MinLen1);
-    StringRef SubStr2 = Str2.substr(0, MinLen2);
+    StringRef SubStr1 = substr(Str1, Length);
+    StringRef SubStr2 = substr(Str2, Length);
     return ConstantInt::get(CI->getType(), SubStr1.compare(SubStr2));
   }
 
   if (HasStr1 && Str1.empty()) // strncmp("", x, n) -> -*x
     return B.CreateNeg(B.CreateZExt(
         B.CreateLoad(B.getInt8Ty(), Str2P, "strcmpload"), CI->getType()));
 
   if (HasStr2 && Str2.empty()) // strncmp(x, "", n) -> *x
Value *LibCallSimplifier::optimizeMemChr(CallInst *CI, IRBuilderBase &B) {
   }
 
   if (!LenC)
     // From now on we need a constant length and constant array.
     return nullptr;
 
   // Truncate the string to LenC without slicing when targeting LP64
   // on an ILP32 host.
-  uint64_t EndOff = std::min(LenC->getZExtValue(), (uint64_t)StringRef::npos);
-  Str = Str.substr(0, EndOff);
+  Str = substr(Str, LenC->getZExtValue());
 
   // If the char is variable but the input str and length are not we can turn
   // this memchr call into a simple bit field test. Of course this only works
   // when the return value is only checked against null.
   //
   // It would be really nice to reuse switch lowering here but we can't change
   // the CFG at this point.
   //
   // memchr("\r\n", C, 2) != nullptr -> (1 << C & ((1 << '\r') | (1 << '\n')))
   // != 0
   //   after bounds check.
   if (Str.empty() || !isOnlyUsedInZeroEqualityComparison(CI))
     return nullptr;
 
   unsigned char Max =
       *std::max_element(reinterpret_cast<const unsigned char *>(Str.begin()),
                         reinterpret_cast<const unsigned char *>(Str.end()));
 
   // Make sure the bit field we're about to create fits in a register on the
   // target.
   // FIXME: On a 64 bit architecture this prevents us from using the
   // interesting range of alpha ascii chars. We could do better by emitting