[ValueTracking] Make getStringLenth aware of strdup

[serge-sans-paille]

Summary

During strlen compile-time evaluation, make it possible to track size of
strduped strings.

[serge-sans-paille]

clang-formatted version

[nikic]

LGTM

[efriedma]

llvm/lib/Analysis/ValueTracking.cpp

4254

Do you need to check somewhere that the string returned by strdup hasn't been modified? The existing code gets away without any checks for modification because getConstantDataArrayInfo only works on constant globals, but strdup returns a modifiable buffer.

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

4254

Great point, sorry for missing that.

[serge-sans-paille]

llvm/lib/Analysis/ValueTracking.cpp

4254

Indeed!

[serge-sans-paille]

Patch reverted by da2d6ebf0ab0badccb89ba20940fdd208636fa59 262eba01b33fd5cda5e4b65a744bac9d87cd7453

[efriedma]

In D123497#3447734, @serge-sans-paille wrote:

Patch reverted by da2d6ebf0ab0badccb89ba20940fdd208636fa59

That patch doesn't appear to exist

llvm/include/llvm/Analysis/ValueTracking.h

constexpr unsigned MaxAnalysisRecursionDepth = 6;
   /// character by default. If TrimAtNul is set to false, then this returns any
   /// trailing null 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);
 
   /// If we can compute the length of the string pointed to by the specified
   /// pointer, return 'len+1'.  If we can't, return 0.
-  uint64_t GetStringLength(const Value *V, unsigned CharSize = 8);
+  uint64_t GetStringLength(const Value *V,
+                           const TargetLibraryInfo *TLI = nullptr,
+                           unsigned CharSize = 8);
 
   /// This function returns call pointer argument that is considered the same by
   /// aliasing rules. You CAN'T use it to replace one value with another. If
   /// \p MustPreserveNullness is true, the call must preserve the nullness of
   /// the pointer.
   const Value *getArgumentAliasingToReturnedPointer(const CallBase *Call,
                                                     bool MustPreserveNullness);
   inline Value *

llvm/lib/Analysis/MemoryBuiltins.cpp

