<div dir="ltr">IR:<div><div>define i32 @calloc_strlen_write_between() {</div><div>  %call = tail call noalias i8* @calloc(i32 10, i32 1) </div><div>  store i8 97, i8* %call, align 1</div><div>  %call1 = tail call i32 @strlen(i8* %call)</div><div>  ret i32 %call1</div><div>}</div></div><div><br></div><div><br></div>static bool eliminateStrlen(CallInst *CI, BasicBlock::iterator &BBI,<br>AliasAnalysis *AA, MemoryDependenceResults *MD,<br>const DataLayout &DL, const TargetLibraryInfo *TLI,<br>InstOverlapIntervalsTy &IOL,<br>DenseMap<Instruction *, size_t> *InstrOrdering) {<br><br>// Must be a strlen.<br>LibFunc Func;<br>Function *Callee = CI->getCalledFunction();<br>if (!TLI->getLibFunc(*Callee, Func) || !TLI->has(Func) ||<br>Func != LibFunc_strlen)<br>return false;<br><br>Value *Dst = CI->getOperand(0);<br>Instruction *UnderlyingPointer =<br>dyn_cast<Instruction>(GetUnderlyingObject(Dst, DL));<br>if (!UnderlyingPointer)<br>return false;<br>if (!isStringFromCalloc(Dst, TLI))<br>return false;<br><br>if (memoryIsNotModifiedBetween(UnderlyingPointer, CI, AA)) {<br>Value *Len = ConstantInt::get(CI->getType(), 0);<br>CI->replaceAllUsesWith(Len);<br>CI->eraseFromParent();<br>return true;<br>}<br>return false;<br>}<div><br></div><div><br></div><div>------------------------------------------------------</div><div>That IR is still wrongly transformed with this code to ret i32 0 (but there is write between calloc and strlen). Any suggestions?</div></div><div class="gmail_extra"><br><div class="gmail_quote">2018-05-23 0:49 GMT+02:00 Dávid Bolvanský <span dir="ltr"><<a href="mailto:david.bolvansky@gmail.com" target="_blank">david.bolvansky@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>It works with</div><div><br></div>MemoryLocation MemoryLocation::get(const CallInst *CI) {<br>AAMDNodes AATags;<br>CI->getAAMetadata(AATags);<br>const auto &DL = CI->getModule()-><wbr>getDataLayout();<br><br>return MemoryLocation(CI, DL.getTypeStoreSize(CI-><wbr>getType()), AATags);<br>}<div><br></div><div>Is it fine? :) </div></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">2018-05-22 23:56 GMT+02:00 Dávid Bolvanský <span dir="ltr"><<a href="mailto:david.bolvansky@gmail.com" target="_blank">david.bolvansky@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Looks like there are many overloads for "get". <a href="http://llvm.org/doxygen/MemoryLocation_8cpp_source.html" target="_blank">http://llvm.org/doxygen<wbr>/MemoryLocation_8cpp_source.<wbr>html</a><div><br></div><div>But nothing for CallInst. Any suggestions how to do a proper one? I will look at it too.</div></div><div class="m_-7725043753438901422HOEnZb"><div class="m_-7725043753438901422h5"><div class="gmail_extra"><br><div class="gmail_quote">2018-05-22 23:34 GMT+02:00 Dávid Bolvanský <span dir="ltr"><<a href="mailto:david.bolvansky@gmail.com" target="_blank">david.bolvansky@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Full stack trace:<div><br></div><div><span><div>opt: /home/xbolva00/LLVM/llvm/inclu<wbr>de/llvm/ADT/Optional.h:176: T* llvm::Optional<T>::getPointer(<wbr>) [with T = llvm::MemoryLocation]: Assertion `Storage.hasVal' failed.</div></span><div>Stack dump:</div><div>0.<span class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332gmail-Apple-tab-span" style="white-space:pre-wrap">     </span>Program arguments: opt aaa.ll -dse -S </div><div>1.<span class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332gmail-Apple-tab-span" style="white-space:pre-wrap"> </span>Running pass 'Function Pass Manager' on module 'aaa.ll'.</div><div>2.<span class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332gmail-Apple-tab-span" style="white-space:pre-wrap">        </span>Running pass 'Dead Store Elimination' on function '@calloc_strlen'</div><div>LLVMSymbolizer: error reading file: No such file or directory</div><div>#0 0x000056135ebe698a (opt+0x212198a)</div><div>#1 0x000056135ebe4cf4 (opt+0x211fcf4)</div><div>#2 0x000056135ebe4e32 (opt+0x211fe32)</div><div>#3 0x00007f6e35b14150 __restore_rt (/lib/x86_64-linux-gnu/libpthr<wbr>ead.so.0+0x13150)</div><div>#4 0x00007f6e3481b0bb gsignal /build/glibc-itYbWN/glibc-2.26<wbr>/signal/../sysdeps/unix/sysv/l<wbr>inux/raise.c:51:0</div><div>#5 0x00007f6e3481cf5d abort /build/glibc-itYbWN/glibc-2.26<wbr>/stdlib/abort.c:92:0</div><div>#6 0x00007f6e34812f17 __assert_fail_base /build/glibc-itYbWN/glibc-2.26<wbr>/assert/assert.c:92:0</div><div>#7 0x00007f6e34812fc2 (/lib/x86_64-linux-gnu/libc.so<wbr>.6+0x2efc2)</div><div>#8 0x000056135e962b80 (opt+0x1e9db80)</div><div>#9 0x000056135e969260 (opt+0x1ea4260)</div><div>#10 0x000056135e96a6e0 (opt+0x1ea56e0)</div><div>#11 0x000056135e61d561 (opt+0x1b58561)</div><div>#12 0x000056135e61d5d9 (opt+0x1b585d9)</div><div>#13 0x000056135e61cbb7 (opt+0x1b57bb7)</div><div>#14 0x000056135d175216 (opt+0x6b0216)</div><div>#15 0x00007f6e348051c1 __libc_start_main /build/glibc-itYbWN/glibc-2.26<wbr>/csu/../csu/libc-start.c:342:0</div><div>#16 0x000056135d1f404a (opt+0x72f04a)</div></div><div><br></div></div><div class="m_-7725043753438901422m_1114758970894209448HOEnZb"><div class="m_-7725043753438901422m_1114758970894209448h5"><div class="gmail_extra"><br><div class="gmail_quote">2018-05-22 23:32 GMT+02:00 Friedman, Eli <span dir="ltr"><<a href="mailto:efriedma@codeaurora.org" target="_blank">efriedma@codeaurora.org</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
  
    
  
  <div text="#000000" bgcolor="#FFFFFF">
    <div class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128moz-cite-prefix">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.<br>
      <br>
      (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.)<span class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332HOEnZb"><font color="#888888"><br>
      <br>
      -Eli</font></span><div><div class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332h5"><br>
      <br>
      On 5/22/2018 2:16 PM, Dávid Bolvanský wrote:<br>
    </div></div></div><div><div class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332h5">
    <blockquote type="cite">
      <div dir="ltr">* <span style="color:rgb(0,0,0);white-space:pre-wrap">if (isStringFromCalloc(Dst, TLI)) should be </span><span style="color:rgb(0,0,0);white-space:pre-wrap">if (!isStringFromCalloc(Dst, TLI))</span>
        <div><span style="color:rgb(0,0,0);white-space:pre-wrap">
</span></div>
        <div><font color="#000000"><span style="white-space:pre-wrap">but still asserting...</span></font></div>
      </div>
      <div class="gmail_extra"><br>
        <div class="gmail_quote">2018-05-22 23:06 GMT+02:00 Dávid
          Bolvanský <span dir="ltr"><<a href="mailto:david.bolvansky@gmail.com" target="_blank">david.bolvansky@gmail.com</a>></span>:<br>
          <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
            <div dir="ltr">Can you help a bit?
              <div><br>
              </div>
              <div>I try to work with DSE but I got the following
                assert:</div>
              <div>
                <div>opt: /home/xbolva00/LLVM/llvm/inclu<wbr>de/llvm/ADT/Optional.h:176:
                  T* llvm::Optional<T>::getPointer(<wbr>) [with T
                  = llvm::MemoryLocation]: Assertion `Storage.hasVal'
                  failed.</div>
              </div>
              <div><br>
              </div>
              <div>
                <pre style="color:rgb(0,0,0);word-wrap:break-word;white-space:pre-wrap">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>(GetUnder<wbr>lyingObject(Dst, DL));
  if (!UnderlyingPointer)
    return false;
  if (isStringFromCalloc(Dst, TLI))
    return false;
  errs() << "before\n";
  if (memoryIsNotModifiedBetween(Un<wbr>derlyingPointer, CI, AA)) { <--- CRASH
    errs() << "after\n";
  }
  return false;
}</pre>
                <pre style="color:rgb(0,0,0);word-wrap:break-word;white-space:pre-wrap">Do you know what is wrong here? I followed the "example" (in eliminateNoopStore) how to use "memoryIsNotModifiedBetween".</pre>
                <pre style="color:rgb(0,0,0);word-wrap:break-word;white-space:pre-wrap"></pre>
                <pre style="color:rgb(0,0,0);word-wrap:break-word;white-space:pre-wrap">Thank you for advice</pre>
                <pre style="color:rgb(0,0,0);word-wrap:break-word;white-space:pre-wrap"></pre>
              </div>
            </div>
            <div class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128HOEnZb">
              <div class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128h5">
                <div class="gmail_extra"><br>
                  <div class="gmail_quote">2018-05-21 21:06 GMT+02:00
                    Friedman, Eli <span dir="ltr"><<a href="mailto:efriedma@codeaurora.org" target="_blank">efriedma@codeaurora.org</a>></span>:<br>
                    <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
                      <div text="#000000" bgcolor="#FFFFFF">
                        <div class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128m_3282544529915536139m_7569404264700124646moz-cite-prefix">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
                          <a class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128m_3282544529915536139m_7569404264700124646moz-txt-link-freetext" href="https://reviews.llvm.org/D40480" target="_blank">https://reviews.llvm.org/D4048<wbr>0</a>.)<br>
                          <br>
                          But yes, memoryIsNotModifiedBetween has the
                          right meaning.<span class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128m_3282544529915536139HOEnZb"><font color="#888888"><br>
                              <br>
                              -Eli</font></span>
                          <div>
                            <div class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128m_3282544529915536139h5"><br>
                              <br>
                              On 5/21/2018 7:48 AM, Dávid Bolvanský
                              wrote:<br>
                            </div>
                          </div>
                        </div>
                        <div>
                          <div class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128m_3282544529915536139h5">
                            <blockquote type="cite">
                              <div dir="ltr"><span style="font-size:12.8px">"memory
                                  accesses between the malloc and the
                                  memset</span><span style="font-size:12.8px"> without an
                                  expensive linear scan of the
                                  block/function" </span>
                                <div><span style="font-size:12.8px"><br>
                                  </span></div>
                                <div><span style="font-size:12.8px">(1)
                                    do you mean just use
                                    "memoryIsNotModifiedBetween"
                                    function in DSE to check it?</span>
                                  <div><br>
                                  </div>
                                  <div>x = maloc(..);</div>
                                  <div>memset(x, ...) </div>
                                  <div><br>
                                  </div>
                                  <div>(2) GetUnderlyingObject would
                                    give me Value * (from malloc) ?</div>
                                  <div>
                                    <div><span style="font-size:12.8px"><br>
                                      </span></div>
                                    <div><span style="font-size:12.8px">Also
                                        another case:</span></div>
                                    <div><span style="font-size:12.8px"><br>
                                      </span></div>
                                    <div><span style="font-size:12.8px">memset(s,
                                        0, len); // len > 1</span></div>
                                    <div><span style="font-size:12.8px">return
                                        strlen(s); // optimize to 0</span></div>
                                    <div><span style="font-size:12.8px"><br>
                                      </span></div>
                                    <div><span style="font-size:12.8px">(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?</span></div>
                                    <div><span style="font-size:12.8px"><br>
                                      </span></div>
                                    <div><span style="font-size:12.8px">(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)</span></div>
                                    <div><span style="font-size:12.8px"><br>
                                      </span></div>
                                    <div><span style="font-size:12.8px">(5)
                                        new malloc memset folding /
                                         memset + strlen case should be
                                        implemented in DSE, right?</span></div>
                                  </div>
                                </div>
                              </div>
                              <div class="gmail_extra"><br>
                                <div class="gmail_quote">2018-05-17
                                  21:36 GMT+02:00 Friedman, Eli <span dir="ltr"><<a href="mailto:efriedma@codeaurora.org" target="_blank">efriedma@codeaurora.org</a>></span>:<br>
                                  <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
                                    <div text="#000000" bgcolor="#FFFFFF">
                                      <div class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128m_3282544529915536139m_7569404264700124646m_6141790905467921389moz-cite-prefix">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.)<span class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128m_3282544529915536139m_7569404264700124646HOEnZb"><font color="#888888"><br>
                                            <br>
                                            -Eli</font></span>
                                        <div>
                                          <div class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128m_3282544529915536139m_7569404264700124646h5"><br>
                                            <br>
                                            On 5/17/2018 12:17 PM, Dávid
                                            Bolvanský wrote:<br>
                                          </div>
                                        </div>
                                      </div>
                                      <div>
                                        <div class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128m_3282544529915536139m_7569404264700124646h5">
                                          <blockquote type="cite">
                                            <div dir="ltr">As we talked
                                              in <a href="https://reviews.llvm.org/D45344" target="_blank">https://reviews.llvm.org/D4534<wbr>4</a>,
                                              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.
                                              <div><br>
                                              </div>
                                              <div>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? </div>
                                              <div>We have standard
                                                malloc + memset folding
                                                there, so a  few  new
                                                lines should not do bad
                                                things.</div>
                                              <div><br>
                                              </div>
                                              <div>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.<br>
                                                <div><br>
                                                </div>
                                                <div><br>
                                                </div>
                                              </div>
                                            </div>
                                            <div class="gmail_extra"><br>
                                              <div class="gmail_quote">2018-05-17
                                                21:00 GMT+02:00
                                                Friedman, Eli <span dir="ltr"><<a href="mailto:efriedma@codeaurora.org" target="_blank">efriedma@codeaurora.org</a>></span>:<br>
                                                <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span>On
                                                    5/17/2018 8:58 AM,
                                                    Dávid Bolvanský via
                                                    llvm-dev wrote:<br>
                                                    <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
                                                      Hello,<br>
                                                      <br>
                                                      I would like to
                                                      find a way to do
                                                      this removal
                                                      properly. I found
                                                      DSE and
                                                      "eliminateNoopStore"
                                                      can be useful for
                                                      this thing.<br>
                                                      <br>
                                                      What I mean?<br>
                                                      int *test =
                                                      malloc(15 *
                                                      sizeof(int));<br>
                                                      test[10] = 12;
                                                      < ----- remove
                                                      this store<br>
memset(test,0,sizeof(int) * 15);<br>
                                                    </blockquote>
                                                    <br>
                                                  </span> This is
                                                  classic dead store
                                                  elimination, and it's
                                                  already handled by
                                                  DSE. At least, we
                                                  optimize the following
                                                  testcase:<br>
                                                  <br>
                                                  #include
                                                  <stdlib.h><br>
                                                  #include
                                                  <string.h><br>
                                                  void bar(int*);<br>
                                                  void f() {<span><br>
                                                      int *test =
                                                    malloc(15 *
                                                    sizeof(int));<br>
                                                      test[10] = 12;<br>
                                                  </span>  
                                                  memset(test,0,sizeof(int)
                                                  * 15);<br>
                                                    bar(test);<br>
                                                  }<br>
                                                  <br>
                                                  You should be able to
                                                  look at the existing
                                                  code to understand how
                                                  it's handled (using
                                                  MemoryDependenceAnalysis).<span class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128m_3282544529915536139m_7569404264700124646m_6141790905467921389HOEnZb"><font color="#888888"><br>
                                                      <br>
                                                      -Eli<br>
                                                      <br>
                                                      -- <br>
                                                      Employee of
                                                      Qualcomm
                                                      Innovation Center,
                                                      Inc.<br>
                                                      Qualcomm
                                                      Innovation Center,
                                                      Inc. is a member
                                                      of Code Aurora
                                                      Forum, a Linux
                                                      Foundation
                                                      Collaborative
                                                      Project<br>
                                                      <br>
                                                    </font></span></blockquote>
                                              </div>
                                              <br>
                                            </div>
                                          </blockquote>
                                          <p><br>
                                          </p>
                                          <pre class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128m_3282544529915536139m_7569404264700124646m_6141790905467921389moz-signature" cols="72">-- 
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project</pre>
                                        </div>
                                      </div>
                                    </div>
                                  </blockquote>
                                </div>
                                <br>
                              </div>
                            </blockquote>
                            <p><br>
                            </p>
                            <pre class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128m_3282544529915536139m_7569404264700124646moz-signature" cols="72">-- 
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project</pre>
                          </div>
                        </div>
                      </div>
                    </blockquote>
                  </div>
                  <br>
                </div>
              </div>
            </div>
          </blockquote>
        </div>
        <br>
      </div>
    </blockquote>
    <p><br>
    </p>
    <pre class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128moz-signature" cols="72">-- 
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project</pre>
  </div></div></div>

</blockquote></div><br></div>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div>