[InstCombine] Calloc-ed strings optimizations

[xbolva00]

Summary

Example cases:
strlen(calloc(...)) -> 0

[xbolva00]

This comment was removed by xbolva00.

[bkramer]

This looks overly specific. Can you teach GetStringLength about this instead? All of the transformations should already work if GetStringLength returns a length of zero.

[xbolva00]

Extend GetStringLength with knowledge if the value comes from calloc.

[xbolva00]

include/llvm/Analysis/ValueTracking.h

277 ↗

(On Diff #147552)

Or should I leave const here and then const_cast for dyn_cast in isStringFromCalloc?

[bkramer]

include/llvm/Analysis/ValueTracking.h

277 ↗

(On Diff #147552)

Leave the const here and make the variables in isStringFromCalloc const too. There should be no need for const_cast, dyn_cast will preserve const input types.

lib/Analysis/ValueTracking.cpp

3392 ↗

(On Diff #147552)

APInt::isNullValue() is preferable over getZExtValue()==0 because it also handles integer widths > 64

[xbolva00]

• Added const to variables in isStringFromCalloc
• Use APInt::isNullValue()

[xbolva00]

• Fixed a comment

[bkramer]

lib/Transforms/Utils/SimplifyLibCalls.cpp

215 ↗

(On Diff #147552)

What if strlen(Src) < Len?

207 ↗

(On Diff #147758)

Is this correct? strncpy fills the rest of the string with null bytes, strncat does not.

[xbolva00]

lib/Transforms/Utils/SimplifyLibCalls.cpp

215 ↗

(On Diff #147552)

That is ok
Len < SrcLen case is handled below...
and then we return emitStrLenMemCpy(Src, Dst, SrcLen, B);

207 ↗

(On Diff #147758)

Good point. So we can do nothing at all in this case? or use memcpy + store null byte?

[xbolva00]

lib/Transforms/Utils/SimplifyLibCalls.cpp

207 ↗

(On Diff #147758)

" memcpy + store null byte: ... Nope, cannot do this. It will copy bytes even after \0. Strncat does not do it.

I removed incorrect transformations for str(n)cat to str(n)cpy. So patch is done.

[xbolva00]

Is it ok now?

[bkramer]

lg

[spatel]

llvm/trunk/test/Transforms/InstCombine/zero-string.ll

62

Make sure you test locally before committing. There's no final '}' here, so this broke bots.
Hopefully fixed with rL332990

62

Wrong link:
rL332992

[efriedma]

It looks like this patch doesn't handle the case where the memory allocated by calloc() is modified?

[xbolva00]

In D47059#1108252, @efriedma wrote:

It looks like this patch doesn't handle the case where the memory allocated by calloc() is modified?

Ok, I will remove it from InstCombine - https://reviews.llvm.org/D47218

It could be moved to DSE later with that check.

Well, we cannot teach GetStringLength about it then. So it is useless anyway to move it to DSE?

llvm/trunk/include/llvm/Analysis/ValueTracking.h

class Value;
   /// 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, unsigned CharSize = 8);
 
   /// This method strips off any GEP address adjustments and pointer casts from
   /// the specified value, returning the original object being addressed. Note
   /// that the returned value has pointer type if the specified value does. If
   /// the MaxLookup value is non-zero, it limits the number of instructions to
   /// be stripped off.
   Value *GetUnderlyingObject(Value *V, const DataLayout &DL,
                              unsigned MaxLookup = 6);

llvm/trunk/lib/Analysis/MemoryBuiltins.cpp

 
 SizeOffsetType ObjectSizeOffsetVisitor::visitCallSite(CallSite CS) {
   Optional<AllocFnsTy> FnData = getAllocationSize(CS.getInstruction(), TLI);
   if (!FnData)
     return unknown();
 
   // Handle strdup-like functions separately.
   if (FnData->AllocTy == StrDupLike) {
-    APInt Size(IntTyBits, GetStringLength(CS.getArgument(0)));
+    APInt Size(IntTyBits, GetStringLength(CS.getArgument(0), TLI));
     if (!Size)
       return unknown();
 
     // Strndup limits strlen.
     if (FnData->FstParam > 0) {
       ConstantInt *Arg =
           dyn_cast<ConstantInt>(CS.getArgument(FnData->FstParam));
       if (!Arg)

llvm/trunk/lib/Analysis/ValueTracking.cpp

static uint64_t GetStringLengthH(const Value *V,
   for (unsigned E = Slice.Length; NullIndex < E; ++NullIndex) {
     if (Slice.Array->getElementAsInteger(Slice.Offset + NullIndex) == 0)
       break;
   }
 
   return NullIndex + 1;
 }
 
+static bool isStringFromCalloc(const Value *Str, const TargetLibraryInfo *TLI) {
+  const CallInst *Calloc = dyn_cast<CallInst>(Str);
+  if (!Calloc)
+    return false;
+
+  const Function *InnerCallee = Calloc->getCalledFunction();
+  if (!InnerCallee)
+    return false;
+
+  LibFunc Func;
+  if (!TLI->getLibFunc(*InnerCallee, Func) || !TLI->has(Func) ||
+      Func != LibFunc_calloc)
+    return false;
+
+  const ConstantInt *N = dyn_cast<ConstantInt>(Calloc->getOperand(0));
+  const ConstantInt *Size = dyn_cast<ConstantInt>(Calloc->getOperand(1));
+
+  if (!N || !Size)
+    return false;
+
+  if (N->isNullValue() || Size->isNullValue())
+    return false;
+
+  return 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 llvm::GetStringLength(const Value *V, unsigned CharSize) {
-  if (!V->getType()->isPointerTy()) return 0;
+uint64_t llvm::GetStringLength(const Value *V, const TargetLibraryInfo *TLI, unsigned CharSize) {
+  if (!V->getType()->isPointerTy())
+    return 0;
+  if (isStringFromCalloc(V, TLI))
+    return 1;
 
   SmallPtrSet<const PHINode*, 32> PHIs;
   uint64_t Len = GetStringLengthH(V, PHIs, 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;
 }
 

llvm/trunk/lib/Transforms/Utils/SimplifyLibCalls.cpp

 //===----------------------------------------------------------------------===//
 
 Value *LibCallSimplifier::optimizeStrCat(CallInst *CI, IRBuilder<> &B) {
   // Extract some information from the instruction
   Value *Dst = CI->getArgOperand(0);
   Value *Src = CI->getArgOperand(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 == 0)
     return nullptr;
   --Len; // Unbias length.
 
   // Handle the simple, do-nothing case: strcat(x, "") -> x
   if (Len == 0)
     return Dst;
 
Value *LibCallSimplifier::optimizeStrNCat(CallInst *CI, IRBuilder<> &B) {
 
   // We don't do anything if length is not constant.
   if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getArgOperand(2)))
     Len = LengthArg->getZExtValue();
   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 == 0)
     return nullptr;
   --SrcLen; // Unbias length.
 
   // Handle the simple, do-nothing cases:
   // strncat(x, "", c) -> x
   // strncat(x,  c, 0) -> x
   if (SrcLen == 0 || Len == 0)
Value *LibCallSimplifier::optimizeStrChr(CallInst *CI, IRBuilder<> &B) {
   Function *Callee = CI->getCalledFunction();
   FunctionType *FT = Callee->getFunctionType();
   Value *SrcStr = CI->getArgOperand(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 == 0 || !FT->getParamType(1)->isIntegerTy(32)) // memchr needs i32.
       return nullptr;
 
     return emitMemChr(SrcStr, CI->getArgOperand(1), // include nul.
                       ConstantInt::get(DL.getIntPtrType(CI->getContext()), Len),
                       B, DL, TLI);
   }
 
Value *LibCallSimplifier::optimizeStrCmp(CallInst *CI, IRBuilder<> &B) {
   if (HasStr1 && Str1.empty()) // strcmp("", x) -> -*x
     return B.CreateNeg(
         B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"), CI->getType()));
 
   if (HasStr2 && Str2.empty()) // strcmp(x,"") -> *x
     return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
 
   // strcmp(P, "x") -> memcmp(P, "x", 2)
-  uint64_t Len1 = GetStringLength(Str1P);
-  uint64_t Len2 = GetStringLength(Str2P);
+  uint64_t Len1 = GetStringLength(Str1P, TLI);
+  uint64_t Len2 = GetStringLength(Str2P, TLI);
   if (Len1 && Len2) {
     return emitMemCmp(Str1P, Str2P,
                       ConstantInt::get(DL.getIntPtrType(CI->getContext()),
                                        std::min(Len1, Len2)),
                       B, DL, TLI);
   }
 
   return nullptr;

 }
 
 Value *LibCallSimplifier::optimizeStrCpy(CallInst *CI, IRBuilder<> &B) {
   Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
   if (Dst == Src) // strcpy(x,x)  -> x
     return Src;
 
   // See if we can get the length of the input string.
-  uint64_t Len = GetStringLength(Src);
+  uint64_t Len = GetStringLength(Src, TLI);
   if (Len == 0)
     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.
   B.CreateMemCpy(Dst, 1, Src, 1,
                  ConstantInt::get(DL.getIntPtrType(CI->getContext()), Len));
   return Dst;
 }
 
 Value *LibCallSimplifier::optimizeStpCpy(CallInst *CI, IRBuilder<> &B) {
   Function *Callee = CI->getCalledFunction();
   Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
   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 == 0)
     return nullptr;
 
   Type *PT = Callee->getFunctionType()->getParamType(0);
   Value *LenV = ConstantInt::get(DL.getIntPtrType(PT), Len);
   Value *DstEnd = B.CreateGEP(B.getInt8Ty(), Dst,
                               ConstantInt::get(DL.getIntPtrType(PT), Len - 1));
 
   // 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.
   B.CreateMemCpy(Dst, 1, Src, 1, LenV);
   return DstEnd;
 }
 
 Value *LibCallSimplifier::optimizeStrNCpy(CallInst *CI, IRBuilder<> &B) {
   Function *Callee = CI->getCalledFunction();
   Value *Dst = CI->getArgOperand(0);
   Value *Src = CI->getArgOperand(1);
   Value *LenOp = CI->getArgOperand(2);
 
   // See if we can get the length of the input string.
-  uint64_t SrcLen = GetStringLength(Src);
+  uint64_t SrcLen = GetStringLength(Src, TLI);
   if (SrcLen == 0)
     return nullptr;
   --SrcLen;
 
   if (SrcLen == 0) {
     // strncpy(x, "", y) -> memset(align 1 x, '\0', y)
     B.CreateMemSet(Dst, B.getInt8('\0'), LenOp, 1);
     return Dst;
Value *LibCallSimplifier::optimizeStrNCpy(CallInst *CI, IRBuilder<> &B) {
   return Dst;
 }
 
 Value *LibCallSimplifier::optimizeStringLength(CallInst *CI, IRBuilder<> &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 nullptr;
   }
 
   // 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 (isLocallyOpenedFile(CI->getArgOperand(1), CI, B, TLI))
       return emitFPutSUnlocked(CI->getArgOperand(0), CI->getArgOperand(1), B,
                                TLI);
     else
       // We can't optimize if return value is used.
       return nullptr;
   }
 
   // fputs(s,F) --> fwrite(s,1,strlen(s),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 emitFWrite(
       CI->getArgOperand(0),
       ConstantInt::get(DL.getIntPtrType(CI->getContext()), Len - 1),
       CI->getArgOperand(1), B, DL, TLI);
bool 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 (isString) {
-      uint64_t Len = GetStringLength(CI->getArgOperand(SizeOp));
+      uint64_t Len = GetStringLength(CI->getArgOperand(SizeOp), TLI);
       // If the length is 0 we don't know how long it is and so we can't
       // remove the check.
       if (Len == 0)
         return false;
       return ObjSizeCI->getZExtValue() >= Len;
     }
     if (ConstantInt *SizeCI = dyn_cast<ConstantInt>(CI->getArgOperand(SizeOp)))
       return ObjSizeCI->getZExtValue() >= SizeCI->getZExtValue();
Value *FortifiedLibCallSimplifier::optimizeStrpCpyChk(CallInst *CI,
   // string lengths for varying.
   if (isFortifiedCallFoldable(CI, 2, 1, true))
     return emitStrCpy(Dst, Src, B, TLI, Name.substr(2, 6));
 
   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 == 0)
     return nullptr;
 
   Type *SizeTTy = DL.getIntPtrType(CI->getContext());
   Value *LenV = ConstantInt::get(SizeTTy, Len);
   Value *Ret = emitMemCpyChk(Dst, Src, LenV, ObjSize, B, DL, TLI);
   // If the function was an __stpcpy_chk, and we were able to fold it into
   // a __memcpy_chk, we still need to return the correct end pointer.
Value *FortifiedLibCallSimplifier::optimizeCall(CallInst *CI) {
   default:
     break;
   }
   return nullptr;
 }
 
 FortifiedLibCallSimplifier::FortifiedLibCallSimplifier(
     const TargetLibraryInfo *TLI, bool OnlyLowerUnknownSize)
-    : TLI(TLI), OnlyLowerUnknownSize(OnlyLowerUnknownSize) {}
+    : TLI(TLI), OnlyLowerUnknownSize(OnlyLowerUnknownSize) {}
 No newline at end of file

llvm/trunk/test/Transforms/InstCombine/zero-string.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instcombine  -S | FileCheck %s
+
+declare i32 @strlen(i8* nocapture)
+declare noalias i8* @calloc(i32, i32)
+declare noalias i8* @malloc(i32)
+
+define i32 @calloc_strlen() {
+; CHECK-LABEL: @calloc_strlen(
+; CHECK-NEXT:    ret i32 0
+;
+  %call = tail call noalias i8* @calloc(i32 10, i32 1)
+  %call1 = tail call i32 @strlen(i8* %call)
+  ret i32 %call1
+}
+
+define i32 @calloc_strlen_not_const_nmemb(i32 %n) {
+; CHECK-LABEL: @calloc_strlen_not_const_nmemb(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call noalias i8* @calloc(i32 [[N:%.*]], i32 10)
+; CHECK-NEXT:    [[CALL1:%.*]] = tail call i32 @strlen(i8* [[CALL]])
+; CHECK-NEXT:    ret i32 [[CALL1]]
+;
+  %call = tail call noalias i8* @calloc(i32 %n, i32 10)
+  %call1 = tail call i32 @strlen(i8* %call) #4
+  ret i32 %call1
+}
+
+
+define i32 @calloc_strlen_not_const_size(i32 %size) {
+; CHECK-LABEL: @calloc_strlen_not_const_size(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call noalias i8* @calloc(i32 1, i32 [[SIZE:%.*]])
+; CHECK-NEXT:    [[CALL1:%.*]] = tail call i32 @strlen(i8* [[CALL]])
+; CHECK-NEXT:    ret i32 [[CALL1]]
+;
+  %call = tail call noalias i8* @calloc(i32 1, i32 %size)
+  %call1 = tail call i32 @strlen(i8* %call) #4
+  ret i32 %call1
+}
+
+
+define i32 @calloc_strlen_not_const_args(i32 %n, i32 %size) {
+; CHECK-LABEL: @calloc_strlen_not_const_args(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call noalias i8* @calloc(i32 [[N:%.*]], i32 [[SIZE:%.*]])
+; CHECK-NEXT:    [[CALL1:%.*]] = tail call i32 @strlen(i8* [[CALL]])
+; CHECK-NEXT:    ret i32 [[CALL1]]
+;
+  %call = tail call noalias i8* @calloc(i32 %n, i32 %size)
+  %call1 = tail call i32 @strlen(i8* %call) #4
+  ret i32 %call1
+}
+
+
+define i32 @malloc_strlen() {
+; CHECK-LABEL: @malloc_strlen(
+; CHECK-NEXT:    [[CALL:%.*]] = tail call noalias i8* @malloc(i32 10)
+; CHECK-NEXT:    [[CALL1:%.*]] = tail call i32 @strlen(i8* [[CALL]])
+; CHECK-NEXT:    ret i32 [[CALL1]]
+;
+  %call = tail call noalias i8* @malloc(i32 10)
+  %call1 = tail call i32 @strlen(i8* %call)
+  ret i32 %call1
+