[InstCombine] snprintf (d, size, "%s", s) -> memccpy (d, s, '\0', size - 1), d[size - 1] = 0

[xbolva00]

Summary

snprintf (d, size, "%s", s)
->
memccpy (d, s, '\0', size - 1),
d[size - 1] = 0

memccpy is much faster than snprintf my microbenchmark

time ./snprintf.out 1000000

real 0m0,057s
user 0m0,057s
sys 0m0,000s

time ./memccpy.out 1000000

real 0m0,021s
user 0m0,021s
sys 0m0,000s

[efriedma]

Do we have accurate TLI information for memccpy? Not sure exactly how widely available it is.

If we're going to start generating memccpy calls, do we need to implement optimizations for it? For example, memccpy of a constant string can be transformed to memcpy.

[xbolva00]

There is a comment in TLI:

     // Win32 does not support these functions, but
     // they are generally available on POSIX-compliant systems.
...
         TLI.setUnavailable(LibFunc_memccpy);

If we're going to start generating memccpy calls, do we need to implement optimizations for it? For example, memccpy of a constant string can be transformed to memcpy.

Yeah, as follow up patch.
snprintf (d, size, "%s", "constant") is handled currently, so we should not regress the current "snprintf" calls with this transform..

[xbolva00]

In D67986#1681631, @efriedma wrote:

If we're going to start generating memccpy calls, do we need to implement optimizations for it? For example, memccpy of a constant string can be transformed to memcpy.

Ok, done: https://reviews.llvm.org/D68089

[xbolva00]

Wrote a simple microbenchmark - memccpy is 4-5x faster than sprintf in this case.

[xbolva00]

Oh, I think the proposed transformation in that paper is incorrect.

It should rather be:
memccpy(d,s,0, n-1)
d[n-1] = 0

Since "A terminating null character is automatically appended after the content written." (snprintf)

[efriedma]

Yes, that's right. Thanks for spotting that.

[xbolva00]

Updated. Current tranformations should be correct now.

[xbolva00]

Rebased + added one new test

[lebedev.ri]

lib/Transforms/Utils/SimplifyLibCalls.cpp

2581

Where did we ask TLI about the existence of memccpy?

2583

It likely should be CreateInBoundsGEP().

[xbolva00]

lib/Transforms/Utils/SimplifyLibCalls.cpp

2581

emitMemCCpy calls emitLibcall which checks it - otherwise returns nullptr.

Ah, and we should not emit store in that case, if emitmemccpy failed. Thanks!

2583

I was wondering about this too, then code above is broken too :) I will fix it.

[xbolva00]

Addressed review comments

[xbolva00]

test/Transforms/InstCombine/snprintf-memccpy.ll

47

hmm...

Should I call DecSize->eraseFromParent() ?

[nickdesaulniers]

It sounds like memccpy is part of C20. Can we not do this transform unless LangOpt says we're C20 or greater? Otherwise the Linux kernel doesn't implement this routine.

[lebedev.ri]

In D67986#1691643, @nickdesaulniers wrote:

It sounds like memccpy is part of C20. Can we not do this transform unless LangOpt says we're C20 or greater? Otherwise the Linux kernel doesn't implement this routine.

LLVM middle-end does not and should not care what (if any) language standard the frontend was targeting when producing the initial IR.
Only the presence (as per TargetLoweringInfo::has()) of the replacement builtin matters.

[xbolva00]

The kernel should use same workaround as for bcmp transformation in this case.

Otherwise the Linux kernel doesn't implement this routine.

Original paper is from a GCC dev, so I think GCC will implement memccpy like optimizations for GCC 10 too.

[xbolva00]

Can the kernel just implement it this easy way? memccpy is not very known but I believe there are places in the kernel where memccpy could be used efficiently by kernel devs.

https://code.woboq.org/userspace/glibc/string/memccpy.c.html

[efriedma]

It sounds like memccpy is part of C20. Can we not do this transform unless LangOpt says we're C20 or greater? Otherwise the Linux kernel doesn't implement this routine.

