[SimplifyLibCalls] Add dereferenceable bytes from known callsites

[xbolva00]

Summary

int mm(char *a, char *b) {

return memcmp(a,b,16);

}

Currently:
define dso_local i32 @mm(i8* nocapture readonly %a, i8* nocapture readonly %b) local_unnamed_addr #1 {
entry:

%call = tail call i32 @memcmp(i8* %a, i8* %b, i64 16)
ret i32 %call

}

After patch:
define dso_local i32 @mm(i8* nocapture readonly %a, i8* nocapture readonly %b) local_unnamed_addr #1 {
entry:

%call = tail call i32 @memcmp(i8* dereferenceable(16)  %a, i8* dereferenceable(16)  %b, i64 16)
ret i32 %call

}

[xbolva00]

Please @jdoerfert check it. I will add more tests when the code is OK.

[xbolva00]

lib/Transforms/Utils/SimplifyLibCalls.cpp

193

Copy paste from @spatel 's patch: https://reviews.llvm.org/D64258

We should find proper place for this.

[xbolva00]

Some ideas
1, + memchr
2, infer noalias as follow up

[jdoerfert]

I like the direction, first obstacle identified but solvable. We need tests.

lib/Transforms/Utils/SimplifyLibCalls.cpp

193

The Attributor has a similar, though more elaborate, utility which is not exposed yet. I would expect that to be usable but the interface is in flux right now. I'd go with this and a TODO note.

---

Edit: Reading through the use cases, maybe we should use the Attributor code which can handle more cases. What is happening here is not what we want, see my example below.

---

Proposal, do it here, sth like:

static void annotateDereferenceableBytes(CallSite CS, unsigned ArgNo, uint64_t DerefBytes) {
  if (CS.getDereferenceableBytes(ArgNo) < DerefBytes) {
    CS.removeParamAttr(ArgNo, Attribute::Dereferenceable);
    CS.removeParamAttr(ArgNo, Attribute::DereferenceableOrNull);
    // TODO: CallSite does not have an `addParamAttr` for integer attributes.
    CS.addAttribute(ArgNo + AttributeList::FirstArgIndex, Attribute::getWithDereferenceableBytes(CS->getContext(), DerefBytes));
  }
}

(I did not try to compile this!)

943

LHS and RHS are call site operands for which we deduced dereferenceability. Thus we want to annotate the call site. Now with this code, if I'm not mistaken, there are two possibilities for LHS, RHS is the same:

1. LHS is anything but an argument -> no annotation -> not what we want
2. LHS is an argument -> annotation at the argument -> not necessarily correct, see below:

We should not derive deref for the arguments a or b from the memcmp call. We can and should derive deref for their usage in the memcmp call.

void foo(int *a, int *b) {
  if (a && b)
    memcmp(a, b, 4);
}

983

What does the return value here mean? I'm also confused by the Op0 which was there already.

[xbolva00]

memchr support.

[xbolva00]

lib/Transforms/Utils/SimplifyLibCalls.cpp

943

Right. I also wanted to annotate callsite arguments but I didnt find a nice API.

I will try your code above.

983

nullptr means that nothing was simplified.

below, for memcpy, we can just turn memcpy libcall to memcpy intrinsic.

[xbolva00]

Thanks for review, I am going to address your notes now + tests.

[jdoerfert]

lib/Transforms/Utils/SimplifyLibCalls.cpp

983

but why is the pointer operand returned?

[xbolva00]

lib/Transforms/Utils/SimplifyLibCalls.cpp

983

llvm memcpy intrinsic "returns" void so in order to fix return value, we return dst pointer.

return memcpy(dst, ...)

to

llvm.memcpy(dst, ....)
return dst;

I dont know why this was designed this way :)

[xbolva00]

lib/Transforms/Utils/SimplifyLibCalls.cpp

983

https://llvm.org/docs/LangRef.html#llvm-memcpy-intrinsic

[xbolva00]

Addressed review tips.
Added tests. (extensive tests for memcmp, light tests for others)

[xbolva00]

(I havent run test suite yet, I expect many test files need to be updated.. I will do it tommorow)

lib/Transforms/Utils/SimplifyLibCalls.cpp

193

if (CI->getDereferenceableBytes(ArgNo + 1) < DerefBytes) {

quite surprising :) spent some time on find this :D

