DSE: Remove useless stores between malloc & memset

Hello,

I would like to find a way to do this removal properly. I found DSE and “eliminateNoopStore” can be useful for this thing.

What I mean?
int *test = malloc(15 * sizeof(int));
test[10] = 12; < ----- remove this store
memset(test,0,sizeof(int) * 15);

I already checked the function “eliminateNoopStore”.
Looks good, I think I would be to get the value (“A”) we store to, is from malloc. Then a pointer capture analysis would be performed. These steps should not be hard.

The problem: how to do the detection that the value “A” is later zeroed using memset? Traverse over all uses of “A”? Can you recommend me the proper way how to check this?

Thank you

p.s: In the future it could be used for proper malloc + memset folding to calloc, currently it is a bit suboptimal.

This is classic dead store elimination, and it's already handled by DSE. At least, we optimize the following testcase:

#include <stdlib.h>
#include <string.h>
void bar(int*);
void f() {
int *test = malloc(15 * sizeof(int));
test[10] = 12;
memset(test,0,sizeof(int) * 15);
bar(test);
}

You should be able to look at the existing code to understand how it's handled (using MemoryDependenceAnalysis).

-Eli

“memory accesses between the malloc and the memset without an expensive linear scan of the block/function”

(1) do you mean just use “memoryIsNotModifiedBetween” function in DSE to check it?

x = maloc(…);
memset(x, …)

(2) GetUnderlyingObject would give me Value * (from malloc) ?

Also another case:

memset(s, 0, len); // len > 1
return strlen(s); // optimize to 0

(3) How to check memset and strlen pairs? I have a strlen call, I have a “Value *” for “s”. What is the best way to construct memset + strlen pairs?

(4) Can this be somehow generalized (and not only for strlen)? So GetStringLength in ValueTracking would be taught about this info (string is empty after memset)

(5) new malloc memset folding / memset + strlen case should be implemented in DSE, right?

memoryIsNotModifiedBetween is precisely the sort of expensive walk we shouldn't be doing... I'm surprised it hasn't caused any serious issues yet. Ideally, what we should be doing is using MemorySSA to find a dependency from the memset: if the closest dependency is the malloc, there aren't any stores between the memset and the malloc. (But we aren't using MemorySSA in DSE yet; see https://reviews.llvm.org/D40480.)

But yes, memoryIsNotModifiedBetween has the right meaning.

-Eli

Can you help a bit?

I try to work with DSE but I got the following assert:

opt: /home/xbolva00/LLVM/llvm/include/llvm/ADT/Optional.h:176: T* llvm::Optional::getPointer() [with T = llvm::MemoryLocation]: Assertion `Storage.hasVal’ failed.

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 (!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;
  errs() << "before\n";
  if (memoryIsNotModifiedBetween(UnderlyingPointer, CI, AA)) { <--- CRASH
    errs() << "after\n";
  }
  return false;
}
Do you know what is wrong here? I followed the "example" (in eliminateNoopStore) how to use "memoryIsNotModifiedBetween".

Thank you for advice

  • if (isStringFromCalloc(Dst, TLI)) should be if (!isStringFromCalloc(Dst, TLI))

but still asserting…

It looks like the memoryIsNotModifiedBetween assumes the second argument is a store, or some other instruction supported by MemoryLocation::get. If you're passing in something else, you'll have to compute the MemoryLocation some other way.

(Generally, if you're asking a question about an assertion, please include the whole stack trace; it's hard to guess what's happening otherwise.)

-Eli

Full stack trace:

opt: /home/xbolva00/LLVM/llvm/include/llvm/ADT/Optional.h:176: T* llvm::Optional::getPointer() [with T = llvm::MemoryLocation]: Assertion `Storage.hasVal’ failed.
Stack dump:
0. Program arguments: opt aaa.ll -dse -S

  1. Running pass ‘Function Pass Manager’ on module ‘aaa.ll’.
  2. Running pass ‘Dead Store Elimination’ on function ‘@calloc_strlen
    LLVMSymbolizer: error reading file: No such file or directory
    #0 0x000056135ebe698a (opt+0x212198a)
    #1 0x000056135ebe4cf4 (opt+0x211fcf4)
    #2 0x000056135ebe4e32 (opt+0x211fe32)
    #3 0x00007f6e35b14150 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x13150)
    #4 0x00007f6e3481b0bb gsignal /build/glibc-itYbWN/glibc-2.26/signal/…/sysdeps/unix/sysv/linux/raise.c:51:0
    #5 0x00007f6e3481cf5d abort /build/glibc-itYbWN/glibc-2.26/stdlib/abort.c:92:0
    #6 0x00007f6e34812f17 __assert_fail_base /build/glibc-itYbWN/glibc-2.26/assert/assert.c:92:0
    #7 0x00007f6e34812fc2 (/lib/x86_64-linux-gnu/libc.so.6+0x2efc2)
    #8 0x000056135e962b80 (opt+0x1e9db80)
    #9 0x000056135e969260 (opt+0x1ea4260)
    #10 0x000056135e96a6e0 (opt+0x1ea56e0)
    #11 0x000056135e61d561 (opt+0x1b58561)
    #12 0x000056135e61d5d9 (opt+0x1b585d9)
    #13 0x000056135e61cbb7 (opt+0x1b57bb7)
    #14 0x000056135d175216 (opt+0x6b0216)
    #15 0x00007f6e348051c1 __libc_start_main /build/glibc-itYbWN/glibc-2.26/csu/…/csu/libc-start.c:342:0
    #16 0x000056135d1f404a (opt+0x72f04a)

Looks like there are many overloads for “get”. http://llvm.org/doxygen/MemoryLocation_8cpp_source.html

But nothing for CallInst. Any suggestions how to do a proper one? I will look at it too.

It works with

MemoryLocation MemoryLocation::get(const CallInst *CI) {
AAMDNodes AATags;
CI->getAAMetadata(AATags);
const auto &DL = CI->getModule()->getDataLayout();

return MemoryLocation(CI, DL.getTypeStoreSize(CI->getType()), AATags);
}

Is it fine? :slight_smile:

IR:

define i32 @calloc_strlen_write_between() {
%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
}

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 (!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)) {
Value *Len = ConstantInt::get(CI->getType(), 0);
CI->replaceAllUsesWith(Len);
CI->eraseFromParent();
return true;
}
return false;
}

You might want to look more carefully at how you're constructing the MemoryLocation. The first argument is a pointer, and the second argument is the number of bytes pointed to by that pointer (or MemoryLocation::UnknownSize if the number of bytes accessed isn't known).

More generally, copy-pasting code you don't understand isn't a good idea.

-Eli

Yeah, sorry for that. Better “It compiles ok (but maybe incorrect code)”, not “It works” as I wrote.

Can you review https://reviews.llvm.org/D47237?

My tests look ok but I am still not sure about MemoryLocation::get(const CallInst *CI) if implemented correctly. This is my first patch for DSE, so I am aware of “DSE” things I don’t know yet but I like to learn new things :slight_smile: