thr3ads.net - llvm dev - [llvm-dev] Generalizing load/store promotion in LICM [Sep 2018]

If this information is useful, please help other people find it:
Share via:

John Brawn via llvm-dev

2018-Sep-14 11:56 UTC

[llvm-dev] Generalizing load/store promotion in LICM

For doing PRE on the load, it looks like there’s only two things stopping GVN
PRE from doing it:
* GVN::PerformLoadPRE doesn’t hoist loads that are conditional. Probably this
can be overcome with some kind of
     heuristic that allows it to happen in loops when the blocks where a load
would have to be inserted are outside
     the loop.
* IsFullyAvailableInBlock goes around the loop and double-counts the entry-edge
into the loop as unavailable. I’m
     pretty sure this can be easily fixed by marking the block that
PerformLoadPRE calls IsFullyAvailableInBlock on as
     FullyAvailable, so it stops there when following the back-edge.
I did a quick experiment (solving the first problem by just commenting out that
check) and this worked for a simple
test case of
int x;
int arr[32];
void fn(int n) {
   for (int i = 0; i < n; i++) {
     if (arr[i]) {
       x++;
     }
   }
}
So perhaps the load PRE half can be done without a separate pass.

John

From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of Alina
Sbirlea via llvm-dev
Sent: 13 September 2018 22:01
To: listmail at philipreames.com
Cc: llvm-dev at lists.llvm.org
Subject: Re: [llvm-dev] Generalizing load/store promotion in LICM

For context, I've been looking into replacing the use of AST
(AliasSetTracker) with MemorySSA in LICM. This works great for sinking/hoisting
but does not apply well for promotion, and one of the solutions I considered is
precisely ripping out the promotion part and replacing its functionality with a
separate PRE pass + possibly store sinking. FWIW I think that's the right
way to go.
I did not get deep enough into working on the solution but I would gladly have a
detailed discussion to move this forward.

Reading into detail now.

Thanks,
Alina

On Thu, Sep 13, 2018 at 1:43 PM Philip Reames <listmail at
philipreames.com<mailto:listmail at philipreames.com>> wrote:
(minor inline additions)

On 09/13/2018 01:51 AM, Chandler Carruth wrote:

Haven't had time to dig into this, but wanted to add +Alina
Sbirlea<mailto:asbirlea at google.com> to the thread as she has been
working on promotion and other aspects of LICM for a long time here.
Thanks!

On Wed, Sep 12, 2018 at 11:41 PM Philip Reames <listmail at
philipreames.com<mailto:listmail at philipreames.com>> wrote:

I'm thinking about making some semi radical changes to load store promotion
works in LICM, and figured it would be a good idea to get buy in before I
actually started writing code.  :)

TLDR: legality of sinking stores to exits is hard, can we separate load handling
into a super aggressive form of PRE, and use predicated stores to avoid solving
legality question?



Background

We've been seeing an interesting class of problems recently that looks
roughly like this:

for (int = 0; i < N; i++)
  if (a[i] == 0) // some data dependent check
    g_count++; // conditional load and store to shared location

The critical detail in this example is that g_count is a global location which
may be accessed concurrently* by multiple threads.  The challenge here is that
we don't know whether the store ever executes, and we're not allowed to
insert a store along any path that didn't originally contain them.  Said
differently, if all elements in "a" are non-zero, we're not
allowed to store to g_count.  We do know that the g_count location is
dereferenceable though.

(*Please, let's avoid the memory model derailment here.  I'm simplifying
and C++ language rules aren't real useful for my Java language frontend
anyways.  In practice, all the access are atomic, but unordered, but we'll
leave that out of discussion otherwise.)

I have two approaches I'm considering here.  These are orthogonal, but I
suspect we'll want to implement both.



Proposal A - Use predicated stores in loop exits

The basic idea is that we don't worry about solving the legality question
above, and just insert a store which is predicated on a condition which is true
exactly when the original store ran.  In pseudo code, this looks something like:

