Re: [PATCH v2] Match: Support __builtin_add_overflow branch form for unsigned SAT_ADD

[Richard Biener <richard.guenther@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 8540 bytes --]

On Fri, May 24, 2024 at 8:56 AM Richard Biener
<richard.guenther@gmail.com> wrote:
>
> On Fri, May 24, 2024 at 8:37 AM Li, Pan2 <pan2.li@intel.com> wrote:
> >
> > Thanks Jeff and Richard for suggestion and reviewing.
> >
> > Have another try in phiopt to do the convert from PHI to stmt = cond ? a : b.
> > It can perform the convert from PHI to stmt = cond ? a : b successfully, and then
> > the widen-mul is able to do the recog to .SAT_ADD.
> >
> > For now, to limit the risck, the above convert from PHI to stmt = cond ? a : b only be performed when matched,
> > as well as the backend support the usadd standard name. Unfortunately, I am stuck in the case that when the lhs
> > is not matched, we need to clean up something like created stmt in previous, or we will have ICE for missing definition.
> >
> > sat_add.c: In function ‘sat_add_u_3_uint8_t’:
> > sat_add.c:69:1: error: missing definition
> >    69 | SAT_ADD_U_3(uint8_t);
> >       | ^~~~~~~~~~~
> > for SSA_NAME: _6 in statement:
> > # VUSE <.MEM_14(D)>
> > return _6;
> > during GIMPLE pass: phiopt
> > dump file: sat_add.c.046t.phiopt1
> > sat_add.c:69:1: internal compiler error: verify_ssa failed
> > 0x1db41ba verify_ssa(bool, bool
> > /home/pli/gcc/555/riscv-gnu-toolchain/gcc/__RISCV_BUILD__/../gcc/tree-ssa.cc:1203
> > 0x18e3075 execute_function_todo
> >         /home/pli/gcc/555/riscv-gnu-toolchain/gcc/__RISCV_BUILD__/../gcc/passes.cc:2096
> > 0x18e1c52 do_per_function
> >         /home/pli/gcc/555/riscv-gnu-toolchain/gcc/__RISCV_BUILD__/../gcc/passes.cc:1688
> > 0x18e3222 execute_todo
> >
> > I bet the reason is that we created new stmt like stmt_cond and stmt_val but we don't insert it.
> > Thus, there will be orphan nodes somewhere and we need something like rollback to recover the
> > gimple up to a point. I tried sorts of release_xx or likewise but seems not working.
> >
> > So is there any suggest to take care of such gimple rollback or another solution for this? Below are
> > The function to perform the convert from PHI to stmt = cond ? a : b for reference, thanks a lot.
> >
> > Pan
> >
> > diff --git a/gcc/tree-ssa-phiopt.cc b/gcc/tree-ssa-phiopt.cc
> > index 918cf50b589..7982b65bac4 100644
> > --- a/gcc/tree-ssa-phiopt.cc
> > +++ b/gcc/tree-ssa-phiopt.cc
> > @@ -486,6 +486,88 @@ phiopt_early_allow (gimple_seq &seq, gimple_match_op &op)
> >      }
> >  }
> >
> > +extern bool gimple_unsigned_integer_sat_add (tree, tree*, tree (*)(tree));
> > +
> > +/* Try to match the phi expr to the gimple cond. Return true if we can
> > +   perform the convert or return false.  There will be some restrictions
> > +   or such kind of conversion, aka:
> > +
> > +   1. Only selected pattern will try this convert.
> > +   2. The generated gassign matched the selected IFN pattern.
> > +   3. The backend has implement the standard name.
> > +
> > +   From:
> > +     <bb 2> :
> > +     _1 = x_3(D) + y_4(D);
> > +     if (_1 >= x_3(D))
> > +       goto <bb 3>; [INV]
> > +     else
> > +       goto <bb 4>; [INV]
> > +
> > +     <bb 3> :
> > +
> > +     <bb 4> :
> > +     # _2 = PHI <255(2), _1(3)>
> > +
> > +   To:
> > +     <bb 2> :
> > +     _1 = x_3(D) + y_4(D);
> > +     phi_cond_6 = _1 >= x_3(D);
> > +     _2 = phi_cond_6 ? _1 : 255; */
> > +
> > +static bool
> > +match_phi_to_gimple_cond (basic_block cond_bb, gphi *phi, tree arg0, tree arg1)
>
> You should do this in widen-mult and/or ISEL and if necessary for vectorization
> in tree-if-conv.cc, though eventually what if-convert creates might be
> good enough
> to match during pattern recognition.
>
> > +{
> > +  gcond *cond = as_a <gcond *> (*gsi_last_bb (cond_bb));
> > +
> > +  if (!cond)
> > +    return false;
> > +
> > +  enum tree_code code = gimple_cond_code (cond);
> > +  tree phi_result = gimple_phi_result (phi);
> > +  tree cond_tree = make_temp_ssa_name (boolean_type_node, NULL, "phi_cond");
> > +  tree cmp_tree = build2 (code, boolean_type_node, gimple_cond_lhs (cond),
> > +                         gimple_cond_rhs (cond));
> > +  tree rhs = build3 (COND_EXPR, TREE_TYPE (phi_result), cond_tree, arg0, arg1);
>
> phiopt directly uses cmp_tree, so you could do that as well and avoid stmt_cond.
>
> > +
> > +  gassign *stmt_cond = gimple_build_assign (cond_tree, cmp_tree);
> > +  gassign *stmt_val = gimple_build_assign (phi_result, rhs);
> > +
> > +  tree ops[2];
> > +  tree lhs = gimple_assign_lhs (stmt_val);
> > +  bool matched_p = (gimple_unsigned_integer_sat_add (lhs, ops, NULL)
> > +    && direct_internal_fn_supported_p (IFN_SAT_ADD, TREE_TYPE (lhs),
> > +                                      OPTIMIZE_FOR_BOTH));
> > +
> > +  if (matched_p)
> > +    {
> > +      gimple_stmt_iterator gsi = gsi_last_bb (cond_bb);
> > +      gimple_stmt_iterator psi = gsi_for_stmt (phi);
> > +
> > +      gsi_insert_before (&gsi, stmt_cond, GSI_SAME_STMT);
> > +      gsi_insert_before (&gsi, stmt_val, GSI_SAME_STMT);
> > +      remove_phi_node (&psi, false);
>
> You only matched but you do not insert the actual .SAT_ADD here and that's
> the definition that's missing.  You probably shouldn't need to add the
> cond-stmt?
>
> > +    }
> > +  else
> > +    {
> > +      // Clean up the stmt created, but non of blow works well.
> > +      // gsi = gsi_for_stmt (stmt_val);
> > +      // gsi_remove (&gsi, true);
> > +      // release_defs (stmt_val);
> > +      // ggc_free (stmt_val);
> > +
> > +      // gsi = gsi_for_stmt (stmt_cond);
> > +      // gsi_remove (&gsi, true);
> > +      // release_defs (stmt_cond);
> > +      // ggc_free (stmt_cond);
> > +
> > +      // release_defs (stmt_cond);
> > +      // release_defs (stmt_val);
> > +      release_ssa_name (cond_tree);
>
> As you don't insert the stmts you should be able to simply
> only release the SSA names and ggc_free the stmt.  You can also
> look at maybe_fold_comparisons_from_match_pd in gimple-fold.cc
> for more "ugly" ways to do this.
>
> Building a helper in one place to match a PHI def as COND_EXPR
> might be nice.  As said, avoiding all the mess by providing native
> support from genmatch would be even better, but I'm not asking you
> to do that.

For reference the attached outlines where/what to do if you are curious.

Richard.

>
> Richard.
>
> > +    }
> > +
> > +  return matched_p;
> > +}
> > +
> > /* gimple_simplify_phiopt is like gimple_simplify but designed for PHIOPT.
> >     Return NULL if nothing can be simplified or the resulting simplified value
> >     with parts pushed if EARLY_P was true. Also rejects non allowed tree code
> > @@ -826,6 +908,9 @@ match_simplify_replacement (basic_block cond_bb, basic_block middle_bb,
> >       So, given the condition COND, and the two PHI arguments, match and simplify
> >       can happen on (COND) ? arg0 : arg1. */
> >
> > +  if (match_phi_to_gimple_cond (cond_bb, phi, arg0, arg1))
> > +    return true;
> > +
> >    stmt = last_nondebug_stmt (cond_bb);
> >
> >    /* We need to know which is the true edge and which is the false
> >
> >
> > -----Original Message-----
> > From: Jeff Law <jeffreyalaw@gmail.com>
> > Sent: Thursday, May 23, 2024 10:59 PM
> > To: Richard Biener <richard.guenther@gmail.com>; Li, Pan2 <pan2.li@intel.com>
> > Cc: gcc-patches@gcc.gnu.org; juzhe.zhong@rivai.ai; kito.cheng@gmail.com; tamar.christina@arm.com; pinskia@gmail.com
> > Subject: Re: [PATCH v2] Match: Support __builtin_add_overflow branch form for unsigned SAT_ADD
> >
> >
> >
> > On 5/23/24 6:14 AM, Richard Biener wrote:
> > > On Thu, May 23, 2024 at 1:08 PM Li, Pan2 <pan2.li@intel.com> wrote:
> > >>
> > >> I have a try to convert the PHI from Part-A to Part-B, aka PHI to _2 = phi_cond ? _1 : 255.
> > >> And then we can do the matching on COND_EXPR in the underlying widen-mul pass.
> > >>
> > >> Unfortunately, meet some ICE when verify_gimple_phi in sccopy1 pass =>
> > >> sat_add.c:66:1: internal compiler error: tree check: expected class ‘type’, have ‘exceptional’ (error_mark) in useless_type_conversion_p, at gimple-expr.cc:86
> > >
> > > Likely you have released _2, more comments below on your previous mail.
> > You can be sure by calling debug_tree () on the SSA_NAME node in
> > question.  If it reports "in-free-list", then that's definitive that the
> > SSA_NAME was released back to the SSA_NAME manager.  If that SSA_NAME is
> > still in the IL, then that's very bad.
> >
> > jeff
> >

[-- Attachment #2: p --]
[-- Type: application/octet-stream, Size: 1642 bytes --]

diff --git a/gcc/genmatch.cc b/gcc/genmatch.cc
index c982c95b70f..29584d0ba20 100644
--- a/gcc/genmatch.cc
+++ b/gcc/genmatch.cc
@@ -3251,6 +3251,7 @@ dt_node::gen_kids_1 (FILE *f, int indent, bool gimple, int depth,
 			  depth);
 	  indent += 4;
 	  fprintf_indent (f, indent, "{\n");
+	  bool seen_cond_expr = false;
 	  for (unsigned i = 0; i < exprs_len; ++i)
 	    {
 	      expr *e = as_a <expr *> (gimple_exprs[i]->op);
@@ -3262,6 +3263,9 @@ dt_node::gen_kids_1 (FILE *f, int indent, bool gimple, int depth,
 	      else
 		{
 		  id_base *op = e->operation;
+		  /* ???  Mark 'e' for this processing and only handle
+		     outermost (match ... COND_EXPRs.  */
+		  seen_cond_expr |= *op == COND_EXPR;
 		  if (*op == CONVERT_EXPR || *op == NOP_EXPR)
 		    fprintf_indent (f, indent, "CASE_CONVERT:\n");
 		  else
@@ -3275,6 +3279,26 @@ dt_node::gen_kids_1 (FILE *f, int indent, bool gimple, int depth,
 	  fprintf_indent (f, indent, "default:;\n");
 	  fprintf_indent (f, indent, "}\n");
 	  indent -= 4;
+	  if (seen_cond_expr)
+	    {
+	      fprintf_indent (f, indent,
+			      "else if (gphi *_a%d = dyn_cast <gphi *> (_d%d))\n",
+			      depth, depth);
+	      indent += 2;
+	      for (unsigned i = 0; i < exprs_len; ++i)
+		{
+		  expr *e = as_a <expr *> (gimple_exprs[i]->op);
+		  if (*e->operation == COND_EXPR)
+		    {
+		      /* Now do what ::gen does, namely
+			 perform ::gen_gimple_expr but for the
+			 condition operand build a GENERIC expression
+			 from the dominating GIMPLE_COND (ugh).
+			 And then manually recurse  to gen_kids.  */
+		    }
+		}
+	      indent -= 2;
+	    }
 	}
 
       if (fns_len)