This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH V3][GCC] Algorithmic optimization in match and simplify
- From: James Greenhalgh <james dot greenhalgh at arm dot com>
- To: Richard Biener <richard dot guenther at gmail dot com>
- Cc: Andre Simoes Dias Vieira <Andre dot SimoesDiasVieira at arm dot com>, GCC Patches <gcc-patches at gcc dot gnu dot org>
- Date: Fri, 9 Oct 2015 17:11:36 +0100
- Subject: Re: [PATCH V3][GCC] Algorithmic optimization in match and simplify
- Authentication-results: sourceware.org; auth=none
- References: <55E092D9 dot 8070700 at arm dot com> <alpine dot DEB dot 2 dot 20 dot 1508281956570 dot 9451 at laptop-mg dot saclay dot inria dot fr> <55E5AACB dot 3050205 at arm dot com> <CAFiYyc0j=1JYycYi9zBFMZooCE7C-mxZUUjiXzrAX47jgKaRvw at mail dot gmail dot com> <55E82AFF dot 4020401 at arm dot com> <CAFiYyc2znWLc-S7txfaJT2VatwSmg_7pZ81__ehoGpU1Qdtf6w at mail dot gmail dot com> <5605303B dot 7080102 at arm dot com> <CAFiYyc1VRqo_vKHjnmnSStKS=4-B3nrgv4cus+wdGkxFGU+CMg at mail dot gmail dot com> <5614D5F7 dot 2000806 at arm dot com> <CAFiYyc0hd6ih_9VZ8jYNTPn5_gFxbChFm6ou9AGfgxNHE=YCEA at mail dot gmail dot com>
On Thu, Oct 08, 2015 at 01:29:34PM +0100, Richard Biener wrote:
> > Thanks again for the comments Richard!
> >
> > A new algorithmic optimisation:
> >
> > ((X inner_op C0) outer_op C1)
> > With X being a tree where value_range has reasoned certain bits to always be
> > zero throughout its computed value range, we will call this the zero_mask,
> > and with inner_op = {|,^}, outer_op = {|,^} and inner_op != outer_op.
> > if (inner_op == '^') C0 &= ~C1;
> > if ((C0 & ~zero_mask) == 0) then emit (X outer_op (C0 outer_op C1)
> > if ((C1 & ~zero_mask) == 0) then emit (X inner_op (C0 outer_op C1)
> >
> > And extended '(X & C2) << C1 into (X << C1) & (C2 << C1)' and
> > '(X & C2) >> C1 into (X >> C1) & (C2 >> C1)' to also accept the bitwise or
> > and xor operators:
> > '(X {&,^,|} C2) << C1 into (X << C1) {&,^,|} (C2 << C1)' and
> > '(X {&,^,|} C2) >> C1 into (X >> C1) & (C2 >> C1)'.
> >
> > The second transformation enables more applications of the first. Also some
> > targets may benefit from delaying shift operations. I am aware that such an
> > optimization, in combination with one or more optimizations that cause the
> > reverse transformation, may lead to an infinite loop. Though such behavior
> > has not been detected during regression testing and bootstrapping on
> > aarch64.
> >
> > gcc/ChangeLog:
> >
> > 2015-10-05 Andre Vieira <andre.simoesdiasvieira@arm.com>
> >
> > * match.pd: Added a new pattern
> > ((X inner_op C0) outer_op C1)
> > and expanded existing one
> > (X {|,^,&} C0) {<<,>>} C1 -> (X {<<,>>} C1) {|,^,&} (C0 {<<,>>} C1)
> >
> > gcc/testsuite/ChangeLog:
> >
> > 2015-10-05 Andre Vieira <andre.simoesdiasvieira@arm.com>
> >
> > Hale Wang <hale.wang@arm.com>
> >
> > * gcc.dg/tree-ssa/forwprop-33.c: New test.
>
> Ok.
>
> Thanks,
> Richard.
>
As Andre does not have commit rights, I've committed this on his behalf as
revision 228661. Please watch for any fallout over the weekend.
Andre, please check your ChangeLog format in future. In the end I
committed this:
gcc/ChangeLog
2015-10-09 Andre Vieira <andre.simoesdiasvieira@arm.com>
* match.pd: ((X inner_op C0) outer_op C1) New pattern.
((X & C2) << C1): Expand to...
(X {&,^,|} C2 << C1): ...This.
((X & C2) >> C1): Expand to...
(X {&,^,|} C2 >> C1): ...This.
gcc/testsuite/ChangeLog
2015-10-09 Andre Vieira <andre.simoesdiasvieira@arm.com>
Hale Wang <hale.wang@arm.com>
* gcc.dg/tree-ssa/forwprop-33.c: New.
Thanks,
James