[DSE] Calloc-strlen optimizations

[xbolva00]

Summary

Transforms:
strlen(calloc(...)) -> 0

[xbolva00]

lib/Analysis/MemoryLocation.cpp

24

To add support for other ops, maybe extend function to
MemoryLocation::get(const CallInst *CI, const Value *Op)?

lib/Transforms/Scalar/DeadStoreElimination.cpp

1108

eliminateNoopStore uses "isCallocLikeFn" (does it check if any of the arguments is zero?), but I believe I could not use it here. Suggestions?

[xbolva00]

lib/Transforms/Scalar/DeadStoreElimination.cpp

1409–1410

Sorry for removal, my debug lines were here.

I will restore these empty lines in the next patch update.

[xbolva00]

• Restored blank lines
• Better get for CallInst
• Other improvements

[vsk]

Is this a common pattern, or are there real-world benchmarks this improves?

This adds a fair bit of code to a hot part of the compiler, so it'd be worth sharing LNT and CTMark data to make sure there aren't any regressions (http://llvm.org/docs/lnt/quickstart.html, https://github.com/llvm-mirror/test-suite/tree/master/CTMark).

[xbolva00]

In D47237#1109008, @vsk wrote:

Is this a common pattern, or are there real-world benchmarks this improves?

This adds a fair bit of code to a hot part of the compiler, so it'd be worth sharing LNT and CTMark data to make sure there aren't any regressions (http://llvm.org/docs/lnt/quickstart.html, https://github.com/llvm-mirror/test-suite/tree/master/CTMark).

I will try to run that benchmarks, but I see no reasons for regressions, but I will check it :)

This patch also introduces "base" in DSE for more future transformations like:
memset(s, 0, len)
strlen(s) --> 0

And also in the future we can finally do proper malloc+memset folding to calloc (currently there is suboptimal code for it in InstCombine)

Edit: data from CTMark: https://www.diffchecker.com/Zs5boksn

[xbolva00]

lib/Analysis/MemoryLocation.cpp

22

Self note: add assert for nonnull Op.

lib/Transforms/Scalar/DeadStoreElimination.cpp

1125

I would like to also reduce number of args here, since we don't need some of them.

new name: optimizeLibCalls?

1133

I should check if CI->isNoBuiltin, I will fix it later

1136

I would like to do here a similar switch like the one in SimplifyLibCalls

Value *NewInst = nullptr;
switch (...) {

case LibFunc_strlen:
     NewInst = optimizeStrlen(CI, BBI, AA, MD, DL, TLI, IOL, InstrOrdering);
     break;
 ....

}

if (NewInst) {

CI->replaceAllUsesWith(NewInst);
CI->eraseFromParent();
return true;

}

Suggestions?

[vsk]

In D47237#1109013, @xbolva00 wrote:

In D47237#1109008, @vsk wrote:

Is this a common pattern, or are there real-world benchmarks this improves?

This adds a fair bit of code to a hot part of the compiler, so it'd be worth sharing LNT and CTMark data to make sure there aren't any regressions (http://llvm.org/docs/lnt/quickstart.html, https://github.com/llvm-mirror/test-suite/tree/master/CTMark).

I will try to run that benchmarks, but I see no reasons for regressions, but I will check it :)

Thanks. For patches which touch hot and/or performance-sensitive parts of the compiler, it's standard practice to provide benchmark results. This is a basic way to communicate improvements and to catch regressions (both performance & compile-time).

This patch also introduces "base" in DSE for more future transformations like:
memset(s, 0, len)
strlen(s) --> 0

And also in the future we can finally do proper malloc+memset folding to calloc (currently there is suboptimal code for it in InstCombine)

Edit: data from CTMark: https://www.diffchecker.com/Zs5boksn

Could you aggregate this data over multiple runs, and report some statistics so we can compare the baseline versus the patched compiler at a high-level? The same goes for LNT. It would be useful to see if/how the geomean execution time & compile time change. For individual benchmarks, it's standard practice to share which benchmarks improve the most (& by how much), and which benchmarks regress.

[xbolva00]

Thanks, yes, sure!

But I would like to fix things from the code review, maybe @efriedma can look at it? He already gave me some advices related to DSE. After major notes would be addressed, I would do benchmarks :)

[efriedma]

I can't imagine a situation where this transform would trigger in practice... but maybe I don't write enough C code. How often does this trigger on some large codebase, like the LLVM testsuite?

include/llvm/Analysis/MemoryLocation.h

82

I'd rather not mess with this interface... if the instruction is a call, the caller needs to be more aware of what exactly it's asking for (since it could access any number of different memory locations).

lib/Analysis/MemoryLocation.cpp

23

TBAA metadata doesn't get applied to calls (I'm not sure what the semantics would be), so you probably don't need to call getAAMetadata.

lib/Transforms/Scalar/DeadStoreElimination.cpp

581

Can you just make the MemoryLocation a parameter here? I don't think your changes to MemoryLocation.h are useful.

