> -----Original Message-----
> From: Richard Biener <rguent...@suse.de>
> Sent: Tuesday, June 21, 2022 2:15 PM
> To: Tamar Christina <tamar.christ...@arm.com>
> Cc: gcc-patches@gcc.gnu.org; nd <n...@arm.com>; ja...@redhat.com
> Subject: RE: [PATCH 2/2]middle-end: Support recognition of three-way
> max/min.
> 
> On Mon, 20 Jun 2022, Tamar Christina wrote:
> 
> > > -----Original Message-----
> > > From: Richard Biener <rguent...@suse.de>
> > > Sent: Monday, June 20, 2022 9:36 AM
> > > To: Tamar Christina <tamar.christ...@arm.com>
> > > Cc: gcc-patches@gcc.gnu.org; nd <n...@arm.com>; ja...@redhat.com
> > > Subject: Re: [PATCH 2/2]middle-end: Support recognition of three-way
> > > max/min.
> > >
> > > On Thu, 16 Jun 2022, Tamar Christina wrote:
> > >
> > > > Hi All,
> > > >
> > > > This patch adds support for three-way min/max recognition in phi-opts.
> > > >
> > > > Concretely for e.g.
> > > >
> > > > #include <stdint.h>
> > > >
> > > > uint8_t three_min (uint8_t xc, uint8_t xm, uint8_t xy) {
> > > >         uint8_t  xk;
> > > >     if (xc < xm) {
> > > >         xk = (uint8_t) (xc < xy ? xc : xy);
> > > >     } else {
> > > >         xk = (uint8_t) (xm < xy ? xm : xy);
> > > >     }
> > > >     return xk;
> > > > }
> > > >
> > > > we generate:
> > > >
> > > >   <bb 2> [local count: 1073741824]:
> > > >   _5 = MIN_EXPR <xc_1(D), xy_3(D)>;
> > > >   _7 = MIN_EXPR <xm_2(D), _5>;
> > > >   return _7;
> > > >
> > > > instead of
> > > >
> > > >   <bb 2>:
> > > >   if (xc_2(D) < xm_3(D))
> > > >     goto <bb 3>;
> > > >   else
> > > >     goto <bb 4>;
> > > >
> > > >   <bb 3>:
> > > >   xk_5 = MIN_EXPR <xc_2(D), xy_4(D)>;
> > > >   goto <bb 5>;
> > > >
> > > >   <bb 4>:
> > > >   xk_6 = MIN_EXPR <xm_3(D), xy_4(D)>;
> > > >
> > > >   <bb 5>:
> > > >   # xk_1 = PHI <xk_5(3), xk_6(4)>
> > > >   return xk_1;
> > > >
> > > > The same function also immediately deals with turning a
> > > > minimization problem into a maximization one if the results are
> > > > inverted.  We do this here since doing it in match.pd would end up
> > > > changing the shape of the BBs and adding additional instructions
> > > > which would prevent various
> > > optimizations from working.
> > >
> > > Can you explain a bit more?
> >
> > I'll respond to this one first In case it changes how you want me to 
> > proceed.
> >
> > I initially had used a match.pd rule to do the min to max conversion,
> > but a number of testcases started to fail.  The reason was that a lot
> > of the foldings checked that the BB contains only a single SSA and that that
> SSA is a phi node.
> >
> > By changing the min into max, the negation of the result ends up In
> > the same BB and so the optimizations are skipped leading to less optimal
> code.
> >
> > I did look into relaxing those phi opts but it felt like I'd make a
> > rather arbitrary exception for minus and seemed better to handle it in the
> minmax folding.
> 
> That's a possibility but we try to maintain a single place for a transform 
> which
> might be in match.pd which would then also handle this when there's a RHS
> COND_EXPR connecting the stmts rather than a PHI node.

Sorry, I am probably missing something here.  Just to be clear at the moment I 
just do it all in
minmax_replacement, so everything is already in one place.  It's a simple 
extension of the code
already there.

Are you suggesting I have to move it all to match.pd?  That's non-trivial..

Thanks,
Tamar

