Peter Lawrence via llvm-dev
2017-May-17 15:38 UTC
[llvm-dev] Which pass should be propagating memory copies
Daniel,
You’ve given pretty good arguments for why not to do this in GVN,
How about thinking about other ways to approach the problem
Peter Lawrence.
> On May 17, 2017, at 7:36 AM, via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
>
> Message: 4
> Date: Tue, 16 May 2017 22:07:44 -0700
> From: Daniel Berlin via llvm-dev <llvm-dev at lists.llvm.org
<mailto:llvm-dev at lists.llvm.org>>
> To: Keno Fischer <keno at juliacomputing.com <mailto:keno at
juliacomputing.com>>
> Cc: llvm-dev <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>>
> Subject: Re: [llvm-dev] Which pass should be propagating memory copies
> Message-ID:
> <CAF4BwTWyD+ROFCNkV-9hcPoJVpyOUO4xAwtWr38e2sA2Eb84eQ at mail.gmail.com
<mailto:CAF4BwTWyD+ROFCNkV-9hcPoJVpyOUO4xAwtWr38e2sA2Eb84eQ at
mail.gmail.com>>
> Content-Type: text/plain; charset="utf-8"
>
> So,
> both GVN's we have mainly exist to eliminate redundancies, they
don't
> perform general transforms.
> So in your example, it would be "easy" to make NewGVN see through
the
> memcpys
>
> ie
> teach it that memcpy(a, b, full size of b and a) means a = b, and propagate
> it through, and whatever goodness this entails.
>
> It also currently knows how to coerce loads of memset/memcpy to pull the
> value out of the original piece, even when they are *not* full size memcpy.
> This requires instruction insertion in non-constant cases.
> So it only does this for constants ATM (but I have code to extend it to the
> general case and it works fine, it's in my patch list).
>
> The infrastructure i'm about to commit tomorrow also makes it know that
it
> can use alternative "fake" instructions to represent values, and
make the
> instructions real later.
>
> So for example, for
>
> if (foo)
> a = 5, b = 2
> else
> b = 5, a = 2
>
> return a + b
> it knows that a+b is equivalent to 7
>
> and when faced with:
> if (foo)
> a = 5, b = 2
> else
> b = 5, a = 3
>
> return a+b
> it knows that a+b is equivalent to phi(7, 8) (which doesn't exist in
the
> original program), and that it can insert that phi to eliminate c.
>
> You could use that infrastructure to teach it that the memcpy's are
> equivalent to stores that it could insert.
>
> I would actually start by teaching it about memcpy in general, and that
> full size memcpy implies value equivalence (this would require wiring it
> into performSymbolicCallEvaluation), that store of a memcpy target and
> memcpy are equivalent when they copy/store the same value (see the FIXME in
> performSymbolicStoreEvaluation).
>
> If you want to teach it to try to see memcpy's as stores, that's
possible
> too.
> It's a bit trickier because NewGVN is ruthless. It terminates only at
> fixpoint. So you have to make the conditions under which you do things
> like "see memcpy as store" totally deterministic and ordered, or
someone
> will come up with a testcase where we bounce forever between two the
> possible values for the same thing.
>
> We have a bunch of verifiers to try to help with this, but as Davide can
> tell you, it can be a workout sometimes :)
>
> At this point, in the base, it's really rare to be able to trigger this
> behavior (and all cases i'm aware of involve undef).
> But if you add symbolic evaluation code, it usually takes a few tries to
> get it right.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170517/30d52322/attachment.html>
Daniel Berlin via llvm-dev
2017-May-17 17:18 UTC
[llvm-dev] Which pass should be propagating memory copies
Hi Peter, There are of course many ways to approach the problem and anywhere that does it has various trade-offs. Trying to find any perfect place is a fools errand. The other obvious place we have is memcpyopt. FWIW, I don't think your earlier suggestion of converting it into stores would work 1. There are always going to be objects large enough that the architecture optimized memcpy is going to be faster, and we aren't always going to be able to form them back from stores later. So we would never just lower everything to stores. 2. Because of #1, we're not going to get rid of memcpy and it's always going to be valuable to teach these passes how to look through memcpy anyway. On Wed, May 17, 2017, 8:38 AM Peter Lawrence via llvm-dev < llvm-dev at lists.llvm.org> wrote:> Daniel, > You’ve given pretty good arguments for why not to do this in > GVN, > How about thinking about other ways to approach the problem > > Peter Lawrence. > > > > On May 17, 2017, at 7:36 AM, via llvm-dev <llvm-dev at lists.llvm.org> wrote: > > Message: 4 > Date: Tue, 16 May 2017 22:07:44 -0700 > From: Daniel Berlin via llvm-dev <llvm-dev at lists.llvm.org> > To: Keno Fischer <keno at juliacomputing.com> > Cc: llvm-dev <llvm-dev at lists.llvm.org> > Subject: Re: [llvm-dev] Which pass should be propagating memory copies > Message-ID: > <CAF4BwTWyD+ROFCNkV-9hcPoJVpyOUO4xAwtWr38e2sA2Eb84eQ at mail.gmail.com> > Content-Type: text/plain; charset="utf-8" > > > > So, > both GVN's we have mainly exist to eliminate redundancies, they don't > perform general transforms. > So in your example, it would be "easy" to make NewGVN see through the > memcpys > > ie > teach it that memcpy(a, b, full size of b and a) means a = b, and propagate > it through, and whatever goodness this entails. > > It also currently knows how to coerce loads of memset/memcpy to pull the > value out of the original piece, even when they are *not* full size memcpy. > This requires instruction insertion in non-constant cases. > So it only does this for constants ATM (but I have code to extend it to the > general case and it works fine, it's in my patch list). > > The infrastructure i'm about to commit tomorrow also makes it know that it > can use alternative "fake" instructions to represent values, and make the > instructions real later. > > So for example, for > > if (foo) > a = 5, b = 2 > else > b = 5, a = 2 > > return a + b > it knows that a+b is equivalent to 7 > > and when faced with: > if (foo) > a = 5, b = 2 > else > b = 5, a = 3 > > return a+b > it knows that a+b is equivalent to phi(7, 8) (which doesn't exist in the > original program), and that it can insert that phi to eliminate c. > > You could use that infrastructure to teach it that the memcpy's are > equivalent to stores that it could insert. > > I would actually start by teaching it about memcpy in general, and that > full size memcpy implies value equivalence (this would require wiring it > into performSymbolicCallEvaluation), that store of a memcpy target and > memcpy are equivalent when they copy/store the same value (see the FIXME in > performSymbolicStoreEvaluation). > > If you want to teach it to try to see memcpy's as stores, that's possible > too. > It's a bit trickier because NewGVN is ruthless. It terminates only at > fixpoint. So you have to make the conditions under which you do things > like "see memcpy as store" totally deterministic and ordered, or someone > will come up with a testcase where we bounce forever between two the > possible values for the same thing. > > We have a bunch of verifiers to try to help with this, but as Davide can > tell you, it can be a workout sometimes :) > > At this point, in the base, it's really rare to be able to trigger this > behavior (and all cases i'm aware of involve undef). > But if you add symbolic evaluation code, it usually takes a few tries to > get it right. > > _______________________________________________ > 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/20170517/383fb00c/attachment.html>