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

Hi All,

 

I'm looking into converting LICM to use MemorySSA instead of AliasSets to
determine when it is safe to hoist/sink/promote loads and stores to get
around the issue of alias set collapse (see discussion [1]).  I have a
prototype implementation, but have run into two issues that I could use
input from the designers of MemorySSA to resolve:

1)      Is MemorySSA intended to be maintained across passes?  More
specifically how is it intended to interact with the Pass Manager?  In my
current prototype I'm just building it at the start of LICM.

2)      What is the intended method for dealing with changes to the function
that invalidate the MemorySSA form?  I see that there is a way to remove
nodes from the MemorySSA graph, but for other transformations (e.g. hoisting
a load) am I supposed to just update the MemorySSA graph myself?

 

 

[1] http://lists.llvm.org/pipermail/llvm-dev/2015-April/084881.html

 

--

Geoff Berry

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/20160411/f6a2ee70/attachment.html>

On Mon, Apr 11, 2016 at 12:03 PM, Geoff Berry <gberry at codeaurora.org>
wrote:
> Hi All,
>
>
>
> I’m looking into converting LICM to use MemorySSA instead of AliasSets to
> determine when it is safe to hoist/sink/promote loads and stores to get
> around the issue of alias set collapse (see discussion [1]).
>
Thank you

> I have a prototype implementation, but have run into two issues that I
> could use input from the designers of MemorySSA to resolve:
>
> 1)      Is MemorySSA intended to be maintained across passes?  More
> specifically how is it intended to interact with the Pass Manager?  In my
> current prototype I’m just building it at the start of LICM.
>
I am working on it, it will be preserved/destroyed like any analysis pass.

> 2)      What is the intended method for dealing with changes to the
> function that invalidate the MemorySSA form?  I see that there is a way to
> remove nodes from the MemorySSA graph, but for other transformations (e.g.
> hoisting a load) am I supposed to just update the MemorySSA graph myself?
>
For hoisting loads, i have an API that will work abotu to be under review
over here:
http://reviews.llvm.org/D18090
a load hoist will look something like this to update:

  // We also hoist operands of loads using this function, so check to see if
  // this is really a memory access before we try to update MemorySSA for
it.
  MemoryAccess *HoistCandAccess = MSSA->getMemoryAccess(HoistCand);
  if (HoistCandAccess) {
    MemoryUseOrDef *MUD = cast<MemoryUseOrDef>(HoistCandAccess);
    // What is happening here is that we are creating the hoisted access
    // and destroying the old accesses.
    MSSA->createMemoryAccess(HoistedInst, MUD->getDefiningAccess(), BB,
                             MemorySSA::End);
    MSSA->removeMemoryAccess(HoistCandAccess);
    MSSA->removeMemoryAccess(MSSA->getMemoryAccess(ElseInst));
  }


(this is "create a new access with this memorydef as it's definition,
kill
these two old loads").


A store sink is slightly harder, but it will be similar.

Comments welcome!


>
>
>
>
> [1] http://lists.llvm.org/pipermail/llvm-dev/2015-April/084881.html
>
>
>
> --
>
> Geoff Berry
>
> 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/20160411/9d97c1b1/attachment.html>

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.

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, so when a later query is made
with the load whose immediate def used to be the call, the removed call node is
returned.  The simple fix below resolves the issue, but may be too big of a
hammer?

 

@@ -802,17 +836,8 @@ void CachingMemorySSAWalker::invalidateInfo(MemoryAccess
*MA) {

     doCacheRemove(MA, Q, Q.StartingLoc);

     return;

   }

-  // If it is not a use, the best we can do right now is destroy the cache.

-  bool IsCall = false;

-

-  if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA)) {

-    Instruction *I = MUD->getMemoryInst();

-    IsCall = bool(ImmutableCallSite(I));

-  }

-  if (IsCall)

-    CachedUpwardsClobberingCall.clear();

-  else

-    CachedUpwardsClobberingAccess.clear();

+  CachedUpwardsClobberingCall.clear();

+  CachedUpwardsClobberingAccess.clear();

}

 void CachingMemorySSAWalker::doCacheRemove(const MemoryAccess *M,

 

--

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: Monday, April 11, 2016 4:17 PM
To: Geoff Berry <gberry at codeaurora.org>
Cc: llvm-dev <llvm-dev at lists.llvm.org>; Sanjoy Das <sanjoy at
playingwithpointers.com>; Hal Finkel <hfinkel at anl.gov>
Subject: Re: [LICM][MemorySSA] Converting LICM pass to use MemorySSA to avoid
AliasSet collapse issue

 

 

 

On Mon, Apr 11, 2016 at 12:03 PM, Geoff Berry <gberry at codeaurora.org
<mailto:gberry at codeaurora.org> > wrote:

Hi All,

 

I’m looking into converting LICM to use MemorySSA instead of AliasSets to
determine when it is safe to hoist/sink/promote loads and stores to get around
the issue of alias set collapse (see discussion [1]).

 

Thank you

 

I have a prototype implementation, but have run into two issues that I could use
input from the designers of MemorySSA to resolve:

1)      Is MemorySSA intended to be maintained across passes?  More specifically
how is it intended to interact with the Pass Manager?  In my current prototype
I’m just building it at the start of LICM.

I am working on it, it will be preserved/destroyed like any analysis pass.

 

2)      What is the intended method for dealing with changes to the function
that invalidate the MemorySSA form?  I see that there is a way to remove nodes
from the MemorySSA graph, but for other transformations (e.g. hoisting a load)
am I supposed to just update the MemorySSA graph myself?

 

For hoisting loads, i have an API that will work abotu to be under review over
here:

http://reviews.llvm.org/D18090

a load hoist will look something like this to update:

 

  // We also hoist operands of loads using this function, so check to see if

  // this is really a memory access before we try to update MemorySSA for it.

  MemoryAccess *HoistCandAccess = MSSA->getMemoryAccess(HoistCand);

  if (HoistCandAccess) {

    MemoryUseOrDef *MUD = cast<MemoryUseOrDef>(HoistCandAccess);

    // What is happening here is that we are creating the hoisted access

    // and destroying the old accesses.

    MSSA->createMemoryAccess(HoistedInst, MUD->getDefiningAccess(), BB,

                             MemorySSA::End);

    MSSA->removeMemoryAccess(HoistCandAccess);

    MSSA->removeMemoryAccess(MSSA->getMemoryAccess(ElseInst));

  }

 

 

(this is "create a new access with this memorydef as it's definition,
kill these two old loads").

 

 

A store sink is slightly harder, but it will be similar.

 

Comments welcome!

 

 

 

 

[1] http://lists.llvm.org/pipermail/llvm-dev/2015-April/084881.html

 

--

Geoff Berry

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/20160420/38516bbe/attachment-0001.html>