RE: [PATCH 2/2]middle-end: Support recognition of three-way max/min.

[Richard Biener <rguenther@suse.de>]

On Tue, 21 Jun 2022, Tamar Christina wrote:

> > -----Original Message-----
> > From: Richard Biener <rguenther@suse.de>
> > Sent: Tuesday, June 21, 2022 2:15 PM
> > To: Tamar Christina <Tamar.Christina@arm.com>
> > Cc: gcc-patches@gcc.gnu.org; nd <nd@arm.com>; jakub@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 <rguenther@suse.de>
> > > > Sent: Monday, June 20, 2022 9:36 AM
> > > > To: Tamar Christina <Tamar.Christina@arm.com>
> > > > Cc: gcc-patches@gcc.gnu.org; nd <nd@arm.com>; jakub@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..

I was hoping Andrew was going to respond with an estimate as to how
far he is along moving the minmax replacement to match.pd.

I'm just after less overall work.  But then improving minmax_replacement
is OK (see my comments on the actual patch), it just will make the
match.pd attempt more complex because of the need to handle diamonds.

Richard.

> 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 <rguenther@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 <rguenther@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 <rguenther@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)