Index: include/llvm/Analysis/MemoryLocation.h =================================================================== --- include/llvm/Analysis/MemoryLocation.h +++ include/llvm/Analysis/MemoryLocation.h @@ -67,16 +67,19 @@ /// Return a location with information about the memory reference by the given /// instruction. + static MemoryLocation get(const CallInst *CI, const Value *Op); static MemoryLocation get(const LoadInst *LI); static MemoryLocation get(const StoreInst *SI); static MemoryLocation get(const VAArgInst *VI); static MemoryLocation get(const AtomicCmpXchgInst *CXI); static MemoryLocation get(const AtomicRMWInst *RMWI); - static MemoryLocation get(const Instruction *Inst) { - return *MemoryLocation::getOrNone(Inst); + static MemoryLocation get(const Instruction *Inst, const Value *Op = nullptr) { + return *MemoryLocation::getOrNone(Inst, Op); } - static Optional getOrNone(const Instruction *Inst) { + static Optional getOrNone(const Instruction *Inst, const Value *Op = nullptr) { switch (Inst->getOpcode()) { + case Instruction::Call: + return get(cast(Inst), Op); case Instruction::Load: return get(cast(Inst)); case Instruction::Store: Index: lib/Analysis/MemoryLocation.cpp =================================================================== --- lib/Analysis/MemoryLocation.cpp +++ lib/Analysis/MemoryLocation.cpp @@ -18,6 +18,13 @@ #include "llvm/IR/Type.h" using namespace llvm; +MemoryLocation MemoryLocation::get(const CallInst *CI, const Value *Op) { + AAMDNodes AATags; + CI->getAAMetadata(AATags); + + return MemoryLocation(Op, UnknownSize, AATags); +} + MemoryLocation MemoryLocation::get(const LoadInst *LI) { AAMDNodes AATags; LI->getAAMetadata(AATags); Index: lib/Transforms/Scalar/DeadStoreElimination.cpp =================================================================== --- lib/Transforms/Scalar/DeadStoreElimination.cpp +++ lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -577,8 +577,10 @@ /// Precondition: Second instruction must be dominated by the first /// instruction. static bool memoryIsNotModifiedBetween(Instruction *FirstI, - Instruction *SecondI, - AliasAnalysis *AA) { + Instruction *SecondI, AliasAnalysis *AA, + const Value *Op = nullptr) { + if (FirstI == SecondI) + return true; SmallVector WorkList; SmallPtrSet Visited; BasicBlock::iterator FirstBBI(FirstI); @@ -586,7 +588,7 @@ BasicBlock::iterator SecondBBI(SecondI); BasicBlock *FirstBB = FirstI->getParent(); BasicBlock *SecondBB = SecondI->getParent(); - MemoryLocation MemLoc = MemoryLocation::get(SecondI); + MemoryLocation MemLoc = MemoryLocation::get(SecondI, Op); // Start checking the store-block. WorkList.push_back(SecondBB); @@ -1059,6 +1061,83 @@ return false; } +static bool isStringFromCalloc(const Value *Str, const TargetLibraryInfo *TLI) { + const CallInst *Calloc = dyn_cast(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(Calloc->getOperand(0)); + const ConstantInt *Size = dyn_cast(Calloc->getOperand(1)); + + if (!N || !Size) + return false; + + if (N->isNullValue() || Size->isNullValue()) + return false; + + return true; +} + +static bool eliminateStrlen(CallInst *CI, BasicBlock::iterator &BBI, + AliasAnalysis *AA, MemoryDependenceResults *MD, + const DataLayout &DL, const TargetLibraryInfo *TLI, + InstOverlapIntervalsTy &IOL, + DenseMap *InstrOrdering) { + + // Must be a strlen. + LibFunc Func; + Function *Callee = CI->getCalledFunction(); + if (!Callee) + return false; + + if (!TLI->getLibFunc(*Callee, Func) || !TLI->has(Func) || + Func != LibFunc_strlen) + return false; + + Value *Dst = CI->getOperand(0); + Instruction *UnderlyingPointer = + dyn_cast(GetUnderlyingObject(Dst, DL)); + + if (!UnderlyingPointer) + return false; + + if (!isStringFromCalloc(Dst, TLI)) + return false; + + if (memoryIsNotModifiedBetween(UnderlyingPointer, CI, AA, Dst)) { + Value *Len = ConstantInt::get(CI->getType(), 0); + CI->replaceAllUsesWith(Len); + CI->eraseFromParent(); + return true; + } + return false; +} + +static bool eliminateLibCalls(Instruction *Inst, BasicBlock::iterator &BBI, + AliasAnalysis *AA, MemoryDependenceResults *MD, + const DataLayout &DL, + const TargetLibraryInfo *TLI, + InstOverlapIntervalsTy &IOL, + DenseMap *InstrOrdering) { + CallInst *CI = dyn_cast(Inst); + if (!CI) + return false; + + bool Changed = false; + Changed |= eliminateStrlen(CI, BBI, AA, MD, DL, TLI, IOL, InstrOrdering); + // more to be added later + return Changed; +} + static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA, MemoryDependenceResults *MD, DominatorTree *DT, const TargetLibraryInfo *TLI) { @@ -1087,6 +1166,12 @@ Instruction *Inst = &*BBI++; + // eliminate/replace library calls + if (eliminateLibCalls(Inst, BBI, AA, MD, DL, TLI, IOL, &InstrOrdering)) { + MadeChange = true; + continue; + } + size_t CurInstNumber = InstrIndex++; InstrOrdering.insert(std::make_pair(Inst, CurInstNumber)); if (Inst->mayThrow()) { Index: test/Transforms/DeadStoreElimination/zero-string.ll =================================================================== --- test/Transforms/DeadStoreElimination/zero-string.ll +++ test/Transforms/DeadStoreElimination/zero-string.ll @@ -0,0 +1,75 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -dse -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 +} + +define i32 @calloc_strlen_write_between() { +; CHECK-LABEL: @calloc_strlen_write_between( +; CHECK-NEXT: [[CALL:%.*]] = tail call noalias i8* @calloc(i32 10, i32 1) +; CHECK-NEXT: store i8 97, i8* [[CALL]], align 1 +; CHECK-NEXT: [[CALL1:%.*]] = tail call i32 @strlen(i8* [[CALL]]) +; CHECK-NEXT: ret i32 [[CALL1]] +; + %call = tail call noalias i8* @calloc(i32 10, i32 1) + store i8 97, i8* %call, align 1 + %call1 = tail call i32 @strlen(i8* %call) + ret i32 %call1 +}