[PATCH] Amend match.pd syntax with force-simplified results

[PATCH] Amend match.pd syntax with force-simplified results

[Richard Biener]

This adds a ! marker to result expressions that should simplify
(and if not fail the simplification).  This can for example be
used like

(simplify
  (plus (vec_cond:s @0 @1 @2) @3)
  (vec_cond @0 (plus! @1 @3) (plus! @2 @3)))

to make the simplification only apply in case both plus operations
in the result end up simplified to a simple operand.

Bootstrap & regtest running on x86_64-unknown-linux-gnu.

2020-07-31  Richard Biener  <rguenther@suse.de>

	* genmatch.c (expr::force_leaf): Add and initialize.
	(expr::gen_transform): Honor force_leaf by passing
	NULL as sequence argument to maybe_push_res_to_seq.
	(parser::parse_expr): Allow ! marker on result expression
	operations.
	* doc/match-and-simplify.texi: Amend.
---
 gcc/doc/match-and-simplify.texi | 15 +++++++++++++++
 gcc/genmatch.c                  | 19 ++++++++++++++++---
 2 files changed, 31 insertions(+), 3 deletions(-)

diff --git a/gcc/doc/match-and-simplify.texi b/gcc/doc/match-and-simplify.texi
index 1df8b90e7c4..41980acbfe9 100644
--- a/gcc/doc/match-and-simplify.texi
+++ b/gcc/doc/match-and-simplify.texi
@@ -361,6 +361,21 @@ Usually the types of the generated result expressions are
 determined from the context, but sometimes like in the above case
 it is required that you specify them explicitely.
 
+Another modifier for generated expressions is @code{!} which
+tells the machinery to only consider the simplification in case
+the marked expression simplified to a simple operand.  Consider
+for example
+
+@smallexample
+(simplify
+  (plus (vec_cond:s @@0 @@1 @@2) @@3)
+  (vec_cond @@0 (plus! @@1 @@3) (plus! @@2 @@3)))
+@end smallexample
+
+which moves the outer @code{plus} operation to the inner arms
+of the @code{vec_cond} expression but only if the actual plus
+operations both simplify.
+
 As intermediate conversions are often optional there is a way to
 avoid the need to repeat patterns both with and without such
 conversions.  Namely you can mark a conversion as being optional
diff --git a/gcc/genmatch.c b/gcc/genmatch.c
index 0a8cba62e0c..88459d9686e 100644
--- a/gcc/genmatch.c
+++ b/gcc/genmatch.c
@@ -697,12 +697,13 @@ 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), opt_grp (0) {}
+      is_generic (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),
-      opt_grp (e->opt_grp) {}
+      force_leaf (e->force_leaf), opt_grp (e->opt_grp) {}
   void append_op (operand *op) { ops.safe_push (op); }
   /* The operator and its operands.  */
   id_base *operation;
@@ -717,6 +718,9 @@ public:
   /* Whether pushing any stmt to the sequence should be conditional
      on this expression having a single-use.  */
   bool force_single_use;
