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

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
<mailto: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/20160420/f04e9baf/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: memssa-remove-cache-bug.ll
Type: application/octet-stream
Size: 263 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160420/f04e9baf/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: memssa-remove-cache-bug.log
Type: application/octet-stream
Size: 2726 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160420/f04e9baf/attachment-0001.obj>

Hi!
> readonly calls are treated as clobbers by MemorySSA which leads to extra
walking of MemoryDefs to not regress some EarlyCSE test cases

Can you share a testcase for this too, please? Specifically, the first test
in test/Transforms/Util/MemorySSA/function-mem-attrs.ll shows that we
should treat readonly calls + calls to readonly functions as MemoryUses, so
if we're thinking they're clobbers somehow, that sounds like a bug...

Thank you!
George

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/20160420/71e40b1b/attachment.html>

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/20160420/98f26745/attachment-0001.html>

Okay, do you think this case needs a unittest?  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.

 

--

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
<mailto: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 <mailto:dberlin at
dberlin.org> ]
Sent: Wednesday, April 20, 2016 1:06 PM
To: Geoff Berry <gberry at codeaurora.org <mailto:gberry at
codeaurora.org> >; George Burgess <gbiv at google.com <mailto:gbiv
at google.com> >
Cc: llvm-dev <llvm-dev at lists.llvm.org <mailto: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
<mailto: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/c717fdb5/attachment.html>

Hi George,

 

After digging a little deeper, it appears that readonly calls showing up as
MemoryDefs is only happening on an EarlyCSE test that is using the new pass
manager (test/Transforms/EarlyCSE/basic.ll test5 if you’re curious), so I
suspect it is an issue with the new pass manager setup code for either
MemorySSA, my changes to EarlyCSE, the test run command line or something else
not related to the MemorySSA code proper.

 

--

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: George Burgess [mailto:gbiv at google.com] 
Sent: Wednesday, April 20, 2016 3:29 PM
To: Geoff Berry <gberry at codeaurora.org>
Cc: Daniel Berlin <dberlin at dberlin.org>; llvm-dev <llvm-dev at
lists.llvm.org>
Subject: Re: [LICM][MemorySSA] Converting LICM pass to use MemorySSA to avoid
AliasSet collapse issue

 

Hi!

 
> readonly calls are treated as clobbers by MemorySSA which leads to extra
walking of MemoryDefs to not regress some EarlyCSE test cases
 

Can you share a testcase for this too, please? Specifically, the first test in
test/Transforms/Util/MemorySSA/function-mem-attrs.ll shows that we should treat
readonly calls + calls to readonly functions as MemoryUses, so if we're
thinking they're clobbers somehow, that sounds like a bug...

 

Thank you!

George

 

On Wed, Apr 20, 2016 at 12:06 PM, Geoff Berry <gberry at codeaurora.org
<mailto: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 <mailto:dberlin at
dberlin.org> ]
Sent: Wednesday, April 20, 2016 1:06 PM
To: Geoff Berry <gberry at codeaurora.org <mailto:gberry at
codeaurora.org> >; George Burgess <gbiv at google.com <mailto:gbiv
at google.com> >
Cc: llvm-dev <llvm-dev at lists.llvm.org <mailto: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
<mailto: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/61237001/attachment.html>