[InstCombine] Fold strnlen of constant strings.

[msebor]

Summary

This patch in the strnlen series implements folding of calls with constant string arguments.

Depends on D123816.

[nikic]

LG

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

654

The Min name doesn't really make sense to me here -- if anything, this is a max. I'd call this LenC or maybe LenWithoutNull to highlight where the -1 comes from.

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

Value *LibCallSimplifier::optimizeStrNCpy(CallInst *CI, IRBuilderBase &B) {
   copyFlags(*CI, NewCI);
   return Dst;
 }
 
 Value *LibCallSimplifier::optimizeStringLength(CallInst *CI, IRBuilderBase &B,
                                                unsigned CharSize,
                                                Value *Bound) {
   Value *Src = CI->getArgOperand(0);
+  Type *CharTy = B.getIntNTy(CharSize);
 
   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 (uint64_t Len = GetStringLength(Src, CharSize)) {
+    Value *LenC = ConstantInt::get(CI->getType(), Len - 1);
+    // Fold strlen("xyz") -> 3 and strnlen("xyz", 2) -> 2
+    // and strnlen("xyz", Bound) -> min(3, Bound) for nonconstant Bound.
+    if (Bound)
+      return B.CreateBinaryIntrinsic(Intrinsic::umin, LenC, Bound);
+    return LenC;
+  }
+
+  if (Bound)
+    // Punt for strnlen for now.
+    return nullptr;
 
   // 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
   // of i8. Otherwise, we would need to scale the offset x before doing the
   // subtraction. This will make the optimization more complex, and it's not
   // very useful because calling strlen for a pointer of other types is

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

;
   ret i64 %len
 }
 
 
 ; Fold strnlen(s5, 4) to 4.
 
 define i64 @fold_strnlen_s5_4() {
 ; CHECK-LABEL: @fold_strnlen_s5_4(
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* noundef nonnull dereferenceable(1) getelementptr inbounds ([6 x i8], [6 x i8]* @s5, i64 0, i64 0), i64 4)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 4
 ;
   %ptr = getelementptr [6 x i8], [6 x i8]* @s5, i32 0, i32 0
   %len = call i64 @strnlen(i8* %ptr, i64 4)
   ret i64 %len
 }
 
 
 ; Fold strnlen(s5, 5) to 5.
 
 define i64 @fold_strnlen_s5_5() {
 ; CHECK-LABEL: @fold_strnlen_s5_5(
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* noundef nonnull dereferenceable(1) getelementptr inbounds ([6 x i8], [6 x i8]* @s5, i64 0, i64 0), i64 5)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 5
 ;
   %ptr = getelementptr [6 x i8], [6 x i8]* @s5, i32 0, i32 0
   %len = call i64 @strnlen(i8* %ptr, i64 5)
   ret i64 %len
 }
 
 
 ; Fold strnlen(s5, (size_t)-1) to 5.
 
 define i64 @fold_strnlen_s5_m1() {
 ; CHECK-LABEL: @fold_strnlen_s5_m1(
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* noundef nonnull dereferenceable(1) getelementptr inbounds ([6 x i8], [6 x i8]* @s5, i64 0, i64 0), i64 -1)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 5
 ;
   %ptr = getelementptr [6 x i8], [6 x i8]* @s5, i32 0, i32 0
   %len = call i64 @strnlen(i8* %ptr, i64 -1)
   ret i64 %len
 }
 
 
 ; Fold strnlen(s5_3 + 4, 5) to 1.
 
 define i64 @fold_strnlen_s5_3_p4_5() {
 ; CHECK-LABEL: @fold_strnlen_s5_3_p4_5(
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* noundef nonnull dereferenceable(1) getelementptr inbounds ([9 x i8], [9 x i8]* @s5_3, i64 0, i64 4), i64 5)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 1
 ;
   %ptr = getelementptr [9 x i8], [9 x i8]* @s5_3, i32 0, i32 4
   %len = call i64 @strnlen(i8* %ptr, i64 5)
   ret i64 %len
 }
 
 
-; Fold strnlen(s5_3 + 5, 5) to 1.
+; Fold strnlen(s5_3 + 5, 5) to 0.
 
 define i64 @fold_strnlen_s5_3_p5_5() {
 ; CHECK-LABEL: @fold_strnlen_s5_3_p5_5(
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* noundef nonnull dereferenceable(1) getelementptr inbounds ([9 x i8], [9 x i8]* @s5_3, i64 0, i64 5), i64 5)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 0
 ;
   %ptr = getelementptr [9 x i8], [9 x i8]* @s5_3, i32 0, i32 5
   %len = call i64 @strnlen(i8* %ptr, i64 5)
   ret i64 %len
 }
 
 
 ; Fold strnlen(s5_3 + 6, 5) to 3.
 
 define i64 @fold_strnlen_s5_3_p6_5() {
 ; CHECK-LABEL: @fold_strnlen_s5_3_p6_5(
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* noundef nonnull dereferenceable(1) getelementptr inbounds ([9 x i8], [9 x i8]* @s5_3, i64 0, i64 6), i64 5)
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 3
 ;
   %ptr = getelementptr [9 x i8], [9 x i8]* @s5_3, i32 0, i32 6
   %len = call i64 @strnlen(i8* %ptr, i64 5)
   ret i64 %len
 }

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

;
   ret i64 %len
 }
 
 
 ; Fold strnlen(a3, n) to min(sizeof(a3), n)
 
 define i64 @fold_strnlen_a3_n(i64 %n) {
 ; CHECK-LABEL: @fold_strnlen_a3_n(
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @a3, i64 0, i64 0), i64 [[N:%.*]])
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i64 @llvm.umin.i64(i64 [[N:%.*]], i64 3)
+; CHECK-NEXT:    ret i64 [[TMP1]]
 ;
 
   %ptr = getelementptr [3 x i8], [3 x i8]* @a3, i64 0, i64 0
   %len = call i64 @strnlen(i8* %ptr, i64 %n)
   ret i64 %len
 }
 
 
 ; Fold strnlen(s3, n) to min(strlen(s3), n)
 
 define i64 @fold_strnlen_s3_n(i64 %n) {
 ; CHECK-LABEL: @fold_strnlen_s3_n(
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @s3, i64 0, i64 0), i64 [[N:%.*]])
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i64 @llvm.umin.i64(i64 [[N:%.*]], i64 3)
+; CHECK-NEXT:    ret i64 [[TMP1]]
 ;
 
   %ptr = getelementptr [4 x i8], [4 x i8]* @s3, i64 0, i64 0
   %len = call i64 @strnlen(i8* %ptr, i64 %n)
   ret i64 %len
 }