[jdoerfert]

One minor request, a few nits, LGTM.

lib/Transforms/Utils/SimplifyLibCalls.cpp

193

My bad, I added AttributeList::FirstArgIndex (= 1) below but forgot it above.
Can you replace 1 with AttributeList::FirstArgIndex please.

785

Maybe call annotateDereferenceableBytes after the zero check.

947

Again, I guess if the inner condition hits the annotations are lost (are they?). We could annotate afterwards.

987

I don't mind but you don't even need the Op0 .. changes anymore.

[xbolva00]

Fixed nits

[xbolva00]

Hello @jdoerfert.

I found another opportunity

char *d;

char * xmain(unsigned long n) {

char *s = malloc(32);
__builtin_memcpy(s, d, n);
return s;

}

define dso_local noalias i8* @xmain(i64 %n) local_unnamed_addr #0 {
entry:

%call = tail call i8* @malloc(i64 32)
%0 = load i8*, i8** @d, align 8, !tbaa !2
tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 1 %call, i8* align 1 %0, i64 %n, i1 false)
ret i8* %call

}

from malloc-like functions we can infer e.g. tail call void @llvm.memcpy.p0i8.p0i8.i64(i8*dereferenceable_or_null(32) align 1 %call, i8* align 1 %0, i64 %n, i1 false)

@spatel not sure what is best approach here.. in SLC's optimizeMalloc walk thru all malloc's users (+ sane threshold?) and annotate them?

[xbolva00]

Or by conservative (dont make IC much slower) and check only str(n)cpy, memcpy, memmove, memset buffers if they come from malloc/realloc/calloc?

Edit: maybe we can just add deref or null (C) to malloc ret value and it would do the right thing easily.

[jdoerfert]

In D66079#1630512, @xbolva00 wrote:

Edit: maybe we can just add deref or null (C) to malloc ret value and it would do the right thing easily.

Yes! That is what we should do.

include/llvm/Transforms/Utils/SimplifyLibCalls.h

private:
   Value *optimizeStrTo(CallInst *CI, IRBuilder<> &B);
   Value *optimizeStrSpn(CallInst *CI, IRBuilder<> &B);
   Value *optimizeStrCSpn(CallInst *CI, IRBuilder<> &B);
   Value *optimizeStrStr(CallInst *CI, IRBuilder<> &B);
   Value *optimizeMemChr(CallInst *CI, IRBuilder<> &B);
   Value *optimizeMemCmp(CallInst *CI, IRBuilder<> &B);
   Value *optimizeBCmp(CallInst *CI, IRBuilder<> &B);
   Value *optimizeMemCmpBCmpCommon(CallInst *CI, IRBuilder<> &B);
-  Value *optimizeMemCpy(CallInst *CI, IRBuilder<> &B);
-  Value *optimizeMemMove(CallInst *CI, IRBuilder<> &B);
-  Value *optimizeMemSet(CallInst *CI, IRBuilder<> &B);
+  Value *optimizeMemCpy(CallInst *CI, IRBuilder<> &B, bool isIntrinsic = false);
+  Value *optimizeMemMove(CallInst *CI, IRBuilder<> &B, bool isIntrinsic = false);
+  Value *optimizeMemSet(CallInst *CI, IRBuilder<> &B, bool isIntrinsic = false);
   Value *optimizeRealloc(CallInst *CI, IRBuilder<> &B);
   Value *optimizeWcslen(CallInst *CI, IRBuilder<> &B);
   // Wrapper for all String/Memory Library Call Optimizations
   Value *optimizeStringMemoryLibCall(CallInst *CI, IRBuilder<> &B);
 
   // Math Library Optimizations
   Value *optimizeCAbs(CallInst *CI, IRBuilder<> &B);
   Value *optimizePow(CallInst *CI, IRBuilder<> &B);

lib/Transforms/Utils/SimplifyLibCalls.cpp

if (!isDereferenceableAndAlignedPointer(Str, 1, APInt(64, Len), DL))
     return false;
 
   if (CI->getFunction()->hasFnAttribute(Attribute::SanitizeMemory))
     return false;
 
   return true;
 }
 
