[InstCombine] Format String optimizations

[xbolva00]

Summary

Inserts constants into format strings.

printf("Hello, %s", "world") - > printf("Hello world")

[xbolva00]

TODO:

• Fix things requested in reviews
• Add support for fprintf, sprintf, snprintf

[xbolva00]

Some tests fail with this change:
CodeGen/X86/no-plt-libcalls.ll
Transforms/InstCombine/printf-1.ll
Transforms/InstCombine/printf-2.ll

I will check it..

[xbolva00]

Updated other tests

[xbolva00]

Updated constant propagation.

[efriedma]

I'm not sure we can rewrite calls to varargs functions safely in general given the current state of the C ABI rules in LLVM.

Sometimes clang does weird things to conform with the ABI rules, because the LLVM type system isn't the same as the C system. For most functions, it's pretty easy to tell it happened: if the IR signature of the function doesn't match the expected signature, something weird happened, so we can just bail out. But varargs functions don't specify a complete signature, so we can't tell if the clang ABI code was forced to do something weird, like split an argument into multiple values, or insert a padding value. For example, for the target mips64-unknown-linux-gnu, a call like printf("asdf%Lf", 1.0L); gets lowered to the following:

%call = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i32 0, i32 0), i64 undef, fp128 0xL00000000000000003FFF000000000000) #2

[xbolva00]

Fixed case like printf("%s%d", "", 1) in constant propagation to format string.

[xbolva00]

In D47159#1107120, @efriedma wrote:

I'm not sure we can rewrite calls to varargs functions safely in general given the current state of the C ABI rules in LLVM.

Sometimes clang does weird things to conform with the ABI rules, because the LLVM type system isn't the same as the C system. For most functions, it's pretty easy to tell it happened: if the IR signature of the function doesn't match the expected signature, something weird happened, so we can just bail out. But varargs functions don't specify a complete signature, so we can't tell if the clang ABI code was forced to do something weird, like split an argument into multiple values, or insert a padding value. For example, for the target mips64-unknown-linux-gnu, a call like printf("asdf%Lf", 1.0L); gets lowered to the following:

%call = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i32 0, i32 0), i64 undef, fp128 0xL00000000000000003FFF000000000000) #2

Ahh, so should I stop to work on this then?

[xbolva00]

printf("asdf%Lf", 1.0L); is also interesting to see Clang vs GCC. GCC does some weird magic :D

https://godbolt.org/g/CSW4Ti

I tested some architectures, only mips seems to have such weird IR.

Maybe it is possible to turn this transformation for some, e.g. x86?

[xbolva00]

Restricted to x86 for now
Fixed format string in arg bug + added tests

[rsmith]

Converting to printf("single string literal") will likely be a small performance pessimization (because the string literal must be scanned for embedded % characters). I think the most efficient form is instead likely to be a format string comprising *only* format specifiers; for example, given

printf("hello %s, my favorite number is %d because it is %s", "world", n, "prime");

... when optimizing for speed, the best code we can produce is probably

printf("%s%d%s", "hello world, my favorite number is ", n, " because it is prime");

... whereas when optimizing for size, it's probably

printf("hello world, my favorite number is %d because it is prime", n);

(but in the latter case we probably also want to check that each of the input string literals has only one use or we risk increasing the data size).

test/Transforms/InstCombine/format-str.ll

30

The transform miscompiles this case. The original program would print out "str: str: %s" and the transformed program will make an invalid call to printf.

[xbolva00]

Too bad we cannot transform printf(str) to fputs(str, stdout)/fwrite. It would be quite interesting I think. But since we know how stdout is represented under GNU/glibc, we can do it under condition "isLinux && isGNU" ?

CI->getModule->getGlobalVariable("stdout")?

But this can be done for only for constants since "%%" could be in the format string.

What do you think?