+  /* Whether in the result expression this should be a leaf node
+     with any children simplified down to simple operands.  */
+  bool force_leaf;
   /* If non-zero, the group for optional handling.  */
   unsigned char opt_grp;
   virtual void gen_transform (FILE *f, int, const char *, bool, int,
@@ -2520,7 +2524,8 @@ expr::gen_transform (FILE *f, int indent, const char *dest, bool gimple,
       fprintf (f, ");\n");
       fprintf_indent (f, indent, "tem_op.resimplify (lseq, valueize);\n");
       fprintf_indent (f, indent,
-		      "_r%d = maybe_push_res_to_seq (&tem_op, lseq);\n", depth);
+		      "_r%d = maybe_push_res_to_seq (&tem_op, %s);\n", depth,
+		      !force_leaf ? "lseq" : "NULL");
       fprintf_indent (f, indent,
 		      "if (!_r%d) return false;\n",
 		      depth);
@@ -4240,6 +4245,14 @@ parser::parse_expr ()
   bool force_capture = false;
   const char *expr_type = NULL;
 
+  if (!parsing_match_operand
+      && token->type == CPP_NOT
+      && !(token->flags & PREV_WHITE))
+    {
+      eat_token (CPP_NOT);
+      e->force_leaf = true;
+    }
+
   if (token->type == CPP_COLON
       && !(token->flags & PREV_WHITE))
     {
-- 
2.26.2

Re: [PATCH] Amend match.pd syntax with force-simplified results

[Marc Glisse]

On Fri, 31 Jul 2020, Richard Biener wrote:

> This adds a ! marker to result expressions that should simplify
> (and if not fail the simplification).  This can for example be
> used like
>
> (simplify
>  (plus (vec_cond:s @0 @1 @2) @3)
>  (vec_cond @0 (plus! @1 @3) (plus! @2 @3)))
>
> to make the simplification only apply in case both plus operations
> in the result end up simplified to a simple operand.

Thanks.

The ! syntax seems fine. If we run out, we can always introduce an 
attribute-like syntax: (plus[force_leaf] @1 @2), but we aren't there yet. 
And either this feature will see a lot of use and deserve its short 
syntax, or it won't and it will be easy to reclaim '!' for something else.

I am wondering about GENERIC. IIUC, '!' is ignored for GENERIC. Should we 
protect some/most uses of this syntax with #if GIMPLE? In my case, I think 
resimplify might simply return non-0 because it swapped the operands, 
which should not be sufficient to enable the transformation.

-- 
Marc Glisse

Re: [PATCH] Amend match.pd syntax with force-simplified results

[Richard Biener]

On Fri, 31 Jul 2020, Marc Glisse wrote:

> On Fri, 31 Jul 2020, Richard Biener wrote:
> 
> > This adds a ! marker to result expressions that should simplify
> > (and if not fail the simplification).  This can for example be
> > used like
> >
> > (simplify
> >  (plus (vec_cond:s @0 @1 @2) @3)
> >  (vec_cond @0 (plus! @1 @3) (plus! @2 @3)))
> >
> > to make the simplification only apply in case both plus operations
> > in the result end up simplified to a simple operand.
> 
> Thanks.
> 
> The ! syntax seems fine. If we run out, we can always introduce an
> attribute-like syntax: (plus[force_leaf] @1 @2), but we aren't there yet. And
> either this feature will see a lot of use and deserve its short syntax, or it
> won't and it will be easy to reclaim '!' for something else.
> 
> I am wondering about GENERIC. IIUC, '!' is ignored for GENERIC. Should we
> protect some/most uses of this syntax with #if GIMPLE? In my case, I think
> resimplify might simply return non-0 because it swapped the operands, which
> should not be sufficient to enable the transformation.

I think the resimplify logic also only works on GIMPLE.  But you are
right - I forgot about GENERIC.  But it should be straight-forward
to adjust its code generation from

         {
            tree _o1[2], _r1;
            _o1[0] = captures[2];
            _o1[1] = unshare_expr (captures[4]);
            _r1 = fold_build2_loc (loc, PLUS_EXPR, TREE_TYPE (_o1[0]), 
_o1[0], _o1[1]);
            res_op1 = _r1;
          }
          tree res_op2;
          {
            tree _o1[2], _r1;
            _o1[0] = captures[3];
            _o1[1] = captures[4];
            _r1 = fold_build2_loc (loc, PLUS_EXPR, TREE_TYPE (_o1[0]), 
_o1[0], _o1[1]);
            res_op2 = _r1;
          }
          tree _r;
          _r = fold_build3_loc (loc, VEC_COND_EXPR, type, res_op0, 
res_op1, res_op2);

to add a

      if (!CONSTANT_CLASS_P (_r1) || DECL_P (_r1))
        return NULL_TREE;

or maybe if (EXPR_P (_r1))?  On GENRIC it's a bit more difficult
since (plus! @0 @1) should be OK for say @0 == a + b and @1 == 0
simplifying to @0 itself.  Likewise @0 == a + 1 and @1 == 1
simplifying to a + 2 should be OK (we've changed a leaf).  Or
maybe that's not OK - who knows...

Of course we'd better change fold_build.. to fold_binary as well.

Or we simply automatically disable those patterns for GENERIC
(though that would probably be unexpected).

Sorry for not thinking about GENERIC - seems like a (small) mess
there ;)

Richard.

Re: [PATCH] Amend match.pd syntax with force-simplified results

[Marc Glisse]

On Fri, 31 Jul 2020, Richard Biener wrote:

> Or we simply automatically disable those patterns for GENERIC
> (though that would probably be unexpected).

Since the definition is not clear, whatever we do will be unexpected at 
least in some cases. Disabling it for GENERIC for now seems ok to me, we 
can always extend it later...

-- 
Marc Glisse

Re: [PATCH] Amend match.pd syntax with force-simplified results

[Richard Biener]

On Fri, 31 Jul 2020, Marc Glisse wrote:

> On Fri, 31 Jul 2020, Richard Biener wrote:
> 
> > Or we simply automatically disable those patterns for GENERIC
> > (though that would probably be unexpected).
> 
> Since the definition is not clear, whatever we do will be unexpected at least
> in some cases. Disabling it for GENERIC for now seems ok to me, we can always
> extend it later...

Fair enough.  I'm going to test and install the following which means
! using patterns need to be guarded with #if GIMPLE for now.

Richard.

From 3237456abe8d384ada9ef6b972ee0bd81caf8112 Mon Sep 17 00:00:00 2001
From: Richard Biener <rguenther@suse.de>
Date: Mon, 3 Aug 2020 10:30:49 +0200
Subject: [PATCH] mark match.pd ! not implemented on GENERIC

This makes us error when the ! operator modifier is encountered
when not targeting GIMPLE.

2020-08-03  Richard Biener  <rguenther@suse.de>

	* genmatch.c (parser::gimple): New.
	(parser::parser): Initialize gimple flag member.
	(parser::parse_expr): Error on ! operator modifier when
	not targeting GIMPLE.
	(main): Pass down gimple flag to parser ctor.

	* doc/match-and-simplify.texi: Amend accordingly.
---
 gcc/doc/match-and-simplify.texi |  3 ++-
 gcc/genmatch.c                  | 11 ++++++++---
 2 files changed, 10 insertions(+), 4 deletions(-)

diff --git a/gcc/doc/match-and-simplify.texi b/gcc/doc/match-and-simplify.texi
index 41980acbfe9..8752bd2afe1 100644
--- a/gcc/doc/match-and-simplify.texi
+++ b/gcc/doc/match-and-simplify.texi
@@ -374,7 +374,8 @@ for example
 
 which moves the outer @code{plus} operation to the inner arms
 of the @code{vec_cond} expression but only if the actual plus
-operations both simplify.
+operations both simplify.  Note this is currently only supported
+for code generation targeting @code{GIMPLE}.
 
 As intermediate conversions are often optional there is a way to
 avoid the need to repeat patterns both with and without such
diff --git a/gcc/genmatch.c b/gcc/genmatch.c
index 88459d9686e..109dce2d469 100644
--- a/gcc/genmatch.c
+++ b/gcc/genmatch.c
@@ -3946,7 +3946,7 @@ write_header (FILE *f, const char *head)
 class parser
 {
 public:
-  parser (cpp_reader *);
+  parser (cpp_reader *, bool gimple);
 
 private:
   const cpp_token *next ();
@@ -3983,6 +3983,7 @@ private:
   void finish_match_operand (operand *);
 
   cpp_reader *r;
+  bool gimple;
   vec<c_expr *> active_ifs;
   vec<vec<user_id *> > active_fors;
   hash_set<user_id *> *oper_lists_set;
@@ -4249,6 +4250,9 @@ parser::parse_expr ()
       && token->type == CPP_NOT
       && !(token->flags & PREV_WHITE))
     {
+      if (!gimple)
+	fatal_at (token, "forcing simplification to a leaf is not supported "
+		  "for GENERIC");
       eat_token (CPP_NOT);
       e->force_leaf = true;
     }
@@ -5042,9 +5046,10 @@ parser::finish_match_operand (operand *op)
 
 /* Main entry of the parser.  Repeatedly parse outer control structures.  */
 
-parser::parser (cpp_reader *r_)
+parser::parser (cpp_reader *r_, bool gimple_)
 {
   r = r_;
+  gimple = gimple_;
   active_ifs = vNULL;
   active_fors = vNULL;
   simplifiers = vNULL;
@@ -5151,7 +5156,7 @@ main (int argc, char **argv)
 #include "internal-fn.def"
 
   /* Parse ahead!  */
-  parser p (r);
+  parser p (r, gimple);
 
   if (gimple)
     write_header (stdout, "gimple-match-head.c");
-- 
2.26.2

Re: [PATCH] Amend match.pd syntax with force-simplified results

[Marc Glisse]

On Fri, 31 Jul 2020, Richard Biener wrote:

> This adds a ! marker to result expressions that should simplify
> (and if not fail the simplification).  This can for example be
> used like
>
> (simplify
>  (plus (vec_cond:s @0 @1 @2) @3)
>  (vec_cond @0 (plus! @1 @3) (plus! @2 @3)))
>
> to make the simplification only apply in case both plus operations
> in the result end up simplified to a simple operand.

(replacing plus with bit_ior)
The generated code in gimple_simplify_BIT_IOR_EXPR may look like

   {
     tree _o1[2], _r1;
     _o1[0] = captures[2];
     _o1[1] = captures[4];
     gimple_match_op tem_op (res_op->cond.any_else (), BIT_IOR_EXPR, TREE_TYPE (_o1[0]), _o1[0], _o1[1]);
     tem_op.resimplify (lseq, valueize);
     _r1 = maybe_push_res_to_seq (&tem_op, NULL);
     if (!_r1) return false;
     res_op->ops[1] = _r1;
   }

In particular, it contains this "return false" which directly exits the 
function, instead of just giving up on this particular transformation and 
trying the next one. I'll reorder my transformations to work around this, 
but it looks like a pre-existing limitation.

-- 
Marc Glisse

Re: [PATCH] Amend match.pd syntax with force-simplified results

[Richard Biener]

On Tue, 4 Aug 2020, Marc Glisse wrote:

> On Fri, 31 Jul 2020, Richard Biener wrote:
> 
> > This adds a ! marker to result expressions that should simplify
> > (and if not fail the simplification).  This can for example be
> > used like
> >
> > (simplify
> >  (plus (vec_cond:s @0 @1 @2) @3)
> >  (vec_cond @0 (plus! @1 @3) (plus! @2 @3)))
> >
> > to make the simplification only apply in case both plus operations
> > in the result end up simplified to a simple operand.
> 
> (replacing plus with bit_ior)
> The generated code in gimple_simplify_BIT_IOR_EXPR may look like
> 
>   {
>     tree _o1[2], _r1;
>     _o1[0] = captures[2];
>     _o1[1] = captures[4];
>     gimple_match_op tem_op (res_op->cond.any_else (), BIT_IOR_EXPR, TREE_TYPE
>     (_o1[0]), _o1[0], _o1[1]);
>     tem_op.resimplify (lseq, valueize);
>     _r1 = maybe_push_res_to_seq (&tem_op, NULL);
>     if (!_r1) return false;
>     res_op->ops[1] = _r1;
>   }
> 
> In particular, it contains this "return false" which directly exits the
> function, instead of just giving up on this particular transformation and
> trying the next one. I'll reorder my transformations to work around this, but
> it looks like a pre-existing limitation.

Yes, that's a pre-existing limitation/feature.  Once the "match" part of
a pattern applied, (plus (vec_cond:s @0 @1 @2) @3) in this case,
it wins even if it doesn't succeed in the end.  Patterns are "tried"
in the order they appear in match.pd, so you have to make sure to
put more specific ones before generic ones for example

(simplify
 (plus @1 @2)
 (if (false)
  @1)))

would shadow any later pattern with an outermost (plus ...).

genmatch tries to warn about such situations but obviously it can't
always guess correctly, in particular about "late" fails.

Hmm, looks like it doesn't warn about

(simplify
 (plus @1 @2)
 (if (false)
  @1))

(simplify
 (plus (minus @1 @2) @2)
 @1)

ah, it works in this case.  I guess which cases fall thru really
depend on the actual code generation and we could "fix" the above
mentioned issue with, hmm ... EH?  (need some block-structured thing,
placing gotos and labels will be too ugly in the code generator).
Or simply nest things more and turn

 if (..) return false;
 ...
 return true;

into

 if (!...)
   {
     ...
     return true;
   }

I guess it's something we could indeed improve on.

Richard,

-- 
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
Germany; GF: Felix Imendörffer; HRB 36809 (AG Nuernberg)

Re: [PATCH] Amend match.pd syntax with force-simplified results

[Richard Biener]

On Wed, 5 Aug 2020, Richard Biener wrote:

> On Tue, 4 Aug 2020, Marc Glisse wrote:
> 
> > On Fri, 31 Jul 2020, Richard Biener wrote:
> > 
> > > This adds a ! marker to result expressions that should simplify
> > > (and if not fail the simplification).  This can for example be
> > > used like
> > >
> > > (simplify
> > >  (plus (vec_cond:s @0 @1 @2) @3)
> > >  (vec_cond @0 (plus! @1 @3) (plus! @2 @3)))
> > >
> > > to make the simplification only apply in case both plus operations
> > > in the result end up simplified to a simple operand.
> > 
> > (replacing plus with bit_ior)
> > The generated code in gimple_simplify_BIT_IOR_EXPR may look like
> > 
> >   {
> >     tree _o1[2], _r1;
> >     _o1[0] = captures[2];
> >     _o1[1] = captures[4];
> >     gimple_match_op tem_op (res_op->cond.any_else (), BIT_IOR_EXPR, TREE_TYPE
> >     (_o1[0]), _o1[0], _o1[1]);
> >     tem_op.resimplify (lseq, valueize);
> >     _r1 = maybe_push_res_to_seq (&tem_op, NULL);
> >     if (!_r1) return false;
> >     res_op->ops[1] = _r1;
> >   }
> > 
> > In particular, it contains this "return false" which directly exits the
> > function, instead of just giving up on this particular transformation and
> > trying the next one. I'll reorder my transformations to work around this, but
> > it looks like a pre-existing limitation.
> 
> Yes, that's a pre-existing limitation/feature.  Once the "match" part of
> a pattern applied, (plus (vec_cond:s @0 @1 @2) @3) in this case,
> it wins even if it doesn't succeed in the end.  Patterns are "tried"
> in the order they appear in match.pd, so you have to make sure to
> put more specific ones before generic ones for example
> 
> (simplify
>  (plus @1 @2)
>  (if (false)
>   @1)))
> 
> would shadow any later pattern with an outermost (plus ...).
> 
> genmatch tries to warn about such situations but obviously it can't
> always guess correctly, in particular about "late" fails.
> 
> Hmm, looks like it doesn't warn about
> 
> (simplify
>  (plus @1 @2)
>  (if (false)
>   @1))
> 
> (simplify
>  (plus (minus @1 @2) @2)
>  @1)
> 
> ah, it works in this case.  I guess which cases fall thru really
> depend on the actual code generation and we could "fix" the above
> mentioned issue with, hmm ... EH?  (need some block-structured thing,
> placing gotos and labels will be too ugly in the code generator).
> Or simply nest things more and turn
> 
>  if (..) return false;
>  ...
>  return true;
> 
> into
> 
>  if (!...)
>    {
>      ...
>      return true;
>    }
> 
> I guess it's something we could indeed improve on.

OK, so the if (!..) route would be quite awkward with how the
code generator is structured.  Using EH would be straight-forward,
just wrap the code generation part in

 try {
...
 } catch (...) { return false }

and replace return false/NULL_TREE with throw; but of course we
have EH disabled.  Then the above might reasonably well translate
to a goto to a unique label we'd have to invent.

I'm testing a patch with the goto.

Richard.