[SimplifyLibcalls] Optimize string concats using s(n)printf

[xbolva00]

Summary

sprintf(buf, "%s%s", buf, str) -> strcat(buf, str)

snprintf(buf, n, "%s%s", buf, str) -> strncat(buf, str, n)

[lebedev.ri]

lib/Transforms/Utils/SimplifyLibCalls.cpp

1841

PRINTF(3)

<...>

NOTES
       Some programs imprudently rely on code such as the following

           sprintf(buf, "%s some further text", buf);

       to  append  text to buf.  However, the standards explicitly note that the results are undefined if source and destination buffers overlap when calling sprintf(), snprintf(), vsprintf(), and vsnprintf().  Depending on the version of gcc(1) used, and the com‐
       piler options employed, calls such as the above will not produce the expected results.

       The glibc implementation of the functions snprintf() and vsnprintf() conforms to the C99 standard, that is, behaves as described above, since glibc version 2.1.  Until glibc 2.0.6, they would return -1 when the output was truncated.

[xbolva00]

lib/Transforms/Utils/SimplifyLibCalls.cpp

1841

char buf[20] = "hello ";
sprintf(buf, "%s%s", buf, "world");
puts(buf);

No build warnings, and maybe they say that undefined results but I always get the correct results.
I hit no problems when trying these codes and transformations.

I am not sure why would this "possibly undefined results from sprintf" case should block this transformation. E.g. we perform many optimizations just because of UB... But sure, suggestions welcome.

Eli?
@efriedma

[efriedma]

Yes, we can do anything if we prove the code has undefined behavior, but I'm not sure why we would prefer a call to strncat over "unreachable".

[xbolva00]

In D46648#1093273, @efriedma wrote:

Yes, we can do anything if we prove the code has undefined behavior, but I'm not sure why we would prefer a call to strncat over "unreachable".

"unreachable" is emitted when (in terms of this transformation)?
snprintf(buf, n, "%s%s", buf, str) works normally, I see no "unreachable".

[efriedma]

If your results appear to be "correct", you're just getting lucky that your particular combination of compiler and C library don't do something else.

We should probably just add clang -Wformat warning, rather than try to optimize it in SimplifyLibCalls.

[lebedev.ri]

In D46648#1093505, @efriedma wrote:

If your results appear to be "correct", you're just getting lucky that your particular combination of compiler and C library don't do something else.

We should probably just add clang -Wformat warning, rather than try to optimize it in SimplifyLibCalls.

And ubsan, if it does not handle this already.

[xbolva00]

-Wformat does not handle it.

UBsan.. I tried but I got some error on my system
/usr/bin/ld: cannot find /usr/local/lib/clang/7.0.0/lib/linux/libclang_rt.ubsan_standalone-x86_64.a

Anyway ok, I will close this.

[xbolva00]

Sorry, accidentally clicked to accept.

[smeenai]

If you're not planning to move forward with the diff, it's better to abandon it rather than close it. Close usually implies it was committed.

[xbolva00]

I am just wondering...

snprintf(buf , n, "some data %s", buf) is UB..
but..
snprintf(buf, n , "%s", buf) should be totally fine. Also for %s%s. If fmt starts with "%s", there should not be a problem.

Eli?

[efriedma]

The C standard is very clear: "If copying takes place between objects that overlap, the behavior is undefined." There is no exception for format strings which start with %s.

[xbolva00]

Ok

include/llvm/Transforms/Utils/BuildLibCalls.h

namespace llvm {
 
   /// Emit a call to the malloc function.
   Value *emitMalloc(Value *Num, IRBuilder<> &B, const DataLayout &DL,
                     const TargetLibraryInfo *TLI);
 
