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

[Richard Biener <rguenther@suse.de>]

On Mon, 20 Jun 2022, Andrew Pinski wrote:

> On Thu, Jun 16, 2022 at 4:11 AM Tamar Christina via Gcc-patches
> <gcc-patches@gcc.gnu.org> 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.
> >
> > 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.
> 
> I have been working on getting rid of minmax_replacement and a few
> others and only having match_simplify_replacement and having the
> simplification logic all in match.pd instead.
> Is there a reason why you can't expand match_simplify_replacement and match.pd?

Btw, I have the below change pending to remove GENERIC comparison op
handling from GIMPLE matching.  I don't yet like the phi-op part very
much which is why I didn't push that yet.

Maybe you can take that into account when extending 
match_simplify_replacement...  (and maybe you have a nicer idea)

Richard.



From 5c2428227e2fbfde72244dbc4aabeecf70c763ed Mon Sep 17 00:00:00 2001
From: Richard Biener <rguenther@suse.de>
Date: Tue, 17 May 2022 09:58:59 +0200
Subject: [PATCH] Remove genmatch GENERIC condition in COND_EXPR support
To: gcc-patches@gcc.gnu.org

The following removes support for matching a GENERIC condition
in COND_EXPRs when doing GIMPLE matching.  Thus cuts 5% of the
size of gimple-match.cc.

Unfortunately it makes phiopt a bit more awkward since the
COND_EXPRs it tries to simplify no longer fit the single
gimple_match_op but instead the comparison now needs to be
separately built.  That also means it is emitted and we have
to avoid leaving it around when it is not actually used by
the simplification to make the cascading transforms work.

Handling insertion only of the used parts of a sequence as
produced by simplification or stmt build and simplification
is something that asks to be separated out in a convenient
way and I have to think on how to best do this still.

2022-05-17  Richard Biener  <rguenther@suse.de>

	* genmatch.cc ():
	* gimple-match.head.cc ():
	* tree-ssa-phiopt.cc ():
---
 gcc/genmatch.cc          | 140 +++------------------------------------
 gcc/gimple-match-head.cc |  61 +++--------------
 gcc/tree-ssa-phiopt.cc   |  45 ++++++++++---
 3 files changed, 57 insertions(+), 189 deletions(-)

diff --git a/gcc/genmatch.cc b/gcc/genmatch.cc
index 2b84b849330..5fbe5aa28b3 100644
--- a/gcc/genmatch.cc
+++ b/gcc/genmatch.cc
@@ -697,12 +697,12 @@ public:
   expr (id_base *operation_, location_t loc, bool is_commutative_ = false)
     : operand (OP_EXPR, loc), operation (operation_),
       ops (vNULL), expr_type (NULL), is_commutative (is_commutative_),
-      is_generic (false), force_single_use (false), force_leaf (false),
+      force_single_use (false), force_leaf (false),
       opt_grp (0) {}
   expr (expr *e)
     : operand (OP_EXPR, e->location), operation (e->operation),
       ops (vNULL), expr_type (e->expr_type), is_commutative (e->is_commutative),
-      is_generic (e->is_generic), force_single_use (e->force_single_use),
+      force_single_use (e->force_single_use),
       force_leaf (e->force_leaf), opt_grp (e->opt_grp) {}
   void append_op (operand *op) { ops.safe_push (op); }
   /* The operator and its operands.  */
@@ -713,8 +713,6 @@ public:
   /* Whether the operation is to be applied commutatively.  This is
      later lowered to two separate patterns.  */
   bool is_commutative;
-  /* Whether the expression is expected to be in GENERIC form.  */
-  bool is_generic;
   /* Whether pushing any stmt to the sequence should be conditional
      on this expression having a single-use.  */
   bool force_single_use;
@@ -1210,107 +1208,6 @@ lower_opt (simplify *s, vec<simplify *>& simplifiers)
     }
 }
 
