[SimplifyLibCalls] Simplify strlen to a subtraction for certain cases

[lihuang]

Summary

This patch implements this optimization:

strlen(s + x)  --> strlen(s) - x,

where s is a pointer to a string literal, and x is an integer variable. Note that strlen(s) is a constant which is known at compile time. This optimization is legal when one of the following is true:

A. x is known to be within the range [0, strlen(s)]
B. The string literal is null-terminated and has only one null terminator "\0" at its end, and (s + x) is proved to be an out-of-bound pointer when x < 0 or x > strlen(s).

Case A is straightforward. For case B, it's legal to do this optimization because strlen will have undefined behavior when (s + x) is out of bound.

[nlopes]

Could you please explain the motivation for this transformation?
Doesn't seem very profitable to me unless strlen(s) has already been computed before. Otherwise we end up visiting more memory positions than with the original code.

[lihuang]

We only do this optimization when s is a string literal, so that strlen(s) could be computed at compile time. The motivation is, this could save some function calls, and gcc has this optimization.

[majnemer]

lib/Transforms/Utils/SimplifyLibCalls.cpp

538–558

Have you tried using something like GetPointerBaseWithConstantOffset? You might be able to replace this code with that.

[lihuang]

lib/Transforms/Utils/SimplifyLibCalls.cpp

538–558

The GEP in this case is not with a constant offset, as x is a variable. So GetPointerBaseWithConstantOffset doesn't help here.

This code actually duplicates part of the code in getConstantStringInfo, but I cannot just use getConstantStringInfo for GEP because it only works with constant offset. I need the same checks here to make sure that the GEP is pointing to a string and the first index is 0.

[lihuang]

Just a kindly ping :)

Hi Sanjay, do you have any comments on this change?

Thanks!

[spatel]

Can you rebase this patch after http://reviews.llvm.org/rL265431 ?
You can use utils/update_test_checks.py to regenerate the CHECK lines.
Sorry for the extra effort, but I used your test cases as experiments for the script.

[spatel]

lib/Transforms/Utils/SimplifyLibCalls.cpp

541–558

These checks are included in getConstantStringInfo(). You do not need to repeat them here?

[lihuang]

Sure, I will rebase the patch after 265431.

lib/Transforms/Utils/SimplifyLibCalls.cpp

541–558

Yes these lines are the same lines in getConstantStringInfo(). The reason I didn't use getConstantStringInfo() here is it only works for GEP with a constant offset. In this case, the offset is a variable, and we need the same checks.

[lihuang]

Hi Sanjay,

I have updated the test using your script, it's an awesome script!

[• dberlin]

So, uh, why not make getConstantStringInfo work for this case too, rather
than duplicate it?

[lihuang]

I tried to make getConstantStringInfo work for this case but didn't find a good way.

I think this case needs a different logic than getConstantStringInfo, though requiring same checks on the GEP. getConstantStringInfo returns the string pointed to by the input pointer, but the string is not decided at compile time when the input pointer is a GEP with variable index. We could extend the logic of getConstantStringInfo, but that will need changing the signature and refactoring lots of code, as this function is already used in many places.

In order to avoid duplicate code, I could extract the GEP part from getConstantStringInfo into another function so it could be shared.

[lihuang]

Updated the changed. Added a helper function in ValueTracking.cpp/h to check if a given GEP is based on a pointer to string and is indexing into that string. This helper function can be used by both getConstantStringInfo() and optimizeStrlen().

[spatel]

include/llvm/Analysis/ValueTracking.h

185–186

Doxygen comments start with 3 slashes ('///'). Also, don't repeat the function name in the comment:
http://llvm.org/docs/CodingStandards.html#doxygen-use-in-documentation-comments

Feel free to fix the rest of the file in a separate commit. :)

lib/Analysis/ValueTracking.cpp

2654–2655

Don't repeat the block comment from the header file.

lib/Transforms/Utils/SimplifyLibCalls.cpp

551–552

You can move this down to where it is actually used.

[lihuang]

include/llvm/Analysis/ValueTracking.h

185–186

Thanks! Will update the rest of this file :)

[spatel]

LGTM.

include/llvm/Analysis/ValueTracking.h

 #include "llvm/Support/DataTypes.h"
 
 namespace llvm {
   class APInt;
   class AddOperator;
   class AssumptionCache;
   class DataLayout;
   class DominatorTree;
+  class GEPOperator;
   class Instruction;
   class Loop;
   class LoopInfo;
   class MDNode;
   class StringRef;
   class TargetLibraryInfo;
   class Value;
 
Value *GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset,
                                           const DataLayout &DL);
   static inline const Value *
   GetPointerBaseWithConstantOffset(const Value *Ptr, int64_t &Offset,
                                    const DataLayout &DL) {
     return GetPointerBaseWithConstantOffset(const_cast<Value *>(Ptr), Offset,
                                             DL);
   }
 