   /// Emit a call to the calloc function.
   Value *emitCalloc(Value *Num, Value *Size, const AttributeList &Attrs,
                     IRBuilder<> &B, const TargetLibraryInfo &TLI);
+
+  /// Emit a call to the strcat function to the builder, for the specified
+  /// pointer arguments.
+  Value *emitStrCat(Value *Dst, Value *Src, IRBuilder<> &B,
+                    const TargetLibraryInfo *TLI, StringRef Name = "strcat");
+
+  /// Emit a call to the strncat function to the builder, for the specified
+  /// pointer arguments and length.
+  Value *emitStrNCat(Value *Dst, Value *Src, Value *Len, IRBuilder<> &B,
+                     const TargetLibraryInfo *TLI, StringRef Name = "strncat");
 }
 
 #endif

lib/Transforms/Utils/BuildLibCalls.cpp

Value *llvm::emitCalloc(Value *Num, Value *Size, const AttributeList &Attrs,
   inferLibFuncAttributes(*M->getFunction("calloc"), TLI);
   CallInst *CI = B.CreateCall(Calloc, {Num, Size}, "calloc");
 
   if (const auto *F = dyn_cast<Function>(Calloc->stripPointerCasts()))
     CI->setCallingConv(F->getCallingConv());
 
   return CI;
 }
+
+Value *llvm::emitStrCat(Value *Dst, Value *Src, IRBuilder<> &B,
+                        const TargetLibraryInfo *TLI, StringRef Name) {
+  if (!TLI->has(LibFunc_strcat))
+    return nullptr;
+
+  Module *M = B.GetInsertBlock()->getModule();
+  Type *I8Ptr = B.getInt8PtrTy();
+  Value *StrCat = M->getOrInsertFunction(Name, I8Ptr, I8Ptr, I8Ptr);
+  inferLibFuncAttributes(*M->getFunction(Name), *TLI);
+  CallInst *CI =
+      B.CreateCall(StrCat, {castToCStr(Dst, B), castToCStr(Src, B)}, Name);
+  if (const Function *F = dyn_cast<Function>(StrCat->stripPointerCasts()))
+    CI->setCallingConv(F->getCallingConv());
+  return CI;
+}
+
+Value *llvm::emitStrNCat(Value *Dst, Value *Src, Value *Len, IRBuilder<> &B,
+                         const TargetLibraryInfo *TLI, StringRef Name) {
+  if (!TLI->has(LibFunc_strncat))
+    return nullptr;
+
+  Module *M = B.GetInsertBlock()->getModule();
+  Type *I8Ptr = B.getInt8PtrTy();
+  Value *StrNCat =
+      M->getOrInsertFunction(Name, I8Ptr, I8Ptr, I8Ptr, Len->getType());
+  inferLibFuncAttributes(*M->getFunction(Name), *TLI);
+  CallInst *CI = B.CreateCall(
+      StrNCat, {castToCStr(Dst, B), castToCStr(Src, B), Len}, "strncat");
+  if (const Function *F = dyn_cast<Function>(StrNCat->stripPointerCasts()))
+    CI->setCallingConv(F->getCallingConv());
+  return CI;
+}
 No newline at end of file