llvm::getAllocSize(const CallBase *CB,
 
   // Get the index type for this address space, results and intermediate
   // computations are performed at that width.
   auto &DL = CB->getModule()->getDataLayout();
   const unsigned IntTyBits = DL.getIndexTypeSizeInBits(CB->getType());
 
   // Handle strdup-like functions separately.
   if (FnData->AllocTy == StrDupLike) {
-    APInt Size(IntTyBits, GetStringLength(Mapper(CB->getArgOperand(0))));
+    APInt Size(IntTyBits, GetStringLength(Mapper(CB->getArgOperand(0)), TLI));
     if (!Size)
       return None;
 
     // Strndup limits strlen.
     if (FnData->FstParam > 0) {
       const ConstantInt *Arg =
         dyn_cast<ConstantInt>(Mapper(CB->getArgOperand(FnData->FstParam)));
       if (!Arg)

llvm/lib/Analysis/ValueTracking.cpp

 
 // These next two are very similar to the above, but also look through PHI
 // nodes.
 // TODO: See if we can integrate these two together.
 
 /// If we can compute the length of the string pointed to by
 /// the specified pointer, return 'len+1'.  If we can't, return 0.
 static uint64_t GetStringLengthH(const Value *V,
-                                 SmallPtrSetImpl<const PHINode*> &PHIs,
+                                 SmallPtrSetImpl<const PHINode *> &PHIs,
+                                 const TargetLibraryInfo *TLI,
                                  unsigned CharSize) {
   // Look through noop bitcast instructions.
   V = V->stripPointerCasts();
 
   // If this is a PHI node, there are two cases: either we have already seen it
   // or we haven't.
   if (const PHINode *PN = dyn_cast<PHINode>(V)) {
     if (!PHIs.insert(PN).second)
       return ~0ULL;  // already in the set.
 
     // If it was new, see if all the input strings are the same length.
     uint64_t LenSoFar = ~0ULL;
     for (Value *IncValue : PN->incoming_values()) {
-      uint64_t Len = GetStringLengthH(IncValue, PHIs, CharSize);
+      uint64_t Len = GetStringLengthH(IncValue, PHIs, TLI, CharSize);
       if (Len == 0) return 0; // Unknown length -> unknown.
 
       if (Len == ~0ULL) continue;
 
       if (Len != LenSoFar && LenSoFar != ~0ULL)
         return 0;    // Disagree -> unknown.
       LenSoFar = Len;
     }
 
     // Success, all agree.
     return LenSoFar;
   }
 
   // strlen(select(c,x,y)) -> strlen(x) ^ strlen(y)
   if (const SelectInst *SI = dyn_cast<SelectInst>(V)) {
-    uint64_t Len1 = GetStringLengthH(SI->getTrueValue(), PHIs, CharSize);
+    uint64_t Len1 = GetStringLengthH(SI->getTrueValue(), PHIs, TLI, CharSize);
     if (Len1 == 0) return 0;
-    uint64_t Len2 = GetStringLengthH(SI->getFalseValue(), PHIs, CharSize);
+    uint64_t Len2 = GetStringLengthH(SI->getFalseValue(), PHIs, TLI, CharSize);
     if (Len2 == 0) return 0;
     if (Len1 == ~0ULL) return Len2;
     if (Len2 == ~0ULL) return Len1;
     if (Len1 != Len2) return 0;
     return Len1;
   }
 
+  if (auto *CB = dyn_cast<CallBase>(V)) {
+    Function *Callee = CB->getCalledFunction();
+    if (!Callee)
+      return 0;
+
+    LibFunc TLIFn;
+    if (!TLI || !TLI->getLibFunc(*CB->getCalledFunction(), TLIFn) ||
+        !TLI->has(TLIFn))
+      return 0;
+
+    if (TLIFn == LibFunc_strdup || TLIFn == LibFunc_dunder_strdup)
+      return GetStringLengthH(CB->getArgOperand(0), PHIs, TLI, CharSize);
+
+    return 0;
+  }
+
   // Otherwise, see if we can read the string.
   ConstantDataArraySlice Slice;
   if (!getConstantDataArrayInfo(V, Slice, CharSize))
     return 0;
 
   if (Slice.Array == nullptr)
     return 1;
 
   // Search for nul characters
   unsigned NullIndex = 0;
   for (unsigned E = Slice.Length; NullIndex < E; ++NullIndex) {
     if (Slice.Array->getElementAsInteger(Slice.Offset + NullIndex) == 0)
       break;
   }
 
   return NullIndex + 1;
 }
 
 /// If we can compute the length of the string pointed to by
 /// the specified pointer, return 'len+1'.  If we can't, return 0.
-uint64_t llvm::GetStringLength(const Value *V, unsigned CharSize) {
+uint64_t llvm::GetStringLength(const Value *V, const TargetLibraryInfo *TLI,
+                               unsigned CharSize) {
   if (!V->getType()->isPointerTy())
     return 0;
 
   SmallPtrSet<const PHINode*, 32> PHIs;
-  uint64_t Len = GetStringLengthH(V, PHIs, CharSize);
+  uint64_t Len = GetStringLengthH(V, PHIs, TLI, CharSize);
   // If Len is ~0ULL, we had an infinite phi cycle: this is dead code, so return
   // an empty string as a length.
   return Len == ~0ULL ? 1 : Len;
 }
 
 const Value *
 llvm::getArgumentAliasingToReturnedPointer(const CallBase *Call,
                                            bool MustPreserveNullness) {

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

 
 Value *LibCallSimplifier::optimizeStrCat(CallInst *CI, IRBuilderBase &B) {
   // Extract some information from the instruction
   Value *Dst = CI->getArgOperand(0);
   Value *Src = CI->getArgOperand(1);
   annotateNonNullNoUndefBasedOnAccess(CI, {0, 1});
 
   // See if we can get the length of the input string.
-  uint64_t Len = GetStringLength(Src);
+  uint64_t Len = GetStringLength(Src, TLI);
   if (Len)
     annotateDereferenceableBytes(CI, 1, Len);
   else
     return nullptr;
   --Len; // Unbias length.
 
   // Handle the simple, do-nothing case: strcat(x, "") -> x
   if (Len == 0)
if (LengthArg) {
     // strncat(x, c, 0) -> x
     if (!Len)
       return Dst;
   } else {
     return nullptr;
   }
 
   // See if we can get the length of the input string.
-  uint64_t SrcLen = GetStringLength(Src);
+  uint64_t SrcLen = GetStringLength(Src, TLI);
   if (SrcLen) {
     annotateDereferenceableBytes(CI, 1, SrcLen);
     --SrcLen; // Unbias length.
   } else {
     return nullptr;
   }
 
   // strncat(x, "", c) -> x
Value *LibCallSimplifier::optimizeStrChr(CallInst *CI, IRBuilderBase &B) {
   FunctionType *FT = Callee->getFunctionType();
   Value *SrcStr = CI->getArgOperand(0);
   annotateNonNullNoUndefBasedOnAccess(CI, 0);
 
   // If the second operand is non-constant, see if we can compute the length
   // of the input string and turn this into memchr.
   ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
   if (!CharC) {
-    uint64_t Len = GetStringLength(SrcStr);
+    uint64_t Len = GetStringLength(SrcStr, TLI);
     if (Len)
       annotateDereferenceableBytes(CI, 0, Len);
     else
       return nullptr;
     if (!FT->getParamType(1)->isIntegerTy(32)) // memchr needs i32.
       return nullptr;
 
     return copyFlags(
if (HasStr1 && Str1.empty()) // strcmp("", x) -> -*x
     return B.CreateNeg(B.CreateZExt(
         B.CreateLoad(B.getInt8Ty(), Str2P, "strcmpload"), CI->getType()));
 
   if (HasStr2 && Str2.empty()) // strcmp(x,"") -> *x
     return B.CreateZExt(B.CreateLoad(B.getInt8Ty(), Str1P, "strcmpload"),
                         CI->getType());
 
   // strcmp(P, "x") -> memcmp(P, "x", 2)
-  uint64_t Len1 = GetStringLength(Str1P);
+  uint64_t Len1 = GetStringLength(Str1P, TLI);
   if (Len1)
     annotateDereferenceableBytes(CI, 0, Len1);
-  uint64_t Len2 = GetStringLength(Str2P);
+  uint64_t Len2 = GetStringLength(Str2P, TLI);
   if (Len2)
     annotateDereferenceableBytes(CI, 1, Len2);
 
   if (Len1 && Len2) {
     return copyFlags(
         *CI, emitMemCmp(Str1P, Str2P,
                         ConstantInt::get(DL.getIntPtrType(CI->getContext()),
                                          std::min(Len1, Len2)),
Value *LibCallSimplifier::optimizeStrNCmp(CallInst *CI, IRBuilderBase &B) {
   if (HasStr1 && Str1.empty()) // strncmp("", x, n) -> -*x
     return B.CreateNeg(B.CreateZExt(
         B.CreateLoad(B.getInt8Ty(), Str2P, "strcmpload"), CI->getType()));
 
   if (HasStr2 && Str2.empty()) // strncmp(x, "", n) -> *x
     return B.CreateZExt(B.CreateLoad(B.getInt8Ty(), Str1P, "strcmpload"),
                         CI->getType());
 
-  uint64_t Len1 = GetStringLength(Str1P);
+  uint64_t Len1 = GetStringLength(Str1P, TLI);
   if (Len1)
     annotateDereferenceableBytes(CI, 0, Len1);
-  uint64_t Len2 = GetStringLength(Str2P);
+  uint64_t Len2 = GetStringLength(Str2P, TLI);
   if (Len2)
     annotateDereferenceableBytes(CI, 1, Len2);
 
   // strncmp to memcmp
   if (!HasStr1 && HasStr2) {
     Len2 = std::min(Len2, Length);
     if (canTransformToMemCmp(CI, Str1P, Len2, DL))
       return copyFlags(
Value *LibCallSimplifier::optimizeStrNCmp(CallInst *CI, IRBuilderBase &B) {
   }
 
   return nullptr;
 }
 
 Value *LibCallSimplifier::optimizeStrNDup(CallInst *CI, IRBuilderBase &B) {
   Value *Src = CI->getArgOperand(0);
   ConstantInt *Size = dyn_cast<ConstantInt>(CI->getArgOperand(1));
-  uint64_t SrcLen = GetStringLength(Src);
+  uint64_t SrcLen = GetStringLength(Src, TLI);
   if (SrcLen && Size) {
     annotateDereferenceableBytes(CI, 0, SrcLen);
     if (SrcLen <= Size->getZExtValue() + 1)
       return copyFlags(*CI, emitStrDup(Src, B, TLI));
   }
 
   return nullptr;
 }
 
 Value *LibCallSimplifier::optimizeStrCpy(CallInst *CI, IRBuilderBase &B) {
   Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
   if (Dst == Src) // strcpy(x,x)  -> x
     return Src;
 
   annotateNonNullNoUndefBasedOnAccess(CI, {0, 1});
   // See if we can get the length of the input string.
-  uint64_t Len = GetStringLength(Src);
+  uint64_t Len = GetStringLength(Src, TLI);
   if (Len)
     annotateDereferenceableBytes(CI, 1, Len);
   else
     return nullptr;
 
   // We have enough information to now generate the memcpy call to do the
   // copy for us.  Make a memcpy to copy the nul byte with align = 1.
   CallInst *NewCI =
if (CI->use_empty())
     return copyFlags(*CI, emitStrCpy(Dst, Src, B, TLI));
 
   if (Dst == Src) { // stpcpy(x,x)  -> x+strlen(x)
     Value *StrLen = emitStrLen(Src, B, DL, TLI);
     return StrLen ? B.CreateInBoundsGEP(B.getInt8Ty(), Dst, StrLen) : nullptr;
   }
 
   // See if we can get the length of the input string.
-  uint64_t Len = GetStringLength(Src);
+  uint64_t Len = GetStringLength(Src, TLI);
   if (Len)
     annotateDereferenceableBytes(CI, 1, Len);
   else
     return nullptr;
 
   Type *PT = Callee->getFunctionType()->getParamType(0);
   Value *LenV = ConstantInt::get(DL.getIntPtrType(PT), Len);
   Value *DstEnd = B.CreateGEP(B.getInt8Ty(), Dst,
Value *LibCallSimplifier::optimizeStrNCpy(CallInst *CI, IRBuilderBase &B) {
   else
     return nullptr;
 
   // strncpy(x, y, 0) -> x
   if (Len == 0)
     return Dst;
 
   // See if we can get the length of the input string.
-  uint64_t SrcLen = GetStringLength(Src);
+  uint64_t SrcLen = GetStringLength(Src, TLI);
   if (SrcLen) {
     annotateDereferenceableBytes(CI, 1, SrcLen);
     --SrcLen; // Unbias length.
   } else {
     return nullptr;
   }
 
   if (SrcLen == 0) {
Value *LibCallSimplifier::optimizeStrNCpy(CallInst *CI, IRBuilderBase &B) {
   return Dst;
 }
 
 Value *LibCallSimplifier::optimizeStringLength(CallInst *CI, IRBuilderBase &B,
                                                unsigned CharSize) {
   Value *Src = CI->getArgOperand(0);
 
   // Constant folding: strlen("xyz") -> 3
-  if (uint64_t Len = GetStringLength(Src, CharSize))
+  if (uint64_t Len = GetStringLength(Src, TLI, 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
   // 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
if (getConstantDataArrayInfo(GEP->getOperand(0), Slice, CharSize)) {
         return B.CreateSub(ConstantInt::get(CI->getType(), NullTermIdx),
                            Offset);
       }
     }
   }
 
   // strlen(x?"foo":"bars") --> x ? 3 : 4
   if (SelectInst *SI = dyn_cast<SelectInst>(Src)) {
-    uint64_t LenTrue = GetStringLength(SI->getTrueValue(), CharSize);
-    uint64_t LenFalse = GetStringLength(SI->getFalseValue(), CharSize);
+    uint64_t LenTrue = GetStringLength(SI->getTrueValue(), TLI, CharSize);
+    uint64_t LenFalse = GetStringLength(SI->getFalseValue(), TLI, CharSize);
     if (LenTrue && LenFalse) {
       ORE.emit([&]() {
         return OptimizationRemark("instcombine", "simplify-libcalls", CI)
                << "folded strlen(select) to select of constants";
       });
       return B.CreateSelect(SI->getCondition(),
                             ConstantInt::get(CI->getType(), LenTrue - 1),
                             ConstantInt::get(CI->getType(), LenFalse - 1));
if (FormatStr[1] == 's') {
     // strlen(str)+1)
     if (!CI->getArgOperand(2)->getType()->isPointerTy())
       return nullptr;
 
     if (CI->use_empty())
       // sprintf(dest, "%s", str) -> strcpy(dest, str)
       return copyFlags(*CI, emitStrCpy(Dest, CI->getArgOperand(2), B, TLI));
 
-    uint64_t SrcLen = GetStringLength(CI->getArgOperand(2));
+    uint64_t SrcLen = GetStringLength(CI->getArgOperand(2), TLI);
     if (SrcLen) {
       B.CreateMemCpy(
           Dest, Align(1), CI->getArgOperand(2), Align(1),
           ConstantInt::get(DL.getIntPtrType(CI->getContext()), SrcLen));
       // Returns total number of characters written without null-character.
       return ConstantInt::get(CI->getType(), SrcLen - 1);
     } else if (Value *V = emitStpCpy(Dest, CI->getArgOperand(2), B, TLI)) {
       // sprintf(dest, "%s", str) -> stpcpy(dest, str) - dest
Value *LibCallSimplifier::optimizeFPuts(CallInst *CI, IRBuilderBase &B) {
   if (OptForSize)
     return nullptr;
 
   // We can't optimize if return value is used.
   if (!CI->use_empty())
     return nullptr;
 
   // fputs(s,F) --> fwrite(s,strlen(s),1,F)
-  uint64_t Len = GetStringLength(CI->getArgOperand(0));
+  uint64_t Len = GetStringLength(CI->getArgOperand(0), TLI);
   if (!Len)
     return nullptr;
 
   // Known to have no uses (see above).
   return copyFlags(
       *CI,
       emitFWrite(CI->getArgOperand(0),
                  ConstantInt::get(DL.getIntPtrType(CI->getContext()), Len - 1),
FortifiedLibCallSimplifier::isFortifiedCallFoldable(CallInst *CI,
   if (ConstantInt *ObjSizeCI =
           dyn_cast<ConstantInt>(CI->getArgOperand(ObjSizeOp))) {
     if (ObjSizeCI->isMinusOne())
       return true;
     // If the object size wasn't -1 (unknown), bail out if we were asked to.
     if (OnlyLowerUnknownSize)
       return false;
     if (StrOp) {
-      uint64_t Len = GetStringLength(CI->getArgOperand(*StrOp));
+      uint64_t Len = GetStringLength(CI->getArgOperand(*StrOp), TLI);
       // If the length is 0 we don't know how long it is and so we can't
       // remove the check.
       if (Len)
         annotateDereferenceableBytes(CI, *StrOp, Len);
       else
         return false;
       return ObjSizeCI->getZExtValue() >= Len;
     }
if (isFortifiedCallFoldable(CI, 2, None, 1)) {
     else
       return copyFlags(*CI, emitStpCpy(Dst, Src, B, TLI));
   }
 
   if (OnlyLowerUnknownSize)
     return nullptr;
 
   // Maybe we can stil fold __st[rp]cpy_chk to __memcpy_chk.
-  uint64_t Len = GetStringLength(Src);
+  uint64_t Len = GetStringLength(Src, TLI);
   if (Len)
     annotateDereferenceableBytes(CI, 1, Len);
   else
     return nullptr;
 
   // FIXME: There is really no guarantee that sizeof(size_t) is equal to
   // sizeof(int*) for every target. So the assumption used here to derive the
   // SizeTBits based on the size of an integer pointer in address space zero

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; Test that the strlen library call simplifier works correctly.
 ;
 ; RUN: opt < %s -passes=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"
 @null = constant [1 x i8] zeroinitializer
 @null_hello = constant [7 x i8] c"\00hello\00"
 @nullstring = constant i8 0
 @a = common global [32 x i8] zeroinitializer, align 1
 @null_hello_mid = constant [13 x i8] c"hello wor\00ld\00"
 
 declare i32 @strlen(i8*)
+declare noalias i8* @strdup(i8*)
 
 ; Check strlen(string constant) -> integer constant.
 
 define i32 @test_simplify1() {
 ; CHECK-LABEL: @test_simplify1(
 ; CHECK-NEXT:    ret i32 5
 ;
   %hello_p = getelementptr [6 x i8], [6 x i8]* @hello, i32 0, i32 0

 ;
   %gep = getelementptr i8, i8* %ptr, i64 1
   store i8 49, i8* %gep
   %len = tail call i32 @strlen(i8* nonnull dereferenceable(1) %ptr)
   %cmp = icmp eq i32 %len, 0
   ret i1 %cmp
 }
 
+; Check strlen(strdup(string constant)) -> integer constant.
+
+define i32 @test_simplify_strduped_constant() {
+; CHECK-LABEL: @test_simplify_strduped_constant(
+; CHECK-NEXT:    ret i32 5
+;
+  %hello_p = getelementptr [6 x i8], [6 x i8]* @hello, i32 0, i32 0
+  %hello_s = call i8* @strdup(i8* %hello_p)
+  %hello_l = call i32 @strlen(i8* %hello_s)
+  ret i32 %hello_l
+}
+
+
 attributes #0 = { null_pointer_is_valid }