[llvm-dev] DSE: Remove useless stores between malloc & memset

[Dávid Bolvanský via llvm-dev]

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<T>::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



2018-05-21 21:06 GMT+02:00 Friedman, Eli <efriedma at codeaurora.org>:

> 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
>
>
> On 5/21/2018 7:48 AM, Dávid Bolvanský wrote:
>
> "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?
>
> 2018-05-17 21:36 GMT+02:00 Friedman, Eli <efriedma at codeaurora.org>:
>
>> The fundamental problem with trying to do that sort of transform in
>> instcombine is that you don't have access to MemoryDependenceAnalysis or
>> MemorySSA; you need a data structure like that to figure out whether there
>> are any memory accesses between the malloc and the memset without an
>> expensive linear scan of the block/function.  (You can sort of get around
>> the problem in simple cases by adding arbitrary limits to the number of you
>> scan, but it doesn't generalize well.)
>>
>> -Eli
>>
>>
>> On 5/17/2018 12:17 PM, Dávid Bolvanský wrote:
>>
>> As we talked in https://reviews.llvm.org/D45344, the problem was dead
>> stores. And I know why :D There was just -instcombine pass. I forgot to do
>> -dse before -instcombine so this is why I did custom "store removal" code
>> there.
>>
>> I would like to finish malloc + llvm.memset folding. Yes, you told you
>> would like to see the whole foldMallocMemset in DSE but extend it for
>> llvm.memset in InstCombine... is it really so bad to do?
>> We have standard malloc + memset folding there, so a  few  new lines
>> should not do bad things.
>>
>> If I reopen D45344, reupload patch with removed my custom "store removal"
>> code, It could be ok, no? The patch as is worked/works for me for malloc
>> + llvm.memset folding, I would just add -dse to tests to handle dead stores.
>>
>>
>>
>> 2018-05-17 21:00 GMT+02:00 Friedman, Eli <efriedma at codeaurora.org>:
>>
>>> On 5/17/2018 8:58 AM, Dávid Bolvanský via llvm-dev wrote:
>>>
>>>> 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);
>>>>
>>>
>>> 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
>>>
>>> --
>>> Employee of Qualcomm Innovation Center, Inc.
>>> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a
>>> Linux Foundation Collaborative Project
>>>
>>>
>>
>> --
>> Employee of Qualcomm Innovation Center, Inc.
>> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project
>>
>>
>
> --
> Employee of Qualcomm Innovation Center, Inc.
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20180522/e6b1022e/attachment.html>