[SimplifyLibcalls] Realloc(null, N) -> Malloc(N)

[xbolva00]

Summary

realloc(null, N) -> malloc(N)

[xbolva00]

I would like to hear your feedback on these three changes

1. malloc(N) + realloc(ptr, N + X) -> fold to -> malloc(N + X), remove realloc
2. malloc(N) + realloc(ptr, N - X) -> fold to -> malloc(N), remove realloc
3. realloc(NULL, N) -> malloc(N)

@efriedma @lebedev.ri @spatel and others...

Edit: I think only 3. should stay in this patch..

lib/Transforms/Utils/SimplifyLibCalls.cpp

847

This is somehow problematic, if I remove this check, this code will crash on 32bit.

define i8* @foo(i32 %n) #0 {

%call = call noalias i8* @malloc(i32 %n) #2
%add = add nsw i32 %n, 2
%call1 = call i8* @realloc(i8* %call, i32 %add) #2
ret i8* %call1

}

Any ideas why, @spatel @efriedma ?

[efriedma]

lib/Transforms/Utils/BuildLibCalls.cpp

1048

Why are the implementations of emitMalloc and emitCalloc different? (I'm specifically concerned about missing call to inferLibFuncAttributes.)

test/Transforms/InstCombine/realloc.ll

13

This doesn't look like it's what you meant to test.

[xbolva00]

test/Transforms/InstCombine/realloc.ll

13

oh yes, I will rework test soon.

[xbolva00]

test/Transforms/InstCombine/realloc.ll

13

Done.

[efriedma]

lib/Transforms/Utils/BuildLibCalls.cpp

1051

This isn't right; should be TLI->has(LibFunc_calloc).

[xbolva00]

lib/Transforms/Utils/BuildLibCalls.cpp

1051

Fixed.

Anyway, emitCalloc function I just copied from SimplifyLibCalls since it has no sense to have it there. So some time ago when it was merged and there was without proper review?

[xbolva00]

Any review or merge? @spatel ?

[efriedma]

LGTM

[xbolva00]

In D45413#1068982, @efriedma wrote:

LGTM

I have no write access, so somebody must merge it. @spatel ?

[spatel]

The patch doesn't compile as-is. Please post a corrected patch.

/llvm/lib/Transforms/Utils/BuildLibCalls.cpp:1061:11: error: member reference type 'const llvm::TargetLibraryInfo' is not a pointer; did you mean to use
      '.'?
  if (!TLI->has(LibFunc_calloc))
       ~~~^~
          .
/llvm/lib/Transforms/Utils/BuildLibCalls.cpp:1069:53: error: indirection requires pointer operand ('const llvm::TargetLibraryInfo' invalid)
  inferLibFuncAttributes(*M->getFunction("calloc"), *TLI);

include/llvm/Transforms/Utils/BuildLibCalls.h

namespace llvm {
   /// File is a pointer to FILE.
   Value *emitFPutS(Value *Str, Value *File, IRBuilder<> &B,
                    const TargetLibraryInfo *TLI);
 
   /// Emit a call to the fwrite function. This assumes that Ptr is a pointer,
   /// Size is an 'intptr_t', and File is a pointer to FILE.
   Value *emitFWrite(Value *Ptr, Value *Size, Value *File, IRBuilder<> &B,
                     const DataLayout &DL, const TargetLibraryInfo *TLI);
+
+  /// Emit a call to the malloc function.
+  Value *emitMalloc(Value *Len, IRBuilder<> &B, const DataLayout &DL,
+                    const TargetLibraryInfo *TLI);
+
+  /// Emit a call to the calloc function.
+  Value *emitCalloc(Value *Num, Value *Size, const AttributeList &Attrs,
+                    IRBuilder<> &B, const TargetLibraryInfo &TLI)
 }
 
 #endif

include/llvm/Transforms/Utils/SimplifyLibCalls.h

private:
   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 *optimizeMemCpy(CallInst *CI, IRBuilder<> &B);
   Value *optimizeMemMove(CallInst *CI, IRBuilder<> &B);
   Value *optimizeMemSet(CallInst *CI, IRBuilder<> &B);
+  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 *optimizeCos(CallInst *CI, IRBuilder<> &B);
   Value *optimizePow(CallInst *CI, IRBuilder<> &B);

lib/Transforms/Utils/BuildLibCalls.cpp

Value *llvm::emitFWrite(Value *Ptr, Value *Size, Value *File, IRBuilder<> &B,
   CallInst *CI =
       B.CreateCall(F, {castToCStr(Ptr, B), Size,
                        ConstantInt::get(DL.getIntPtrType(Context), 1), File});
 
   if (const Function *Fn = dyn_cast<Function>(F->stripPointerCasts()))
     CI->setCallingConv(Fn->getCallingConv());
   return CI;
 }
+
+Value *llvm::emitMalloc(Value *Len, IRBuilder<> &B, const DataLayout &DL,
+                        const TargetLibraryInfo *TLI) {
+  if (!TLI->has(LibFunc_malloc))
+    return nullptr;
+
+  Module *M = B.GetInsertBlock()->getModule();
+  LLVMContext &Context = B.GetInsertBlock()->getContext();
+  Value *Malloc = M->getOrInsertFunction("malloc", B.getInt8PtrTy(),
+                                         DL.getIntPtrType(Context));
+  inferLibFuncAttributes(*M->getFunction("malloc"), *TLI);
+  CallInst *CI = B.CreateCall(Malloc, Len, "malloc");
+
+  if (const Function *F = dyn_cast<Function>(Malloc->stripPointerCasts()))
+    CI->setCallingConv(F->getCallingConv());
+
+  return CI;
+}
+
+Value *llvm::emitCalloc(Value *Num, Value *Size, const AttributeList &Attrs,
+                  IRBuilder<> &B, const TargetLibraryInfo &TLI) {
+  LibFunc Func;
+  if (!TLI.getLibFunc("calloc", Func) || !TLI.has(Func))
+    return nullptr;
+
+  Module *M = B.GetInsertBlock()->getModule();
+  const DataLayout &DL = M->getDataLayout();
+  IntegerType *PtrType = DL.getIntPtrType((B.GetInsertBlock()->getContext()));
+  Value *Calloc = M->getOrInsertFunction("calloc", Attrs, B.getInt8PtrTy(),
+                                         PtrType, PtrType);
+  CallInst *CI = B.CreateCall(Calloc, {Num, Size}, "calloc");
+
+  if (const auto *F = dyn_cast<Function>(Calloc->stripPointerCasts()))
+    CI->setCallingConv(F->getCallingConv());
+
+  return CI;
+}

lib/Transforms/Utils/SimplifyLibCalls.cpp

 
 Value *LibCallSimplifier::optimizeMemMove(CallInst *CI, IRBuilder<> &B) {
   // 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);
 }
 
-// TODO: Does this belong in BuildLibCalls or should all of those similar
-// functions be moved here?
-static Value *emitCalloc(Value *Num, Value *Size, const AttributeList &Attrs,
-                         IRBuilder<> &B, const TargetLibraryInfo &TLI) {
+
+// Fold malloc with realloc to just malloc, if possible
+static Value *foldMallocRealloc(CallInst *Realloc, IRBuilder<> &B,
+                                const DataLayout &DL,
+                                const TargetLibraryInfo &TLI) {
+  // realloc(Src, NewSize)
+  Value *ReallocSize = Realloc->getArgOperand(1);
+  auto *Dst = Realloc->getArgOperand(0);
+
+  auto *Malloc = dyn_cast<CallInst>(Dst);
+  if (!Malloc)
+    return nullptr;
+
+  Function *InnerCallee = Malloc->getCalledFunction();
+  if (!InnerCallee)
+    return nullptr;
+
+  // check if malloc
   LibFunc Func;
-  if (!TLI.getLibFunc("calloc", Func) || !TLI.has(Func))
+  if (!TLI.getLibFunc(*InnerCallee, Func) || !TLI.has(Func) ||
+      Func != LibFunc_malloc)
     return nullptr;
 
-  Module *M = B.GetInsertBlock()->getModule();
-  const DataLayout &DL = M->getDataLayout();
-  IntegerType *PtrType = DL.getIntPtrType((B.GetInsertBlock()->getContext()));
-  Value *Calloc = M->getOrInsertFunction("calloc", Attrs, B.getInt8PtrTy(),
-                                         PtrType, PtrType);
-  CallInst *CI = B.CreateCall(Calloc, { Num, Size }, "calloc");
+  bool isSExt = false;
+  BinaryOperator *BinOp = nullptr;
+  if (auto *SE = dyn_cast<SExtInst>(ReallocSize)) {
+    isSExt = true;
+    BinOp = dyn_cast<BinaryOperator>(SE->getOperand(0));
+  } else {
+    BinOp = dyn_cast<BinaryOperator>(ReallocSize);
+  }
 
-  if (const auto *F = dyn_cast<Function>(Calloc->stripPointerCasts()))
-    CI->setCallingConv(F->getCallingConv());
+  if (!isSExt && Dst->hasOneUse())
+    return nullptr;
 
-  return CI;
+  if (!BinOp)
+    return nullptr;
+
+  // lhs of BinOp has to be size paramater in malloc
+  Value *MallocSize = Malloc->getOperand(0);
+  auto *SE = dyn_cast<SExtInst>(Malloc->getOperand(0));
+  if (isSExt) {
+    if (SE->getOperand(0) != BinOp->getOperand(0))
+      return nullptr;
+  } else {
+    if (MallocSize != BinOp->getOperand(0))
+      return nullptr;
+  }
+
+  // if new size > old size, malloc can use new size
+  // if new size < old size, realloc can go away
+  auto OpCode = BinOp->getOpcode();
+  if (OpCode == Instruction::Add || OpCode == Instruction::Mul) {
+    if (auto *CInt = dyn_cast<ConstantInt>(BinOp->getOperand(1))) {
+      // malloc(n), realloc(ptr, n+x) -> malloc(n+x)
+      if (CInt->getSExtValue() > 0) {
+        B.SetInsertPoint(Malloc->getParent(), --Malloc->getIterator());
+        if (isSExt) {
+          Value *BinOp = B.CreateBinOp(OpCode, SE->getOperand(0), CInt);
+          Malloc->setOperand(0, B.CreateSExt(BinOp, ReallocSize->getType()));
+        } else {
+          Malloc->setOperand(0, B.CreateBinOp(OpCode, MallocSize, CInt));
+        }
+      }
+
+      // remove realloc if reallocing to smaller size
+      // malloc(n), realloc(ptr, n-x) -> malloc(x);
+      return Dst;
+    }
+  }
+
+  return nullptr;
 }
 
 /// Fold memset[_chk](malloc(n), 0, n) --> calloc(1, n).
 static Value *foldMallocMemset(CallInst *Memset, IRBuilder<> &B,
                                const TargetLibraryInfo &TLI) {
   // This has to be a memset of zeros (bzero).
   auto *FillValue = dyn_cast<ConstantInt>(Memset->getArgOperand(1));
   if (!FillValue || FillValue->getZExtValue() != 0)
if (auto *Calloc = foldMallocMemset(CI, B, *TLI))
     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 *LibCallSimplifier::optimizeRealloc(CallInst *CI, IRBuilder<> &B) {
+  if (match(CI->getArgOperand(0), m_Zero()))
+    return emitMalloc(CI->getArgOperand(1), B, DL, TLI);
+
+  if (Value *V = foldMallocRealloc(CI, B, DL, *TLI))
+    return V;
+
+  return nullptr;
+}
+
 //===----------------------------------------------------------------------===//
 // Math Library Optimizations
 //===----------------------------------------------------------------------===//
 
 /// Return a variant of Val with float type.
 /// Currently this works in two cases: If Val is an FPExtension of a float
 /// value to something bigger, simply return the operand.
 /// If Val is a ConstantFP but can be converted to a float ConstantFP without
if (TLI->getLibFunc(*Callee, Func) && TLI->has(Func)) {
     case LibFunc_memcmp:
       return optimizeMemCmp(CI, Builder);
     case LibFunc_memcpy:
       return optimizeMemCpy(CI, Builder);
     case LibFunc_memmove:
       return optimizeMemMove(CI, Builder);
     case LibFunc_memset:
       return optimizeMemSet(CI, Builder);
+    case LibFunc_realloc:
+      return optimizeRealloc(CI, Builder);
     case LibFunc_wcslen:
       return optimizeWcslen(CI, Builder);
     default:
       break;
     }
   }
   return nullptr;
 }

test/Transforms/InstCombine/realloc.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
+; Function Attrs: nounwind
+declare i8* @realloc(i8*, i64) #1
+
+; Function Attrs: nounwind
+declare noalias i8* @malloc(i64) #1
+
+; Function Attrs: noinline nounwind uwtable
 define i8* @malloc_realloc_1(i32 %n) #0 {
 ; CHECK-LABEL: @malloc_realloc_1(
-; CHECK-NEXT:    [[CALL:%.*]] = call noalias i8* @malloc(i32 [[N:%.*]])
-; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[N]], 12
-; CHECK-NEXT:    [[CALL1:%.*]] = call i8* @realloc(i8* [[CALL]], i32 [[ADD]])
-; CHECK-NEXT:    ret i8* [[CALL1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[N:%.*]], 12
+; CHECK-NEXT:    [[TMP2:%.*]] = sext i32 [[TMP1]] to i64
+; CHECK-NEXT:    [[CALL:%.*]] = call noalias i8* @malloc(i64 [[TMP2]])
+; CHECK-NEXT:    ret i8* [[CALL]]
 ;
-  %call = call noalias i8* @malloc(i32 %n) #2
-  %add = add nsw i32 %n, 12
-  %call1 = call i8* @realloc(i8* %call, i32 %add) #2
-  ret i8* %call1
+  %conv = sext i32 %n to i64
+  %call = call noalias i8* @malloc(i64 %conv) #2
+  %mul = mul nsw i32 %n, 12
+  %conv1 = sext i32 %mul to i64
+  %call2 = call i8* @realloc(i8* %call, i64 %conv1) #2
+  ret i8* %call2
 }
 
-; Function Attrs: nounwind
-declare i8* @realloc(i8*, i32) #1
-
-; Function Attrs: nounwind
-declare noalias i8* @malloc(i32) #1
-
-; Function Attrs: noinline nounwind
+; Function Attrs: noinline nounwind uwtable
 define i8* @malloc_realloc_2(i32 %n) #0 {
 ; CHECK-LABEL: @malloc_realloc_2(
-; CHECK-NEXT:    [[CALL:%.*]] = call noalias i8* @malloc(i32 [[N:%.*]])
-; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[N]], 12
-; CHECK-NEXT:    [[CALL1:%.*]] = call i8* @realloc(i8* [[CALL]], i32 [[MUL]])
-; CHECK-NEXT:    ret i8* [[CALL1]]
+; CHECK-NEXT:    [[CONV:%.*]] = sext i32 [[N:%.*]] to i64
+; CHECK-NEXT:    [[CALL:%.*]] = call noalias i8* @malloc(i64 [[CONV]])
+; CHECK-NEXT:    ret i8* [[CALL]]
 ;
-  %call = call noalias i8* @malloc(i32 %n) #2
-  %mul = mul nsw i32 %n, 12
-  %call1 = call i8* @realloc(i8* %call, i32 %mul) #2
-  ret i8* %call1
+  %conv = sext i32 %n to i64
+  %call = call noalias i8* @malloc(i64 %conv) #2
+  %sub = add nsw i32 %n, -12
+  %conv1 = sext i32 %sub to i64
+  %call2 = call i8* @realloc(i8* %call, i64 %conv1) #2
+  ret i8* %call2
 }
 