> 
> Richard.
> 
> > Thanks,
> > Tamar
> >
> > >
> > > > Bootstrapped Regtested on aarch64-none-linux-gnu and no issues.
> > > >
> > > > Ok for master?
> > > >
> > > > Thanks,
> > > > Tamar
> > > >
> > > > gcc/ChangeLog:
> > > >
> > > >         * tree-ssa-phiopt.cc (minmax_replacement): Optionally search for
> > > the phi
> > > >         sequence of a three-way conditional.
> > > >         (replace_phi_edge_with_variable): Support deferring of BB 
> > > > removal.
> > > >         (tree_ssa_phiopt_worker): Detect diamond phi structure for 
> > > > three-
> > > way
> > > >         min/max.
> > > >         (strip_bit_not, invert_minmax_code): New.
> > > >
> > > > gcc/testsuite/ChangeLog:
> > > >
> > > >         * gcc.dg/tree-ssa/split-path-1.c: Disable phi-opts so we don't
> > > optimize
> > > >         code away.
> > > >         * gcc.dg/tree-ssa/minmax-3.c: New test.
> > > >         * gcc.dg/tree-ssa/minmax-4.c: New test.
> > > >         * gcc.dg/tree-ssa/minmax-5.c: New test.
> > > >         * gcc.dg/tree-ssa/minmax-6.c: New test.
> > > >         * gcc.dg/tree-ssa/minmax-7.c: New test.
> > > >         * gcc.dg/tree-ssa/minmax-8.c: New test.
> > > >
> > > > --- inline copy of patch --
> > > > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-3.c
> > > > b/gcc/testsuite/gcc.dg/tree-ssa/minmax-3.c
> > > > new file mode 100644
> > > > index
> > > >
> > >
> 0000000000000000000000000000000000000000..de3b2e946e81701e3b75f580e
> > > 6a8
> > > > 43695a05786e
> > > > --- /dev/null
> > > > +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-3.c
> > > > @@ -0,0 +1,17 @@
> > > > +/* { dg-do compile } */
> > > > +/* { dg-options "-O -fdump-tree-phiopt" } */
> > > > +
> > > > +#include <stdint.h>
> > > > +
> > > > +uint8_t three_min (uint8_t xc, uint8_t xm, uint8_t xy) {
> > > > +       uint8_t  xk;
> > > > +    if (xc < xm) {
> > > > +        xk = (uint8_t) (xc < xy ? xc : xy);
> > > > +    } else {
> > > > +        xk = (uint8_t) (xm < xy ? xm : xy);
> > > > +    }
> > > > +    return xk;
> > > > +}
> > > > +
> > > > +/* { dg-final { scan-tree-dump-times "MIN_EXPR" 3 "phiopt1" } }
> > > > +*/
> > > > +/* { dg-final { scan-tree-dump-times "MAX_EXPR" 0 "phiopt1" } }
> > > > +*/
> > > > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-4.c
> > > > b/gcc/testsuite/gcc.dg/tree-ssa/minmax-4.c
> > > > new file mode 100644
> > > > index
> > > >
> > >
> 0000000000000000000000000000000000000000..0b6d667be868c2405eaefd17c
> > > b52
> > > > 2da44bafa0e2
> > > > --- /dev/null
> > > > +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-4.c
> > > > @@ -0,0 +1,17 @@
> > > > +/* { dg-do compile } */
> > > > +/* { dg-options "-O -fdump-tree-phiopt" } */
> > > > +
> > > > +#include <stdint.h>
> > > > +
> > > > +uint8_t three_max (uint8_t xc, uint8_t xm, uint8_t xy) {
> > > > +    uint8_t     xk;
> > > > +    if (xc > xm) {
> > > > +        xk = (uint8_t) (xc > xy ? xc : xy);
> > > > +    } else {
> > > > +        xk = (uint8_t) (xm > xy ? xm : xy);
> > > > +    }
> > > > +    return xk;
> > > > +}
> > > > +
> > > > +/* { dg-final { scan-tree-dump-times "MIN_EXPR" 0 "phiopt1" } }
> > > > +*/
> > > > +/* { dg-final { scan-tree-dump-times "MAX_EXPR" 3 "phiopt1" } }
> > > > +*/
> > > > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-5.c
> > > > b/gcc/testsuite/gcc.dg/tree-ssa/minmax-5.c
> > > > new file mode 100644
> > > > index
> > > >
> > >
> 0000000000000000000000000000000000000000..650601a3cc75d09a9e6e54a35f
> > > 5b
> > > > 9993074f8510
> > > > --- /dev/null
> > > > +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-5.c
> > > > @@ -0,0 +1,17 @@
> > > > +/* { dg-do compile } */
> > > > +/* { dg-options "-O -fdump-tree-phiopt" } */
> > > > +
> > > > +#include <stdint.h>
> > > > +
> > > > +uint8_t three_minmax1 (uint8_t xc, uint8_t xm, uint8_t xy) {
> > > > +       uint8_t  xk;
> > > > +    if (xc > xm) {
> > > > +        xk = (uint8_t) (xc < xy ? xc : xy);
> > > > +    } else {
> > > > +        xk = (uint8_t) (xm < xy ? xm : xy);
> > > > +    }
> > > > +    return xk;
> > > > +}
> > > > +
> > > > +/* { dg-final { scan-tree-dump-times "MIN_EXPR" 2 "phiopt1" } }
> > > > +*/
> > > > +/* { dg-final { scan-tree-dump-times "MAX_EXPR" 1 "phiopt1" } }
> > > > +*/
> > > > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-6.c
> > > > b/gcc/testsuite/gcc.dg/tree-ssa/minmax-6.c
> > > > new file mode 100644
> > > > index
> > > >
> > >
> 0000000000000000000000000000000000000000..a628f6d99222958cfd8c410f0e
> > > 85
> > > > 639e3a49dd4b
> > > > --- /dev/null
> > > > +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-6.c
> > > > @@ -0,0 +1,17 @@
> > > > +/* { dg-do compile } */
> > > > +/* { dg-options "-O -fdump-tree-phiopt" } */
> > > > +
> > > > +#include <stdint.h>
> > > > +
> > > > +uint8_t three_minmax3 (uint8_t xc, uint8_t xm, uint8_t xy) {
> > > > +        uint8_t  xk;
> > > > +    if (xc > xm) {
> > > > +        xk = (uint8_t) (xy < xc ? xc : xy);
> > > > +    } else {
> > > > +        xk = (uint8_t) (xm < xy ? xm : xy);
> > > > +    }
> > > > +    return xk;
> > > > +}
> > > > +
> > > > +/* { dg-final { scan-tree-dump-times "MIN_EXPR" 1 "phiopt1" } }
> > > > +*/
> > > > +/* { dg-final { scan-tree-dump-times "MAX_EXPR" 1 "phiopt1" } }
> > > > +*/
> > > > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-7.c
> > > > b/gcc/testsuite/gcc.dg/tree-ssa/minmax-7.c
> > > > new file mode 100644
> > > > index
> > > >
> > >
> 0000000000000000000000000000000000000000..cb42412c4ada433b2f59df0a8b
> > > ef
> > > > 9fa7b1c5e104
> > > > --- /dev/null
> > > > +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-7.c
> > > > @@ -0,0 +1,16 @@
> > > > +/* { dg-do compile } */
> > > > +/* { dg-options "-O -fdump-tree-phiopt" } */
> > > > +
> > > > +#include <stdint.h>
> > > > +
> > > > +uint8_t three_minmax2 (uint8_t xc, uint8_t xm, uint8_t xy) {
> > > > +       uint8_t  xk;
> > > > +    if (xc > xm) {
> > > > +        xk = (uint8_t) (xc > xy ? xc : xy);
> > > > +    } else {
> > > > +        xk = (uint8_t) (xm < xy ? xm : xy);
> > > > +    }
> > > > +    return xk;
> > > > +}
> > > > +/* { dg-final { scan-tree-dump-times "MIN_EXPR" 1 "phiopt1" } }
> > > > +*/
> > > > +/* { dg-final { scan-tree-dump-times "MAX_EXPR" 1 "phiopt1" } }
> > > > +*/
> > > > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-8.c
> > > > b/gcc/testsuite/gcc.dg/tree-ssa/minmax-8.c
> > > > new file mode 100644
> > > > index
> > > >
> > >
> 0000000000000000000000000000000000000000..9cd050e932376bc50bd6ae60c
> > > b65
> > > > 4fcab0bfdd1c
> > > > --- /dev/null
> > > > +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-8.c
> > > > @@ -0,0 +1,17 @@
> > > > +/* { dg-do compile } */
> > > > +/* { dg-options "-O -fdump-tree-phiopt" } */
> > > > +
> > > > +#include <stdint.h>
> > > > +
> > > > +uint8_t three_minmax11 (uint8_t xc, uint8_t xm, uint8_t xy) {
> > > > +        uint8_t  xk;
> > > > +    if (xc < xm) {
> > > > +        xk = (uint8_t) (xc > xy ? xc : xy);
> > > > +    } else {
> > > > +        xk = (uint8_t) (xm > xy ? xm : xy);
> > > > +    }
> > > > +    return xk;
> > > > +}
> > > > +
> > > > +/* { dg-final { scan-tree-dump-times "MIN_EXPR" 1 "phiopt1" } }
> > > > +*/
> > > > +/* { dg-final { scan-tree-dump-times "MAX_EXPR" 2 "phiopt1" } }
> > > > +*/
> > > > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/split-path-1.c
> > > > b/gcc/testsuite/gcc.dg/tree-ssa/split-path-1.c
> > > > index
> > > >
> > >
> 8b23ef4c7a3484cdc1647ee6d1b150f15685beff..902dde44a50e171b4f34ba724
> > > 7d7
> > > > 5a32d2c860ed 100644
> > > > --- a/gcc/testsuite/gcc.dg/tree-ssa/split-path-1.c
> > > > +++ b/gcc/testsuite/gcc.dg/tree-ssa/split-path-1.c
> > > > @@ -1,5 +1,5 @@
> > > >  /* { dg-do run } */
> > > > -/* { dg-options "-O2 -fsplit-paths
> > > > -fdump-tree-split-paths-details --param
> > > > max-jump-thread-duplication-stmts=20" } */
> > > > +/* { dg-options "-O2 -fsplit-paths
> > > > +-fdump-tree-split-paths-details --param
> > > > +max-jump-thread-duplication-stmts=20 -fno-ssa-phiopt" } */
> > > >
> > > >  #include <stdio.h>
> > > >  #include <stdlib.h>
> > > > diff --git a/gcc/tree-ssa-phiopt.cc b/gcc/tree-ssa-phiopt.cc index
> > > >
> > >
> 562468b7f02a9ffe2713318add551902c14f89c3..6246f054006ff16e73602e7ce2
> > > e
> > > 3
> > > > 67d2d21421b1 100644
> > > > --- a/gcc/tree-ssa-phiopt.cc
> > > > +++ b/gcc/tree-ssa-phiopt.cc
> > > > @@ -62,8 +62,8 @@ static gphi *factor_out_conditional_conversion
> > > > (edge,
> > > edge, gphi *, tree, tree,
> > > >                                                 gimple *);
> > > >  static int value_replacement (basic_block, basic_block,
> > > >                               edge, edge, gphi *, tree, tree); -static 
> > > > bool
> > > > minmax_replacement (basic_block, basic_block,
> > > > -                               edge, edge, gphi *, tree, tree);
> > > > +static bool minmax_replacement (basic_block, basic_block,
> basic_block,
> > > > +                               edge, edge, gphi *, tree, tree, bool);
> > > >  static bool spaceship_replacement (basic_block, basic_block,
> > > >                                    edge, edge, gphi *, tree, tree);  
> > > > static bool
> > > > cond_removal_in_builtin_zero_pattern (basic_block, basic_block, @@
> > > > -73,7 +73,7 @@ static bool cond_store_replacement (basic_block,
> > > basic_block, edge, edge,
> > > >                                     hash_set<tree> *);
> > > >  static bool cond_if_else_store_replacement (basic_block,
> > > > basic_block, basic_block);  static hash_set<tree> *
> > > > get_non_trapping (); -static void replace_phi_edge_with_variable
> > > > (basic_block, edge, gphi *, tree);
> > > > +static void replace_phi_edge_with_variable (basic_block, edge,
> > > > +gphi *, tree, bool);
> > > >  static void hoist_adjacent_loads (basic_block, basic_block,
> > > >                                   basic_block, basic_block);
> > > >  static bool gate_hoist_loads (void); @@ -199,6 +199,7 @@
> > > > tree_ssa_phiopt_worker (bool do_store_elim, bool
> > > do_hoist_loads, bool early_p)
> > > >        basic_block bb1, bb2;
> > > >        edge e1, e2;
> > > >        tree arg0, arg1;
> > > > +      bool diamond_minmax_p = false;
> > > >
> > > >        bb = bb_order[i];
> > > >
> > > > @@ -265,6 +266,29 @@ tree_ssa_phiopt_worker (bool do_store_elim,
> > > bool do_hoist_loads, bool early_p)
> > > >             hoist_adjacent_loads (bb, bb1, bb2, bb3);
> > > >           continue;
> > > >         }
> > > > +      else if (EDGE_SUCC (bb1, 0)->dest == EDGE_SUCC (bb2, 0)->dest
> > > > +              && single_succ_p (bb1)
> > > > +              && single_succ_p (bb2)
> > > > +              && single_pred_p (bb1)
> > > > +              && single_pred_p (bb2)
> > > > +              && single_succ_p (EDGE_SUCC (bb1, 0)->dest))
> > >
> > > please do the single_succ/pred checks below where appropriate, also
> > > what's the last check about?  why does the merge block need a single
> successor?
> > >
> > > > +       {
> > > > +         gimple_stmt_iterator it1 = gsi_start_nondebug_after_labels_bb
> > > (bb1);
> > > > +         gimple_stmt_iterator it2 = gsi_start_nondebug_after_labels_bb
> > > (bb2);
> > > > +         if (gsi_one_before_end_p (it1) && gsi_one_before_end_p (it2))
> > > > +           {
> > > > +             gimple *stmt1 = gsi_stmt (it1);
> > > > +             gimple *stmt2 = gsi_stmt (it2);
> > > > +             if (is_gimple_assign (stmt1) && is_gimple_assign (stmt2))
> > > > +               {
> > > > +                 enum tree_code code1 = gimple_assign_rhs_code (stmt1);
> > > > +                 enum tree_code code2 = gimple_assign_rhs_code (stmt2);
> > > > +                 diamond_minmax_p
> > > > +                   = (code1 == MIN_EXPR || code1 == MAX_EXPR)
> > > > +                     && (code2 == MIN_EXPR || code2 == MAX_EXPR);
> > > > +               }
> > > > +           }
> > > > +       }
> > >
> > > I'd generalize this to general diamond detection, simply cutting off
> > > *_replacement workers that do not handle diamonds and do appropriate
> > > checks in minmax_replacement only.
> > >
> > > >        else
> > > >         continue;
> > > >
> > > > @@ -316,6 +340,13 @@ tree_ssa_phiopt_worker (bool do_store_elim,
> > > bool do_hoist_loads, bool early_p)
> > > >           if (!candorest)
> > > >             continue;
> > > >
> > > > +         /* Check that we're looking for nested phis.  */
> > > > +         if (phis == NULL && diamond_minmax_p)
> > > > +           {
> > > > +             phis = phi_nodes (EDGE_SUCC (bb2, 0)->dest);
> > > > +             e2 = EDGE_SUCC (bb2, 0);
> > > > +           }
> > > > +
> > >
> > > instead
> > >
> > >           basic_block merge = diamond_p ? EDGE_SUCC (bb2, 0)->dest : bb2;
> > >           gimple_seq phis = phi_nodes (merge);
> > >
> > >
> > > >           phi = single_non_singleton_phi_for_edges (phis, e1, e2);
> > > >           if (!phi)
> > > >             continue;
> > > > @@ -329,6 +360,7 @@ tree_ssa_phiopt_worker (bool do_store_elim,
> > > > bool do_hoist_loads, bool early_p)
> > > >
> > > >           gphi *newphi;
> > > >           if (single_pred_p (bb1)
> > > > +             && !diamond_minmax_p
> > > >               && (newphi = factor_out_conditional_conversion (e1, e2, 
> > > > phi,
> > > >                                                               arg0, 
> > > > arg1,
> > > >                                                               
> > > > cond_stmt)))
> > > > @@ -343,20 +375,25 @@ tree_ssa_phiopt_worker (bool
> do_store_elim,
> > > bool do_hoist_loads, bool early_p)
> > > >             }
> > > >
> > > >           /* Do the replacement of conditional if it can be done.  */
> > > > -         if (!early_p && two_value_replacement (bb, bb1, e2, phi, arg0,
> > > arg1))
> > > > +         if (!early_p
> > > > +             && !diamond_minmax_p
> > > > +             && two_value_replacement (bb, bb1, e2, phi, arg0, arg1))
> > > >             cfgchanged = true;
> > > > -         else if (match_simplify_replacement (bb, bb1, e1, e2, phi,
> > > > -                                              arg0, arg1,
> > > > -                                              early_p))
> > > > +         else if (!diamond_minmax_p
> > > > +                  && match_simplify_replacement (bb, bb1, e1, e2, phi,
> > > > +                                                 arg0, arg1, early_p))
> > > >             cfgchanged = true;
> > > >           else if (!early_p
> > > > +                  && !diamond_minmax_p
> > > >                    && single_pred_p (bb1)
> > > >                    && cond_removal_in_builtin_zero_pattern (bb, bb1, e1,
> > > e2,
> > > >                                                             phi, arg0, 
> > > > arg1))
> > > >             cfgchanged = true;
> > > > -         else if (minmax_replacement (bb, bb1, e1, e2, phi, arg0, 
> > > > arg1))
> > > > +         else if (minmax_replacement (bb, bb1, bb2, e1, e2, phi, arg0, 
> > > > arg1,
> > > > +                                      diamond_minmax_p))
> > > >             cfgchanged = true;
> > > >           else if (single_pred_p (bb1)
> > > > +                  && !diamond_minmax_p
> > > >                    && spaceship_replacement (bb, bb1, e1, e2, phi, arg0,
> > > arg1))
> > > >             cfgchanged = true;
> > > >         }
> > > > @@ -385,7 +422,7 @@ tree_ssa_phiopt_worker (bool do_store_elim,
> > > > bool do_hoist_loads, bool early_p)
> > > >
> > > >  static void
> > > >  replace_phi_edge_with_variable (basic_block cond_block,
> > > > -                               edge e, gphi *phi, tree new_tree)
> > > > +                               edge e, gphi *phi, tree new_tree, bool
> > > delete_bb = true)
> > > >  {
> > > >    basic_block bb = gimple_bb (phi);
> > > >    gimple_stmt_iterator gsi;
> > > > @@ -428,7 +465,7 @@ replace_phi_edge_with_variable (basic_block
> > > cond_block,
> > > >      edge_to_remove = EDGE_SUCC (cond_block, 1);
> > > >    else
> > > >      edge_to_remove = EDGE_SUCC (cond_block, 0);
> > > > -  if (EDGE_COUNT (edge_to_remove->dest->preds) == 1)
> > > > +  if (EDGE_COUNT (edge_to_remove->dest->preds) == 1 &&
> delete_bb)
> > >
> > > why do you need this change?
> > >
> > > Did you check whether the new case works when the merge block has
> > > more than two incoming edges?
> > >
> > > >      {
> > > >        e->flags |= EDGE_FALLTHRU;
> > > >        e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); @@ -
> > > 1564,15
> > > > +1601,52 @@ value_replacement (basic_block cond_bb, basic_block
> > > middle_bb,
> > > >    return 0;
> > > >  }
> > > >
> > > > +/* If VAR is an SSA_NAME that points to a BIT_NOT_EXPR then
> > > > +return the
> > > TREE for
> > > > +   the value being inverted.  */
> > > > +
> > > > +static tree
> > > > +strip_bit_not (tree var)
> > > > +{
> > > > +  if (TREE_CODE (var) != SSA_NAME)
> > > > +    return NULL_TREE;
> > > > +
> > > > +  gimple *assign = SSA_NAME_DEF_STMT (var);  if (gimple_code
> > > > + (assign) != GIMPLE_ASSIGN)
> > > > +    return NULL_TREE;
> > > > +
> > > > +  if (gimple_assign_rhs_code (assign) != BIT_NOT_EXPR)
> > > > +    return NULL_TREE;
> > > > +
> > > > +  return gimple_assign_rhs1 (assign); }
> > > > +
> > > > +/* Invert a MIN to a MAX or a MAX to a MIN expression CODE.  */
> > > > +
> > > > +enum tree_code
> > > > +invert_minmax_code (enum tree_code code) {
> > > > +  switch (code) {
> > > > +  case MIN_EXPR:
> > > > +    return MAX_EXPR;
> > > > +  case MAX_EXPR:
> > > > +    return MIN_EXPR;
> > > > +  default:
> > > > +    gcc_unreachable ();
> > > > +  }
> > > > +}
> > > > +
> > > >  /*  The function minmax_replacement does the main work of doing
> > > > the
> > > minmax
> > > >      replacement.  Return true if the replacement is done.  Otherwise
> return
> > > >      false.
> > > >      BB is the basic block where the replacement is going to be done on.
> > > ARG0
> > > > -    is argument 0 from the PHI.  Likewise for ARG1.  */
> > > > +    is argument 0 from the PHI.  Likewise for ARG1.
> > > > +
> > > > +    If THREEWAY_P then expect the BB to be laid out in diamond
> > > > + shape with
> > > each
> > > > +    BB containing only a MIN or MAX expression.  */
> > > >
> > > >  static bool
> > > > -minmax_replacement (basic_block cond_bb, basic_block middle_bb,
> > > > -                   edge e0, edge e1, gphi *phi, tree arg0, tree arg1)
> > > > +minmax_replacement (basic_block cond_bb, basic_block middle_bb,
> > > basic_block alt_middle_bb,
> > > > +                   edge e0, edge e1, gphi *phi, tree arg0, tree arg1, 
> > > > bool
> > > > +threeway_p)
> > > >  {
> > > >    tree result;
> > > >    edge true_edge, false_edge;
> > > > @@ -1727,9 +1801,14 @@ minmax_replacement (basic_block cond_bb,
> > > basic_block middle_bb,
> > > >    if (false_edge->dest == middle_bb)
> > > >      false_edge = EDGE_SUCC (false_edge->dest, 0);
> > > >
> > > > +  /* When THREEWAY_P then e1 will point to the edge of the final
> > > transition
> > > > +     from middle-bb to end.  */
> > > >    if (true_edge == e0)
> > > >      {
> > > > -      gcc_assert (false_edge == e1);
> > > > +      if (threeway_p)
> > > > +       gcc_assert (false_edge == EDGE_PRED (e1->src, 0));
> > > > +      else
> > > > +       gcc_assert (false_edge == e1);
> > > >        arg_true = arg0;
> > > >        arg_false = arg1;
> > > >      }
> > > > @@ -1768,6 +1847,133 @@ minmax_replacement (basic_block
> cond_bb,
> > > basic_block middle_bb,
> > > >        else
> > > >         return false;
> > > >      }
> > > > +  else if (middle_bb != alt_middle_bb && threeway_p)
> > > > +    {
> > > > +      /* Recognize the following case:
> > > > +
> > > > +        if (smaller < larger)
> > > > +          a = MIN (smaller, c);
> > > > +        else
> > > > +          b = MIN (larger, c);
> > > > +        x = PHI <a, b>
> > > > +
> > > > +        This is equivalent to
> > > > +
> > > > +        a = MIN (smaller, c);
> > > > +        x = MIN (larger, a);  */
> > > > +
> > > > +      gimple *assign = last_and_only_stmt (middle_bb);
> > > > +      tree lhs, op0, op1, bound;
> > > > +      tree alt_lhs, alt_op0, alt_op1;
> > > > +      bool invert = false;
> > > > +
> > > > +      if (!single_pred_p (middle_bb)
> > > > +         || !single_pred_p (alt_middle_bb))
> > > > +       return false;
> > > > +
> > > > +      if (!assign
> > > > +         || gimple_code (assign) != GIMPLE_ASSIGN)
> > > > +       return false;
> > > > +
> > > > +      lhs = gimple_assign_lhs (assign);
> > > > +      ass_code = gimple_assign_rhs_code (assign);
> > > > +      if (ass_code != MAX_EXPR && ass_code != MIN_EXPR)
> > > > +       return false;
> > > > +
> > > > +      op0 = gimple_assign_rhs1 (assign);
> > > > +      op1 = gimple_assign_rhs2 (assign);
> > > > +
> > > > +      assign = last_and_only_stmt (alt_middle_bb);
> > > > +      if (!assign
> > > > +         || gimple_code (assign) != GIMPLE_ASSIGN)
> > > > +       return false;
> > > > +
> > > > +      alt_lhs = gimple_assign_lhs (assign);
> > > > +      if (ass_code != gimple_assign_rhs_code (assign))
> > > > +       return false;
> > > > +
> > > > +      alt_op0 = gimple_assign_rhs1 (assign);
> > > > +      alt_op1 = gimple_assign_rhs2 (assign);
> > > > +
> > > > +      if (!operand_equal_for_phi_arg_p (lhs, arg_true)
> > > > +        || !operand_equal_for_phi_arg_p (alt_lhs, arg_false))
> > > > +       return false;
> > > > +
> > > > +      if ((operand_equal_for_phi_arg_p (op0, smaller)
> > > > +               || (alt_smaller
> > > > +                   && operand_equal_for_phi_arg_p (op0, alt_smaller)))
> > > > +              && (operand_equal_for_phi_arg_p (alt_op0, larger)
> > > > +                  || (alt_larger
> > > > +                      && operand_equal_for_phi_arg_p (alt_op0, 
> > > > alt_larger))))
> > > > +       {
> > > > +         /* We got here if the condition is true, i.e., SMALLER < 
> > > > LARGER.  */
> > > > +         if (!operand_equal_for_phi_arg_p (op1, alt_op1))
> > > > +           return false;
> > > > +
> > > > +         if ((arg0 = strip_bit_not (op0)) != NULL
> > > > +             && (arg1 = strip_bit_not (alt_op0)) != NULL
> > > > +             && (bound = strip_bit_not (op1)) != NULL)
> > > > +           {
> > > > +             minmax = MAX_EXPR;
> > > > +             ass_code = invert_minmax_code (ass_code);
> > > > +             invert = true;
> > > > +           }
> > > > +         else
> > > > +           {
> > > > +             bound = op1;
> > > > +             minmax = MIN_EXPR;
> > > > +             arg0 = op0;
> > > > +             arg1 = alt_op0;
> > > > +            }
> > > > +       }
> > > > +      else if ((operand_equal_for_phi_arg_p (op0, larger)
> > > > +               || (alt_larger
> > > > +                   && operand_equal_for_phi_arg_p (op0, alt_larger)))
> > > > +              && (operand_equal_for_phi_arg_p (alt_op0, smaller)
> > > > +                  || (alt_smaller
> > > > +                      && operand_equal_for_phi_arg_p (alt_op0,
> > > alt_smaller))))
> > > > +       {
> > > > +         /* We got here if the condition is true, i.e., SMALLER > 
> > > > LARGER.  */
> > > > +         if (!operand_equal_for_phi_arg_p (op1, alt_op1))
> > > > +           return false;
> > > > +
> > > > +         if ((arg0 = strip_bit_not (op0)) != NULL
> > > > +             && (arg1 = strip_bit_not (alt_op0)) != NULL
> > > > +             && (bound = strip_bit_not (op1)) != NULL)
> > > > +           {
> > > > +             minmax = MIN_EXPR;
> > > > +             ass_code = invert_minmax_code (ass_code);
> > > > +             invert = true;
> > > > +           }
> > > > +         else
> > > > +           {
> > > > +             bound = op1;
> > > > +             minmax = MAX_EXPR;
> > > > +             arg0 = op0;
> > > > +             arg1 = alt_op0;
> > > > +            }
> > > > +       }
> > > > +      else
> > > > +       return false;
> > >
> > > Did you check you have coverage for all cases above in your testcases?
> > >
> > > > +      /* Reset any range information from the basic block.  */
> > > > +      reset_flow_sensitive_info_in_bb (cond_bb);
> > >
> > > Huh.  You need to reset flow-sensitive info of the middle-bb stmt
> > > that prevails only...
> > >
> > > > +      /* Emit the statement to compute min/max.  */
> > > > +      gimple_seq stmts = NULL;
> > > > +      tree phi_result = PHI_RESULT (phi);
> > > > +      result = gimple_build (&stmts, minmax, TREE_TYPE
> > > > + (phi_result), arg0,
> > > bound);
> > > > +      result = gimple_build (&stmts, ass_code, TREE_TYPE
> > > > + (phi_result), result, arg1);
> > >
> > > ... but you are re-building both here.  And also you drop locations,
> > > the preserved min/max should keep the old, the new should get the
> > > location of ... hmm, the condition possibly?
> > >
> > > > +      if (invert)
> > > > +       result = gimple_build (&stmts, BIT_NOT_EXPR, TREE_TYPE
> > > (phi_result),
> > > > +result);
> > > > +
> > > > +      gsi = gsi_last_bb (cond_bb);
> > > > +      gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
> > > > +
> > > > +      replace_phi_edge_with_variable (cond_bb, e1, phi, result, false);
> > > > +      return true;
> > > > +    }
> > > >    else
> > > >      {
> > > >        /* Recognize the following case, assuming d <= u:
> > > >
> > > >
> > > >
> > > >
> > > >
> > >
> > > --
> > > Richard Biener <rguent...@suse.de>
> > > SUSE Software Solutions Germany GmbH, Frankenstraße 146, 90461
> > > Nuernberg, Germany; GF: Ivo Totev, Andrew Myers, Andrew McDonald,
> > > Boudien Moerman; HRB 36809 (AG Nuernberg)
> >
> 
> --
> Richard Biener <rguent...@suse.de>
> SUSE Software Solutions Germany GmbH, Frankenstraße 146, 90461
> Nuernberg, Germany; GF: Ivo Totev, Andrew Myers, Andrew McDonald,
> Boudien Moerman; HRB 36809 (AG Nuernberg)

Reply via email to