Index: include/llvm/Transforms/Utils/BuildLibCalls.h =================================================================== --- include/llvm/Transforms/Utils/BuildLibCalls.h +++ include/llvm/Transforms/Utils/BuildLibCalls.h @@ -120,6 +120,14 @@ /// 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 Index: include/llvm/Transforms/Utils/SimplifyLibCalls.h =================================================================== --- include/llvm/Transforms/Utils/SimplifyLibCalls.h +++ include/llvm/Transforms/Utils/SimplifyLibCalls.h @@ -124,6 +124,7 @@ 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); Index: lib/Transforms/Utils/BuildLibCalls.cpp =================================================================== --- lib/Transforms/Utils/BuildLibCalls.cpp +++ lib/Transforms/Utils/BuildLibCalls.cpp @@ -1026,3 +1026,40 @@ 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(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(Calloc->stripPointerCasts())) + CI->setCallingConv(F->getCallingConv()); + + return CI; +} Index: lib/Transforms/Utils/SimplifyLibCalls.cpp =================================================================== --- lib/Transforms/Utils/SimplifyLibCalls.cpp +++ lib/Transforms/Utils/SimplifyLibCalls.cpp @@ -811,25 +811,78 @@ 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(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(ReallocSize)) { + isSExt = true; + BinOp = dyn_cast(SE->getOperand(0)); + } else { + BinOp = dyn_cast(ReallocSize); + } + + if (!isSExt && Dst->hasOneUse()) + return nullptr; - if (const auto *F = dyn_cast(Calloc->stripPointerCasts())) - CI->setCallingConv(F->getCallingConv()); + if (!BinOp) + return nullptr; - return CI; + // lhs of BinOp has to be size paramater in malloc + Value *MallocSize = Malloc->getOperand(0); + auto *SE = dyn_cast(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(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). @@ -889,6 +942,16 @@ 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 //===----------------------------------------------------------------------===// @@ -2080,6 +2143,8 @@ 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: Index: test/Transforms/InstCombine/realloc.ll =================================================================== --- /dev/null +++ test/Transforms/InstCombine/realloc.ll @@ -1,59 +1,67 @@ ; 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 -} \ No newline at end of file + %conv = sext i32 %n to i64 + %call = call i8* @realloc(i8* null, i64 %conv) #2 + ret i8* %call +}