[InstCombine] Transform strrchr to memrchr for constant strings

[msebor]

Summary

This change adds a memrchr library function call emitter and simplifies the strrchr call handler to use it instead of duplicating a subset of the former function's transformations in the handler. This in turn enables transforming calls with the empty string S such as strrchr(S, C) to the test C ? S : 0. A call to memrchr when the length of the string is known is also likely to be faster than one to strrchr with the corresponding arguments.

[nikic]

llvm/lib/Transforms/Utils/BuildLibCalls.cpp

1543

This one probably needs an isLibFuncEmittable check, because memrchr is a GNU extension. It looks like PS targets do mark it as unavailable.

[msebor]

llvm/lib/Transforms/Utils/BuildLibCalls.cpp

1543

isLibFuncEmittable is called from emitLibCall so I think this parts should be fine. Or am I missing something here?

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

362

I did forget that memrchr isn't standard so this will fail on targets without it as you noted. Are we okay with losing that optimization on those targets or should I keep the existing optimization and use it when emitMemRChr fails?

[nikic]

LGTM

llvm/lib/Transforms/Utils/BuildLibCalls.cpp

1543

Nope, my bad. It also looks like copyFlags will already handle a null argument correctly, so your code is fine as-is.

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

362

As it's just the one target that disables it, I think it's fine to drop the optimization.

llvm/include/llvm/Transforms/Utils/BuildLibCalls.h

namespace llvm {
   Value *emitMemPCpy(Value *Dst, Value *Src, Value *Len, IRBuilderBase &B,
                      const DataLayout &DL, const TargetLibraryInfo *TLI);
 
   /// Emit a call to the memchr function. This assumes that Ptr is a pointer,
   /// Val is an i32 value, and Len is an 'intptr_t' value.
   Value *emitMemChr(Value *Ptr, Value *Val, Value *Len, IRBuilderBase &B,
                     const DataLayout &DL, const TargetLibraryInfo *TLI);
 
+  /// Emit a call to the memrchr function, analogously to emitMemChr.
+  Value *emitMemRChr(Value *Ptr, Value *Val, Value *Len, IRBuilderBase &B,
+                    const DataLayout &DL, const TargetLibraryInfo *TLI);
+
   /// Emit a call to the memcmp function.
   Value *emitMemCmp(Value *Ptr1, Value *Ptr2, Value *Len, IRBuilderBase &B,
                     const DataLayout &DL, const TargetLibraryInfo *TLI);
 
   /// Emit a call to the bcmp function.
   Value *emitBCmp(Value *Ptr1, Value *Ptr2, Value *Len, IRBuilderBase &B,
                   const DataLayout &DL, const TargetLibraryInfo *TLI);
 

llvm/lib/Transforms/Utils/BuildLibCalls.cpp

FunctionCallee llvm::getOrInsertLibFunc(Module *M, const TargetLibraryInfo &TLI,
   case LibFunc_fputc:
   case LibFunc_putchar:
     setArgExtAttr(*F, 0, TLI);
     break;
   case LibFunc_ldexp:
   case LibFunc_ldexpf:
   case LibFunc_ldexpl:
   case LibFunc_memchr:
+  case LibFunc_memrchr:
   case LibFunc_strchr:
     setArgExtAttr(*F, 1, TLI);
     break;
   case LibFunc_memccpy:
     setArgExtAttr(*F, 2, TLI);
     break;
 
     // These are functions that are known to not need any argument extension
Value *llvm::emitMemChr(Value *Ptr, Value *Val, Value *Len, IRBuilderBase &B,
                         const DataLayout &DL, const TargetLibraryInfo *TLI) {
   LLVMContext &Context = B.GetInsertBlock()->getContext();
   return emitLibCall(
       LibFunc_memchr, B.getInt8PtrTy(),
       {B.getInt8PtrTy(), B.getInt32Ty(), DL.getIntPtrType(Context)},
       {castToCStr(Ptr, B), Val, Len}, B, TLI);
 }
 
+Value *llvm::emitMemRChr(Value *Ptr, Value *Val, Value *Len, IRBuilderBase &B,
+                        const DataLayout &DL, const TargetLibraryInfo *TLI) {
+  LLVMContext &Context = B.GetInsertBlock()->getContext();
+  return emitLibCall(
+      LibFunc_memrchr, B.getInt8PtrTy(),
+      {B.getInt8PtrTy(), B.getInt32Ty(), DL.getIntPtrType(Context)},
+      {castToCStr(Ptr, B), Val, Len}, B, TLI);
+}
+
 Value *llvm::emitMemCmp(Value *Ptr1, Value *Ptr2, Value *Len, IRBuilderBase &B,
                         const DataLayout &DL, const TargetLibraryInfo *TLI) {
   LLVMContext &Context = B.GetInsertBlock()->getContext();
   return emitLibCall(
       LibFunc_memcmp, B.getInt32Ty(),
       {B.getInt8PtrTy(), B.getInt8PtrTy(), DL.getIntPtrType(Context)},
       {castToCStr(Ptr1, B), castToCStr(Ptr2, B), Len}, B, TLI);
 }

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

if (I == StringRef::npos) // Didn't find the char.  strchr returns null.
     return Constant::getNullValue(CI->getType());
 
   // strchr(s+n,c)  -> gep(s+n+i,c)
   return B.CreateInBoundsGEP(B.getInt8Ty(), SrcStr, B.getInt64(I), "strchr");
 }
 