-/* Lower the compare operand of COND_EXPRs to a
-   GENERIC and a GIMPLE variant.  */
-
-static vec<operand *>
-lower_cond (operand *o)
-{
-  vec<operand *> ro = vNULL;
-
-  if (capture *c = dyn_cast<capture *> (o))
-    {
-      if (c->what)
-	{
-	  vec<operand *> lop = vNULL;
-	  lop = lower_cond (c->what);
-
-	  for (unsigned i = 0; i < lop.length (); ++i)
-	    ro.safe_push (new capture (c->location, c->where, lop[i],
-				       c->value_match));
-	  return ro;
-	}
-    }
-
-  expr *e = dyn_cast<expr *> (o);
-  if (!e || e->ops.length () == 0)
-    {
-      ro.safe_push (o);
-      return ro;
-    }
-
-  vec< vec<operand *> > ops_vector = vNULL;
-  for (unsigned i = 0; i < e->ops.length (); ++i)
-    ops_vector.safe_push (lower_cond (e->ops[i]));
-
-  auto_vec< vec<operand *> > result;
-  auto_vec<operand *> v (e->ops.length ());
-  v.quick_grow_cleared (e->ops.length ());
-  cartesian_product (ops_vector, result, v, 0);
-
-  for (unsigned i = 0; i < result.length (); ++i)
-    {
-      expr *ne = new expr (e);
-      for (unsigned j = 0; j < result[i].length (); ++j)
-	ne->append_op (result[i][j]);
-      ro.safe_push (ne);
-      /* If this is a COND with a captured expression or an
-         expression with two operands then also match a GENERIC
-	 form on the compare.  */
-      if (*e->operation == COND_EXPR
-	  && ((is_a <capture *> (e->ops[0])
-	       && as_a <capture *> (e->ops[0])->what
-	       && is_a <expr *> (as_a <capture *> (e->ops[0])->what)
-	       && as_a <expr *>
-	            (as_a <capture *> (e->ops[0])->what)->ops.length () == 2)
-	      || (is_a <expr *> (e->ops[0])
-		  && as_a <expr *> (e->ops[0])->ops.length () == 2)))
-	{
-	  ne = new expr (e);
-	  for (unsigned j = 0; j < result[i].length (); ++j)
-	    ne->append_op (result[i][j]);
-	  if (capture *c = dyn_cast <capture *> (ne->ops[0]))
-	    {
-	      expr *ocmp = as_a <expr *> (c->what);
-	      expr *cmp = new expr (ocmp);
-	      for (unsigned j = 0; j < ocmp->ops.length (); ++j)
-		cmp->append_op (ocmp->ops[j]);
-	      cmp->is_generic = true;
-	      ne->ops[0] = new capture (c->location, c->where, cmp,
-					c->value_match);
-	    }
-	  else
-	    {
-	      expr *ocmp = as_a <expr *> (ne->ops[0]);
-	      expr *cmp = new expr (ocmp);
-	      for (unsigned j = 0; j < ocmp->ops.length (); ++j)
-		cmp->append_op (ocmp->ops[j]);
-	      cmp->is_generic = true;
-	      ne->ops[0] = cmp;
-	    }
-	  ro.safe_push (ne);
-	}
-    }
-
-  return ro;
-}
-
-/* Lower the compare operand of COND_EXPRs to a
-   GENERIC and a GIMPLE variant.  */
-
-static void
-lower_cond (simplify *s, vec<simplify *>& simplifiers)
-{
-  vec<operand *> matchers = lower_cond (s->match);
-  for (unsigned i = 0; i < matchers.length (); ++i)
-    {
-      simplify *ns = new simplify (s->kind, s->id, matchers[i], s->result,
-				   s->for_vec, s->capture_ids);
-      ns->for_subst_vec.safe_splice (s->for_subst_vec);
-      simplifiers.safe_push (ns);
-    }
-}
-
 /* Return true if O refers to ID.  */
 
 bool
@@ -1541,7 +1438,7 @@ lower_for (simplify *sin, vec<simplify *>& simplifiers)
 /* Lower the AST for everything in SIMPLIFIERS.  */
 
 static void
-lower (vec<simplify *>& simplifiers, bool gimple)
+lower (vec<simplify *>& simplifiers, bool)
 {
   auto_vec<simplify *> out_simplifiers;
   for (auto s: simplifiers)
@@ -1560,11 +1457,7 @@ lower (vec<simplify *>& simplifiers, bool gimple)
     lower_for (s, out_simplifiers);
 
   simplifiers.truncate (0);
-  if (gimple)
-    for (auto s: out_simplifiers)
-      lower_cond (s, simplifiers);
-  else
-    simplifiers.safe_splice (out_simplifiers);
+  simplifiers.safe_splice (out_simplifiers);
 }
 
 
@@ -1742,8 +1635,7 @@ cmp_operand (operand *o1, operand *o2)
     {
       expr *e1 = static_cast<expr *>(o1);
       expr *e2 = static_cast<expr *>(o2);
-      return (e1->operation == e2->operation
-	      && e1->is_generic == e2->is_generic);
+      return e1->operation == e2->operation;
     }
   else
     return false;