Doesn't the kernel use -fno-builtin? That should be enough to suppress this optimization.

In general, we assume that TargetLibraryInfo is providing an accurate picture of what functions are available. If it isn't, we should fix that in some general way.

[xbolva00]

but -fno-builtin is maybe too aggressive? somebody should benchmark kernel with/without it.

Anyway, I thought -fno-builtin-memccpy also could disable it, but no.. -fno-builtin-snprintf / -ffreestanding works.

[efriedma]

Oh, hmm... actually, just realized something; is the new formulation actually equivalent? Specifically, is it okay to write to "d[size - 1]" if the string is short? Say, for example, you have something like snprintf(buf, 10, "%s", "x"). That normally writes to two elements of the array: 0 and 1. The rewritten version writes to three elements: 0, 1, and 9.

[efriedma]

-fno-builtin-memccpy doesn't work because memccpy isn't listed in include/clang/Basic/Builtins.def. We should probably fix that.

[lebedev.ri]

In D67986#1692020, @efriedma wrote:

Oh, hmm... actually, just realized something; is the new formulation actually equivalent? Specifically, is it okay to write to "d[size - 1]" if the string is short? Say, for example, you have something like snprintf(buf, 10, "%s", "x"). That normally writes to two elements of the array: 0 and 1. The rewritten version writes to three elements: 0, 1, and 9.

Sounds like this should be guarded to only work for simple (non-volatile, non-atomic) pointers?

[xbolva00]

-fno-builtin-memccpy doesn't work because memccpy isn't listed in include/clang/Basic/Builtins.def. We should probably fix that.

Just add new record:
LIBBUILTIN(memccpy, "v*v*vC*iz", "f", "string.h", ALL_LANGUAGES)

?

Than great, then linux kernel would just use -fno-builtin-memccpy and we are fine here.

Sounds like this should be guarded to only work for simple (non-volatile, non-atomic) pointers?

Good catch, yeah, I will do it. 'Dst' must be simple ptr.

[xbolva00]

Say, for example, you have something like snprintf(buf, 10, "%s", "x"). That normally writes to two elements of the array: 0 and 1. The rewritten version writes to three elements: 0, 1, and 9.

Hm, this is right. We overwrite d[size -1] always -> bad. I have no more ideas, probably we can do nothing, just abandon this transformation.

[efriedma]

You could do something like if (!memccpy (d, s, '\0', size - 1)) d[size - 1] = 0;, I guess. That's a few more instructions that I'd really like, but I don't see a better alternative.

[xbolva00]

In D67986#1692126, @efriedma wrote:

You could do something like if (!memccpy (d, s, '\0', size - 1)) d[size - 1] = 0;, I guess. That's a few more instructions that I'd really like, but I don't see a better alternative.

Yeah, but probably InstCombine is not best place to create such ranches/phis, select would be better.

Maybe this could work?
char *ret = memccpy (d, s, '\0', n - 1);
char * ptr = ret ? ret - 1 : &d[n - 1];
*ptr = 0;

[xbolva00]

Missclicked, sorry.

[xbolva00]

And yes, with D68377 -fno-builtin-memccpy works -> Ideal fix for the linux kernel.

[joerg]

I'd make the argument that it should be strlcpy if present. That covers a lot of existing systems too. I'm not sure this optimisation should be done for freestanding mode though.

[xbolva00]

I'm not sure this optimisation should be done for freestanding mode though.

I said it above, -ffreestanding disables this transformation too.

I'd make the argument that it should be strlcpy if present. That covers a lot of existing systems too.

strlcpy is good idea and it is faster than memccpy. but.. I need to link with -lbsd on Ubuntu.

I dont use BSD systems, so I am not gonna to do your suggested transformation since I cant test it. But patches are welcome, I will be happy to look at it if you send one here.

[xbolva00]

In D67986#1687323, @xbolva00 wrote:

Oh, I think the proposed transformation in that paper is incorrect.

It should rather be:
memccpy(d,s,0, n-1)
d[n-1] = 0

Since "A terminating null character is automatically appended after the content written." (snprintf)

@efriedma, what do you think about this sequence?