include/llvm/Transforms/Utils/BuildLibCalls.h

 // optimization passes that need to call the various functions.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_UTILS_BUILDLIBCALLS_H
 #define LLVM_TRANSFORMS_UTILS_BUILDLIBCALLS_H
 
 #include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/ADT/APInt.h"
 #include "llvm/IR/IRBuilder.h"
 
 namespace llvm {
   class Value;
   class DataLayout;
   class TargetLibraryInfo;
 
   /// Analyze the name and prototype of the given function and set any
namespace llvm {
   Value *emitFGetSUnlocked(Value *Str, Value *Size, Value *File, IRBuilder<> &B,
                            const TargetLibraryInfo *TLI);
 
   /// Emit a call to the fread_unlocked function. This assumes that Ptr is a
   /// pointer, Size is an 'intptr_t', N is nmemb and File is a pointer to FILE.
   Value *emitFReadUnlocked(Value *Ptr, Value *Size, Value *N, Value *File,
                            IRBuilder<> &B, const DataLayout &DL,
                            const TargetLibraryInfo *TLI);
+  /// Emit a call to the printf function. Vector Args contains an arguments.
+  Value *emitPrintF(ArrayRef<Value *> Args, IRBuilder<> &B,
+                    const TargetLibraryInfo *TLI);
   }
 
 #endif

lib/Transforms/Utils/BuildLibCalls.cpp

Value *llvm::emitFReadUnlocked(Value *Ptr, Value *Size, Value *N, Value *File,
   if (File->getType()->isPointerTy())
     inferLibFuncAttributes(*M->getFunction(FReadUnlockedName), *TLI);
   CallInst *CI = B.CreateCall(F, {castToCStr(Ptr, B), Size, N, File});
 
   if (const Function *Fn = dyn_cast<Function>(F->stripPointerCasts()))
     CI->setCallingConv(Fn->getCallingConv());
   return CI;
 }
+
+Value *llvm::emitPrintF(ArrayRef<Value *> Args, IRBuilder<> &B,
+                    const TargetLibraryInfo *TLI) {
+  if (!TLI->has(LibFunc_printf))
+    return nullptr;
+
+  Module *M = B.GetInsertBlock()->getModule();
+  FunctionType *FT = FunctionType::get(B.getInt32Ty(), B.getInt8PtrTy(), true);
+  Value *PrintF = M->getOrInsertFunction("printf", FT);
+  inferLibFuncAttributes(*M->getFunction("printf"), *TLI);
+  CallInst *CI = B.CreateCall(PrintF, Args, "printf");
+  if (const Function *F = dyn_cast<Function>(PrintF->stripPointerCasts()))
+    CI->setCallingConv(F->getCallingConv());
+  return CI;
+}

lib/Transforms/Utils/SimplifyLibCalls.cpp

static bool isLocallyOpenedFile(Value *File, CallInst *CI, IRBuilder<> &B,
 
   inferLibFuncAttributes(*CI->getCalledFunction(), *TLI);
   if (PointerMayBeCaptured(File, true, true))
     return false;
 
   return true;
 }
 
+static Value *optimizeFormatString(StringRef FmtStr, unsigned FmtStrIndex,
+                                   CallInst *CI, IRBuilder<> &B,
+                                   SmallVector<Value *, 8> &Args) {
+  assert(CI->getNumArgOperands() > FmtStrIndex + 1 &&
+         "Nothing to fold in optimizeFormatString");
+  Triple T(CI->getModule()->getTargetTriple());
+  if (T.getArch() != Triple::x86_64)
+    return nullptr;
+
+  std::string NewFmtStr = FmtStr;
+  bool Changed = false;
+  unsigned OpCounter = FmtStrIndex;
+  const unsigned FmtTypeIdLen = 2; // support %s, %d, etc for now
+
+  int NextChar;
+  StringRef Str;
+  Value *Op;
+  for (unsigned I = 0; I < NewFmtStr.size() - 1; ++I) {
+    if (NewFmtStr[I] != '%')
+      continue;
+
+    NextChar = NewFmtStr[I + 1];
+    if (NextChar == '%') // skip %%
+      continue;
+
+    ++OpCounter;
+    Op = CI->getArgOperand(OpCounter);
+    if (!isa<Constant>(Op))
+      continue;
+
+    Changed = false;
+    switch (NextChar) {
+    case 's': {
+      if (getConstantStringInfo(Op, Str)) {
+        NewFmtStr.replace(I, FmtTypeIdLen, Str);
+        Changed = true;
+        I += Str.size() - 1;
+      } else {
+        Args.push_back(Op);
+      }
+      break;
+    }
+
+    case 'c': {
+      if (ConstantInt *CInt = dyn_cast<ConstantInt>(Op)) {
+        NewFmtStr.replace(I, FmtTypeIdLen,
+                          std::string(1, CInt->getZExtValue()));
+        Changed = true;
+      } else {
+        Args.push_back(Op);
+      }
+      break;
+    }
+
+    case 'u': {
+      if (ConstantInt *CInt = dyn_cast<ConstantInt>(Op)) {
+        NewFmtStr.replace(I, FmtTypeIdLen,
+                          CInt->getValue().toString(10, false /* isSigned */));
+        Changed = true;
+      } else {
+        Args.push_back(Op);
+      }
+      break;
+    }
+
+    case 'i':
+    case 'd': {
+      if (ConstantInt *CInt = dyn_cast<ConstantInt>(Op)) {
+        NewFmtStr.replace(I, FmtTypeIdLen,
+                          CInt->getValue().toString(10, true /* isSigned */));
+        Changed = true;
+      } else {
+        Args.push_back(Op);
+      }
+      break;
+    }
+
+    default: {
+      Args.push_back(Op);
+      break;
+    }
+    }
+
+    ++I;
+  }
+
+  return Changed ? B.CreateGlobalStringPtr(NewFmtStr, "str") : nullptr;
+}
+
 //===----------------------------------------------------------------------===//
 // String and Memory Library Call Optimizations
 //===----------------------------------------------------------------------===//
 
 Value *LibCallSimplifier::optimizeStrCat(CallInst *CI, IRBuilder<> &B) {
   // Extract some information from the instruction
   Value *Dst = CI->getArgOperand(0);
   Value *Src = CI->getArgOperand(1);
static bool isReportingError(Function *Callee, CallInst *CI, int StreamArg) {
   if (!GV || !GV->isDeclaration())
     return false;
   return GV->getName() == "stderr";
 }
 
 Value *LibCallSimplifier::optimizePrintFString(CallInst *CI, IRBuilder<> &B) {
   // Check for a fixed format string.
   StringRef FormatStr;
-  if (!getConstantStringInfo(CI->getArgOperand(0), FormatStr))
+  Value *Op1 = CI->getArgOperand(0);
+  if (!getConstantStringInfo(Op1, FormatStr))
     return nullptr;
 
-  // Empty format string -> noop.
-  if (FormatStr.empty()) // Tolerate printf's declared void.
-    return CI->use_empty() ? (Value *)CI : ConstantInt::get(CI->getType(), 0);
+  // Optimize format string with args
+  if (CI->getNumArgOperands() > 1) {
+    SmallVector<Value *, 8> Args;
+    Args.push_back(Op1);
+    if (Value *V = optimizeFormatString(FormatStr, 0, CI, B, Args)) {
+      Args[0] = castToCStr(V, B); // Use new format arg
+      return emitPrintF(Args, B, TLI);
+    }
+  }
 
   // Do not do any of the following transformations if the printf return value
   // is used, in general the printf return value is not compatible with either
   // putchar() or puts().
   if (!CI->use_empty())
     return nullptr;
 
+  // Empty format string -> noop.
+  if (FormatStr.empty())
+    return ConstantInt::get(CI->getType(), 0);
+
   // printf("x") -> putchar('x'), even for "%" and "%%".
   if (FormatStr.size() == 1 || FormatStr == "%%")
     return emitPutChar(B.getInt32(FormatStr[0]), B, TLI);
 
   // printf("%s", "a") --> putchar('a')
   if (FormatStr == "%s" && CI->getNumArgOperands() > 1) {
     StringRef ChrStr;
     if (!getConstantStringInfo(CI->getOperand(1), ChrStr))

test/Transforms/InstCombine/format-str.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instcombine -S -mtriple=x86_64-unknown-unknown-unknown | FileCheck %s
+
+@.str = private unnamed_addr constant [9 x i8] c"char: %c\00", align 1
+@.str.1 = private unnamed_addr constant [8 x i8] c"int: %d\00", align 1
+@.str.2 = private unnamed_addr constant [8 x i8] c"int: %i\00", align 1
+@.str.3 = private unnamed_addr constant [9 x i8] c"uint: %u\00", align 1
+@.str.4 = private unnamed_addr constant [8 x i8] c"str: %s\00", align 1
+@.str.5 = private unnamed_addr constant [4 x i8] c"str\00", align 1
+@.str.6 = private unnamed_addr constant [36 x i8] c"char %c, int %d, string %s, uint %u\00", align 1
+@.str.7 = private unnamed_addr constant [12 x i8] c"%s: int: %d\00", align 1
+@.str.8 = private unnamed_addr constant [5 x i8] c"test\00", align 1
+@.str.9 = private unnamed_addr constant [13 x i8] c"%s: char: %d\00", align 1
+@.str.10 = private unnamed_addr constant [13 x i8] c"%s: uint: %u\00", align 1
+@.str.11 = private unnamed_addr constant [13 x i8] c"%d: char: %d\00", align 1
+@.str.12 = private unnamed_addr constant [5 x i8] c"%s%d\00", align 1
+@.str.13 = private unnamed_addr constant [1 x i8] zeroinitializer, align 1
+
+; CHECK: @str = private unnamed_addr constant [8 x i8] c"char: A\00"
+; CHECK: @str.1 = private unnamed_addr constant [7 x i8] c"int: 5\00"
+; CHECK: @str.2 = private unnamed_addr constant [7 x i8] c"int: 6\00"
+; CHECK: @str.3 = private unnamed_addr constant [8 x i8] c"uint: 7\00"
+; CHECK: @str.4 = private unnamed_addr constant [9 x i8] c"str: str\00"
+; CHECK: @str.5 = private unnamed_addr constant [34 x i8] c"char A, int 5, string str, uint 7\00"
+; CHECK: @str.6 = private unnamed_addr constant [14 x i8] c"test: int: %d\00"
+; CHECK: @str.7 = private unnamed_addr constant [13 x i8] c"%s: char: 65\00"
+; CHECK: @str.8 = private unnamed_addr constant [15 x i8] c"test: uint: %u\00"
+; CHECK: @str.9 = private unnamed_addr constant [12 x i8] c"5: char: %d\00"
+; CHECK: @str.10 = private unnamed_addr constant [3 x i8] c"%d\00"
+; CHECK: @str.11 = private unnamed_addr constant [13 x i8] c"str: str: %s\00"
+
+
+declare i32 @putchar(i32)
+declare i32 @printf(i8* nocapture readonly, ...)
+
+define void @print_const_char() {
+; CHECK-LABEL: @print_const_char(
+; CHECK-NEXT:    [[PRINTF:%.*]] = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([8 x i8], [8 x i8]* @str, i64 0, i64 0))
+; CHECK-NEXT:    ret void
+;
+  %call = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([9 x i8], [9 x i8]* @.str, i32 0, i32 0), i32 65)
+  ret void
+}
+
+define void @print_const_signed() {
+; CHECK-LABEL: @print_const_signed(
+; CHECK-NEXT:    [[PRINTF:%.*]] = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([7 x i8], [7 x i8]* @str.1, i64 0, i64 0))
+; CHECK-NEXT:    ret void
+;
+  %call = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([8 x i8], [8 x i8]* @.str.1, i32 0, i32 0), i32 5)
+  ret void
+}
+
+
+define void @print_const_signed2() {
+; CHECK-LABEL: @print_const_signed2(
+; CHECK-NEXT:    [[PRINTF:%.*]] = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([7 x i8], [7 x i8]* @str.2, i64 0, i64 0))
+; CHECK-NEXT:    ret void
+;
+  %call = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([8 x i8], [8 x i8]* @.str.2, i32 0, i32 0), i32 6)
+  ret void
+}
+
+
+define void @print_const_unsigned() {
+; CHECK-LABEL: @print_const_unsigned(
+; CHECK-NEXT:    [[PRINTF:%.*]] = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([8 x i8], [8 x i8]* @str.3, i64 0, i64 0))
+; CHECK-NEXT:    ret void
+;
+  %call = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([9 x i8], [9 x i8]* @.str.3, i32 0, i32 0), i32 7)
+  ret void
+}
+
+
+define void @print_const_str() {
+; CHECK-LABEL: @print_const_str(
+; CHECK-NEXT:    [[PRINTF:%.*]] = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([9 x i8], [9 x i8]* @str.4, i64 0, i64 0))
+; CHECK-NEXT:    ret void
+;
+  %call = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([8 x i8], [8 x i8]* @.str.4, i32 0, i32 0), i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str.5, i32 0, i32 0))
+  ret void
+}
+
+
+define void @print_all() {
+; CHECK-LABEL: @print_all(
+; CHECK-NEXT:    [[PRINTF:%.*]] = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([34 x i8], [34 x i8]* @str.5, i64 0, i64 0))
+; CHECK-NEXT:    ret void
+;
+  %call = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([36 x i8], [36 x i8]* @.str.6, i32 0, i32 0), i32 65, i32 5, i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str.5, i32 0, i32 0), i32 7)
+  ret void
+}
+
+
+define void @print_partial(i32 %n) {
+; CHECK-LABEL: @print_partial(
+; CHECK-NEXT:    [[PRINTF:%.*]] = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([14 x i8], [14 x i8]* @str.6, i64 0, i64 0))
+; CHECK-NEXT:    ret void
+;
+  %call = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([12 x i8], [12 x i8]* @.str.7, i32 0, i32 0), i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str.8, i32 0, i32 0), i32 %n)
+  ret void
+}
+
+
+define void @print_partial2(i8* %s) {
+; CHECK-LABEL: @print_partial2(
+; CHECK-NEXT:    [[PRINTF:%.*]] = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([13 x i8], [13 x i8]* @str.7, i64 0, i64 0))
+; CHECK-NEXT:    ret void
+;
+  %call = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([13 x i8], [13 x i8]* @.str.9, i32 0, i32 0), i8* %s, i32 65)
+  ret void
+}
+
+
+define void @print_partial3(i32 %n) {
+; CHECK-LABEL: @print_partial3(
+; CHECK-NEXT:    [[PRINTF:%.*]] = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([15 x i8], [15 x i8]* @str.8, i64 0, i64 0))
+; CHECK-NEXT:    ret void
+;
+  %call = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([13 x i8], [13 x i8]* @.str.10, i32 0, i32 0), i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str.8, i32 0, i32 0), i32 %n)
+  ret void
+}
+
+
+define void @print_partial4(i8 signext %c) {
+; CHECK-LABEL: @print_partial4(
+; CHECK-NEXT:    [[PRINTF:%.*]] = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([12 x i8], [12 x i8]* @str.9, i64 0, i64 0))
+; CHECK-NEXT:    ret void
+;
+  %conv = sext i8 %c to i32
+  %call = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([13 x i8], [13 x i8]* @.str.11, i32 0, i32 0), i32 5, i32 %conv)
+  ret void
+}
+
+define void @print_empty_str_signed()  {
+; CHECK-LABEL: @print_empty_str_signed(
+; CHECK-NEXT:    [[PRINTF:%.*]] = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @str.10, i64 0, i64 0))
+; CHECK-NEXT:    ret void
+;
+  %call = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str.12, i64 0, i64 0), i8* getelementptr inbounds ([1 x i8], [1 x i8]* @.str.13, i64 0, i64 0), i32 5)
+  ret void
+}
+
+define void @print_fmt_in_arg() {
+; CHECK-LABEL: @print_fmt_in_arg(
+; CHECK-NEXT:    [[PRINTF:%.*]] = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([13 x i8], [13 x i8]* @str.11, i64 0, i64 0))
+; CHECK-NEXT:    ret void
+;
+  %call = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([8 x i8], [8 x i8]* @.str.4, i32 0, i32 0), i8* getelementptr inbounds ([8 x i8], [8 x i8]* @.str.4, i32 0, i32 0))
+  ret void
+}