+  /// Returns true if the GEP is based on a pointer to a string (array of i8), 
+  /// and is indexing into this string.
+  bool isGEPBasedOnPointerToString(const GEPOperator *GEP);
+
   /// getConstantStringInfo - This function computes the length of a
   /// null-terminated C string pointed to by V.  If successful, it returns true
   /// and returns the string in Str.  If unsuccessful, it returns false.  This
   /// does not include the trailing nul character by default.  If TrimAtNul is
   /// set to false, then this returns any trailing nul characters as well as any
   /// other characters that come after it.
   bool getConstantStringInfo(const Value *V, StringRef &Str,
                              uint64_t Offset = 0, bool TrimAtNul = true);

lib/Analysis/ValueTracking.cpp

while (Visited.insert(Ptr).second) {
     } else {
       break;
     }
   }
   Offset = ByteOffset.getSExtValue();
   return Ptr;
 }
 
+bool llvm::isGEPBasedOnPointerToString(const GEPOperator *GEP) {
+  // Make sure the GEP has exactly three arguments.
+  if (GEP->getNumOperands() != 3)
+    return false;
+
+  // Make sure the index-ee is a pointer to array of i8.
+  ArrayType *AT = dyn_cast<ArrayType>(GEP->getSourceElementType());
+  if (!AT || !AT->getElementType()->isIntegerTy(8))
+    return false;
+
+  // Check to make sure that the first operand of the GEP is an integer and
+  // has value 0 so that we are sure we're indexing into the initializer.
+  const ConstantInt *FirstIdx = dyn_cast<ConstantInt>(GEP->getOperand(1));
+  if (!FirstIdx || !FirstIdx->isZero())
+    return false;
+
+  return true;
+} 
 
 /// This function computes the length of a null-terminated C string pointed to
 /// by V. If successful, it returns true and returns the string in Str.
 /// If unsuccessful, it returns false.
 bool llvm::getConstantStringInfo(const Value *V, StringRef &Str,
                                  uint64_t Offset, bool TrimAtNul) {
   assert(V);
 
   // Look through bitcast instructions and geps.
   V = V->stripPointerCasts();
 
   // If the value is a GEP instruction or constant expression, treat it as an
   // offset.
   if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
-    // Make sure the GEP has exactly three arguments.
-    if (GEP->getNumOperands() != 3)
-      return false;
-
-    // Make sure the index-ee is a pointer to array of i8.
-    ArrayType *AT = dyn_cast<ArrayType>(GEP->getSourceElementType());
-    if (!AT || !AT->getElementType()->isIntegerTy(8))
-      return false;
-
-    // Check to make sure that the first operand of the GEP is an integer and
-    // has value 0 so that we are sure we're indexing into the initializer.
-    const ConstantInt *FirstIdx = dyn_cast<ConstantInt>(GEP->getOperand(1));
-    if (!FirstIdx || !FirstIdx->isZero())
+    // The GEP operator should be based on a pointer to string constant, and is
+    // indexing into the string constant.
+    if (!isGEPBasedOnPointerToString(GEP))
       return false;
 
     // If the second index isn't a ConstantInt, then this is a variable index
     // into the array.  If this occurs, we can't say anything meaningful about
     // the string.
     uint64_t StartIdx = 0;
     if (const ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(2)))
       StartIdx = CI->getZExtValue();

lib/Transforms/Utils/SimplifyLibCalls.cpp