-; Function Attrs: noinline nounwind
+; Function Attrs: noinline nounwind uwtable
 define i8* @malloc_realloc_3(i32 %n) #0 {
 ; CHECK-LABEL: @malloc_realloc_3(
-; CHECK-NEXT:    [[CALL:%.*]] = call noalias i8* @malloc(i32 [[N:%.*]])
-; CHECK-NEXT:    [[SUB:%.*]] = add nsw i32 [[N]], -12
-; CHECK-NEXT:    [[CALL1:%.*]] = call i8* @realloc(i8* [[CALL]], i32 [[SUB]])
-; CHECK-NEXT:    ret i8* [[CALL1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[N:%.*]], 12
+; CHECK-NEXT:    [[TMP2:%.*]] = sext i32 [[TMP1]] to i64
+; CHECK-NEXT:    [[CALL:%.*]] = call noalias i8* @malloc(i64 [[TMP2]])
+; CHECK-NEXT:    ret i8* [[CALL]]
 ;
-  %call = call noalias i8* @malloc(i32 %n) #2
-  %sub = add nsw i32 %n, -12
-  %call1 = call i8* @realloc(i8* %call, i32 %sub) #2
-  ret i8* %call1
+  %conv = sext i32 %n to i64
+  %call = call noalias i8* @malloc(i64 %conv) #2
+  %add = add nsw i32 %n, 12
+  %conv1 = sext i32 %add to i64
+  %call2 = call i8* @realloc(i8* %call, i64 %conv1) #2
+  ret i8* %call2
 }
 
-; Function Attrs: noinline nounwind
+; Function Attrs: noinline nounwind uwtable
 define i8* @realloc_to_malloc(i32 %n) #0 {
 ; CHECK-LABEL: @realloc_to_malloc(
-; CHECK-NEXT:    [[MALLOC:%.*]] = call i8* @malloc(i32 [[N:%.*]])
+; CHECK-NEXT:    [[CONV:%.*]] = sext i32 [[N:%.*]] to i64
+; CHECK-NEXT:    [[MALLOC:%.*]] = call i8* @malloc(i64 [[CONV]])
 ; CHECK-NEXT:    ret i8* [[MALLOC]]
 ;
-  %malloc = call i8* @malloc(i32 %n)
-  ret i8* %malloc
-}
+  %conv = sext i32 %n to i64
+  %call = call i8* @realloc(i8* null, i64 %conv) #2
+  ret i8* %call
+}