[llvm-dev] [LICM][MemorySSA] Converting LICM pass to use MemorySSA to avoid AliasSet collapse issue

Thu Apr 21 08:31:23 PDT 2016

On Thu, Apr 21, 2016 at 8:21 AM, Geoff Berry <gberry at codeaurora.org> wrote:

>
>
> Okay, do you think this case needs a unittest?
>

I would think the right answer is to have a verifyRemoved(X), and call it
with expensive checks on (from invalidateInfo)

Have it verify that, after invalidation, no removed memoryAccesses appear
in the cache.

This would be a quite expensive check  with the current caching scheme, but
probably helpful for debugging.

>  I think I can construct one by comparing the results from
> getClobberingMemoryAccess before and after a call to removeMemoryAccess to
> make sure they’re different, but I don’t know how much of a pain it will be
> to construct the test IR programmatically.
>

Constructing the testIR programmatically is pretty easy, but i don't know
that a unittest without access to the internals will be able to verify the
cache state.

>
>
> --
>
> Geoff Berry
>
> Employee of Qualcomm Innovation Center, Inc.
>
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux
> Foundation Collaborative Project
>
>
>
> *From:* Daniel Berlin [mailto:dberlin at dberlin.org]
> *Sent:* Wednesday, April 20, 2016 3:45 PM
> *To:* Geoff Berry <gberry at codeaurora.org>
> *Cc:* George Burgess <gbiv at google.com>; llvm-dev <llvm-dev at lists.llvm.org>
>
> *Subject:* Re: [LICM][MemorySSA] Converting LICM pass to use MemorySSA to
> avoid AliasSet collapse issue
>
>
>
> Oh, crap.
>
> I wasn't thinking hard enough about the case you described.
>
>
>
> Okay. So your patch is right as the conservative thing to do.
>
> The real problem here is that we don't know what cache entries point to
> other cache entries.
>
>
>
> We do in some special cases (If the use list contains only memoryuses, we
> know all the cache entries that need invalidation), but not in general.
>
>
>
> Given most queries are about loads and not stores, and loads don't even
> need to be cached after memoryssa is built anyway (they will already
> directly point to the nearest clobbering definition), i think we should
> just apply your patch.
>
>
>
>
>
>
>
> On Wed, Apr 20, 2016 at 12:06 PM, Geoff Berry <gberry at codeaurora.org>
> wrote:
>
> 1)      Sounds good.  This isn’t holding me up so I’ll just try to keep
> an eye out for these changes.
>
>
>
> 2)      I’ve attached an example IR file and debug log of where the
> caching is going bad.  It depends on my changes to EarlyCSE, but hopefully
> it is clear from the debug output what is going on.  Let me know if there
> is a better way to get this repro case to you.  Also, I’ll be on IRC for
> the next couple of hours if you would like to have a quicker discussion.
>
>
>
> --
>
> Geoff Berry
>
> Employee of Qualcomm Innovation Center, Inc.
>
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux
> Foundation Collaborative Project
>
>
>
> *From:* Daniel Berlin [mailto:dberlin at dberlin.org]
> *Sent:* Wednesday, April 20, 2016 1:06 PM
> *To:* Geoff Berry <gberry at codeaurora.org>; George Burgess <gbiv at google.com
> >
> *Cc:* llvm-dev <llvm-dev at lists.llvm.org>
> *Subject:* Re: [LICM][MemorySSA] Converting LICM pass to use MemorySSA to
> avoid AliasSet collapse issue
>
>
>
>
>
>
>
> On Wed, Apr 20, 2016 at 9:58 AM, Geoff Berry <gberry at codeaurora.org>
> wrote:
>
> Hi Daniel,
>
>
>
> Thanks for the info.  I’ve started looking into converting EarlyCSE to use
> MemorySSA first since 1) I don’t think it needs any additional MemorySSA
> update API and 2) the particular case I’m looking at needs EarlyCSE to
> catch more load cases before LICM to be profitable.
>
> I have a prototype working, but have run into two issues:
>
>
>
> 1)      readonly calls are treated as clobbers by MemorySSA which leads
> to extra walking of MemoryDefs to not regress some EarlyCSE test cases.
> This isn’t a huge deal, I’m just wondering if it is intentional or
> something that just hasn’t been gotten to yet.
>
>
>
> George is working on the optimizations, of which this is one.
>
> I think this is one of the ones his current patch (under review) addresses.
>
>
>
> 2)      There seems to be a bug in the CachingMemorySSAWalker
> invalidation causing it to return MemoryAccess nodes that have been
> removed.  In the case I’m seeing, a call node is removed from MemorySSA
> which causes CachingMemorySSAWalker::invalidateInfo() to clear the
> CachedUpwardsClobberingCall map.  However, this same call node is present
> as a value in the CachedUpwardsClobberingAccess map,
>
>
>
> Unless i'm missing something, this should not have happened, and we should
> assert they are not being added to the cache.
>
>
>
> The truth is the caching parts are complicated and ugly. It was meant to
> be a pretty simple cache, but it's known to be inefficient (memory wise)
> and it's on the list of things to clean up and make sane.
>
>
>
> Do you have a testcase where this happens?
>
> A quick glance says we check whether it's a call in all the right places,
> which means there must be a place we are not *setting* isCall properly.
>
>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160421/6193e525/attachment.html>