if (FT->getNumParams() != 1 || FT->getParamType(0) != B.getInt8PtrTy() ||
     return nullptr;
 
   Value *Src = CI->getArgOperand(0);
 
   // Constant folding: strlen("xyz") -> 3
   if (uint64_t Len = GetStringLength(Src))
     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 
+  // 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 
+  // very uncommon.
+  if (GEPOperator *GEP = dyn_cast<GEPOperator>(Src)) {
+    if (!isGEPBasedOnPointerToString(GEP))
+      return nullptr;
+
+    StringRef Str;
+    if (getConstantStringInfo(GEP->getOperand(0), Str, 0, false)) {
+      size_t NullTermIdx = Str.find('\0');
+      
+      // If the string does not have '\0', leave it to strlen to compute
+      // its length.
+      if (NullTermIdx == StringRef::npos)
+        return nullptr;
+     
+      Value *Offset = GEP->getOperand(2);
+      unsigned BitWidth = Offset->getType()->getIntegerBitWidth();
+      APInt KnownZero(BitWidth, 0);
+      APInt KnownOne(BitWidth, 0);
+      computeKnownBits(Offset, KnownZero, KnownOne, DL, 0, nullptr, CI, 
+                       nullptr);
+      KnownZero.flipAllBits();
+      size_t ArrSize = 
+             cast<ArrayType>(GEP->getSourceElementType())->getNumElements();
+
+      // KnownZero's bits are flipped, so zeros in KnownZero now represent 
+      // bits known to be zeros in Offset, and ones in KnowZero represent 
+      // bits unknown in Offset. Therefore, Offset is known to be in range
+      // [0, NullTermIdx] when the flipped KnownZero is non-negative and 
+      // unsigned-less-than NullTermIdx.
+      //
+      // If Offset is not provably in the range [0, NullTermIdx], we can still 
+      // optimize if we can prove that the program has undefined behavior when 
+      // Offset is outside that range. That is the case when GEP->getOperand(0) 
+      // is a pointer to an object whose memory extent is NullTermIdx+1.
+      if ((KnownZero.isNonNegative() && KnownZero.ule(NullTermIdx)) || 
+          (GEP->isInBounds() && isa<GlobalVariable>(GEP->getOperand(0)) &&
+           NullTermIdx == ArrSize - 1))
+        return B.CreateSub(ConstantInt::get(CI->getType(), NullTermIdx), 
+                           Offset);
+    }
+
+    return nullptr;
+  }
+
   // strlen(x?"foo":"bars") --> x ? 3 : 4
   if (SelectInst *SI = dyn_cast<SelectInst>(Src)) {
     uint64_t LenTrue = GetStringLength(SI->getTrueValue());
     uint64_t LenFalse = GetStringLength(SI->getFalseValue());
     if (LenTrue && LenFalse) {
       Function *Caller = CI->getParent()->getParent();
       emitOptimizationRemark(CI->getContext(), "simplify-libcalls", *Caller,
                              SI->getDebugLoc(),

test/Transforms/InstCombine/strlen-1.ll

-; NOTE: Assertions have been autogenerated by update_test_checks.py
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; Test that the strlen library call simplifier works correctly.
 ;
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128"
 
 @hello = constant [6 x i8] c"hello\00"
 @longer = constant [7 x i8] c"longer\00"
;
   ret i32 %l
 }
 
 ; Check the case that should be simplified to a sub instruction.
 ; strlen(@hello + x) --> 5 - x
 
 define i32 @test_simplify10(i32 %x) {
 ; CHECK-LABEL: @test_simplify10(
-; CHECK-NEXT:    [[HELLO_P:%.*]] = getelementptr inbounds [6 x i8], [6 x i8]* @hello, i32 0, i32 %x
-; CHECK-NEXT:    [[HELLO_L:%.*]] = call i32 @strlen(i8* [[HELLO_P]])
-; CHECK-NEXT:    ret i32 [[HELLO_L]]
+; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 5, %x
+; CHECK-NEXT:    ret i32 [[TMP1]]
 ;
   %hello_p = getelementptr inbounds [6 x i8], [6 x i8]* @hello, i32 0, i32 %x
   %hello_l = call i32 @strlen(i8* %hello_p)
   ret i32 %hello_l
 }
 
 ; strlen(@null_hello_mid + (x & 7)) --> 9 - (x & 7)
 
 define i32 @test_simplify11(i32 %x) {
 ; CHECK-LABEL: @test_simplify11(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 %x, 7
-; CHECK-NEXT:    [[HELLO_P:%.*]] = getelementptr inbounds [13 x i8], [13 x i8]* @null_hello_mid, i32 0, i32 [[AND]]
-; CHECK-NEXT:    [[HELLO_L:%.*]] = call i32 @strlen(i8* [[HELLO_P]])
-; CHECK-NEXT:    ret i32 [[HELLO_L]]
+; CHECK-NEXT:    [[TMP1:%.*]] = sub nsw i32 9, [[AND]]
+; CHECK-NEXT:    ret i32 [[TMP1]]
 ;
   %and = and i32 %x, 7
   %hello_p = getelementptr inbounds [13 x i8], [13 x i8]* @null_hello_mid, i32 0, i32 %and
   %hello_l = call i32 @strlen(i8* %hello_p)
   ret i32 %hello_l
 }
 
 ; Check cases that shouldn't be simplified.