[InstCombine] Fold strnlen with a bound of zero and one.

[msebor]

Summary

This patch in the strnlen series implements folding of calls with a bound of either zero or one.

Depends on D123815.

[nikic]

llvm/include/llvm/Transforms/Utils/SimplifyLibCalls.h

242

nit: Indent not aligned.

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

649

Isn't this select the wrong way around? You're doing *s != 0 ? 0 : 1 here.

You might also want to directly emit the zext form if InstCombine is going to fold it anyway, so that would be zext(s != 0).

[msebor]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

649

Yes, it is backwards. Good catch! The test is wrong too. I was worried about something like this happening after checking in the baseline tests first and then relying on update_test_checks.py to update the assertions.

[msebor]

Fix logic error and use zext instead of select.

[nikic]

llvm/test/Transforms/InstCombine/strnlen-2.ll

92

Hm, how does this one get folded? It doesn't have either 0 or 1 as the bound.

[msebor]

llvm/test/Transforms/InstCombine/strnlen-2.ll

92

This is strnlen(C ? "123" : "12345", 6). (I use sN for a constant string of length N and aN for a non-const array of N elements.)

[nikic]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

648

This should be B., causes the build failure in pre-merge checks.

llvm/test/Transforms/InstCombine/strnlen-2.ll

92

I still don't see how this one would get folded as part of this patch. Are you sure it's not from one of the later patches?

[msebor]

Fix merge problems.

[msebor]

llvm/test/Transforms/InstCombine/strnlen-2.ll

92

Yes, I screwed up the merge. I'm not used to working this way. I'm spending more time moving code around than actually developing it, and making mistakes in the process.

[nikic]

LGTM

llvm/include/llvm/Transforms/Utils/SimplifyLibCalls.h

private:
   Value *optimizeSPrintFString(CallInst *CI, IRBuilderBase &B);
   Value *optimizeSnPrintFString(CallInst *CI, IRBuilderBase &B);
   Value *optimizeFPrintFString(CallInst *CI, IRBuilderBase &B);
 
   /// hasFloatVersion - Checks if there is a float version of the specified
   /// function by checking for an existing function with name FuncName + f
   bool hasFloatVersion(StringRef FuncName);
 
-  /// Shared code to optimize strlen+wcslen.
-  Value *optimizeStringLength(CallInst *CI, IRBuilderBase &B, unsigned CharSize);
+  /// Shared code to optimize strlen+wcslen and strnlen+wcsnlen.
+  Value *optimizeStringLength(CallInst *CI, IRBuilderBase &B, unsigned CharSize,
+                              Value *Bound = nullptr);
 };
 } // End llvm namespace
 
 #endif

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