 Value *LibCallSimplifier::optimizeStrRChr(CallInst *CI, IRBuilderBase &B) {
   Value *SrcStr = CI->getArgOperand(0);
-  ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
+  Value *CharVal = CI->getArgOperand(1);
+  ConstantInt *CharC = dyn_cast<ConstantInt>(CharVal);
   annotateNonNullNoUndefBasedOnAccess(CI, 0);
 
-  // Cannot fold anything if we're not looking for a constant.
-  if (!CharC)
-    return nullptr;
-
   StringRef Str;
   if (!getConstantStringInfo(SrcStr, Str)) {
     // strrchr(s, 0) -> strchr(s, 0)
-    if (CharC->isZero())
+    if (CharC && CharC->isZero())
       return copyFlags(*CI, emitStrChr(SrcStr, '\0', B, TLI));
     return nullptr;
   }
 
-  // Compute the offset.
-  size_t I = (0xFF & CharC->getSExtValue()) == 0
-                 ? Str.size()
-                 : Str.rfind(CharC->getSExtValue());
-  if (I == StringRef::npos) // Didn't find the char. Return null.
-    return Constant::getNullValue(CI->getType());
-
-  // strrchr(s+n,c) -> gep(s+n+i,c)
-  return B.CreateInBoundsGEP(B.getInt8Ty(), SrcStr, B.getInt64(I), "strrchr");
+  // Try to expand strrchr to the memrchr nonstandard extension if it's
+  // available, or simply fail otherwise.
+  uint64_t NBytes = Str.size() + 1;   // Include the terminating nul.
+  Type *IntPtrType = DL.getIntPtrType(CI->getContext());
+  Value *Size = ConstantInt::get(IntPtrType, NBytes);
+  return copyFlags(*CI, emitMemRChr(SrcStr, CharVal, Size, B, DL, TLI));
 }
 
 Value *LibCallSimplifier::optimizeStrCmp(CallInst *CI, IRBuilderBase &B) {
   Value *Str1P = CI->getArgOperand(0), *Str2P = CI->getArgOperand(1);
   if (Str1P == Str2P) // strcmp(x,x)  -> 0
     return ConstantInt::get(CI->getType(), 0);
 
   StringRef Str1, Str2;

llvm/test/Transforms/InstCombine/strcall-no-nul.ll

;
   ret void
 }
 
 
 ; Fold strrchr(a5 + 5, '\0') to null.
 
