[Bug tree-optimization/25290] PHI-OPT could be rewritten so that is uses fold

[Bug tree-optimization/25290] PHI-OPT could be rewritten so that is uses fold

[pinskia at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=25290

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
         AssignedTo|unassigned at gcc dot       |pinskia at gcc dot gnu.org
                   |gnu.org                     |

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-01-21 22:01:00 UTC ---
I actually have a patch to do this but only for the late PHIOPT as it keeps
around cond_expr.

[Bug tree-optimization/25290] PHI-OPT could be rewritten so that is uses fold

[pinskia at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=25290

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-02-23 23:25:53 UTC ---
Maybe not fold but rather what I am working on, gimple_combine.

[Bug tree-optimization/25290] PHI-OPT could be rewritten so that is uses fold

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=25290

Marc Glisse <glisse at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |glisse at gcc dot gnu.org

--- Comment #6 from Marc Glisse <glisse at gcc dot gnu.org> ---
I assume it would help with this?

int f(int a,int b){
  return (a<0)&(b<0);
}
int g(int a,int b){
  return (a<0)?(b<0):0;
}
int h(int a,int b){
  if (a<0) return (b<0);
  return 0;
}

where (on x86) we turn g into f, but we don't notice that h is the same. In
asm, that is:

    movl    %esi, %eax
    andl    %edi, %eax
    shrl    $31, %eax

((a<0)&(b<0) is later optimized to (a&b)<0)

vs

    shrl    $31, %esi
    xorl    %eax, %eax
    testl    %edi, %edi
    cmovs    %esi, %eax

[Bug tree-optimization/25290] PHI-OPT could be rewritten so that is uses fold

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=25290

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #5)
> Maybe not fold but rather what I am working on, gimple_combine.

Rather now gimple_simplify (which is from the match-and-simplify branch).

[Bug tree-optimization/25290] PHI-OPT could be rewritten so that is uses fold

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=25290

--- Comment #8 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #7)
> (In reply to Andrew Pinski from comment #5)
> > Maybe not fold but rather what I am working on, gimple_combine.
> 
> Rather now gimple_simplify (which is from the match-and-simplify branch).

Though I am running into an issue with this.  See
https://gcc.gnu.org/ml/gcc/2014-11/msg00055.html .

[Bug tree-optimization/25290] PHI-OPT could be rewritten so that is uses match

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=25290
Bug 25290 depends on bug 100609, which changed state.

Bug 100609 Summary: bool - 1 is not simplified to -a
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100609

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|---                         |INVALID

[Bug tree-optimization/25290] PHI-OPT could be rewritten so that is uses match

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=25290

--- Comment #16 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I Have a new patch though I need to remove some code still.

[Bug tree-optimization/25290] PHI-OPT could be rewritten so that is uses match

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=25290

--- Comment #17 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Andrew Pinski <pinskia@gcc.gnu.org>:

https://gcc.gnu.org/g:9f55df63154a39d67ef5b24def7044bf87300831

commit r12-1152-g9f55df63154a39d67ef5b24def7044bf87300831
Author: Andrew Pinski <apinski@marvell.com>
Date:   Tue Jun 1 01:05:09 2021 +0000

    Replace conditional_replacement with match and simplify

    This is the first of series of patches to simplify phi-opt
    to use match and simplify in many cases.  This simplification
    will more things to optimize.

    This is what Richard requested in
    https://gcc.gnu.org/pipermail/gcc-patches/2021-May/571197.html
    and I think it is the right thing to do too.

    OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions.

    gcc/ChangeLog:

            PR tree-optimization/25290
            * tree-ssa-phiopt.c (match_simplify_replacement):
            New function.
            (tree_ssa_phiopt_worker): Use match_simplify_replacement.
            (two_value_replacement): Change the comment about
            conditional_replacement.
            (conditional_replacement): Delete.

[Bug tree-optimization/25290] PHI-OPT could be rewritten so that is uses match

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=25290

--- Comment #18 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to CVS Commits from comment #17)

Note this is the only start of the patches, this is not fully fixed, it is
being worked on in a series of patches rather than one big one.

[Bug tree-optimization/25290] PHI-OPT could be rewritten so that is uses match

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=25290

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                URL|https://gcc.gnu.org/piperma |
                   |il/gcc-patches/2021-May/571 |
                   |055.html                    |

--- Comment #19 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
First patch for this was committed as r12-1152.
The second patch for this was posted at
https://gcc.gnu.org/pipermail/gcc-patches/2021-June/571800.html .

[Bug tree-optimization/25290] PHI-OPT could be rewritten so that is uses match

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=25290

--- Comment #20 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Andrew Pinski <pinskia@gcc.gnu.org>:

https://gcc.gnu.org/g:c4574d23cb07340918793a5a98ae7bb2988b3791

commit r12-1309-gc4574d23cb07340918793a5a98ae7bb2988b3791
Author: Andrew Pinski <apinski@marvell.com>
Date:   Tue Jun 1 06:48:05 2021 +0000

    Improve match_simplify_replacement in phi-opt

    This improves match_simplify_replace in phi-opt to handle the
    case where there is one cheap (non-call) preparation statement in the
    middle basic block similar to xor_replacement and others.
    This allows to remove xor_replacement which it does too.

    OK?  Bootstrapped and tested on x86_64-linux-gnu with no regressions.

    Thanks,
    Andrew Pinski

    Changes since v1:
    v3 - Just minor changes to using gimple_assign_lhs
    instead of gimple_lhs and fixing a comment.
    v2 - change the check on the preparation statement to
    allow only assignments and no calls and only assignments
    that feed into the phi.

    gcc/ChangeLog:

            PR tree-optimization/25290
            * tree-ssa-phiopt.c (xor_replacement): Delete.
            (tree_ssa_phiopt_worker): Delete use of xor_replacement.
            (match_simplify_replacement): Allow one cheap preparation
            statement that can be moved to before the if.

    gcc/testsuite/ChangeLog:

            * gcc.dg/tree-ssa/pr96928-1.c: Fix testcase for now that ~
            happens on the outside of the bit_xor.

[Bug tree-optimization/25290] PHI-OPT could be rewritten so that is uses match

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=25290

--- Comment #21 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Note this is not fully fixed, there is still some more work to do to deal with
the non single_non_singleton_phi_for_edges case which will allow to get rid of
value_replacement.

Note to get rid of early_p check and abs_replacement, we need to add
PROP_gimple_lswitch to say we have lowered switches already.

[Bug tree-optimization/25290] PHI-OPT could be rewritten so that is uses match

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=25290

--- Comment #22 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Without load/store handling, here are the following optimizations that either
can move to match.pd already or need some extra work to do it:

* value_replacement: need to handle !single_non_singleton_phi_for_edges case
and more than one feeder statement (2 max according to the current definition)
* cond_removal_in_popcount_clz_ctz_pattern: need 2 feeder statements and
builtin call handling for feeder statements


* two_value_replacement: recored as PR 100958, it can move already
* abs_replacement: needs PROP_gimple_lswitch so we don't change if statements
early enough
** I think majority of the abs handling is already in match.pd.
* minmax_replacement: has some handling of comparisions which might not be in
the match.pd patterns already.  needs PROP_gimple_lswitch also.
** The handling of:
         if (a <= u)
           b = MAX (a, d);
         x = PHI <b, u>
   needs to moved too.


For the ones which cannot move
* factor_out_conditional_conversion: will never move, though it needs
improvement and moved already (PR 56223 and PR 13563)
* spaceship_replacement: cannot move to match.pd depends on use afterwards
which is not hard to deal with in a match pattern.

[Bug tree-optimization/25290] PHI-OPT could be rewritten so that is uses match

[rguenther at suse dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=25290

--- Comment #23 from rguenther at suse dot de <rguenther at suse dot de> ---
On Tue, 8 Jun 2021, pinskia at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=25290
> 
> --- Comment #22 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
> * minmax_replacement: has some handling of comparisions which might not be in
> the match.pd patterns already.  needs PROP_gimple_lswitch also.

Yeah, this is also fold-const.c COND_EXPR simplifications using
fold_cond_expr_with_comparison (to ABS/MIN/MAX) which are not yet
moved to match.pd and are one reason why fold_gimple_assign still
dispatches to fold_ternary_loc ... (it shouldn't).

[Bug tree-optimization/25290] PHI-OPT could be rewritten so that is uses match

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=25290

--- Comment #24 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Next patch series can be found here which removes abs_replacement:
https://gcc.gnu.org/pipermail/gcc-patches/2021-June/573558.html

[Bug tree-optimization/25290] PHI-OPT could be rewritten so that is uses match

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=25290

--- Comment #25 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #22)
So an update on this

> * abs_replacement: needs PROP_gimple_lswitch so we don't change if
> statements early enough
> ** I think majority of the abs handling is already in match.pd.

abs_replacement is done and removed :).

> * minmax_replacement: has some handling of comparisions which might not be
> in the match.pd patterns already.  needs PROP_gimple_lswitch also.
> ** The handling of:
> 	 if (a <= u)
> 	   b = MAX (a, d);
> 	 x = PHI <b, u>
>    needs to moved too.
> 

The minmax is recorded as PR 101024.  There is some more improvements to
gimple_simplify_phiopt needed for early_p as the way min/max patterns are
generated in match.pd (extra casts).

[Bug tree-optimization/25290] PHI-OPT could be rewritten so that is uses match

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=25290

--- Comment #26 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #25)

> The minmax is recorded as PR 101024.  There is some more improvements to
> gimple_simplify_phiopt needed for early_p as the way min/max patterns are
> generated in match.pd (extra casts).

The early_p part was fixed in r12-2185-g5f2d3ff4e5e2ec .

[Bug tree-optimization/25290] PHI-OPT could be rewritten so that is uses match

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=25290

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #40185|0                           |1
        is obsolete|                            |

--- Comment #27 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Created attachment 54813
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=54813&action=edit
Set of patches for moving part of the minmax_replacement to match

This is my current set of patches for moving minmax_replacement to match.

[Bug tree-optimization/25290] PHI-OPT could be rewritten so that is uses match

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=25290

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #54813|0                           |1
        is obsolete|                            |

--- Comment #28 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Created attachment 54821
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=54821&action=edit
New set of patches including some other improvements

This new set includes moving some of cond_removal_in_builtin_zero_pattern
(though not removing it as match-and-simplify phiopt needs to be improved to
support 2 defining statements for each bb).
It also includes fixing the issue dealing with predicate statements which was
missed before.
Also reduces the number of patches for the c++ifing by combining some patches
together.

Note the first patch in the series is an obvious patch which I am going to
apply once GCC 13 branches; it removes a prototype which is not needed as
gate_hoist_loads is defined before its use.

[Bug tree-optimization/25290] PHI-OPT could be rewritten so that is uses match

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=25290

--- Comment #29 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #28)
> Created attachment 54821 [details]
> New set of patches including some other improvements

Note this series does not bootstrap, the last patch found that I had a latent
bug in the patch that started to handle diamond shaped PHIs.

For:
  if (_16 == 34)
    goto <bb 10>; [INV]
  else
    goto <bb 12>; [INV]

  <bb 10> :
  ...
  _27 = csets__identifier_char[_26];
  if (_27 != 0)
    goto <bb 11>; [INV]
  else
    goto <bb 12>; [INV]

  <bb 11> :
  // predicted unlikely by early return (on trees) predictor.
  goto <bb 13>; [INV]

  <bb 12> :
  // predicted unlikely by early return (on trees) predictor.

  <bb 13> :
  # _28 = PHI <1(7), 0(12), 1(4), 1(11)>

I would transform it to use _27 even from bb 12 which is wrong.

I had missed that minmax_replacement did:

      if (!single_pred_p (middle_bb)
          || !single_pred_p (alt_middle_bb)
          || !single_succ_p (middle_bb)
          || !single_succ_p (alt_middle_bb))
        return false;

I will add that check tomorrow.

[Bug tree-optimization/25290] PHI-OPT could be rewritten so that is uses match

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=25290

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #54821|0                           |1
        is obsolete|                            |

--- Comment #30 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Created attachment 54930
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=54930&action=edit
New set of patches

Note this is a new set, It does not do the C++ify as I had done before. It is
missing some of the factor_out_* patches from the previous set; I am
re-implementing that (the last patch in the series is the start of that).

[Bug tree-optimization/25290] PHI-OPT could be rewritten so that is uses match

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=25290

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|patch                       |

--- Comment #31 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
So what is left as of May 4th 2023:
minmax_replacement:
* some min/max detection has not moved to match (cast dealing with INT_MAX)
* `if (a < b) c = min/max(a, d)` transformation has not moved to match

cond_removal_in_builtin_zero_pattern:
* supporting of one extra statement to move out of the conditional (has to be a
cast)

[Bug tree-optimization/25290] PHI-OPT could be rewritten so that is uses match

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=25290

--- Comment #32 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
https://gcc.gnu.org/pipermail/gcc-patches/2004-June/140297.html for reference
where the original idea came from.

[Bug tree-optimization/25290] PHI-OPT could be rewritten so that is uses match

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=25290

--- Comment #33 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Marc Glisse from comment #6)
> I assume it would help with this?

Note that was fixed outside of phiopt in GCC 11 by r11-6609-g13d47c37a2c043 (PR
95731).

[Bug tree-optimization/25290] PHI-OPT could be rewritten so that is uses match

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=25290

--- Comment #34 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #22)
> Without load/store handling, here are the following optimizations that
> either can move to match.pd already or need some extra work to do it:
> 
> * value_replacement: need to handle !single_non_singleton_phi_for_edges case
> and more than one feeder statement (2 max according to the current
> definition)

There is a secondary part to value_replacement which requires more work than
just working on the phi. I have to think of how to handle that.


> * cond_removal_in_popcount_clz_ctz_pattern: need 2 feeder statements and
> builtin call handling for feeder statements



> 
> 
> * two_value_replacement: recored as PR 100958, it can move already

Handled.

> * abs_replacement: needs PROP_gimple_lswitch so we don't change if
> statements early enough
> ** I think majority of the abs handling is already in match.pd.

This is handled.

> * minmax_replacement: has some handling of comparisions which might not be
> in the match.pd patterns already.  needs PROP_gimple_lswitch also.
> ** The handling of:
> 	 if (a <= u)
> 	   b = MAX (a, d);
> 	 x = PHI <b, u>
>    needs to moved too.
> 
> 
> For the ones which cannot move

There is a new part of minmax which I have a patch for but there is one part
missing still (recorded in PR 101024)

> * factor_out_conditional_conversion: will never move, though it needs
> improvement and moved already (PR 56223 and PR 13563)

I have an implementation which moves this over to using gimple_match_op (which
I need to a few testcases for it). Though some of this maybe should move over
to match ...

> * spaceship_replacement: cannot move to match.pd depends on use afterwards
> which is not hard to deal with in a match pattern.

I have to look at what is done for spaceship and maybe merge it in with what is
done for value_replacement (comparison after the phi) since they implement a
similar optimization.