CallInst *NewCI = B.CreateMemCpy(Dst, Align(1), Src, Align(1),
                                    ConstantInt::get(DL.getIntPtrType(PT), Len));
   NewCI->setAttributes(CI->getAttributes());
   NewCI->removeRetAttrs(AttributeFuncs::typeIncompatible(NewCI->getType()));
   copyFlags(*CI, NewCI);
   return Dst;
 }
 
 Value *LibCallSimplifier::optimizeStringLength(CallInst *CI, IRBuilderBase &B,
-                                               unsigned CharSize) {
+                                               unsigned CharSize,
+                                               Value *Bound) {
   Value *Src = CI->getArgOperand(0);
 
+  if (Bound) {
+    if (ConstantInt *BoundCst = dyn_cast<ConstantInt>(Bound)) {
+      if (BoundCst->isZero())
+        // Fold strnlen(s, 0) -> 0 for any s, constant or otherwise.
+        return ConstantInt::get(CI->getType(), 0);
+
+      if (BoundCst->isOne()) {
+        // Fold strnlen(s, 1) -> *s ? 1 : 0 for any s.
+        Type *CharTy = B.getIntNTy(CharSize);
+        Value *CharVal = B.CreateLoad(CharTy, Src, "strnlen.char0");
+        Value *ZeroChar = ConstantInt::get(CharTy, 0);
+        Value *Cmp = B.CreateICmpNE(CharVal, ZeroChar, "strnlen.char0cmp");
+        return B->CreateZExt(Cmp, CI->getType());
+      }
+    }
+    // Otherwise punt for strnlen for now.
+    return nullptr;
+  }
+
   // Constant folding: strlen("xyz") -> 3
   if (uint64_t Len = GetStringLength(Src, CharSize))
     return ConstantInt::get(CI->getType(), Len - 1);
 
   // If s is a constant pointer pointing to a string literal, we can fold
   // strlen(s + x) to strlen(s) - x, when x is known to be in the range
   // [0, strlen(s)] or the string has a single null terminator '\0' at the end.
   // We only try to simplify strlen when the pointer s points to an array
Value *LibCallSimplifier::optimizeStrLen(CallInst *CI, IRBuilderBase &B) {
   if (Value *V = optimizeStringLength(CI, B, 8))
     return V;
   annotateNonNullNoUndefBasedOnAccess(CI, 0);
   return nullptr;
 }
 
 Value *LibCallSimplifier::optimizeStrNLen(CallInst *CI, IRBuilderBase &B) {
   Value *Bound = CI->getArgOperand(1);
+  if (Value *V = optimizeStringLength(CI, B, 8, Bound))
+    return V;
+
   if (isKnownNonZero(Bound, DL))
     annotateNonNullNoUndefBasedOnAccess(CI, 0);
   return nullptr;
 }
 
 Value *LibCallSimplifier::optimizeWcslen(CallInst *CI, IRBuilderBase &B) {
   Module &M = *CI->getModule();
   unsigned WCharSize = TLI->getWCharSize(M) * 8;

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; Verify that strnlen calls with constant string arguments and offsets
 ; and constant bounds are folded correctly.
 ;
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 declare i64 @strnlen(i8*, i64)
 
+@ax = external global [0 x i8]
 @s5 = constant [6 x i8] c"12345\00"
 @s5_3 = constant [9 x i8] c"12345\00xyz"
 
 
 ; Verify that the strnlen pointer argument is not annotated nonnull when
 ; nothing is known about the bound.
 
 define i64 @no_access_strnlen_p_n(i8* %ptr, i64 %n) {

 ; CHECK-NEXT:    ret i64 [[LEN]]
 ;
   %nnz = or i64 %n, 1
   %len = call i64 @strnlen(i8* noundef nonnull dereferenceable(1) %ptr, i64 %nnz)
   ret i64 %len
 }
 
 
+; Fold strnlen(ax, 0) to 0.
+
+define i64 @fold_strnlen_ax_0() {
+; CHECK-LABEL: @fold_strnlen_ax_0(
+; CHECK-NEXT:    ret i64 0
+;
+  %ptr = getelementptr [0 x i8], [0 x i8]* @ax, i32 0, i32 0
+  %len = call i64 @strnlen(i8* %ptr, i64 0)
+  ret i64 %len
+}
+
+
+; Fold strnlen(ax, 1) to *ax ? 1 : 0.
+
+define i64 @fold_strnlen_ax_1() {
+; CHECK-LABEL: @fold_strnlen_ax_1(
+; CHECK-NEXT:    [[STRNLEN_CHAR0:%.*]] = load i8, i8* getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), align 1
+; CHECK-NEXT:    [[STRNLEN_CHAR0CMP_NOT:%.*]] = icmp ne i8 [[STRNLEN_CHAR0]], 0
+; CHECK-NEXT:    [[STRNLEN_SEL:%.*]] = zext i1 [[STRNLEN_CHAR0CMP_NOT]] to i64
+; CHECK-NEXT:    ret i64 [[STRNLEN_SEL]]
+;
+  %ptr = getelementptr [0 x i8], [0 x i8]* @ax, i32 0, i32 0
+  %len = call i64 @strnlen(i8* %ptr, i64 1)
+  ret i64 %len
+}
+
+
 ; Fold strnlen(s5, 0) to 0.
 
 define i64 @fold_strnlen_s5_0() {
 ; CHECK-LABEL: @fold_strnlen_s5_0(
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* getelementptr inbounds ([6 x i8], [6 x i8]* @s5, i64 0, i64 0), i64 0)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 0
 ;
   %ptr = getelementptr [6 x i8], [6 x i8]* @s5, i32 0, i32 0
   %len = call i64 @strnlen(i8* %ptr, i64 0)
   ret i64 %len
 }
 
 
 ; Fold strnlen(s5, 4) to 4.

llvm/test/Transforms/InstCombine/strnlen-2.ll

 @s6 = constant [7 x i8] c"123456\00"
 @s7 = constant [8 x i8] c"1234567\00"
 
 
 ; Fold strnlen (C ? s3 : s5, 0) to 0.
 
 define i64 @fold_strnlen_s3_s5_0(i1 %C) {
 ; CHECK-LABEL: @fold_strnlen_s3_s5_0(
-; CHECK-NEXT:    [[PTR:%.*]] = select i1 [[C:%.*]], i8* getelementptr inbounds ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* getelementptr inbounds ([7 x i8], [7 x i8]* @s6, i64 0, i64 0)
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* [[PTR]], i64 0)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 0
 ;
   %ptr = select i1 %C, i8* getelementptr ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* getelementptr ([7 x i8], [7 x i8]* @s6, i64 0, i64 0)
 
   %len = call i64 @strnlen(i8* %ptr, i64 0)
   ret i64 %len
 }
 
 
 ; Fold strnlen (C ? s3 : s5, 1) to 1.
 
 define i64 @fold_strnlen_s3_s5_1(i1 %C) {
 ; CHECK-LABEL: @fold_strnlen_s3_s5_1(
-; CHECK-NEXT:    [[PTR:%.*]] = select i1 [[C:%.*]], i8* getelementptr inbounds ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* getelementptr inbounds ([7 x i8], [7 x i8]* @s6, i64 0, i64 0)
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* noundef nonnull dereferenceable(1) [[PTR]], i64 1)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 1
 ;
   %ptr = select i1 %C, i8* getelementptr ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i8* getelementptr ([7 x i8], [7 x i8]* @s6, i64 0, i64 0)
 
   %len = call i64 @strnlen(i8* %ptr, i64 1)
   ret i64 %len
 }
 
 
;
   ret i64 %len
 }
 
 
 ; Fold strnlen (C ? s3 : s5, 6) to C ? 3 : 5.
 
 define i64 @fold_strnlen_s5_6(i1 %C) {
 ; CHECK-LABEL: @fold_strnlen_s5_6(
-; CHECK-NEXT:    [[PTR:%.*]] = select i1 [[C:%.*]], i8* getelementptr inbounds ([6 x i8], [6 x i8]* @s5, i64 0, i64 0), i8* getelementptr inbounds ([7 x i8], [7 x i8]* @s6, i64 0, i64 0)
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* noundef nonnull dereferenceable(1) [[PTR]], i64 6)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[C:%.*]], i64 3, i64 5
+; CHECK-NEXT:    ret i64 [[TMP1]]
 ;
 
   %ptr = select i1 %C, i8* getelementptr ([6 x i8], [6 x i8]* @s5, i64 0, i64 0), i8* getelementptr ([7 x i8], [7 x i8]* @s6, i64 0, i64 0)
 
   %len = call i64 @strnlen(i8* %ptr, i64 6)
   ret i64 %len
 }
 

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

 @s5 = constant [6 x i8] c"12345\00"
 @s5_3 = constant [10 x i8] c"12345\00abc\00"
 
 
 ; Fold strnlen(sx + i, 0) to 0.
 
 define i64 @fold_strnlen_sx_pi_0(i64 %i) {
 ; CHECK-LABEL: @fold_strnlen_sx_pi_0(
-; CHECK-NEXT:    [[PTR:%.*]] = getelementptr [0 x i8], [0 x i8]* @sx, i64 0, i64 [[I:%.*]]
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* [[PTR]], i64 0)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 0
 ;
 
   %ptr = getelementptr [0 x i8], [0 x i8]* @sx, i64 0, i64 %i
   %len = call i64 @strnlen(i8* %ptr, i64 0)
   ret i64 %len
 }
 
 
;
   ret i64 %len
 }
 
 
 ; Fold strnlen(s3 + i, 0) to 0.
 
 define i64 @fold_strnlen_s3_pi_0(i64 %i) {
 ; CHECK-LABEL: @fold_strnlen_s3_pi_0(
-; CHECK-NEXT:    [[PTR:%.*]] = getelementptr inbounds [4 x i8], [4 x i8]* @s3, i64 0, i64 [[I:%.*]]
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* nonnull [[PTR]], i64 0)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 0
 ;
   %ptr = getelementptr inbounds [4 x i8], [4 x i8]* @s3, i64 0, i64 %i
   %len = call i64 @strnlen(i8* %ptr, i64 0)
   ret i64 %len
 }
 
 
 ; Fold strnlen(s5 + i, 0) to 0.
 
 define i64 @call_strnlen_s5_pi_0(i64 zeroext %i) {
 ; CHECK-LABEL: @call_strnlen_s5_pi_0(
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* getelementptr inbounds ([6 x i8], [6 x i8]* @s5, i64 0, i64 0), i64 0)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 0
 ;
   %ptr = getelementptr [6 x i8], [6 x i8]* @s5, i32 0, i32 0
   %len = call i64 @strnlen(i8* %ptr, i64 0)
   ret i64 %len
 }
 
 
 ; Fold strnlen(s5_3 + i, 0) to 0.
 
 define i64 @fold_strnlen_s5_3_pi_0(i64 zeroext %i) {
 ; CHECK-LABEL: @fold_strnlen_s5_3_pi_0(
-; CHECK-NEXT:    [[PTR:%.*]] = getelementptr [10 x i8], [10 x i8]* @s5_3, i64 0, i64 [[I:%.*]]
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* [[PTR]], i64 0)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 0
 ;
   %ptr = getelementptr [10 x i8], [10 x i8]* @s5_3, i32 0, i64 %i
   %len = call i64 @strnlen(i8* %ptr, i64 0)
   ret i64 %len
 }
 
 
 ; Do not fold strnlen(s5_3 + i, n).