@@ -2815,26 +2707,16 @@ dt_operand::gen_gimple_expr (FILE *f, int indent, int depth)
 
       if (id->kind == id_base::CODE)
 	{
-	  if (e->is_generic
-	      || *id == REALPART_EXPR || *id == IMAGPART_EXPR
+	  if (*id == REALPART_EXPR || *id == IMAGPART_EXPR
 	      || *id == BIT_FIELD_REF || *id == VIEW_CONVERT_EXPR)
 	    {
 	      /* ???  If this is a memory operation we can't (and should not)
 		 match this.  The only sensible operand types are
 		 SSA names and invariants.  */
-	      if (e->is_generic)
-		{
-		  char opname[20];
-		  get_name (opname);
-		  fprintf_indent (f, indent,
-				  "tree %s = TREE_OPERAND (%s, %i);\n",
-				  child_opname, opname, i);
-		}
-	      else
-		fprintf_indent (f, indent,
-				"tree %s = TREE_OPERAND "
-				"(gimple_assign_rhs1 (_a%d), %i);\n",
-				child_opname, depth, i);
+	      fprintf_indent (f, indent,
+			      "tree %s = TREE_OPERAND "
+			      "(gimple_assign_rhs1 (_a%d), %i);\n",
+			      child_opname, depth, i);
 	      fprintf_indent (f, indent,
 			      "if ((TREE_CODE (%s) == SSA_NAME\n",
 			      child_opname);
@@ -2940,7 +2822,7 @@ dt_node::gen_kids (FILE *f, int indent, bool gimple, int depth)
 		preds.safe_push (op);
 	      else
 		{
-		  if (gimple && !e->is_generic)
+		  if (gimple)
 		    gimple_exprs.safe_push (op);
 		  else
 		    generic_exprs.safe_push (op);
diff --git a/gcc/gimple-match-head.cc b/gcc/gimple-match-head.cc
index 4c80d77f8ba..41a11a3cf64 100644
--- a/gcc/gimple-match-head.cc
+++ b/gcc/gimple-match-head.cc
@@ -150,17 +150,11 @@ maybe_resimplify_conditional_op (gimple_seq *seq, gimple_match_op *res_op,
       tree_code op_code = (tree_code) res_op->code;
       bool op_could_trap;
 
-      /* COND_EXPR will trap if, and only if, the condition
-	 traps and hence we have to check this.  For all other operations, we
-	 don't need to consider the operands.  */
-      if (op_code == COND_EXPR)
-	op_could_trap = generic_expr_could_trap_p (res_op->ops[0]);
-      else
-	op_could_trap = operation_could_trap_p ((tree_code) res_op->code,
-						FLOAT_TYPE_P (res_op->type),
-						honor_trapv,
-						res_op->op_or_null (1));
-
+      /* For no operations we have to consider the operands.  */
+      op_could_trap = operation_could_trap_p ((tree_code) res_op->code,
+					      FLOAT_TYPE_P (res_op->type),
+					      honor_trapv,
+					      res_op->op_or_null (1));
       if (!op_could_trap)
 	{
 	  res_op->cond.cond = NULL_TREE;
@@ -922,11 +916,10 @@ try_conditional_simplification (internal_fn ifn, gimple_match_op *res_op,
 
    Both routines take a tree argument and returns a tree.  */
 
-template<typename ValueizeOp, typename ValueizeCondition>
+template<typename ValueizeOp>
 inline bool
 gimple_extract (gimple *stmt, gimple_match_op *res_op,
-		ValueizeOp valueize_op,
-		ValueizeCondition valueize_condition)
+		ValueizeOp valueize_op)
 {
   switch (gimple_code (stmt))
     {
@@ -977,11 +970,7 @@ gimple_extract (gimple *stmt, gimple_match_op *res_op,
 	    }
 	  case GIMPLE_TERNARY_RHS:
 	    {
-	      tree rhs1 = gimple_assign_rhs1 (stmt);
-	      if (code == COND_EXPR && COMPARISON_CLASS_P (rhs1))
-		rhs1 = valueize_condition (rhs1);
-	      else
-		rhs1 = valueize_op (rhs1);
+	      tree rhs1 = valueize_op (gimple_assign_rhs1 (stmt));
 	      tree rhs2 = valueize_op (gimple_assign_rhs2 (stmt));
 	      tree rhs3 = valueize_op (gimple_assign_rhs3 (stmt));
 	      res_op->set_op (code, type, rhs1, rhs2, rhs3);
@@ -1053,7 +1042,7 @@ bool
 gimple_extract_op (gimple *stmt, gimple_match_op *res_op)
 {
   auto nop = [](tree op) { return op; };
-  return gimple_extract (stmt, res_op, nop, nop);
+  return gimple_extract (stmt, res_op, nop);
 }
 
 /* The main STMT based simplification entry.  It is used by the fold_stmt
@@ -1068,38 +1057,8 @@ gimple_simplify (gimple *stmt, gimple_match_op *res_op, gimple_seq *seq,
     {
       return do_valueize (op, top_valueize, valueized);
     };
-  auto valueize_condition = [&](tree op) -> tree
-    {
-      bool cond_valueized = false;
-      tree lhs = do_valueize (TREE_OPERAND (op, 0), top_valueize,
-			      cond_valueized);
-      tree rhs = do_valueize (TREE_OPERAND (op, 1), top_valueize,
-			      cond_valueized);
-      gimple_match_op res_op2 (res_op->cond, TREE_CODE (op),
-			       TREE_TYPE (op), lhs, rhs);
-      if ((gimple_resimplify2 (seq, &res_op2, valueize)
-	   || cond_valueized)
-	  && res_op2.code.is_tree_code ())
-	{
-	  auto code = tree_code (res_op2.code);
-	  if (TREE_CODE_CLASS (code) == tcc_comparison)
-	    {
-	      valueized = true;
-	      return build2 (code, TREE_TYPE (op),
-			     res_op2.ops[0], res_op2.ops[1]);
-	    }
-	  else if (code == SSA_NAME
-		   || code == INTEGER_CST
-		   || code == VECTOR_CST)
-	    {
-	      valueized = true;
-	      return res_op2.ops[0];
-	    }
-	}
-      return valueize_op (op);
-    };
 
-  if (!gimple_extract (stmt, res_op, valueize_op, valueize_condition))
+  if (!gimple_extract (stmt, res_op, valueize_op))
     return false;
 
   if (res_op->code.is_internal_fn ())
diff --git a/gcc/tree-ssa-phiopt.cc b/gcc/tree-ssa-phiopt.cc
index e61d9736937..8130a60e5bb 100644
--- a/gcc/tree-ssa-phiopt.cc
+++ b/gcc/tree-ssa-phiopt.cc
@@ -885,15 +885,17 @@ gimple_simplify_phiopt (bool early_p, tree type, gimple *comp_stmt,
      less efficient.
      Don't use fold_build2 here as that might create (bool)a instead of just
      "a != 0".  */
-  tree cond = build2_loc (loc, comp_code, boolean_type_node,
-			  cmp0, cmp1);
+  tree cond_def = gimple_build (&seq1, comp_code,
+				boolean_type_node, cmp0, cmp1);
   gimple_match_op op (gimple_match_cond::UNCOND,
-		      COND_EXPR, type, cond, arg0, arg1);
+		      COND_EXPR, type, cond_def, arg0, arg1);
 
   if (op.resimplify (&seq1, follow_all_ssa_edges))
     {
       /* Early we want only to allow some generated tree codes. */
       if (!early_p
+	  /* ???  The following likely needs adjustments for the extra
+	     comparison stmt.  */
 	  || phiopt_early_allow (seq1, op))
 	{
 	  result = maybe_push_res_to_seq (&op, &seq1);
@@ -915,11 +917,10 @@ gimple_simplify_phiopt (bool early_p, tree type, gimple *comp_stmt,
   if (comp_code == ERROR_MARK)
     return NULL;
 
-  cond = build2_loc (loc,
-		     comp_code, boolean_type_node,
-		     cmp0, cmp1);
+  cond_def = gimple_build (&seq1, comp_code,
+			   boolean_type_node, cmp0, cmp1);
   gimple_match_op op1 (gimple_match_cond::UNCOND,
-		       COND_EXPR, type, cond, arg1, arg0);
+		       COND_EXPR, type, cond_def, arg1, arg0);
 
   if (op1.resimplify (&seq1, follow_all_ssa_edges))
     {
@@ -1031,9 +1032,35 @@ match_simplify_replacement (basic_block cond_bb, basic_block middle_bb,
     return false;
 
   gsi = gsi_last_bb (cond_bb);
-  /* Insert the sequence generated from gimple_simplify_phiopt.  */
+  /* Insert the sequence generated from gimple_simplify_phiopt.  Remove
+     stmts no longer necessary and produced during intermediate
+     simplification.  */
   if (seq)
-    gsi_insert_seq_before (&gsi, seq, GSI_CONTINUE_LINKING);
+    {
+      gsi_insert_seq_before (&gsi, seq, GSI_CONTINUE_LINKING);
+      do
+	{
+	  gimple *s = gsi_stmt (gsi);
+	  /* ???  Cleaning the sequence before inserting would be
+	     nice, but then immediate uses and stmt operands are
+	     so nice to have...
+	     We could add a gsi_insert_seq_before wrapper doing
+	     the insertion backwards and one stmt at a time.  */
+	  def_operand_p def;
+	  if ((def = single_ssa_def_operand (s, SSA_OP_DEF))
+	      && DEF_FROM_PTR (def) != result
+	      && has_zero_uses (DEF_FROM_PTR (def))
+	      && !gimple_has_side_effects (s))
+	    {
+	      gsi_remove (&gsi, true);
+	      release_defs (s);
+	      ggc_free (s);
+	    }
+	  else
+	    gsi_next (&gsi);
+	}
+      while (gsi_stmt (gsi) != stmt);
+    }
 
   /* If there was a statement to move and the result of the statement
      is going to be used, move it to right before the original
-- 
2.35.3