On Wed, 27 Jul 2022, Tamar Christina wrote:
> > -----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?
Hmm, I think my condition was correct - the code tries to remove the
edge to the middle-block and checks the remaining edge falls through
to the merge block. With a true diamond there is no fallthru to
the merge block to keep so we better don't remove any edge?
> 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)
>
--
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)