llvm/test/Transforms/InstCombine/strnlen-5.ll

 @a5 = external global [5 x i8]
 @s5 = constant [6 x i8] c"12345\00"
 
 
 ; Fold strnlen(ax, 0) == 0 to true.
 
 define i1 @fold_strnlen_ax_0_eqz() {
 ; CHECK-LABEL: @fold_strnlen_ax_0_eqz(
-; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @strnlen(i8* getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), i64 0)
-; CHECK-NEXT:    [[EQZ:%.*]] = icmp eq i64 [[LEN]], 0
-; CHECK-NEXT:    ret i1 [[EQZ]]
+; CHECK-NEXT:    ret i1 true
 ;
 
   %ptr = getelementptr [0 x i8], [0 x i8]* @ax, i64 0, i64 0
   %len = tail call i64 @strnlen(i8* %ptr, i64 0)
   %eqz = icmp eq i64 %len, 0
   ret i1 %eqz
 }
 
 
 ; Fold strnlen(ax, 0) > 0 to false.
 
 define i1 @fold_strnlen_ax_0_gtz() {
 ; CHECK-LABEL: @fold_strnlen_ax_0_gtz(
-; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @strnlen(i8* getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), i64 0)
-; CHECK-NEXT:    [[GTZ:%.*]] = icmp ne i64 [[LEN]], 0
-; CHECK-NEXT:    ret i1 [[GTZ]]
+; CHECK-NEXT:    ret i1 false
 ;
 
   %ptr = getelementptr [0 x i8], [0 x i8]* @ax, i64 0, i64 0
   %len = tail call i64 @strnlen(i8* %ptr, i64 0)
   %gtz = icmp ugt i64 %len, 0
   ret i1 %gtz
 }
 
 
 ; Fold strnlen(ax, 1) == 0 to *ax == 0.
 
 define i1 @fold_strnlen_ax_1_eqz() {
 ; CHECK-LABEL: @fold_strnlen_ax_1_eqz(
-; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @strnlen(i8* noundef nonnull dereferenceable(1) getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), i64 1)
-; CHECK-NEXT:    [[EQZ:%.*]] = icmp eq i64 [[LEN]], 0
-; CHECK-NEXT:    ret i1 [[EQZ]]
+; CHECK-NEXT:    [[STRNLEN_CHAR0:%.*]] = load i8, i8* getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), align 1
+; CHECK-NEXT:    [[STRNLEN_CHAR0CMP_NOT:%.*]] = icmp ne i8 [[STRNLEN_CHAR0]], 0
+; CHECK-NEXT:    ret i1 [[STRNLEN_CHAR0CMP_NOT]]
 ;
 
   %ptr = getelementptr [0 x i8], [0 x i8]* @ax, i64 0, i64 0
   %len = tail call i64 @strnlen(i8* %ptr, i64 1)
   %eqz = icmp eq i64 %len, 0
   ret i1 %eqz
 }
 
 
 ; Fold strnlen(ax, 1) != 0 to *ax != 0.
 
 define i1 @fold_strnlen_ax_1_neqz() {
 ; CHECK-LABEL: @fold_strnlen_ax_1_neqz(
-; CHECK-NEXT:    [[LEN:%.*]] = tail call i64 @strnlen(i8* noundef nonnull dereferenceable(1) getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), i64 1)
-; CHECK-NEXT:    [[NEZ:%.*]] = icmp ne i64 [[LEN]], 0
-; CHECK-NEXT:    ret i1 [[NEZ]]
+; CHECK-NEXT:    [[STRNLEN_CHAR0:%.*]] = load i8, i8* getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), align 1
+; CHECK-NEXT:    [[STRNLEN_CHAR0CMP_NOT:%.*]] = icmp eq i8 [[STRNLEN_CHAR0]], 0
+; CHECK-NEXT:    ret i1 [[STRNLEN_CHAR0CMP_NOT]]
 ;
 
   %ptr = getelementptr [0 x i8], [0 x i8]* @ax, i64 0, i64 0
   %len = tail call i64 @strnlen(i8* %ptr, i64 1)
   %nez = icmp ne i64 %len, 0
   ret i1 %nez
 }