[InstCombine] strncmp(x,y,strlen(x|y)+1) -> strcmp(x,y)

[xbolva00]

Summary

Removes redundant strlen call since str(n)cmp does it too.

[xbolva00]

lib/Transforms/Utils/SimplifyLibCalls.cpp

391

Maybe I should extract this matching code for "strlen(x)+ 1" to helper static function now? Or later in followup folds?

[xbolva00]

Added multi-use tests.

[xbolva00]

ping

[xbolva00]

ping

[efriedma]

lib/Transforms/Utils/SimplifyLibCalls.cpp

391

It would be clearer to reorganize this.

I think "Length" is uninitialized along the "else" path? Or am I missing something?

405

It's not enough to check that the Strlen is a call to strlen; you also have to prove the memory isn't modified between the strlen call and the strncmp call.

[xbolva00]

lib/Transforms/Utils/SimplifyLibCalls.cpp

405

Ah yes! I forget about it. :(

I believe such analysis is not worth to do for this pattern.

Closing..

include/llvm/Transforms/Utils/BuildLibCalls.h

Value *emitStrNLen(Value *Ptr, Value *MaxLen, IRBuilder<> &B,
                      const DataLayout &DL, const TargetLibraryInfo *TLI);
 
   /// Emit a call to the strchr function to the builder, for the specified
   /// pointer and character. Ptr is required to be some pointer type, and the
   /// return value has 'i8*' type.
   Value *emitStrChr(Value *Ptr, char C, IRBuilder<> &B,
                     const TargetLibraryInfo *TLI);
 
+  /// Emit a call to the strcmp function to the builder.
+  Value *emitStrCmp(Value *Ptr1, Value *Ptr2, IRBuilder<> &B,
+                    const DataLayout &DL, const TargetLibraryInfo *TLI);
+
   /// Emit a call to the strncmp function to the builder.
   Value *emitStrNCmp(Value *Ptr1, Value *Ptr2, Value *Len, IRBuilder<> &B,
                      const DataLayout &DL, const TargetLibraryInfo *TLI);
 
   /// Emit a call to the strcpy function to the builder, for the specified
   /// pointer arguments.
   Value *emitStrCpy(Value *Dst, Value *Src, IRBuilder<> &B,
                     const TargetLibraryInfo *TLI);

lib/Transforms/Utils/BuildLibCalls.cpp

 Value *llvm::emitStrChr(Value *Ptr, char C, IRBuilder<> &B,
                         const TargetLibraryInfo *TLI) {
   Type *I8Ptr = B.getInt8PtrTy();
   Type *I32Ty = B.getInt32Ty();
   return emitLibCall(LibFunc_strchr, I8Ptr, {I8Ptr, I32Ty},
                      {castToCStr(Ptr, B), ConstantInt::get(I32Ty, C)}, B, TLI);
 }
 
+Value *llvm::emitStrCmp(Value *Ptr1, Value *Ptr2, IRBuilder<> &B,
+                        const DataLayout &DL, const TargetLibraryInfo *TLI) {
+  return emitLibCall(LibFunc_strcmp, B.getInt32Ty(),
+                     {B.getInt8PtrTy(), B.getInt8PtrTy()},
+                     {castToCStr(Ptr1, B), castToCStr(Ptr2, B)}, B, TLI);
+}
+
 Value *llvm::emitStrNCmp(Value *Ptr1, Value *Ptr2, Value *Len, IRBuilder<> &B,
                          const DataLayout &DL, const TargetLibraryInfo *TLI) {
   LLVMContext &Context = B.GetInsertBlock()->getContext();
   return emitLibCall(
       LibFunc_strncmp, B.getInt32Ty(),
       {B.getInt8PtrTy(), B.getInt8PtrTy(), DL.getIntPtrType(Context)},
       {castToCStr(Ptr1, B), castToCStr(Ptr2, B), Len}, B, TLI);
 }

lib/Transforms/Utils/SimplifyLibCalls.cpp

if (canTransformToMemCmp(CI, Str2P, Len1, DL))
           TLI);
   }
 
   return nullptr;
 }
 
 Value *LibCallSimplifier::optimizeStrNCmp(CallInst *CI, IRBuilder<> &B) {
   Value *Str1P = CI->getArgOperand(0), *Str2P = CI->getArgOperand(1);
+  Value *Len = CI->getArgOperand(2);
   if (Str1P == Str2P) // strncmp(x,x,n)  -> 0
     return ConstantInt::get(CI->getType(), 0);
 
   // Get the length argument if it is constant.
   uint64_t Length;
-  if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getArgOperand(2)))
+  if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(Len)) {
     Length = LengthArg->getZExtValue();
-  else
+  } else {
+    // strncmp(x,y,strlen(x|y)+1) -> strcmp(x,y)
+    Value *Call;
+    if (match(Len, m_Add(m_Value(Call), m_One()))) {
+      auto *Strlen = dyn_cast<CallInst>(Call);
+      if (!Strlen)
+        return nullptr;
+
+      // Is the inner call strlen()?
+      Function *InnerCallee = Strlen->getCalledFunction();
+      if (!InnerCallee)
         return nullptr;
 
+      LibFunc Func;
+      if (!TLI->getLibFunc(*InnerCallee, Func) || !TLI->has(Func) ||
+          Func != LibFunc_strlen)
+        return nullptr;
+
+      auto *StrlenStr = Strlen->getOperand(0);
+      if (StrlenStr != Str1P && StrlenStr != Str2P)
+        return nullptr;
+
+      return emitStrCmp(Str1P, Str2P, B, DL, TLI);
+    }
+  }
+
   if (Length == 0) // strncmp(x,y,0)   -> 0
     return ConstantInt::get(CI->getType(), 0);
 
   if (Length == 1) // strncmp(x,y,1) -> memcmp(x,y,1)