1085

There's no point to checking whether one of the arguments is zero. We can assume they're non-zero because strlen(nullptr) has undefined behavior.

[xbolva00]

In D47237#1111835, @efriedma wrote:

I can't imagine a situation where this transform would trigger in practice... but maybe I don't write enough C code. How often does this trigger on some large codebase, like the LLVM testsuite?

Currently, this is rare, but folding malloc + memset to calloc will bring more hints. This patch also introduces "support for CallInst" in MemoryLocation - what is a nice thing for any future patches.

[xbolva00]

lib/Transforms/Scalar/DeadStoreElimination.cpp

581

Good point! Thanks.

[xbolva00]

lib/Analysis/MemoryLocation.cpp

23

Thanks for info.. So things will become simpler.

include/llvm/Analysis/MemoryLocation.h

public:
   uint64_t Size;
 
   /// The metadata nodes which describes the aliasing of the location (each
   /// member is null if that kind of information is unavailable).
   AAMDNodes AATags;
 
   /// 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<MemoryLocation> getOrNone(const Instruction *Inst) {
+  static Optional<MemoryLocation> getOrNone(const Instruction *Inst, const Value *Op = nullptr) {
     switch (Inst->getOpcode()) {
+    case Instruction::Call:
+      return get(cast<CallInst>(Inst), Op);
     case Instruction::Load:
       return get(cast<LoadInst>(Inst));
     case Instruction::Store:
       return get(cast<StoreInst>(Inst));
     case Instruction::VAArg:
       return get(cast<VAArgInst>(Inst));
     case Instruction::AtomicCmpXchg:
       return get(cast<AtomicCmpXchgInst>(Inst));

lib/Analysis/MemoryLocation.cpp

 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #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);
   const auto &DL = LI->getModule()->getDataLayout();
 
   return MemoryLocation(LI->getPointerOperand(),
                         DL.getTypeStoreSize(LI->getType()), AATags);
 }

lib/Transforms/Scalar/DeadStoreElimination.cpp

static bool isPossibleSelfRead(Instruction *Inst,
   return true;
 }
 
 /// Returns true if the memory which is accessed by the second instruction is not
 /// modified between the first and the second instruction.
 /// 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<BasicBlock *, 16> WorkList;
   SmallPtrSet<BasicBlock *, 8> Visited;
   BasicBlock::iterator FirstBBI(FirstI);
   ++FirstBBI;
   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);
   bool isFirstBlock = true;
 
   // Check all blocks going backward until we reach the load-block.
   while (!WorkList.empty()) {
     BasicBlock *B = WorkList.pop_back_val();
if (UnderlyingPointer && isCallocLikeFn(UnderlyingPointer, TLI) &&
       deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, InstrOrdering);
       ++NumRedundantStores;
       return true;
     }
   }
   return false;
 }
 
+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;
+}
+
+static bool eliminateStrlen(CallInst *CI, BasicBlock::iterator &BBI,
+                            AliasAnalysis *AA, MemoryDependenceResults *MD,
+                            const DataLayout &DL, const TargetLibraryInfo *TLI,
+                            InstOverlapIntervalsTy &IOL,
+                            DenseMap<Instruction *, size_t> *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<Instruction>(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<Instruction *, size_t> *InstrOrdering) {
+  CallInst *CI = dyn_cast<CallInst>(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) {
   const DataLayout &DL = BB.getModule()->getDataLayout();
   bool MadeChange = false;
 
   // FIXME: Maybe change this to use some abstraction like OrderedBasicBlock?
   // The current OrderedBasicBlock can't deal with mutation at the moment.
if (CallInst *F = isFreeCall(&*BBI, TLI)) {
       // Increment BBI after handleFree has potentially deleted instructions.
       // This ensures we maintain a valid iterator.
       ++BBI;
       continue;
     }
 
     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()) {
       LastThrowingInstIndex = CurInstNumber;
       continue;
     }
 
     // Check to see if Inst writes to memory.  If not, continue.

 
 //===----------------------------------------------------------------------===//
 // DSE Pass
 //===----------------------------------------------------------------------===//
 PreservedAnalyses DSEPass::run(Function &F, FunctionAnalysisManager &AM) {
   AliasAnalysis *AA = &AM.getResult<AAManager>(F);
   DominatorTree *DT = &AM.getResult<DominatorTreeAnalysis>(F);
   MemoryDependenceResults *MD = &AM.getResult<MemoryDependenceAnalysis>(F);
   const TargetLibraryInfo *TLI = &AM.getResult<TargetLibraryAnalysis>(F);
 
   if (!eliminateDeadStores(F, AA, MD, DT, TLI))
     return PreservedAnalyses::all();
 
   PreservedAnalyses PA;
   PA.preserveSet<CFGAnalyses>();
   PA.preserve<GlobalsAA>();
   PA.preserve<MemoryDependenceAnalysis>();
   return PA;

test/Transforms/DeadStoreElimination/zero-string.ll

+; 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
+}