> -----Original Message-----
> From: Richard Biener <rguent...@suse.de>
> Sent: Tuesday, July 12, 2022 2:19 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 Tue, 5 Jul 2022, Tamar Christina wrote:
> 
> > > >         }
> > > > +      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?
> >
> > Done.
> >
> > > why does the merge block need a single successor?
> >
> > I was using it to fix an ICE, but I realize that's not the right fix.
> > I'm now checking If the BB is empty instead, in which case it's just a
> > fall through edge so don't treat it as a diamond.
> >
> > >
> > > > +       {
> > > > +         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.
> > >
> >
> > Done.
> >
> > > >        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);
> > >
> >
> > Done.
> >
> > >
> > > >           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?
> >
> > When this function replaces the edge it doesn't seem to update the
> dominators.
> > Since It's replacing the middle BB we then end up with an error
> >
> > gcc/testsuite/gcc.dg/tree-ssa/minmax-14.c:17:1: error: dominator of 5
> > should be 4, not 2
> >
> > during early verify. So instead, I replace the BB but defer its
> > deletion until cleanup which removes it and updates the dominators.
> 
> Hmm, for a diamond shouldn't you replace
> 
>   if (EDGE_SUCC (cond_block, 0)->dest == bb)
>     edge_to_remove = EDGE_SUCC (cond_block, 1);
>   else
>     edge_to_remove = EDGE_SUCC (cond_block, 0);
> 
> with
> 
>   if (EDGE_SUCC (cond_block, 0)->dest == bb)
>     edge_to_remove = EDGE_SUCC (cond_block, 1);
>   else if (EDGE_SUCC (cond_block, 1)->dest == bb)
>     edge_to_remove = EDGE_SUCC (cond_block, 0);
> 
> thus, the code expects to be left with a fallthru to the PHI block which is
> expected to have the immediate dominator being cond_block but with a
> diamond there's a (possibly empty) block inbetween and dominators are
> wrong.

Agreed, but the (EDGE_SUCC (cond_block, 1)->dest == bb) doesn't seem like the
Right one since for a diamond there will be a block in between the two.  Did 
you perhaps
mean  EDGE_SUCC (EDGE_SUCC (cond_block, 1)->dest, 0)->dest == bb? i.e. that 
that destination
across the diamond be bb, and then you remove the middle block?

For the minmax diamond we want both edges removed, since all the code in the 
middle BBs are now
dead.  But this is probably not true in the general sense.

>>> p debug (cond_block)
<bb 2> :
xc_3 = ~xc_2(D);
xm_5 = ~xm_4(D);
xy_7 = ~xy_6(D);
_10 = MAX_EXPR <xc_2(D), xy_6(D)>;
_12 = MIN_EXPR <_10, xm_4(D)>;
_13 = ~_12;
if (xc_3 < xm_5)
  goto <bb 3>; [INV]
else
  goto <bb 4>; [INV]

>>> p debug (EDGE_SUCC (cond_block, 0)->dest)
<bb 3> :
xk_9 = MAX_EXPR <xc_3, xy_7>;
goto <bb 5>; [INV]

>>> p debug (EDGE_SUCC (cond_block, 1)->dest)
<bb 4> :
xk_8 = MAX_EXPR <xm_5, xy_7>;

>>> p debug (bb)
<bb 5> :
# xk_1 = PHI <xk_9(3), xk_8(4)>
return xk_1;

$6 = void

So something like this?