[efriedma]

The sequence from https://reviews.llvm.org/D67986#1692153 works, I guess.

[MaskRay]

This transformation seems to increase code size significantly. Is the snprintf "%s" pattern common enough? I suspect most projects have already used memccpy, stpncpy, strscpy, or strlcpy. For the few that don't, the performance probably does not matter.

[xbolva00]

In D67986#1702901, @MaskRay wrote:

This transformation seems to increase code size significantly. Is the snprintf "%s" pattern common enough? I suspect most projects have already used memccpy, stpncpy, strscpy, or strlcpy. For the few that don't, the performance probably does not matter.

Yes, quite common. But okay, if you dont want it, let's just abandon it.

[jdoerfert]

In D67986#1703031, @xbolva00 wrote:

In D67986#1702901, @MaskRay wrote:

This transformation seems to increase code size significantly. Is the snprintf "%s" pattern common enough? I suspect most projects have already used memccpy, stpncpy, strscpy, or strlcpy. For the few that don't, the performance probably does not matter.

Yes, quite common. But okay, if you dont want it, let's just abandon it.

I wouldn't have quit on this so easily, but OK.

[xbolva00]

BTW, nowdays we transform snprintf(d, s, "%s" , ...) into two calls - memcpy + strlen - and nobody is concerned about code size increase anyway.

So I dont think code size is problem here (if so, !optForSize). Various InstCombine transformations produce two calls. (here it is just call + select..).

I will continue with this patch.

[nickdesaulniers]

In D67986#1702901, @MaskRay wrote:

This transformation seems to increase code size significantly. Is the snprintf "%s" pattern common enough? I suspect most projects have already used memccpy, stpncpy, strscpy, or strlcpy. For the few that don't, the performance probably does not matter.

Sounds like then maybe this optimization should conditionally occur based on optimization level/goals? For instance, maybe it's not appropriate at -Os, but is at -O2?

[xbolva00]

I am fine with your suggestion to restrict it like you said.

(Generally, I think more transforms in instcombine should be restricted this way)

[jdoerfert]

What is the status for this one?

[xbolva00]

I will update this soon.

[xbolva00]

In D67986#1702901, @MaskRay wrote:

This transformation seems to increase code size significantly. Is the snprintf "%s" pattern common enough? I suspect most projects have already used memccpy, stpncpy, strscpy, or strlcpy. For the few that don't, the performance probably does not matter.

I think this is right, since correct expansion via memccpy is quite big even for -O3.

lib/Transforms/Utils/SimplifyLibCalls.cpp