-    return emitMemCmp(Str1P, Str2P, CI->getArgOperand(2), B, DL, TLI);
+    return emitMemCmp(Str1P, Str2P, Len, B, DL, TLI);
 
   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) {
     StringRef SubStr1 = Str1.substr(0, Length);

test/Transforms/InstCombine/strncmp-strlen.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; Test that the strncmp library call simplifier works correctly.
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+declare i32 @strncmp(i8* nocapture, i8* nocapture, i64)
+declare i64 @strlen(i8* nocapture)
+declare void @extra_use(i64)
+
+define i32 @strncmp_strlen(i8* %s, i8* %k) {
+; CHECK-LABEL: @strncmp_strlen(
+; CHECK-NEXT:    [[STRCMP:%.*]] = call i32 @strcmp(i8* [[S:%.*]], i8* [[K:%.*]])
+; CHECK-NEXT:    ret i32 [[STRCMP]]
+;
+  %len = tail call i64 @strlen(i8* %s)
+  %len1 = add i64 %len, 1
+  %r = tail call i32 @strncmp(i8* %s, i8* %k, i64 %len1)
+  ret i32 %r
+}
+
+define i32 @strncmp_strlen2(i8* %s, i8* %k) {
+; CHECK-LABEL: @strncmp_strlen2(
+; CHECK-NEXT:    [[STRCMP:%.*]] = call i32 @strcmp(i8* [[S:%.*]], i8* [[K:%.*]])
+; CHECK-NEXT:    ret i32 [[STRCMP]]
+;
+  %len = tail call i64 @strlen(i8* %k)
+  %len1 = add i64 %len, 1
+  %r = tail call i32 @strncmp(i8* %s, i8* %k, i64 %len1)
+  ret i32 %r
+}
+
+define i32 @strncmp_strlen_multiuse(i8* %s, i8* %k) {
+; CHECK-LABEL: @strncmp_strlen_multiuse(
+; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @strlen(i8* [[S:%.*]])
+; CHECK-NEXT:    call void @extra_use(i64 [[LEN]])
+; CHECK-NEXT:    [[STRCMP:%.*]] = call i32 @strcmp(i8* [[S]], i8* [[K:%.*]])
+; CHECK-NEXT:    ret i32 [[STRCMP]]
+;
+  %len = tail call i64 @strlen(i8* %s)
+  call void @extra_use(i64 %len)
+  %len1 = add i64 %len, 1
+  %r = tail call i32 @strncmp(i8* %s, i8* %k, i64 %len1)
+  ret i32 %r
+}
+
+define i32 @strncmp_strlen_multiuse2(i8* %s, i8* %k) {
+; CHECK-LABEL: @strncmp_strlen_multiuse2(
+; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @strlen(i8* [[S:%.*]])
+; CHECK-NEXT:    [[LEN1:%.*]] = add i64 [[LEN]], 1
+; CHECK-NEXT:    call void @extra_use(i64 [[LEN1]])
+; CHECK-NEXT:    [[STRCMP:%.*]] = call i32 @strcmp(i8* [[S]], i8* [[K:%.*]])
+; CHECK-NEXT:    ret i32 [[STRCMP]]
+;
+  %len = tail call i64 @strlen(i8* %s)
+  %len1 = add i64 %len, 1
+  call void @extra_use(i64 %len1)
+  %r = tail call i32 @strncmp(i8* %s, i8* %k, i64 %len1)
+  ret i32 %r
+}
+
+; Negative tests
+
+define i32 @strncmp_strlen_neg1(i8* %s, i8* %k) {
+; CHECK-LABEL: @strncmp_strlen_neg1(
+; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @strlen(i8* [[S:%.*]])
+; CHECK-NEXT:    [[R:%.*]] = tail call i32 @strncmp(i8* [[S]], i8* [[K:%.*]], i64 [[LEN]])
+; CHECK-NEXT:    ret i32 [[R]]
+;
+  %len = tail call i64 @strlen(i8* %s)
+  %r = tail call i32 @strncmp(i8* %s, i8* %k, i64 %len)
+  ret i32 %r
+}
+
+define i32 @strncmp_strlen_neg2(i8* %s, i8* %k) {
+; CHECK-LABEL: @strncmp_strlen_neg2(
+; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @strlen(i8* [[S:%.*]])
+; CHECK-NEXT:    [[LEN1:%.*]] = add i64 [[LEN]], 2
+; CHECK-NEXT:    [[R:%.*]] = tail call i32 @strncmp(i8* [[S]], i8* [[K:%.*]], i64 [[LEN1]])
+; CHECK-NEXT:    ret i32 [[R]]
+;
+  %len = tail call i64 @strlen(i8* %s)
+  %len1 = add i64 %len, 2
+  %r = tail call i32 @strncmp(i8* %s, i8* %k, i64 %len1)
+  ret i32 %r
+}
+
+define i32 @strncmp_strlen_neg3(i8* %s, i8* %k, i8* %d) {
+; CHECK-LABEL: @strncmp_strlen_neg3(
+; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @strlen(i8* [[D:%.*]])
+; CHECK-NEXT:    [[LEN1:%.*]] = add i64 [[LEN]], 1
+; CHECK-NEXT:    [[R:%.*]] = tail call i32 @strncmp(i8* [[S:%.*]], i8* [[K:%.*]], i64 [[LEN1]])
+; CHECK-NEXT:    ret i32 [[R]]
+;
+  %len = tail call i64 @strlen(i8* %d)
+  %len1 = add i64 %len, 1
+  %r = tail call i32 @strncmp(i8* %s, i8* %k, i64 %len1)
+  ret i32 %r
+}