[InstCombine] Fold strnlen calls in equality to zero.

[msebor]

Summary

This patch in the strnlen series adds folding of calls used in equality expressions with zero.

Depends on D123817.

[xbolva00]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

648

maybe you can drop “strlenfirst” here..

[xbolva00]

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

42

What about “strnlen(…) < 1” ? Do we have such test?

[msebor]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

648

Because the function also handles strnlen besides strlen? I can do that but since other loads in the file are annotated I've changed it to "char0". Let me know if I misunderstood.

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

42

I've added a couple. I expected isOnlyUsedInZeroEqualityComparison() to return true for such expressions but it only handles straight equality. The case is folded by the subsequent code path but the emitted code is slightly different. It seems it might be worth looking into enhancing the function to handle both < 1 and == 0 with unsigned operands (as well as the converse).

[xbolva00]

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

42

No need as < 1 is always canonicalized to == 0.

[nikic]

LG -- the current baseline checks are outdated and a bit confusing for that reason, but otherwise this looks right.

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

648

Looks like this rename did not happen (though I don't really care either way).

[msebor]

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

648

It did, I just haven't posted the updated patch yet. Now that it's been accepted I'll go ahead and commit it with this change.

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

42

Yes, ultimately it is, but it seems to me that it would be helpful to follow the same code path and make the same folding decisions earlier on, in the libcall handler. I don't have a use case for it yet where it would make a difference (the function isn't widely used) but if one comes up I'll revisit it then,

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

 }
 
 Value *LibCallSimplifier::optimizeStringLength(CallInst *CI, IRBuilderBase &B,
                                                unsigned CharSize,
                                                Value *Bound) {
   Value *Src = CI->getArgOperand(0);
   Type *CharTy = B.getIntNTy(CharSize);
 
+  if (isOnlyUsedInZeroEqualityComparison(CI) &&
+      (!Bound || isKnownNonZero(Bound, DL))) {
+    // Fold strlen:
+    //   strlen(x) != 0 --> *x != 0
+    //   strlen(x) == 0 --> *x == 0
+    // and likewise strnlen with constant N > 0:
+    //   strnlen(x, N) != 0 --> *x != 0
+    //   strnlen(x, N) == 0 --> *x == 0
+    return B.CreateZExt(B.CreateLoad(CharTy, Src, "char0"),
+                        CI->getType());
+  }
+
   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.
if (LenTrue && LenFalse) {
                << "folded strlen(select) to select of constants";
       });
       return B.CreateSelect(SI->getCondition(),
                             ConstantInt::get(CI->getType(), LenTrue - 1),
                             ConstantInt::get(CI->getType(), LenFalse - 1));
     }
   }
 
-  // strlen(x) != 0 --> *x != 0
-  // strlen(x) == 0 --> *x == 0
-  if (isOnlyUsedInZeroEqualityComparison(CI))
-    return B.CreateZExt(B.CreateLoad(B.getIntNTy(CharSize), Src, "strlenfirst"),
-                        CI->getType());
-
   return nullptr;
 }
 
 Value *LibCallSimplifier::optimizeStrLen(CallInst *CI, IRBuilderBase &B) {
   if (Value *V = optimizeStringLength(CI, B, 8))
     return V;
   annotateNonNullNoUndefBasedOnAccess(CI, 0);
   return nullptr;

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

;
 
   %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:    [[CHAR0:%.*]] = load i8, i8* getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), align 1
+; CHECK-NEXT:    [[EQZ:%.*]] = icmp eq i8 [[CHAR0]], 0
+; CHECK-NEXT:    ret i1 [[EQZ]]
+;
+
+  %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
+}
+
+
+; Likewise, fold strnlen(ax, 1) < 1 to *ax == 0.
+
+define i1 @fold_strnlen_ax_1_lt1() {
+; CHECK-LABEL: @fold_strnlen_ax_1_lt1(
 ; 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)
-  %eqz = icmp eq i64 %len, 0
-  ret i1 %eqz
+  %nez = icmp ult i64 %len, 1
+  ret i1 %nez
 }
 
 
 ; Fold strnlen(ax, 1) != 0 to *ax != 0.
 
 define i1 @fold_strnlen_ax_1_neqz() {
 ; CHECK-LABEL: @fold_strnlen_ax_1_neqz(
+; CHECK-NEXT:    [[CHAR0:%.*]] = load i8, i8* getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), align 1
+; CHECK-NEXT:    [[NEZ:%.*]] = icmp ne i8 [[CHAR0]], 0
+; CHECK-NEXT:    ret i1 [[NEZ]]
+;
+
+  %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
+}
+
+
+; Likewise, fold strnlen(ax, 1) > 0 to *ax != 0.
+
+define i1 @fold_strnlen_ax_1_gtz() {
+; CHECK-LABEL: @fold_strnlen_ax_1_gtz(
 ; 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:%.*]] = icmp ne i8 [[STRNLEN_CHAR0]], 0
 ; CHECK-NEXT:    ret i1 [[STRNLEN_CHAR0CMP]]
 ;
 
   %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
+  %nez = icmp ugt i64 %len, 0
   ret i1 %nez
 }
 
 
 ; Fold strnlen(ax, 9) == 0 to *ax == 0.
 
 define i1 @fold_strnlen_ax_9_eqz() {
 ; CHECK-LABEL: @fold_strnlen_ax_9_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 9)