+static void inferDereferenceableBytes(Value *V, uint64_t DerefBytes) {
+  if (auto *Arg = dyn_cast<Argument>(V)) {
+    Function *F = Arg->getParent();
+    unsigned ArgNo = Arg->getArgNo();
+    if (F->getParamDereferenceableBytes(ArgNo) < DerefBytes) {
+      F->removeParamAttr(ArgNo, Attribute::Dereferenceable);
+      F->removeParamAttr(ArgNo, Attribute::DereferenceableOrNull);
+      F->addDereferenceableParamAttr(ArgNo, DerefBytes);
+    }
+  }
+}
+
 //===----------------------------------------------------------------------===//
 // String and Memory Library Call Optimizations
 //===----------------------------------------------------------------------===//
 
 Value *LibCallSimplifier::optimizeStrCat(CallInst *CI, IRBuilder<> &B) {
   // Extract some information from the instruction
   Value *Dst = CI->getArgOperand(0);
   Value *Src = CI->getArgOperand(1);
Value *LibCallSimplifier::optimizeMemChr(CallInst *CI, IRBuilder<> &B) {
   ConstantInt *LenC = dyn_cast<ConstantInt>(CI->getArgOperand(2));
 
   // memchr(x, y, 0) -> null
   if (LenC && LenC->isZero())
     return Constant::getNullValue(CI->getType());
 
   // From now on we need at least constant length and string.
   StringRef Str;
   if (!LenC || !getConstantStringInfo(SrcStr, Str, 0, /*TrimAtNul=*/false))
     return nullptr;
 
   // Truncate the string to LenC. If Str is smaller than LenC we will still only
   // scan the string, as reading past the end of it is undefined and we can just
   // return null if we don't find the char.
   Str = Str.substr(0, LenC->getZExtValue());
 
   // If the char is variable but the input str and length are not we can turn
Value *LibCallSimplifier::optimizeMemCmpBCmpCommon(CallInst *CI,
                                                    IRBuilder<> &B) {
   Value *LHS = CI->getArgOperand(0), *RHS = CI->getArgOperand(1);
   Value *Size = CI->getArgOperand(2);
 
   if (LHS == RHS) // memcmp(s,s,x) -> 0
     return Constant::getNullValue(CI->getType());
 
   // Handle constant lengths.
-  if (ConstantInt *LenC = dyn_cast<ConstantInt>(Size))
+  if (ConstantInt *LenC = dyn_cast<ConstantInt>(Size)) {
+    inferDereferenceableBytes(LHS, LenC->getZExtValue());
+    inferDereferenceableBytes(RHS, LenC->getZExtValue());
     if (Value *Res = optimizeMemCmpConstantSize(CI, LHS, RHS,
                                                 LenC->getZExtValue(), B, DL))
       return Res;
+  }
 
   return nullptr;
 }
 
 Value *LibCallSimplifier::optimizeMemCmp(CallInst *CI, IRBuilder<> &B) {
   if (Value *V = optimizeMemCmpBCmpCommon(CI, B))
     return V;
 
Value *LibCallSimplifier::optimizeMemCmp(CallInst *CI, IRBuilder<> &B) {
 
   return nullptr;
 }
 
 Value *LibCallSimplifier::optimizeBCmp(CallInst *CI, IRBuilder<> &B) {
   return optimizeMemCmpBCmpCommon(CI, B);
 }
 
-Value *LibCallSimplifier::optimizeMemCpy(CallInst *CI, IRBuilder<> &B) {
+Value *LibCallSimplifier::optimizeMemCpy(CallInst *CI, IRBuilder<> &B,
+                                         bool isIntrinsic) {
+  Value *Op0 = CI->getArgOperand(0), *Op1 = CI->getArgOperand(1);
+  Value *Size = CI->getArgOperand(2);
+  if (ConstantInt *LenC = dyn_cast<ConstantInt>(Size)) {
+    inferDereferenceableBytes(Op0, LenC->getZExtValue());
+    inferDereferenceableBytes(Op1, LenC->getZExtValue());
+  }
+
+  if (isIntrinsic)
+    return nullptr;
+
   // memcpy(x, y, n) -> llvm.memcpy(align 1 x, align 1 y, n)
-  B.CreateMemCpy(CI->getArgOperand(0), 1, CI->getArgOperand(1), 1,
-                 CI->getArgOperand(2));
-  return CI->getArgOperand(0);
+  B.CreateMemCpy(Op0, 1, Op1, 1, Size);
+  return Op0;
 }
 
-Value *LibCallSimplifier::optimizeMemMove(CallInst *CI, IRBuilder<> &B) {
+Value *LibCallSimplifier::optimizeMemMove(CallInst *CI, IRBuilder<> &B, bool isIntrinsic) {
+  Value *Op0 = CI->getArgOperand(0), *Op1 = CI->getArgOperand(1);
+  Value *Size = CI->getArgOperand(2);
+  if (ConstantInt *LenC = dyn_cast<ConstantInt>(Size)) {
+    inferDereferenceableBytes(Op0, LenC->getZExtValue());
+    inferDereferenceableBytes(Op1, LenC->getZExtValue());
+  }
+
+  if (isIntrinsic)
+    return nullptr;
+
   // memmove(x, y, n) -> llvm.memmove(align 1 x, align 1 y, n)
-  B.CreateMemMove(CI->getArgOperand(0), 1, CI->getArgOperand(1), 1,
-                  CI->getArgOperand(2));
-  return CI->getArgOperand(0);
+  B.CreateMemMove(Op0, 1, Op1, 1, Size);
+  return Op0;
 }
 
 /// Fold memset[_chk](malloc(n), 0, n) --> calloc(1, n).
 Value *LibCallSimplifier::foldMallocMemset(CallInst *Memset, IRBuilder<> &B) {
   // This has to be a memset of zeros (bzero).
   auto *FillValue = dyn_cast<ConstantInt>(Memset->getArgOperand(1));
   if (!FillValue || FillValue->getZExtValue() != 0)
     return nullptr;
if (!Calloc)
     return nullptr;
 
   Malloc->replaceAllUsesWith(Calloc);
   eraseFromParent(Malloc);
 
   return Calloc;
 }
 
-Value *LibCallSimplifier::optimizeMemSet(CallInst *CI, IRBuilder<> &B) {
+Value *LibCallSimplifier::optimizeMemSet(CallInst *CI, IRBuilder<> &B,
+                                         bool isIntrinsic) {
+  Value *Op0 = CI->getArgOperand(0), *Op1 = CI->getArgOperand(1);
+  Value *Size = CI->getArgOperand(2);
+  if (ConstantInt *LenC = dyn_cast<ConstantInt>(Size)) {
+    inferDereferenceableBytes(Op0, LenC->getZExtValue());
+    inferDereferenceableBytes(Op1, LenC->getZExtValue());
+  }
+
+  if (isIntrinsic)
+    return nullptr;
+
   if (auto *Calloc = foldMallocMemset(CI, B))
     return Calloc;
 
   // memset(p, v, n) -> llvm.memset(align 1 p, v, n)
-  Value *Val = B.CreateIntCast(CI->getArgOperand(1), B.getInt8Ty(), false);
-  B.CreateMemSet(CI->getArgOperand(0), Val, CI->getArgOperand(2), 1);
-  return CI->getArgOperand(0);
+  Value *Val = B.CreateIntCast(Op1, B.getInt8Ty(), false);
+  B.CreateMemSet(Op0, Val, Size, 1);
+  return Op0;
 }
 
 Value *LibCallSimplifier::optimizeRealloc(CallInst *CI, IRBuilder<> &B) {
   if (isa<ConstantPointerNull>(CI->getArgOperand(0)))
     return emitMalloc(CI->getArgOperand(1), B, DL, TLI);
 
   return nullptr;
 }
case Intrinsic::pow:
       return optimizePow(CI, Builder);
     case Intrinsic::exp2:
       return optimizeExp2(CI, Builder);
     case Intrinsic::log:
       return optimizeLog(CI, Builder);
     case Intrinsic::sqrt:
       return optimizeSqrt(CI, Builder);
     // TODO: Use foldMallocMemset() with memset intrinsic.
+    case Intrinsic::memset:
+      return optimizeMemSet(CI, Builder, true);
+    case Intrinsic::memcpy:
+      return optimizeMemCpy(CI, Builder, true);
+    case Intrinsic::memmove:
+      return optimizeMemMove(CI, Builder, true);
     default:
       return nullptr;
     }
   }
 
   // Also try to simplify calls to fortified library functions.
   if (Value *SimplifiedFortifiedCI = FortifiedSimplifier.optimizeCall(CI)) {
     // Try to further simplify the result.