Value *LibCallSimplifier::optimizeSPrintFString(CallInst *CI, IRBuilder<> &B) {
   // Decode the second character of the format string.
   if (FormatStr[1] == 'c') {
     // sprintf(dst, "%c", chr) --> *(i8*)dst = chr; *((i8*)dst+1) = 0
     if (!CI->getArgOperand(2)->getType()->isIntegerTy())
       return nullptr;
     Value *V = B.CreateTrunc(CI->getArgOperand(2), B.getInt8Ty(), "char");
     Value *Ptr = castToCStr(CI->getArgOperand(0), B);
     B.CreateStore(V, Ptr);
-    Ptr = B.CreateGEP(B.getInt8Ty(), Ptr, B.getInt32(1), "nul");
+    Ptr = B.CreateInBoundsGEP(B.getInt8Ty(), Ptr, B.getInt32(1), "nul");
     B.CreateStore(B.getInt8(0), Ptr);
 
     return ConstantInt::get(CI->getType(), 1);
   }
 
   if (FormatStr[1] == 's') {
     // sprintf(dest, "%s", str) -> llvm.memcpy(align 1 dest, align 1 str,
     // strlen(str)+1)
if (TLI->has(LibFunc_small_sprintf) && !callHasFP128Argument(CI)) {
     return New;
   }
 
   annotateNonNullBasedOnAccess(CI, {0, 1});
   return nullptr;
 }
 
 Value *LibCallSimplifier::optimizeSnPrintFString(CallInst *CI, IRBuilder<> &B) {
-  // Check for size
-  ConstantInt *Size = dyn_cast<ConstantInt>(CI->getArgOperand(1));
-  if (!Size)
-    return nullptr;
-
-  uint64_t N = Size->getZExtValue();
+  Value *Dst = CI->getArgOperand(0);
+  Value *SizeArg = CI->getArgOperand(1);
+  ConstantInt *Size = dyn_cast<ConstantInt>(SizeArg);
   // Check for a fixed format string.
   StringRef FormatStr;
   if (!getConstantStringInfo(CI->getArgOperand(2), FormatStr))
     return nullptr;
 
   // If we just have a format string (nothing else crazy) transform it.
   if (CI->getNumArgOperands() == 3) {
     // Make sure there's no % in the constant array.  We could try to handle
     // %% -> % in the future if we cared.
     if (FormatStr.find('%') != StringRef::npos)
       return nullptr; // we found a format specifier, bail out.
 
+    if (!Size)
+      return nullptr;
+    uint64_t N = Size->getZExtValue();
     if (N == 0)
       return ConstantInt::get(CI->getType(), FormatStr.size());
     else if (N < FormatStr.size() + 1)
       return nullptr;
 
     // snprintf(dst, size, fmt) -> llvm.memcpy(align 1 dst, align 1 fmt,
     // strlen(fmt)+1)
     B.CreateMemCpy(
-        CI->getArgOperand(0), 1, CI->getArgOperand(2), 1,
+        Dst, 1, CI->getArgOperand(2), 1,
         ConstantInt::get(DL.getIntPtrType(CI->getContext()),
                          FormatStr.size() + 1)); // Copy the null byte.
     return ConstantInt::get(CI->getType(), FormatStr.size());
   }
 
   // The remaining optimizations require the format string to be "%s" or "%c"
   // and have an extra operand.
   if (FormatStr.size() == 2 && FormatStr[0] == '%' &&
       CI->getNumArgOperands() == 4) {
 
     // Decode the second character of the format string.
     if (FormatStr[1] == 'c') {
+      if (!Size)
+        return nullptr;
+      uint64_t N = Size->getZExtValue();
       if (N == 0)
         return ConstantInt::get(CI->getType(), 1);
       else if (N == 1)
         return nullptr;
 
       // snprintf(dst, size, "%c", chr) --> *(i8*)dst = chr; *((i8*)dst+1) = 0
       if (!CI->getArgOperand(3)->getType()->isIntegerTy())
         return nullptr;
       Value *V = B.CreateTrunc(CI->getArgOperand(3), B.getInt8Ty(), "char");
-      Value *Ptr = castToCStr(CI->getArgOperand(0), B);
+      Value *Ptr = castToCStr(Dst, B);
       B.CreateStore(V, Ptr);
-      Ptr = B.CreateGEP(B.getInt8Ty(), Ptr, B.getInt32(1), "nul");
+      Ptr = B.CreateInBoundsGEP(B.getInt8Ty(), Ptr, B.getInt32(1), "nul");
       B.CreateStore(B.getInt8(0), Ptr);
 
       return ConstantInt::get(CI->getType(), 1);
     }
 
     if (FormatStr[1] == 's') {
       // snprintf(dest, size, "%s", str) to llvm.memcpy(dest, str, len+1, 1)
       StringRef Str;
-      if (!getConstantStringInfo(CI->getArgOperand(3), Str))
+      if (!getConstantStringInfo(CI->getArgOperand(3), Str)) {
+        if (CI->use_empty() && isKnownNonZero(SizeArg, DL)) {
+          // snprintf (d, size, "%s", s) -> memccpy (d, s, '\0', size - 1),
+          // d[size - 1] = 0
+          Value *DecSize =
+              B.CreateSub(SizeArg, ConstantInt::get(SizeArg->getType(), 1));
+          Value *V = emitMemCCpy(Dst, CI->getArgOperand(3), B.getInt32('\0'), DecSize, B,
+                      TLI);
+          if (V) {
+            Value *DstEnd = B.CreateInBoundsGEP(B.getInt8Ty(), Dst, DecSize);
+            B.CreateStore(B.getInt8(0), DstEnd);
+            return Dst;
+          }
+        }
         return nullptr;
+      }
 
+      if (!Size)
+        return nullptr;
+      uint64_t N = Size->getZExtValue();
       if (N == 0)
         return ConstantInt::get(CI->getType(), Str.size());
       else if (N < Str.size() + 1)
         return nullptr;
 
-      B.CreateMemCpy(CI->getArgOperand(0), 1, CI->getArgOperand(3), 1,
+      B.CreateMemCpy(Dst, 1, CI->getArgOperand(3), 1,
                      ConstantInt::get(CI->getType(), Str.size() + 1));
 
       // The snprintf result is the unincremented number of bytes in the string.
       return ConstantInt::get(CI->getType(), Str.size());
     }
   }
   return nullptr;
 }

test/Transforms/InstCombine/snprintf-memccpy.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instcombine -S | FileCheck %s --check-prefixes=CHECK,CHECK-MEMCCPY
+; RUN: opt < %s -instcombine -S -mtriple=x86_64-pc-windows-msvc | FileCheck %s --check-prefixes=CHECK,CHECK-NO-MEMCCPY
+
+@.str = private constant [3 x i8] c"%s\00", align 1
+declare i32 @snprintf(i8*, i64, i8*, ...)
+
+define void @test_string_to_buf_retval_nonzero_n(i8* %buf, i8* %str) {
+; CHECK-MEMCCPY-LABEL: @test_string_to_buf_retval_nonzero_n(
+; CHECK-MEMCCPY-NEXT:    [[MEMCCPY:%.*]] = call i8* @memccpy(i8* [[BUF:%.*]], i8* [[STR:%.*]], i32 0, i64 7)
+; CHECK-MEMCCPY-NEXT:    [[TMP1:%.*]] = getelementptr inbounds i8, i8* [[BUF]], i64 7
+; CHECK-MEMCCPY-NEXT:    store i8 0, i8* [[TMP1]], align 1
+; CHECK-MEMCCPY-NEXT:    ret void
+;
+; CHECK-NO-MEMCCPY-LABEL: @test_string_to_buf_retval_nonzero_n(
+; CHECK-NO-MEMCCPY-NEXT:    [[CALL:%.*]] = call i32 (i8*, i64, i8*, ...) @snprintf(i8* nonnull dereferenceable(1) [[BUF:%.*]], i64 8, i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str, i64 0, i64 0), i8* [[STR:%.*]])
+; CHECK-NO-MEMCCPY-NEXT:    ret void
+;
+  %call = call i32 (i8*, i64, i8*, ...) @snprintf(i8* %buf, i64 8, i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str, i64 0, i64 0), i8* %str)
+  ret void
+}
+
+define void @test_string_to_buf_retval_n_one(i8* %buf, i8* %str) {
+; CHECK-MEMCCPY-LABEL: @test_string_to_buf_retval_n_one(
+; CHECK-MEMCCPY-NEXT:    [[MEMCCPY:%.*]] = call i8* @memccpy(i8* [[BUF:%.*]], i8* [[STR:%.*]], i32 0, i64 0)
+; CHECK-MEMCCPY-NEXT:    store i8 0, i8* [[BUF]], align 1
+; CHECK-MEMCCPY-NEXT:    ret void
+;
+; CHECK-NO-MEMCCPY-LABEL: @test_string_to_buf_retval_n_one(
+; CHECK-NO-MEMCCPY-NEXT:    [[CALL:%.*]] = call i32 (i8*, i64, i8*, ...) @snprintf(i8* nonnull dereferenceable(1) [[BUF:%.*]], i64 1, i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str, i64 0, i64 0), i8* [[STR:%.*]])
+; CHECK-NO-MEMCCPY-NEXT:    ret void
+;
+  %call = call i32 (i8*, i64, i8*, ...) @snprintf(i8* %buf, i64 1, i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str, i64 0, i64 0), i8* %str)
+  ret void
+}
+
+define void @test_string_to_buf_retval_known_nonzero_n(i8* %buf, i64 %n, i8* %str) {
+; CHECK-MEMCCPY-LABEL: @test_string_to_buf_retval_known_nonzero_n(
+; CHECK-MEMCCPY-NEXT:    [[SIZE:%.*]] = shl i64 3, [[N:%.*]]
+; CHECK-MEMCCPY-NEXT:    [[TMP1:%.*]] = add i64 [[SIZE]], -1
+; CHECK-MEMCCPY-NEXT:    [[MEMCCPY:%.*]] = call i8* @memccpy(i8* [[BUF:%.*]], i8* [[STR:%.*]], i32 0, i64 [[TMP1]])
+; CHECK-MEMCCPY-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i8, i8* [[BUF]], i64 [[TMP1]]
+; CHECK-MEMCCPY-NEXT:    store i8 0, i8* [[TMP2]], align 1
+; CHECK-MEMCCPY-NEXT:    ret void
+;
+; CHECK-NO-MEMCCPY-LABEL: @test_string_to_buf_retval_known_nonzero_n(
+; CHECK-NO-MEMCCPY-NEXT:    [[SIZE:%.*]] = shl i64 3, [[N:%.*]]
+; CHECK-NO-MEMCCPY-NEXT:    [[TMP1:%.*]] = sub i64 [[SIZE]], 1
+; CHECK-NO-MEMCCPY-NEXT:    [[CALL:%.*]] = call i32 (i8*, i64, i8*, ...) @snprintf(i8* nonnull dereferenceable(1) [[BUF:%.*]], i64 [[SIZE]], i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str, i64 0, i64 0), i8* [[STR:%.*]])
+; CHECK-NO-MEMCCPY-NEXT:    ret void
+;
+  %size = shl i64 3, %n
+  %call = call i32 (i8*, i64, i8*, ...) @snprintf(i8* %buf, i64 %size, i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str, i64 0, i64 0), i8* %str)
+  ret void
+}
+
+; Negative tests
+define i32 @test_string_to_buf_retval_used_n_maybe_zero(i8* %buf, i64 %n, i8* %str) {
+; CHECK-LABEL: @test_string_to_buf_retval_used_n_maybe_zero(
+; CHECK-NEXT:    [[CALL:%.*]] = call i32 (i8*, i64, i8*, ...) @snprintf(i8* [[BUF:%.*]], i64 [[N:%.*]], i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str, i64 0, i64 0), i8* [[STR:%.*]])
+; CHECK-NEXT:    ret i32 [[CALL]]
+;
+  %call = call i32 (i8*, i64, i8*, ...) @snprintf(i8* %buf, i64 %n, i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str, i64 0, i64 0), i8* %str)
+  ret i32 %call
+}
+
+define void @test_string_to_buf_retval_used_zero_n(i8* %buf, i8* %str) {
+; CHECK-LABEL: @test_string_to_buf_retval_used_zero_n(
+; CHECK-NEXT:    [[CALL:%.*]] = call i32 (i8*, i64, i8*, ...) @snprintf(i8* [[BUF:%.*]], i64 0, i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str, i64 0, i64 0), i8* [[STR:%.*]])
+; CHECK-NEXT:    ret void
+;
+  %call = call i32 (i8*, i64, i8*, ...) @snprintf(i8* %buf, i64 0, i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str, i64 0, i64 0), i8* %str)
+  ret void
+}
+
+define void @test_string_to_buf_retval_unused(i8* %buf, i64 %n, i8* %str) {
+; CHECK-LABEL: @test_string_to_buf_retval_unused(
+; CHECK-NEXT:    [[CALL:%.*]] = call i32 (i8*, i64, i8*, ...) @snprintf(i8* [[BUF:%.*]], i64 [[N:%.*]], i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str, i64 0, i64 0), i8* [[STR:%.*]])
+; CHECK-NEXT:    ret void
+;
+  %call = call i32 (i8*, i64, i8*, ...) @snprintf(i8* %buf, i64 %n, i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str, i64 0, i64 0), i8* %str)
+  ret void
+}