 define i8* @fold_strrchr_past_end(i32 %c) {
 ; CHECK-LABEL: @fold_strrchr_past_end(
-; CHECK-NEXT:    ret i8* getelementptr inbounds ([5 x i8], [5 x i8]* @a5, i64 1, i64 0)
+; CHECK-NEXT:    ret i8* null
 ;
   %p5 = getelementptr [5 x i8], [5 x i8]* @a5, i32 0, i32 5
   %r = call i8* @strrchr(i8* %p5, i32 0)
   ret i8* %r
 }
 
 
 ; Fold strstr(a5 + 5, a5) (and vice versa) to null.

llvm/test/Transforms/InstCombine/strrchr-1.ll

 ;
 
   %src = getelementptr [14 x i8], [14 x i8]* @hello, i32 0, i32 0
   %dst = call i8* @strrchr(i8* %src, i32 65280)
   store i8* %dst, i8** @chp
   ret void
 }
 
-define void @test_nosimplify1(i32 %chr) {
-; CHECK-LABEL: @test_nosimplify1(
-; CHECK-NEXT:    [[DST:%.*]] = call i8* @strrchr(i8* noundef nonnull dereferenceable(1) getelementptr inbounds ([14 x i8], [14 x i8]* @hello, i32 0, i32 0), i32 [[CHR:%.*]])
-; CHECK-NEXT:    store i8* [[DST]], i8** @chp, align 4
+define void @test_xform_to_memrchr(i32 %chr) {
+; CHECK-LABEL: @test_xform_to_memrchr(
+; CHECK-NEXT:    [[MEMRCHR:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(14) getelementptr inbounds ([14 x i8], [14 x i8]* @hello, i32 0, i32 0), i32 [[CHR:%.*]], i32 14)
+; CHECK-NEXT:    store i8* [[MEMRCHR]], i8** @chp, align 4
 ; CHECK-NEXT:    ret void
 ;
 
   %src = getelementptr [14 x i8], [14 x i8]* @hello, i32 0, i32 0
   %dst = call i8* @strrchr(i8* %src, i32 %chr)
   store i8* %dst, i8** @chp
   ret void
 }

llvm/test/Transforms/InstCombine/strrchr-3.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; Verify the strrchr("", c) to (unsigned char)c ? "" : 0 transformetion.
+;
+; RUN: opt < %s -passes=instcombine -S | FileCheck %s
+
+@s10 = constant [11 x i8] c"0123456789\00"
+
+declare i8* @strrchr(i8*, i32)
+
+; Fold strrchr(s + 10, c) to (unsigned char)c ? 0 : s + 10.
+
+define i8* @fold_strrchr_sp10_x(i32 %c) {
+; CHECK-LABEL: @fold_strrchr_sp10_x(
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[C:%.*]] to i8
+; CHECK-NEXT:    [[MEMRCHR_CHAR0CMP:%.*]] = icmp eq i8 [[TMP1]], 0
+; CHECK-NEXT:    [[MEMRCHR_SEL:%.*]] = select i1 [[MEMRCHR_CHAR0CMP]], i8* getelementptr inbounds ([11 x i8], [11 x i8]* @s10, i64 0, i64 10), i8* null
+; CHECK-NEXT:    ret i8* [[MEMRCHR_SEL]]
+;
+  %psp10 = getelementptr [11 x i8], [11 x i8]* @s10, i32 0, i32 10
+  %pc = call i8* @strrchr(i8* %psp10, i32 %c)
+  ret i8* %pc
+}
+
+
+; Transform strrchr(s + 9, c) to [the equivalent of] memrchr(s + 9, c, 2).
+
+define i8* @call_strrchr_sp9_x(i32 %c) {
+; CHECK-LABEL: @call_strrchr_sp9_x(
+; CHECK-NEXT:    [[MEMRCHR:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(2) getelementptr inbounds ([11 x i8], [11 x i8]* @s10, i64 0, i64 9), i32 [[C:%.*]], i64 2)
+; CHECK-NEXT:    ret i8* [[MEMRCHR]]
+;
+  %psp9 = getelementptr [11 x i8], [11 x i8]* @s10, i32 0, i32 9
+  %pc = call i8* @strrchr(i8* %psp9, i32 %c)
+  ret i8* %pc
+}
+
+
+; Do not transform strrchr(s + 2, c) (for short strings this could be
+; folded into a chain of OR expressions ala D128011).
+
+define i8* @call_strrchr_sp2_x(i32 %c) {
+; CHECK-LABEL: @call_strrchr_sp2_x(
+; CHECK-NEXT:    [[MEMRCHR:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(9) getelementptr inbounds ([11 x i8], [11 x i8]* @s10, i64 0, i64 2), i32 [[C:%.*]], i64 9)
+; CHECK-NEXT:    ret i8* [[MEMRCHR]]
+;
+  %psp2 = getelementptr [11 x i8], [11 x i8]* @s10, i32 0, i32 2
+  %pc = call i8* @strrchr(i8* %psp2, i32 %c)
+  ret i8* %pc
+}
+
+
+; Do not transform strrchr(s + 1, c).
+
+define i8* @call_strrchr_sp1_x(i32 %c) {
+; CHECK-LABEL: @call_strrchr_sp1_x(
+; CHECK-NEXT:    [[MEMRCHR:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(10) getelementptr inbounds ([11 x i8], [11 x i8]* @s10, i64 0, i64 1), i32 [[C:%.*]], i64 10)
+; CHECK-NEXT:    ret i8* [[MEMRCHR]]
+;
+  %psp1 = getelementptr [11 x i8], [11 x i8]* @s10, i32 0, i32 1
+  %pc = call i8* @strrchr(i8* %psp1, i32 %c)
+  ret i8* %pc
+}