lib/Transforms/Utils/SimplifyLibCalls.cpp

 }
 
 Value *LibCallSimplifier::optimizeSPrintFString(CallInst *CI, IRBuilder<> &B) {
   // Check for a fixed format string.
   StringRef FormatStr;
   if (!getConstantStringInfo(CI->getArgOperand(1), FormatStr))
     return nullptr;
 
+  // sprintf(buf, "%s%s", buf, str) -> strcat(buf, str)
+  if (FormatStr == "%s%s" && CI->getNumArgOperands() == 4) {
+    Value *Buf = CI->getArgOperand(0);
+    Value *Src = CI->getArgOperand(2);
+    if (Buf == Src) {
+      Value *V = emitStrCat(Buf, CI->getArgOperand(3), B, TLI);
+      if (CI->use_empty())
+        return V;
+
+      Value *Len = emitStrLen(V, B, DL, TLI);
+      return B.CreateIntCast(Len, CI->getType(), false);
+    }
+  }
+
   // If we just have a format string (nothing else crazy) transform it.
   if (CI->getNumArgOperands() == 2) {
     // Make sure there's no % in the constant array.  We could try to handle
     // %% -> % in the future if we cared.
     for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
       if (FormatStr[i] == '%')
         return nullptr; // we found a format specifier, bail out.
 
     // sprintf(str, fmt) -> llvm.memcpy(align 1 str, align 1 fmt, strlen(fmt)+1)
     B.CreateMemCpy(CI->getArgOperand(0), 1, CI->getArgOperand(1), 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() < 3)
-    return nullptr;
+  if (FormatStr.size() == 2 && FormatStr[0] == '%' &&
+      CI->getNumArgOperands() == 3) {
 
     // 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");
       B.CreateStore(B.getInt8(0), Ptr);
 
       return ConstantInt::get(CI->getType(), 1);
     }
 
     if (FormatStr[1] == 's') {
       // sprintf(dest, "%s", str) -> llvm.memcpy(dest, str, strlen(str)+1, 1)
       if (!CI->getArgOperand(2)->getType()->isPointerTy())
         return nullptr;
 
       Value *Len = emitStrLen(CI->getArgOperand(2), B, DL, TLI);
       if (!Len)
         return nullptr;
       Value *IncLen =
           B.CreateAdd(Len, ConstantInt::get(Len->getType(), 1), "leninc");
       B.CreateMemCpy(CI->getArgOperand(0), 1, CI->getArgOperand(2), 1, IncLen);
 
       // The sprintf result is the unincremented number of bytes in the string.
       return B.CreateIntCast(Len, CI->getType(), false);
     }
+  }
+
   return nullptr;
 }
 
 Value *LibCallSimplifier::optimizeSPrintF(CallInst *CI, IRBuilder<> &B) {
   Function *Callee = CI->getCalledFunction();
   FunctionType *FT = Callee->getFunctionType();
   if (Value *V = optimizeSPrintFString(CI, B)) {
     return V;

 }
 
 Value *LibCallSimplifier::optimizeSnPrintFString(CallInst *CI, IRBuilder<> &B) {
   // Check for a fixed format string.
   StringRef FormatStr;
   if (!getConstantStringInfo(CI->getArgOperand(2), FormatStr))
     return nullptr;
 
+  // snprintf(buf, n, "%s%s", buf, str) -> strncat(buf, str, n)
+  if (FormatStr == "%s%s" && CI->getNumArgOperands() == 5) {
+    Value *Buf = CI->getArgOperand(0);
+    Value *N = CI->getArgOperand(1);
+    Value *Src = CI->getArgOperand(3);
+    if (Buf == Src) {
+      Value *V = emitStrNCat(Buf, CI->getArgOperand(4), N, B, TLI);
+      if (CI->use_empty())
+        return V;
+
+      Value *Len = emitStrLen(V, B, DL, TLI);
+      return B.CreateIntCast(Len, CI->getType(), false);
+    }
+  }
+
   // Check for size
   ConstantInt *Size = dyn_cast<ConstantInt>(CI->getArgOperand(1));
   if (!Size)
     return nullptr;
 
   uint64_t N = Size->getZExtValue();
 
   // If we just have a format string (nothing else crazy) transform it.

test/Transforms/InstCombine/concat.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+@.str = private unnamed_addr constant [5 x i8] c"%s%s\00", align 1
+
+declare i32 @sprintf(i8* nocapture, i8* nocapture readonly, ...)
+declare i32 @snprintf(i8* nocapture, i32, i8* nocapture readonly, ...)
+declare i8* @strcat(i8*, i8* nocapture readonly)
+declare i32 @strlen(i8* nocapture)
+declare i8* @strncat(i8*, i8* nocapture readonly, i32)
+
+
+define i32 @sprintf_concat_ok_return(i8* %str, i8* %str2) {
+; CHECK-LABEL: @sprintf_concat_ok_return(
+; CHECK-NEXT:    [[STRCAT:%.*]] = call i8* @strcat(i8* [[STR:%.*]], i8* [[STR2:%.*]])
+; CHECK-NEXT:    [[STRLEN:%.*]] = call i64 bitcast (i32 (i8*)* @strlen to i64 (i8*)*)(i8* [[STRCAT]])
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[STRLEN]] to i32
+; CHECK-NEXT:    ret i32 [[TMP1]]
+;
+  %call = tail call i32 (i8*, i8*, ...) @sprintf(i8* %str, i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i32 0, i32 0), i8* %str, i8* %str2) #2
+  ret i32 %call
+}
+
+define void @sprintf_concat_ok(i8* %str, i8* %str2) {
+; CHECK-LABEL: @sprintf_concat_ok(
+; CHECK-NEXT:    [[STRCAT:%.*]] = call i8* @strcat(i8* [[STR:%.*]], i8* [[STR2:%.*]])
+; CHECK-NEXT:    ret void
+;
+  %call = tail call i32 (i8*, i8*, ...) @sprintf(i8* %str, i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i32 0, i32 0), i8* %str, i8* %str2) #2
+  ret void
+}
+
+define i32 @snprintf_concat_ok_return(i8* %str, i8* %str2, i32 %n) {
+; CHECK-LABEL: @snprintf_concat_ok_return(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[STRNCAT:%.*]] = call i8* @strncat(i8* [[STR:%.*]], i8* [[STR2:%.*]], i32 [[N:%.*]])
+; CHECK-NEXT:    [[STRLEN:%.*]] = call i64 bitcast (i32 (i8*)* @strlen to i64 (i8*)*)(i8* [[STRNCAT]])
+; CHECK-NEXT:    [[TMP0:%.*]] = trunc i64 [[STRLEN]] to i32
+; CHECK-NEXT:    ret i32 [[TMP0]]
+;
+entry:
+  %call = tail call i32 (i8*, i32, i8*, ...) @snprintf(i8* %str, i32 %n, i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i32 0, i32 0), i8* %str, i8* %str2) #2
+  ret i32 %call
+}
+
+define void @snprintf_concat_ok(i8* %str, i8* %str2, i32 %n) {
+; CHECK-LABEL: @snprintf_concat_ok(
+; CHECK-NEXT:    [[STRNCAT:%.*]] = call i8* @strncat(i8* [[STR:%.*]], i8* [[STR2:%.*]], i32 [[N:%.*]])
+; CHECK-NEXT:    ret void
+;
+  %call = tail call i32 (i8*, i32, i8*, ...) @snprintf(i8* %str, i32 %n, i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i32 0, i32 0), i8* %str, i8* %str2) #2
+  ret void
+}
+
+define void @snprintf_const_fmt(i8* %str, i8* %str2, i32 %n, i8* nocapture readonly %fmt) {
+; CHECK-LABEL: @snprintf_const_fmt(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call i32 (i8*, i32, i8*, ...) @snprintf(i8* [[STR:%.*]], i32 [[N:%.*]], i8* [[FMT:%.*]], i8* [[STR]], i8* [[STR2:%.*]])
+; CHECK-NEXT:    ret void
+;
+  %call = tail call i32 (i8*, i32, i8*, ...) @snprintf(i8* %str, i32 %n, i8* %fmt, i8* %str, i8* %str2) #2
+  ret void
+}
+
+define void @sprintf_const_fmt(i8* %str, i8* %str2, i8* nocapture readonly %fmt) {
+; CHECK-LABEL: @sprintf_const_fmt(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call i32 (i8*, i8*, ...) @sprintf(i8* [[STR:%.*]], i8* [[FMT:%.*]], i8* [[STR]], i8* [[STR2:%.*]])
+; CHECK-NEXT:    ret void
+;
+  %call = tail call i32 (i8*, i8*, ...) @sprintf(i8* %str, i8* %fmt, i8* %str, i8* %str2) #2
+  ret void
+}