bool StoreLegal = false;
int LocalCount = g_count;
for (int = 0; i < N; i++)
  if (a[i] == 0) {
    LocalCount++;
    StoreLegal = true;
  }
if (StoreLegal) g_count = LocalCount;

There are two obvious concerns here:

  1.  The predicated store might be expensive in practice - true for most
current architectures.
  2.  We''re introducing an extra boolean phi cycle around the loop.

Talking to a couple of folks offline at the socials over the last few months,
the former seems to be the main objection.  I think we can control this by
restricting this transform to when the loop is believed to have a high trip
count and the conditional path is taken with some frequency.   Getting feedback
on this particular point is one of my main reasons for writing this mail.

The second objection can frequently be resolved by finding other expressions
which evaluate to the same boolean.  (In this case, if LocalCount !=
LocalCountOrig assuming i doesn't overflow.)  We already have a framework
with SCEV to do these replacements.  Though, from some quick testing, it would
definitely need strengthening.  However, SCEV can't remove the extra phi in
all cases, so we have to be okay with the extra phi cycle in the general case. 
This seems worthwhile to me, but thoughts?



Proposal B - Separate load and store handling into distinct transforms

(For folks I've discussed this with before, this part is all new.)

Thinking about the problem, it finally occurred to me that we can decompose the
original example into two steps: getting the loads out of the loop, and sinking
the stores out of the loop.  If we can accomplish the former, but not the later,
we've still made meaningful progress.

So, what'd we'd essentially have is a load only transformation which
produces this:
int LocalCount = g_count;
for (int = 0; i < N; i++)
  if (a[i] == 0) {
    LocalCount++;
    g_count = LocalCount;
  }

At this point, we've reduced memory traffic by half, and opened up the
possibility that other parts of the optimizer can exploit the simplified form. 
The last point is particular interesting since we generally try to canonicalize
loads out of loops, and much of the optimizer is tuned for a form with as much
as possible being loop invariant.  As one example, completely by accident,
there's some work going on in the LoopVectorizer right now to handle such
stores to loop invariant addresses during vectorization.  Putting the two pieces
together would let us fully vectorize this loop without needing to sink the
stores at all.

In practice, the existing implementation in LICM would cleanly split along these
lines with little problem.

One way of looking at this load specific transform is as an extreme form of PRE
(partial redundancy elimination).  Our current PRE implementation doesn't
handle cases this complicated.
It occurred to my later that simply framing the new transform as a separate pass
(LoopPRE) and using the same AST + SSA construction approach would be straight
forward.  So, if folks think that having an aggressive form of load PRE in LICM
is going a bit too far, it'd be easy to represent as an optional separate
pass.  I'd still prefer having LICM contain the logic though.


Thoughts?

Philip

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180914/725d4714/attachment-0001.html>

Philip Reames via llvm-dev

2018-Sep-14 23:39 UTC

head link

[llvm-dev] Generalizing load/store promotion in LICM

I agree this approach is possible.  I even have an (ancient, abandoned) 
patch which started down that path. https://reviews.llvm.org/D7061

I view this as being also useful, not a reason not to do the transform 
in LICM.  We've already spent all the analysis cost, we might as well 
use it.

(Lest it's not clear, I'm assuming that if we did do a separate LoopPRE 
pass that we'd have to separate out a AliasSetTrackAnalysis and handle 
invalidation properly though the loop pass pipeline. i.e. not recompute 
the AST)

On 09/14/2018 04:56 AM, John Brawn wrote:>
> For doing PRE on the load, it looks like there’s only two things 
> stopping GVN PRE from doing it:
>
> * GVN::PerformLoadPRE doesn’t hoist loads that are conditional. 
> Probably this can be overcome with some kind of
>
>  heuristic that allows it to happen in loops when the blocks where a 
> load would have to be inserted are outside
>
> the loop.
>
> * IsFullyAvailableInBlock goes around the loop and double-counts the 
> entry-edge into the loop as unavailable. I’m
>
> pretty sure this can be easily fixed by marking the block that 
> PerformLoadPRE calls IsFullyAvailableInBlock on as
>
> FullyAvailable, so it stops there when following the back-edge.
>
> I did a quick experiment (solving the first problem by just commenting 
> out that check) and this worked for a simple
>
> test case of
>
> int x;
>
> int arr[32];
>
> void fn(int n) {
>
>    for (int i = 0; i < n; i++) {
>
>      if (arr[i]) {
>
>        x++;
>
>      }
>
>    }
>
> }
>
> So perhaps the load PRE half can be done without a separate pass.
>
> John
>
> *From:*llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] *On Behalf Of 
> *Alina Sbirlea via llvm-dev
> *Sent:* 13 September 2018 22:01
> *To:* listmail at philipreames.com
> *Cc:* llvm-dev at lists.llvm.org
> *Subject:* Re: [llvm-dev] Generalizing load/store promotion in LICM
>
> For context, I've been looking into replacing the use of AST 
> (AliasSetTracker) with MemorySSA in LICM. This works great for 
> sinking/hoisting but does not apply well for promotion, and one of the 
> solutions I considered is precisely ripping out the promotion part and 
> replacing its functionality with a separate PRE pass + possibly store 
> sinking. FWIW I think that's the right way to go.
>
> I did not get deep enough into working on the solution but I would 
> gladly have a detailed discussion to move this forward.
>
> Reading into detail now.
>
> Thanks,
>
> Alina
>
> On Thu, Sep 13, 2018 at 1:43 PM Philip Reames 
> <listmail at philipreames.com <mailto:listmail at
philipreames.com>> wrote:
>
>     (minor inline additions)
>
>     On 09/13/2018 01:51 AM, Chandler Carruth wrote:
>
>     Haven't had time to dig into this, but wanted to add +Alina
>     Sbirlea <mailto:asbirlea at google.com> to the thread as she has
been
>     working on promotion and other aspects of LICM for a long time here.
>
>     Thanks!
>
>     On Wed, Sep 12, 2018 at 11:41 PM Philip Reames
>     <listmail at philipreames.com <mailto:listmail at
philipreames.com>> wrote:
>
>         I'm thinking about making some semi radical changes to load
>         store promotion works in LICM, and figured it would be a good
>         idea to get buy in before I actually started writing code.  :)
>
>         TLDR: legality of sinking stores to exits is hard, can we
>         separate load handling into a super aggressive form of PRE,
>         and use predicated stores to avoid solving legality question?
>
>         Background
>
>         We've been seeing an interesting class of problems recently
>         that looks roughly like this:
>
>         for (int = 0; i < N; i++)
>           if (a[i] == 0) // some data dependent check
>             g_count++; // conditional load and store to shared location
>
>         The critical detail in this example is that g_count is a
>         global location which may be accessed concurrently* by
>         multiple threads.  The challenge here is that we don't know
>         whether the store ever executes, and we're not allowed to
>         insert a store along any path that didn't originally contain
>         them.  Said differently, if all elements in "a" are
non-zero,
>         we're not allowed to store to g_count.  We do know that the
>         g_count location is dereferenceable though.
>
>         (*Please, let's avoid the memory model derailment here. 
I'm
>         simplifying and C++ language rules aren't real useful for my
>         Java language frontend anyways.  In practice, all the access
>         are atomic, but unordered, but we'll leave that out of
>         discussion otherwise.)
>
>         I have two approaches I'm considering here. These are
>         orthogonal, but I suspect we'll want to implement both.
>
>         Proposal A - Use predicated stores in loop exits
>
>         The basic idea is that we don't worry about solving the
>         legality question above, and just insert a store which is
>         predicated on a condition which is true exactly when the
>         original store ran.  In pseudo code, this looks something like:
>
>         bool StoreLegal = false;
>         int LocalCount = g_count;
>         for (int = 0; i < N; i++)
>           if (a[i] == 0) {
>             LocalCount++;
>             StoreLegal = true;
>           }
>         if (StoreLegal) g_count = LocalCount;
>
>         There are two obvious concerns here:
>
>          1. The predicated store might be expensive in practice - true
>             for most current architectures.
>          2. We''re introducing an extra boolean phi cycle around
the
>             loop.
>
>         Talking to a couple of folks offline at the socials over the
>         last few months, the former seems to be the main objection.  I
>         think we can control this by restricting this transform to
>         when the loop is believed to have a high trip count and the
>         conditional path is taken with some frequency.   Getting
>         feedback on this particular point is one of my main reasons
>         for writing this mail.
>
>         The second objection can frequently be resolved by finding
>         other expressions which evaluate to the same boolean.  (In
>         this case, if LocalCount != LocalCountOrig assuming i doesn't
>         overflow.) We already have a framework with SCEV to do these
>         replacements.  Though, from some quick testing, it would
>         definitely need strengthening.  However, SCEV can't remove the
>         extra phi in all cases, so we have to be okay with the extra
>         phi cycle in the general case. This seems worthwhile to me,
>         but thoughts?
>
>         Proposal B - Separate load and store handling into distinct
>         transforms
>
>         (For folks I've discussed this with before, this part is all
new.)
>
>         Thinking about the problem, it finally occurred to me that we
>         can decompose the original example into two steps: getting the
>         loads out of the loop, and sinking the stores out of the loop.
>         If we can accomplish the former, but not the later, we've
>         still made meaningful progress.
>
>         So, what'd we'd essentially have is a load only
transformation
>         which produces this:
>         int LocalCount = g_count;
>         for (int = 0; i < N; i++)
>           if (a[i] == 0) {
>             LocalCount++;
>             g_count = LocalCount;
>           }
>
>         At this point, we've reduced memory traffic by half, and
>         opened up the possibility that other parts of the optimizer
>         can exploit the simplified form.  The last point is particular
>         interesting since we generally try to canonicalize loads out
>         of loops, and much of the optimizer is tuned for a form with
>         as much as possible being loop invariant.  As one example,
>         completely by accident, there's some work going on in the
>         LoopVectorizer right now to handle such stores to loop
>         invariant addresses during vectorization.  Putting the two
>         pieces together would let us fully vectorize this loop without
>         needing to sink the stores at all.
>
>         In practice, the existing implementation in LICM would cleanly
>         split along these lines with little problem.
>
>         One way of looking at this load specific transform is as an
>         extreme form of PRE (partial redundancy elimination).  Our
>         current PRE implementation doesn't handle cases this
complicated.
>
>     It occurred to my later that simply framing the new transform as a
>     separate pass (LoopPRE) and using the same AST + SSA construction
>     approach would be straight forward.  So, if folks think that
>     having an aggressive form of load PRE in LICM is going a bit too
>     far, it'd be easy to represent as an optional separate pass. 
I'd
>     still prefer having LICM contain the logic though.
>
>         Thoughts?
>
>         Philip
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180914/3bdda920/attachment.html>