diff --git a/gcc/tree-ssa-phiopt.cc b/gcc/tree-ssa-phiopt.cc
index 72d7b40a501..c107eeea1aa 100644
--- a/gcc/tree-ssa-phiopt.cc
+++ b/gcc/tree-ssa-phiopt.cc
@@ -400,7 +400,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, bool 
delete_bb = true)
+                               edge e, gphi *phi, tree new_tree, bool 
diamond_p = false)
 {
   basic_block bb = gimple_bb (phi);
   gimple_stmt_iterator gsi;
@@ -439,9 +439,9 @@ replace_phi_edge_with_variable (basic_block cond_block,
   edge edge_to_remove;
   if (EDGE_SUCC (cond_block, 0)->dest == bb)
     edge_to_remove = EDGE_SUCC (cond_block, 1);
-  else
+  else if (!diamond_p || (diamond_p && EDGE_SUCC (EDGE_SUCC (cond_block, 
1)->dest, 0)->dest == bb))
     edge_to_remove = EDGE_SUCC (cond_block, 0);
-  if (EDGE_COUNT (edge_to_remove->dest->preds) == 1 && delete_bb)
+  if (EDGE_COUNT (edge_to_remove->dest->preds) == 1 && !diamond_p)
     {
       e->flags |= EDGE_FALLTHRU;
       e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
@@ -2147,7 +2147,7 @@ minmax_replacement (basic_block cond_bb, basic_block 
middle_bb, basic_block alt_
       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);
+      replace_phi_edge_with_variable (cond_bb, e1, phi, result, threeway_p);

       return true;
     }


Cheers,
Tamar

> 
> So I think you simply need to handle this properly (and then fall through to
> the else).
> 
> 
> > >
> > > Did you check whether the new case works when the merge block has
> > > more than two incoming edges?
> > >
> >
> > Yes, added a new testcase for it.
> >
> > > > +  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?
> >
> > I've added some more, should now have full coverage.
> 
> Great.
> 
> > >
> > > > +      /* 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?
> >
> > Done, also added a testcase which checks that it still works when -g.
> >
> > Bootstrapped Regtested on aarch64-none-linux-gnu and no issues.
> >
> > Ok for master?
> 
> Besides the above issue it looks good to me.
> 
> Thanks and sorry for the delay.
> Richard.
> 
> > 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-10.c: New test.
> >     * gcc.dg/tree-ssa/minmax-11.c: New test.
> >     * gcc.dg/tree-ssa/minmax-12.c: New test.
> >     * gcc.dg/tree-ssa/minmax-13.c: New test.
> >     * gcc.dg/tree-ssa/minmax-14.c: New test.
> >     * gcc.dg/tree-ssa/minmax-15.c: New test.
> >     * gcc.dg/tree-ssa/minmax-16.c: New test.
> >     * 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.
> >     * gcc.dg/tree-ssa/minmax-9.c: New test.
> >
> > --- inline copy of patch ---
> >
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-10.c
> > b/gcc/testsuite/gcc.dg/tree-ssa/minmax-10.c
> > new file mode 100644
> > index
> >
> 0000000000000000000000000000000000000000..589953684416a9d263084deb5
> 8f6
> > cde7094dd517
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-10.c
> > @@ -0,0 +1,20 @@
> > +/* { dg-do compile } */
> > +/* { dg-options "-O -fdump-tree-optimized" } */
> > +
> > +#include <stdint.h>
> > +
> > +uint8_t three_max (uint8_t xc, uint8_t xm, uint8_t xy) {
> > +    uint8_t         xk;
> > +    xc=~xc;
> > +    xm=~xm;
> > +    xy=~xy;
> > +    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 "optimized" } } */
> > +/* { dg-final { scan-tree-dump-times "= ~" 1 "optimized" } } */
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-11.c
> > b/gcc/testsuite/gcc.dg/tree-ssa/minmax-11.c
> > new file mode 100644
> > index
> >
> 0000000000000000000000000000000000000000..1c2ef01b5d1e639fbf95bb5ca4
> 73
> > b63cc98e9df1
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-11.c
> > @@ -0,0 +1,21 @@
> > +/* { dg-do compile } */
> > +/* { dg-options "-O -fdump-tree-optimized" } */
> > +
> > +#include <stdint.h>
> > +
> > +uint8_t three_minmax1 (uint8_t xc, uint8_t xm, uint8_t xy) {
> > +   uint8_t  xk;
> > +    xc=~xc;
> > +    xm=~xm;
> > +    xy=~xy;
> > +    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 "optimized" } } */
> > +/* { dg-final { scan-tree-dump-times "MAX_EXPR" 1 "optimized" } } */
> > +/* { dg-final { scan-tree-dump-times "= ~" 1 "optimized" } } */
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-12.c
> > b/gcc/testsuite/gcc.dg/tree-ssa/minmax-12.c
> > new file mode 100644
> > index
> >
> 0000000000000000000000000000000000000000..3d0c07d9b57dd689bcb896539
> 377
> > 27ab441e7f2b
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-12.c
> > @@ -0,0 +1,20 @@
> > +/* { 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;
> > +    xc=~xc;
> > +    xm=~xm;
> > +    xy=~xy;
> > +    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-13.c
> > b/gcc/testsuite/gcc.dg/tree-ssa/minmax-13.c
> > new file mode 100644
> > index
> >
> 0000000000000000000000000000000000000000..c0d0f27c8027ae87654532d1b9
> 19
> > cfeccf4413e0
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-13.c
> > @@ -0,0 +1,19 @@
> > +/* { 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;
> > +    xc=~xc;
> > +    xm=~xm;
> > +    xy=~xy;
> > +    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-14.c
> > b/gcc/testsuite/gcc.dg/tree-ssa/minmax-14.c
> > new file mode 100644
> > index
> >
> 0000000000000000000000000000000000000000..9c0cadbf7e3119527cb2007d01
> fe
> > 4c7dd772c069
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-14.c
> > @@ -0,0 +1,21 @@
> > +/* { dg-do compile } */
> > +/* { dg-options "-O -fdump-tree-optimized" } */
> > +
> > +#include <stdint.h>
> > +
> > +uint8_t three_minmax11 (uint8_t xc, uint8_t xm, uint8_t xy) {
> > +        uint8_t  xk;
> > +    xc=~xc;
> > +    xm=~xm;
> > +    xy=~xy;
> > +    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 "optimized" } } */
> > +/* { dg-final { scan-tree-dump-times "MAX_EXPR" 1 "optimized" } } */
> > +/* { dg-final { scan-tree-dump-times "= ~" 1 "optimized" } } */
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-15.c
> > b/gcc/testsuite/gcc.dg/tree-ssa/minmax-15.c
> > new file mode 100644
> > index
> >
> 0000000000000000000000000000000000000000..1d97a16564f069b4348ff325c4f
> d
> > 713a224f838a
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-15.c
> > @@ -0,0 +1,21 @@
> > +/* { dg-do compile } */
> > +/* { dg-options "-O -fdump-tree-phiopt" } */
> > +
> > +#include <stdint.h>
> > +#include <stdbool.h>
> > +
> > +uint8_t three_min (uint8_t xc, uint8_t xm, uint8_t xy, bool m) {
> > +    uint8_t  xk;
> > +    if (xc)
> > +      {
> > +        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-16.c
> > b/gcc/testsuite/gcc.dg/tree-ssa/minmax-16.c
> > new file mode 100644
> > index
> >
> 0000000000000000000000000000000000000000..89377a2cb341bdafa6ba145c61
> c1
> > f966af536839
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-16.c
> > @@ -0,0 +1,17 @@
> > +/* { dg-do compile } */
> > +/* { dg-options "-O -fdump-tree-phiopt -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;
> > +}
> > +
> > +/* { 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-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/minmax-9.c
> > b/gcc/testsuite/gcc.dg/tree-ssa/minmax-9.c
> > new file mode 100644
> > index
> >
> 0000000000000000000000000000000000000000..24f580271c3ac3945860b506d4
> dc
> > 7d178a826093
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-9.c
> > @@ -0,0 +1,20 @@
> > +/* { dg-do compile } */
> > +/* { dg-options "-O -fdump-tree-optimized" } */
> > +
> > +#include <stdint.h>
> > +
> > +uint8_t three_min (uint8_t xc, uint8_t xm, uint8_t xy) {
> > +   uint8_t  xk;
> > +    xc=~xc;
> > +    xm=~xm;
> > +    xy=~xy;
> > +    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 "= ~" 1 "optimized" } } */
> > +/* { dg-final { scan-tree-dump-times "MAX_EXPR" 2 "optimized" } } */
> > 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
> >
> e61d9736937573d773acdf3e43a7c76074bfb2c7..df543b22cd720538c14bcea72f
> c7
> > 8a8dec9bf12b 100644
> > --- a/gcc/tree-ssa-phiopt.cc
> > +++ b/gcc/tree-ssa-phiopt.cc
> > @@ -63,8 +63,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, @@
> > -74,7 +74,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);
> > @@ -200,6 +200,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_p = false;
> >
> >        bb = bb_order[i];
> >
> > @@ -266,6 +267,9 @@ 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
> > +          && !empty_block_p (bb1))
> > +   diamond_p = true;
> >        else
> >     continue;
> >
> > @@ -294,10 +298,13 @@ tree_ssa_phiopt_worker (bool do_store_elim,
> bool do_hoist_loads, bool early_p)
> >     }
> >        else
> >     {
> > -     gimple_seq phis = phi_nodes (bb2);
> >       gimple_stmt_iterator gsi;
> >       bool candorest = true;
> >
> > +     /* Check that we're looking for nested phis.  */
> > +     basic_block merge = diamond_p ? EDGE_SUCC (bb2, 0)->dest : bb2;
> > +     gimple_seq phis = phi_nodes (merge);
> > +
> >       /* Value replacement can work with more than one PHI
> >          so try that first. */
> >       if (!early_p)
> > @@ -317,6 +324,7 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool
> do_hoist_loads, bool early_p)
> >       if (!candorest)
> >         continue;
> >
> > +     e2 = diamond_p ? EDGE_SUCC (bb2, 0) : e2;
> >       phi = single_non_singleton_phi_for_edges (phis, e1, e2);
> >       if (!phi)
> >         continue;
> > @@ -330,6 +338,7 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool
> > do_hoist_loads, bool early_p)
> >
> >       gphi *newphi;
> >       if (single_pred_p (bb1)
> > +         && !diamond_p
> >           && (newphi = factor_out_conditional_conversion (e1, e2, phi,
> >                                                           arg0, arg1,
> >                                                           cond_stmt)))
> > @@ -344,20 +353,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_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_p
> > +              && match_simplify_replacement (bb, bb1, e1, e2, phi,
> > +                                             arg0, arg1, early_p))
> >         cfgchanged = true;
> >       else if (!early_p
> > +              && !diamond_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_p))
> >         cfgchanged = true;
> >       else if (single_pred_p (bb1)
> > +              && !diamond_p
> >                && spaceship_replacement (bb, bb1, e1, e2, phi, arg0,
> arg1))
> >         cfgchanged = true;
> >     }
> > @@ -386,7 +400,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;
> > @@ -427,7 +441,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)
> >      {
> >        e->flags |= EDGE_FALLTHRU;
> >        e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); @@ -
> 1733,15
> > +1747,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;
> > @@ -1896,16 +1947,20 @@ 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 == e1);
> >        arg_true = arg0;
> >        arg_false = arg1;
> >      }
> >    else
> >      {
> >        gcc_assert (false_edge == e0);
> > -      gcc_assert (true_edge == e1);
> > +      if (!threeway_p)
> > +   gcc_assert (true_edge == e1);
> >        arg_true = arg1;
> >        arg_false = arg0;
> >      }
> > @@ -1937,6 +1992,165 @@ 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)
> > +     || !single_succ_p (middle_bb)
> > +     || !single_succ_p (alt_middle_bb))
> > +   return false;
> > +
> > +      /* 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 == EDGE_PRED (e1->src, 0));
> > +      else
> > +   gcc_assert (true_edge == EDGE_PRED (e1->src, 0));
> > +
> > +      bool valid_minmax_p = false;
> > +      gimple_stmt_iterator it1
> > +   = gsi_start_nondebug_after_labels_bb (middle_bb);
> > +      gimple_stmt_iterator it2
> > +   = gsi_start_nondebug_after_labels_bb (alt_middle_bb);
> > +      if (gsi_one_nondebug_before_end_p (it1)
> > +     && gsi_one_nondebug_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);
> > +         valid_minmax_p = (code1 == MIN_EXPR || code1 == MAX_EXPR)
> > +                          && (code2 == MIN_EXPR || code2 ==
> MAX_EXPR);
> > +       }
> > +   }
> > +
> > +      if (!valid_minmax_p)
> > +   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;
> > +
> > +      if (!operand_equal_for_phi_arg_p (lhs, arg_true)
> > +    || !operand_equal_for_phi_arg_p (alt_lhs, arg_false))
> > +   return false;
> > +
> > +      alt_op0 = gimple_assign_rhs1 (assign);
> > +      alt_op1 = gimple_assign_rhs2 (assign);
> > +
> > +      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;
> > +
> > +      /* Emit the statement to compute min/max.  */
> > +      location_t locus = gimple_location (last_stmt (cond_bb));
> > +      gimple_seq stmts = NULL;
> > +      tree phi_result = PHI_RESULT (phi);
> > +      result = gimple_build (&stmts, locus, minmax, TREE_TYPE (phi_result),
> > +                        arg0, bound);
> > +      result = gimple_build (&stmts, locus, ass_code, TREE_TYPE
> (phi_result),
> > +                        result, arg1);
> > +      if (invert)
> > +   result = gimple_build (&stmts, locus, 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, Frankenstrasse 146, 90461
> Nuernberg, Germany; GF: Ivo Totev, Andrew Myers, Andrew McDonald,
> Boudien Moerman; HRB 36809 (AG Nuernberg)

Reply via email to