-; CHECK-NEXT:    [[EQZ:%.*]] = icmp eq i64 [[LEN]], 0
+; CHECK-NEXT:    [[CHAR0:%.*]] = load i8, i8* getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), align 1
+; CHECK-NEXT:    [[EQZ:%.*]] = icmp eq i8 [[CHAR0]], 0
 ; CHECK-NEXT:    ret i1 [[EQZ]]
 ;
 
   %ptr = getelementptr [0 x i8], [0 x i8]* @ax, i64 0, i64 0
   %len = tail call i64 @strnlen(i8* %ptr, i64 9)
   %eqz = icmp eq i64 %len, 0
   ret i1 %eqz
 }
;
   ret i1 %eqz
 }
 
 
 ; Fold strnlen(ax, n) == 0 to *ax == 0 for %0 that's not zero.
 
 define i1 @fold_strnlen_ax_nz_eqz(i64 %n) {
 ; CHECK-LABEL: @fold_strnlen_ax_nz_eqz(
-; CHECK-NEXT:    [[MAX:%.*]] = or i64 [[N:%.*]], 1
-; 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 [[MAX]])
-; CHECK-NEXT:    [[EQZ:%.*]] = icmp eq i64 [[LEN]], 0
+; CHECK-NEXT:    [[CHAR0:%.*]] = load i8, i8* getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), align 1
+; CHECK-NEXT:    [[EQZ:%.*]] = icmp eq i8 [[CHAR0]], 0
 ; CHECK-NEXT:    ret i1 [[EQZ]]
 ;
 
   %max = or i64 %n, 1
   %ptr = getelementptr [0 x i8], [0 x i8]* @ax, i64 0, i64 0
   %len = tail call i64 @strnlen(i8* %ptr, i64 %max)
   %eqz = icmp eq i64 %len, 0
   ret i1 %eqz
 }
 
 
 ; Fold strnlen(ax, n) > 0 to *ax != 0 for n that's not zero.
 
 define i1 @fold_strnlen_ax_nz_gtz(i64 %n) {
 ; CHECK-LABEL: @fold_strnlen_ax_nz_gtz(
-; CHECK-NEXT:    [[MAX:%.*]] = or i64 [[N:%.*]], 1
-; 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 [[MAX]])
-; CHECK-NEXT:    [[GTZ:%.*]] = icmp ne i64 [[LEN]], 0
+; CHECK-NEXT:    [[CHAR0:%.*]] = load i8, i8* getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), align 1
+; CHECK-NEXT:    [[GTZ:%.*]] = icmp ne i8 [[CHAR0]], 0
 ; CHECK-NEXT:    ret i1 [[GTZ]]
 ;
 
   %max = or i64 %n, 1
   %ptr = getelementptr [0 x i8], [0 x i8]* @ax, i64 0, i64 0
   %len = tail call i64 @strnlen(i8* %ptr, i64 %max)
   %gtz = icmp ugt i64 %len, 0
   ret i1 %gtz
 }
 
 
 ; Fold strnlen(a5 + i, n) == 0 to a5[i] == 0 for a nonconstant a5
 ; and a nonzero n.
 
 define i1 @fold_strnlen_a5_pi_nz_eqz(i64 %i, i64 %n) {
 ; CHECK-LABEL: @fold_strnlen_a5_pi_nz_eqz(
-; CHECK-NEXT:    [[NZ:%.*]] = or i64 [[N:%.*]], 1
 ; CHECK-NEXT:    [[PTR:%.*]] = getelementptr inbounds [5 x i8], [5 x i8]* @a5, i64 0, i64 [[I:%.*]]
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* noundef nonnull [[PTR]], i64 [[NZ]])
-; CHECK-NEXT:    [[EQZ:%.*]] = icmp eq i64 [[LEN]], 0
+; CHECK-NEXT:    [[CHAR0:%.*]] = load i8, i8* [[PTR]], align 1
+; CHECK-NEXT:    [[EQZ:%.*]] = icmp eq i8 [[CHAR0]], 0
 ; CHECK-NEXT:    ret i1 [[EQZ]]
 ;
 
   %nz = or i64 %n, 1
   %ptr = getelementptr inbounds [5 x i8], [5 x i8]* @a5, i64 0, i64 %i
   %len = call i64 @strnlen(i8* %ptr, i64 %nz)
   %eqz = icmp eq i64 %len, 0
   ret i1 %eqz
 }
 
 
 ; Fold strnlen(s5 + i, n) == 0 for a constant s5 and nonzero n.
 ; This is first folded to s5[i] == 0 like the above and then finally
 ; to %0 == 5.
 
 define i1 @fold_strnlen_s5_pi_nz_eqz(i64 %i, i64 %n) {
 ; CHECK-LABEL: @fold_strnlen_s5_pi_nz_eqz(
-; CHECK-NEXT:    [[NZ:%.*]] = or i64 [[N:%.*]], 1
-; CHECK-NEXT:    [[PTR:%.*]] = getelementptr inbounds [6 x i8], [6 x i8]* @s5, i64 0, i64 [[I:%.*]]
-; CHECK-NEXT:    [[LEN:%.*]] = call i64 @strnlen(i8* noundef nonnull [[PTR]], i64 [[NZ]])
-; CHECK-NEXT:    [[EQZ:%.*]] = icmp eq i64 [[LEN]], 0
+; CHECK-NEXT:    [[EQZ:%.*]] = icmp eq i64 [[I:%.*]], 5
 ; CHECK-NEXT:    ret i1 [[EQZ]]
 ;
 
   %nz = or i64 %n, 1
   %ptr = getelementptr inbounds [6 x i8], [6 x i8]* @s5, i64 0, i64 %i
   %len = call i64 @strnlen(i8* %ptr, i64 %nz)
   %eqz = icmp eq i64 %len, 0
   ret i1 %eqz