Alina Sbirlea via llvm-dev

2018-Sep-18 22:10 UTC

head link

[llvm-dev] Generalizing load/store promotion in LICM

On Fri, Sep 14, 2018 at 4:39 PM Philip Reames via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> I agree this approach is possible.  I even have an (ancient, abandoned)
> patch which started down that path.  https://reviews.llvm.org/D7061
>
> I view this as being also useful, not a reason not to do the transform in
> LICM.  We've already spent all the analysis cost, we might as well use
it.
>
> (Lest it's not clear, I'm assuming that if we did do a separate
LoopPRE
> pass that we'd have to separate out a AliasSetTrackAnalysis and handle
> invalidation properly though the loop pass pipeline.  i.e. not recompute
> the AST)
>
I was suggesting dropping the use of the AST entirely :). Not going to
happen tomorrow, but at some point...

>
> On 09/14/2018 04:56 AM, John Brawn wrote:
>
> For doing PRE on the load, it looks like there’s only two things stopping
> GVN PRE from doing it:
>
> * GVN::PerformLoadPRE doesn’t hoist loads that are conditional. Probably
> this can be overcome with some kind of
>
>      heuristic that allows it to happen in loops when the blocks where a
> load would have to be inserted are outside
>
>      the loop.
>
> * IsFullyAvailableInBlock goes around the loop and double-counts the
> entry-edge into the loop as unavailable. I’m
>
>      pretty sure this can be easily fixed by marking the block that
> PerformLoadPRE calls IsFullyAvailableInBlock on as
>
>      FullyAvailable, so it stops there when following the back-edge.
>
> I did a quick experiment (solving the first problem by just commenting out
> that check) and this worked for a simple
>
> test case of
>
> int x;
>
> int arr[32];
>
> void fn(int n) {
>
>    for (int i = 0; i < n; i++) {
>
>      if (arr[i]) {
>
>        x++;
>
>      }
>
>    }
>
> }
>
> So perhaps the load PRE half can be done without a separate pass.
>
>
>
> John
>
>
>
> *From:* llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org
> <llvm-dev-bounces at lists.llvm.org>] *On Behalf Of *Alina Sbirlea
via
> llvm-dev
> *Sent:* 13 September 2018 22:01
> *To:* listmail at philipreames.com
> *Cc:* llvm-dev at lists.llvm.org
> *Subject:* Re: [llvm-dev] Generalizing load/store promotion in LICM
>
>
>
> For context, I've been looking into replacing the use of AST
> (AliasSetTracker) with MemorySSA in LICM. This works great for
> sinking/hoisting but does not apply well for promotion, and one of the
> solutions I considered is precisely ripping out the promotion part and
> replacing its functionality with a separate PRE pass + possibly store
> sinking. FWIW I think that's the right way to go.
>
> I did not get deep enough into working on the solution but I would gladly
> have a detailed discussion to move this forward.
>
>
>
> Reading into detail now.
>
>
>
> Thanks,
>
> Alina
>
>
>
> On Thu, Sep 13, 2018 at 1:43 PM Philip Reames <listmail at
philipreames.com>
> wrote:
>
> (minor inline additions)
>
> On 09/13/2018 01:51 AM, Chandler Carruth wrote:
>
> Haven't had time to dig into this, but wanted to add +Alina Sbirlea
> <asbirlea at google.com> to the thread as she has been working on
promotion
> and other aspects of LICM for a long time here.
>
> Thanks!
>
> On Wed, Sep 12, 2018 at 11:41 PM Philip Reames <listmail at
philipreames.com>
> wrote:
>
> I'm thinking about making some semi radical changes to load store
> promotion works in LICM, and figured it would be a good idea to get buy in
> before I actually started writing code.  :)
>
> TLDR: legality of sinking stores to exits is hard, can we separate load
> handling into a super aggressive form of PRE, and use predicated stores to
> avoid solving legality question?
>
>
>
> Background
>
> We've been seeing an interesting class of problems recently that looks
> roughly like this:
>
> for (int = 0; i < N; i++)
>   if (a[i] == 0) // some data dependent check
>     g_count++; // conditional load and store to shared location
>
> The critical detail in this example is that g_count is a global location
> which may be accessed concurrently* by multiple threads.  The challenge
> here is that we don't know whether the store ever executes, and
we're not
> allowed to insert a store along any path that didn't originally contain
> them.  Said differently, if all elements in "a" are non-zero,
we're not
> allowed to store to g_count.  We do know that the g_count location is
> dereferenceable though.
>
> (*Please, let's avoid the memory model derailment here.  I'm
simplifying
> and C++ language rules aren't real useful for my Java language frontend
> anyways.  In practice, all the access are atomic, but unordered, but
we'll
> leave that out of discussion otherwise.)
>
> I have two approaches I'm considering here.  These are orthogonal, but
I
> suspect we'll want to implement both.
>
>
>
> Proposal A - Use predicated stores in loop exits
>
> The basic idea is that we don't worry about solving the legality
question
> above, and just insert a store which is predicated on a condition which is
> true exactly when the original store ran.  In pseudo code, this looks
> something like:
>
> bool StoreLegal = false;
> int LocalCount = g_count;
> for (int = 0; i < N; i++)
>   if (a[i] == 0) {
>     LocalCount++;
>     StoreLegal = true;
>   }
> if (StoreLegal) g_count = LocalCount;
>
> There are two obvious concerns here:
>
>    1. The predicated store might be expensive in practice - true for most
>    current architectures.
>    2. We''re introducing an extra boolean phi cycle around the
loop.
>
> Talking to a couple of folks offline at the socials over the last few
> months, the former seems to be the main objection.  I think we can control
> this by restricting this transform to when the loop is believed to have a
> high trip count and the conditional path is taken with some frequency.
> Getting feedback on this particular point is one of my main reasons for
> writing this mail.
>
> The second objection can frequently be resolved by finding other
> expressions which evaluate to the same boolean.  (In this case, if
> LocalCount != LocalCountOrig assuming i doesn't overflow.)  We already
have
> a framework with SCEV to do these replacements.  Though, from some quick
> testing, it would definitely need strengthening.  However, SCEV can't
> remove the extra phi in all cases, so we have to be okay with the extra phi
> cycle in the general case.  This seems worthwhile to me, but thoughts?
>
>
>
> Proposal B - Separate load and store handling into distinct transforms
>
> (For folks I've discussed this with before, this part is all new.)
>
> Thinking about the problem, it finally occurred to me that we can
> decompose the original example into two steps: getting the loads out of the
> loop, and sinking the stores out of the loop.  If we can accomplish the
> former, but not the later, we've still made meaningful progress.
>
> So, what'd we'd essentially have is a load only transformation
which
> produces this:
> int LocalCount = g_count;
> for (int = 0; i < N; i++)
>   if (a[i] == 0) {
>     LocalCount++;
>     g_count = LocalCount;
>   }
>
> At this point, we've reduced memory traffic by half, and opened up the
> possibility that other parts of the optimizer can exploit the simplified
> form.  The last point is particular interesting since we generally try to
> canonicalize loads out of loops, and much of the optimizer is tuned for a
> form with as much as possible being loop invariant.  As one example,
> completely by accident, there's some work going on in the
LoopVectorizer
> right now to handle such stores to loop invariant addresses during
> vectorization.  Putting the two pieces together would let us fully
> vectorize this loop without needing to sink the stores at all.
>
> In practice, the existing implementation in LICM would cleanly split along
> these lines with little problem.
>
> One way of looking at this load specific transform is as an extreme form
> of PRE (partial redundancy elimination).  Our current PRE implementation
> doesn't handle cases this complicated.
>
> It occurred to my later that simply framing the new transform as a
> separate pass (LoopPRE) and using the same AST + SSA construction approach
> would be straight forward.  So, if folks think that having an aggressive
> form of load PRE in LICM is going a bit too far, it'd be easy to
represent
> as an optional separate pass.  I'd still prefer having LICM contain the
> logic though.
>
> Thoughts?
>
> Philip
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180918/5631b097/attachment-0001.html>

llvm dev - Sep 2018 - Generalizing load/store promotion in LICM

[llvm-dev] Generalizing load/store promotion in LICM

[llvm-dev] Generalizing load/store promotion in LICM

[llvm-dev] Generalizing load/store promotion in LICM