[PATCH][RFC][match-and-simplify] "Manually" written patterns

[PATCH][RFC][match-and-simplify] "Manually" written patterns

[Richard Biener]

The following introduces "manually" written patterns.  That is,
part of the matching and the transform are fully manual.  An
example where this is necessary is when the result isn't really
an "expression" but a series of statements.

For example take simplifications of the memset builtin.  With
the proposal we coud write

(simplify
  (BUILT_IN_MEMSET @1 @2 integer_zerop)
  @1)
(simplify
  (BUILT_IN_MEMSET (addr@1 @4) INTEGER_CST_P@2 tree_fits_uhwi_p@3)
  (if (gimple_simplify_memset (@1, @2, @3, res_code, res_ops, seq, 
valueize)))
  /* Note "result" intentionally omitted.  The predicate if applying is
     supposed to have populated *res_code and *res_ops and seq.  */)

covering the zero-length case with a regular pattern and the rest
with a if-expr predicate that also does the transform.  Note
that parts of the argument constraining is done via regular
matching predicates and the pattern is inserted into the decision
tree as usual.

How gimple_simplify_memset looks like is visible in the patch.

Note that this exposes the implementation details of the _GIMPLE_
code-path (so the above doesn't even apply to GENERIC - luckily
I've not implemented builtin function simplification for GENERIC
so the above doesn't fall over ;)).

The syntax for the trailing args could be made nicer, but we use
'type' freely as well.

It clearly "abuses" (if ...) but it fits kind-of well.  Makes
simply omitting the result pattern in a regular simplify
fail in interesting ways though...

Caveat: runs into the issue that it's not possible to
query the number of arguments to a function (thus no
re-simplification yet).  I can lookup the decl for the
builtin and parse its DECL_ARGUMENTS, but well...
Similar issue exists when parsing built-in calls,
we can't error on not enough arguments.

Status: it builds.

Comments?

Thanks,
Richard.

2014-08-15  Richard Biener  <rguenther@suse.de>

	* match.pd: Add example memset simplification with manual
	implemented part.
	* gimple-fold.c (gimple_simplify_memset): New function.
	* gimple-fold.h (gimple_simplify_memset): Declare.
	* gimple-match-head.c (gimple_resimplify): New function.
	* genmatch.c (check_no_user_id): Guard against NULL result.
	(write_header): Likewise.
	(dt_simplify::gen_gimple): Deal with NULL result.
	(parse_simplify): Allow missing result.

Index: gcc/match.pd
===================================================================
--- gcc/match.pd	(revision 214018)
+++ gcc/match.pd	(working copy)
@@ -113,6 +113,21 @@ along with GCC; see the file COPYING3.
 #include "match-builtin.pd"
 #include "match-constant-folding.pd"
 
+
+/* "Manual" simplifications but still in the decision tree.
+   Allows us to strip off "easy" parts and (parts of) the
+   pattern/predicate matching.  */
+
+(simplify
+  (BUILT_IN_MEMSET @1 @2 integer_zerop)
+  @1)
+(simplify
+  (BUILT_IN_MEMSET (addr@1 @4) INTEGER_CST_P@2 tree_fits_uhwi_p@3)
+  (if (gimple_simplify_memset (@1, @2, @3, res_code, res_ops, seq, valueize)))
+  /* Note "result" intentionally omitted.  The predicate if applying is
+     supposed to have populated *res_code and *res_ops and seq.  */)
+
+
 /* ????s
 
    We cannot reasonably match vector CONSTRUCTORs or vector constants
Index: gcc/gimple-fold.c
===================================================================
--- gcc/gimple-fold.c	(revision 214018)
+++ gcc/gimple-fold.c	(working copy)
@@ -1335,6 +1335,80 @@ gimple_fold_builtin_memset (gimple_stmt_
   return true;
 }
 
+/* Manual simplification example.
+   Fold function call to builtin memset or bzero setting the
+   memory of size LEN to VAL.  Return whether a simplification was made.  */
+
+bool
+gimple_simplify_memset (tree dest, tree c, tree len,
+			code_helper *res_code, tree *res_ops,
+			gimple_seq *seq, tree (*valueize)(tree))
+{
+  tree etype;
+  unsigned HOST_WIDE_INT length, cval;
+
+  if (!seq)
+    return false;
+
+  /* If the LEN parameter is zero, this is handled by another pattern.
+     But as they are only differing in predicates we can still arrive
+     here (there isn't a integer_nonzerop).  */
+  if (integer_zerop (len))
+    return false;
+
+  gcc_assert (tree_fits_uhwi_p (len));
+
+  gcc_assert (TREE_CODE (c) == INTEGER_CST);
+
+  tree var = dest;
+  gcc_assert (TREE_CODE (var) == ADDR_EXPR);
+
+  var = TREE_OPERAND (var, 0);
+  if (TREE_THIS_VOLATILE (var))
+    return false;
+
+  etype = TREE_TYPE (var);
+  if (TREE_CODE (etype) == ARRAY_TYPE)
+    etype = TREE_TYPE (etype);
+
+  if (!INTEGRAL_TYPE_P (etype)
+      && !POINTER_TYPE_P (etype))
+    return false;
+
+  if (! var_decl_component_p (var))
+    return false;
+
+  length = tree_to_uhwi (len);
+  if (GET_MODE_SIZE (TYPE_MODE (etype)) != length
+      || get_pointer_alignment (dest) / BITS_PER_UNIT < length)
+    return false;
+
+  if (length > HOST_BITS_PER_WIDE_INT / BITS_PER_UNIT)
+    return false;
+
+  if (integer_zerop (c))
+    cval = 0;
+  else
+    {
+      if (CHAR_BIT != 8 || BITS_PER_UNIT != 8 || HOST_BITS_PER_WIDE_INT > 64)
+	return NULL_TREE;
+
+      cval = TREE_INT_CST_LOW (c);
+      cval &= 0xff;
+      cval |= cval << 8;
+      cval |= cval << 16;
+      cval |= (cval << 31) << 1;
+    }
+
+  var = fold_build2 (MEM_REF, etype, dest, build_int_cst (ptr_type_node, 0));
+  gimple store = gimple_build_assign (var, build_int_cst_type (etype, cval));
+  gimple_seq_add_stmt_without_update (seq, store);
+  *res_code = TREE_CODE (dest);
+  res_ops[0] = dest;
+
+  return true;
+}
+
 
 /* Return the string length, maximum string length or maximum value of
    ARG in LENGTH.
Index: gcc/gimple-fold.h
===================================================================
--- gcc/gimple-fold.h	(revision 214018)
+++ gcc/gimple-fold.h	(working copy)
@@ -121,4 +121,10 @@ tree gimple_simplify (enum built_in_func
 tree gimple_simplify (enum built_in_function, tree, tree, tree, tree,
 		      gimple_seq *, tree (*)(tree));
 
+/* Manual simplifiers.  */
+class code_helper;
+bool gimple_simplify_memset (tree dest, tree c, tree len,
+			     code_helper *res_code, tree *res_ops,
+			     gimple_seq *seq, tree (*valueize)(tree));
+
 #endif  /* GCC_GIMPLE_FOLD_H */
Index: gcc/gimple-match-head.c
===================================================================
--- gcc/gimple-match-head.c	(revision 214018)
+++ gcc/gimple-match-head.c	(working copy)
@@ -268,6 +268,31 @@ gimple_resimplify3 (gimple_seq *seq,
   return canonicalized;
 }
 
+static bool
+gimple_resimplify (gimple_seq *seq,
+		   code_helper *res_code, tree type, tree *res_ops,
+		   tree (*valueize)(tree))
+{
+  if (res_code->is_tree_code ())
+    {
+      switch (TREE_CODE_LENGTH ((tree_code) *res_code))
+	{
+	case 1:
+	  return gimple_resimplify1 (seq, res_code, type, res_ops, valueize);
+	case 2:
+	  return gimple_resimplify2 (seq, res_code, type, res_ops, valueize);
+	case 3:
+	  return gimple_resimplify3 (seq, res_code, type, res_ops, valueize);
+	default:
+	  return false;
+	}
+    }
+  else
+    {
+      /* ??? */
+      return false;
+    }
+}
 
 /* Push the exploded expression described by RCODE, TYPE and OPS
    as a statement to SEQ if necessary and return a gimple value
@@ -742,3 +767,4 @@ do_valueize (tree (*valueize)(tree), tre
     return valueize (op);
   return op;
 }
+
Index: gcc/genmatch.c
===================================================================
--- gcc/genmatch.c	(revision 214018)
+++ gcc/genmatch.c	(working copy)
@@ -822,7 +822,8 @@ void
 check_no_user_id (simplify *s)
 {
   check_no_user_id (s->match);
-  check_no_user_id (s->result);
+  if (s->result)
+    check_no_user_id (s->result);
 }
 
 /* Code gen off the AST.  */
@@ -1674,6 +1675,8 @@ dt_simplify::gen_gimple (FILE *f)
     }
       output_line_directive (f, s->result_location);
 
+      if (s->result)
+	{
       if (s->result->type == operand::OP_EXPR)
 	{
 	  expr *e = static_cast <expr *> (s->result);
@@ -1697,6 +1700,15 @@ dt_simplify::gen_gimple (FILE *f)
 	}
       else
 	gcc_unreachable ();
+	}
+      else
+	{
+	  /* ???  We can't statically determine which of the
+	     n-ary gimple_resimplify routines to call so call
+	     a dispatcher.  */
+	  fprintf (f, "gimple_resimplify (seq, res_code, type, "
+		   "res_ops, valueize);\n");
+	}
 
       fprintf (f, "return true;\n");
       if (s->ifexpr_vec != vNULL)
@@ -1954,7 +1966,8 @@ write_header (FILE *f, vec<simplify *>&
 
   /* Outline complex C expressions to helper functions.  */
   for (unsigned i = 0; i < simplifiers.length (); ++i)
-    outline_c_exprs (stdout, simplifiers[i]->result);
+    if (simplifiers[i]->result)
+      outline_c_exprs (stdout, simplifiers[i]->result);
 }
 
 
@@ -2283,8 +2296,12 @@ parse_simplify (cpp_reader *r, source_lo
   operand *ifexpr = parse_c_expr (r, CPP_OPEN_PAREN);
   eat_token (r, CPP_CLOSE_PAREN);
 
-  result_loc = peek (r)->src_loc;
-  simplify *s = new simplify (id, match, match_location, parse_op (r), result_loc);
+  token = peek (r);
+  result_loc = token->src_loc;
+  operand *result = NULL;
+  if (token->type != CPP_CLOSE_PAREN)
+    result = parse_op (r);
+  simplify *s = new simplify (id, match, match_location, result, result_loc);
   s->ifexpr_vec.safe_push (ifexpr);
   return s;
 }

Re: [PATCH][RFC][match-and-simplify] "Manually" written patterns

[Richard Biener]

On Mon, 18 Aug 2014, Prathamesh Kulkarni wrote:

> On Fri, Aug 15, 2014 at 6:18 PM, Richard Biener <rguenther@suse.de> wrote:
> >
> > The following introduces "manually" written patterns.  That is,
> > part of the matching and the transform are fully manual.  An
> > example where this is necessary is when the result isn't really
> > an "expression" but a series of statements.
> >
> > For example take simplifications of the memset builtin.  With
> > the proposal we coud write
> >
> > (simplify
> >   (BUILT_IN_MEMSET @1 @2 integer_zerop)
> >   @1)
> > (simplify
> >   (BUILT_IN_MEMSET (addr@1 @4) INTEGER_CST_P@2 tree_fits_uhwi_p@3)
> >   (if (gimple_simplify_memset (@1, @2, @3, res_code, res_ops, seq,
> > valueize)))
> >   /* Note "result" intentionally omitted.  The predicate if applying is
> >      supposed to have populated *res_code and *res_ops and seq.  */)
> >
> Essentially we are forwarding transform code-gen to gimple_simplify_memset ?
> I was wondering for such functions,
> would it be a good idea to mark them with some symbol (say %) ?
> 
> for eg, the above pattern would be written as:
> 
> (define_forward_fn gimple_simplify_memset 3)
> // forward transform code-gen to gimple_simplify_memset which expects 3 operands
> 
> (simplify
>   (BUILT_IN_MEMSET (addr@1 @4) INTEGER_CST_P@2 tree_fits_uhwi_p@3)
>   (%gimple_simplify_memset @1 @2 @3))
> 
> gimple_simplify would auto-forward the remaining arguments (res,
> res_code, res_ops, etc.)
> to gimple_simplify_memset.

The issue with the above is that it would parse as the "result"
and thus the "result" expression now can magically fail...

I thought about doing

  (if (gimple_simplify_memset (@1, @2, @3, @@))

thus having a "special" @@ that will append the boilerplate arguments.

But both are only to make the syntax prettier.  I also thought
about allowing implicit compound expressions (aka C comma operator)
with using sth like

  (simplify
    (BUILT_IN_MEMSET @1 @2 @3)
    ((= (mem_ref @1 0) @2)
     @1))

well, simplified of course.  That is, the result may be a list
of expressions and we introduce some magic new operator that
allows generating an assigment.  Similarly for a hypothetical
call "simplifier" that does

 (simplify
    (BUILT_IN_FOO @1)
    ((BUILT_IN_FOO_SIDE_EFFECTS @1)
     (BUILT_IN_BAR @1)))

at the moment emitting a sequence of statements is the #1
reason for using "manual simplifiers".  Eventually the
assignment could be done as c_expr

  (simplify
    (BUILT_IN_MEMSET @1 @2 @3)
    ({
       var = fold_build2 (MEM_REF, etype, dest, build_int_cst (ptr_type_node, 0));
       gimple store = gimple_build_assign (var, build_int_cst_type (etype, 
cval));
       gimple_seq_add_stmt_without_update (seq, store);
     }
     @1))

but that accesses the magic 'seq' and the c_expr wouldn't have a "result".
If we restrict all this to GIMPLE then we could require all but the
last "stmts" in the list of expressions to evaluate to a statement
and code-gen the add to the sequence.  But then you'd want to
have common variables in the if-expr and result c_exprs ...

Which is why I proposed it in the awkward (but most powerful and
generic) way.

Richard.


> 
> Thanks,
> Prathamesh
> 
> > covering the zero-length case with a regular pattern and the rest
> > with a if-expr predicate that also does the transform.  Note
> > that parts of the argument constraining is done via regular
> > matching predicates and the pattern is inserted into the decision
> > tree as usual.
> >
> > How gimple_simplify_memset looks like is visible in the patch.
> >
> > Note that this exposes the implementation details of the _GIMPLE_
> > code-path (so the above doesn't even apply to GENERIC - luckily
> > I've not implemented builtin function simplification for GENERIC
> > so the above doesn't fall over ;)).
> >
> > The syntax for the trailing args could be made nicer, but we use
> > 'type' freely as well.
> >
> > It clearly "abuses" (if ...) but it fits kind-of well.  Makes
> > simply omitting the result pattern in a regular simplify
> > fail in interesting ways though...
> >
> > Caveat: runs into the issue that it's not possible to
> > query the number of arguments to a function (thus no
> > re-simplification yet).  I can lookup the decl for the
> > builtin and parse its DECL_ARGUMENTS, but well...
> > Similar issue exists when parsing built-in calls,
> > we can't error on not enough arguments.
> >
> > Status: it builds.
> >
> > Comments?
> >
> > Thanks,
> > Richard.
> >
> > 2014-08-15  Richard Biener  <rguenther@suse.de>
> >
> >         * match.pd: Add example memset simplification with manual
> >         implemented part.
> >         * gimple-fold.c (gimple_simplify_memset): New function.
> >         * gimple-fold.h (gimple_simplify_memset): Declare.
> >         * gimple-match-head.c (gimple_resimplify): New function.
> >         * genmatch.c (check_no_user_id): Guard against NULL result.
> >         (write_header): Likewise.
> >         (dt_simplify::gen_gimple): Deal with NULL result.
> >         (parse_simplify): Allow missing result.
> >
> > Index: gcc/match.pd
> > ===================================================================
> > --- gcc/match.pd        (revision 214018)
> > +++ gcc/match.pd        (working copy)
> > @@ -113,6 +113,21 @@ along with GCC; see the file COPYING3.
> >  #include "match-builtin.pd"
> >  #include "match-constant-folding.pd"
> >
> > +
> > +/* "Manual" simplifications but still in the decision tree.
> > +   Allows us to strip off "easy" parts and (parts of) the
> > +   pattern/predicate matching.  */
> > +
> > +(simplify
> > +  (BUILT_IN_MEMSET @1 @2 integer_zerop)
> > +  @1)
> > +(simplify
> > +  (BUILT_IN_MEMSET (addr@1 @4) INTEGER_CST_P@2 tree_fits_uhwi_p@3)
> > +  (if (gimple_simplify_memset (@1, @2, @3, res_code, res_ops, seq, valueize)))
> > +  /* Note "result" intentionally omitted.  The predicate if applying is
> > +     supposed to have populated *res_code and *res_ops and seq.  */)
> > +
> > +
> >  /* ????s
> >
> >     We cannot reasonably match vector CONSTRUCTORs or vector constants
> > Index: gcc/gimple-fold.c
> > ===================================================================
> > --- gcc/gimple-fold.c   (revision 214018)
> > +++ gcc/gimple-fold.c   (working copy)
> > @@ -1335,6 +1335,80 @@ gimple_fold_builtin_memset (gimple_stmt_
> >    return true;
> >  }
> >
> > +/* Manual simplification example.
> > +   Fold function call to builtin memset or bzero setting the
> > +   memory of size LEN to VAL.  Return whether a simplification was made.  */
> > +
> > +bool
> > +gimple_simplify_memset (tree dest, tree c, tree len,
> > +                       code_helper *res_code, tree *res_ops,
> > +                       gimple_seq *seq, tree (*valueize)(tree))
> > +{
> > +  tree etype;
> > +  unsigned HOST_WIDE_INT length, cval;
> > +
> > +  if (!seq)
> > +    return false;
> > +
> > +  /* If the LEN parameter is zero, this is handled by another pattern.
> > +     But as they are only differing in predicates we can still arrive
> > +     here (there isn't a integer_nonzerop).  */
> > +  if (integer_zerop (len))
> > +    return false;
> > +
> > +  gcc_assert (tree_fits_uhwi_p (len));
> > +
> > +  gcc_assert (TREE_CODE (c) == INTEGER_CST);
> > +
> > +  tree var = dest;
> > +  gcc_assert (TREE_CODE (var) == ADDR_EXPR);
> > +
> > +  var = TREE_OPERAND (var, 0);
> > +  if (TREE_THIS_VOLATILE (var))
> > +    return false;
> > +
> > +  etype = TREE_TYPE (var);
> > +  if (TREE_CODE (etype) == ARRAY_TYPE)
> > +    etype = TREE_TYPE (etype);
> > +
> > +  if (!INTEGRAL_TYPE_P (etype)
> > +      && !POINTER_TYPE_P (etype))
> > +    return false;
> > +
> > +  if (! var_decl_component_p (var))
> > +    return false;
> > +
> > +  length = tree_to_uhwi (len);
> > +  if (GET_MODE_SIZE (TYPE_MODE (etype)) != length
> > +      || get_pointer_alignment (dest) / BITS_PER_UNIT < length)
> > +    return false;
> > +
> > +  if (length > HOST_BITS_PER_WIDE_INT / BITS_PER_UNIT)
> > +    return false;
> > +
> > +  if (integer_zerop (c))
> > +    cval = 0;
> > +  else
> > +    {
> > +      if (CHAR_BIT != 8 || BITS_PER_UNIT != 8 || HOST_BITS_PER_WIDE_INT > 64)
> > +       return NULL_TREE;
> > +
> > +      cval = TREE_INT_CST_LOW (c);
> > +      cval &= 0xff;
> > +      cval |= cval << 8;
> > +      cval |= cval << 16;
> > +      cval |= (cval << 31) << 1;
> > +    }
> > +
> > +  var = fold_build2 (MEM_REF, etype, dest, build_int_cst (ptr_type_node, 0));
> > +  gimple store = gimple_build_assign (var, build_int_cst_type (etype, cval));
> > +  gimple_seq_add_stmt_without_update (seq, store);
> > +  *res_code = TREE_CODE (dest);
> > +  res_ops[0] = dest;
> > +
> > +  return true;
> > +}
> > +
> >
> >  /* Return the string length, maximum string length or maximum value of
> >     ARG in LENGTH.
> > Index: gcc/gimple-fold.h
> > ===================================================================
> > --- gcc/gimple-fold.h   (revision 214018)
> > +++ gcc/gimple-fold.h   (working copy)
> > @@ -121,4 +121,10 @@ tree gimple_simplify (enum built_in_func
> >  tree gimple_simplify (enum built_in_function, tree, tree, tree, tree,
> >                       gimple_seq *, tree (*)(tree));
> >
> > +/* Manual simplifiers.  */
> > +class code_helper;
> > +bool gimple_simplify_memset (tree dest, tree c, tree len,
> > +                            code_helper *res_code, tree *res_ops,
> > +                            gimple_seq *seq, tree (*valueize)(tree));
> > +
> >  #endif  /* GCC_GIMPLE_FOLD_H */
> > Index: gcc/gimple-match-head.c
> > ===================================================================
> > --- gcc/gimple-match-head.c     (revision 214018)
> > +++ gcc/gimple-match-head.c     (working copy)
> > @@ -268,6 +268,31 @@ gimple_resimplify3 (gimple_seq *seq,
> >    return canonicalized;
> >  }
> >
> > +static bool
> > +gimple_resimplify (gimple_seq *seq,
> > +                  code_helper *res_code, tree type, tree *res_ops,
> > +                  tree (*valueize)(tree))
> > +{
> > +  if (res_code->is_tree_code ())
> > +    {
> > +      switch (TREE_CODE_LENGTH ((tree_code) *res_code))
> > +       {
> > +       case 1:
> > +         return gimple_resimplify1 (seq, res_code, type, res_ops, valueize);
> > +       case 2:
> > +         return gimple_resimplify2 (seq, res_code, type, res_ops, valueize);
> > +       case 3:
> > +         return gimple_resimplify3 (seq, res_code, type, res_ops, valueize);
> > +       default:
> > +         return false;
> > +       }
> > +    }
> > +  else
> > +    {
> > +      /* ??? */
> > +      return false;
> > +    }
> > +}
> >
> >  /* Push the exploded expression described by RCODE, TYPE and OPS
> >     as a statement to SEQ if necessary and return a gimple value
> > @@ -742,3 +767,4 @@ do_valueize (tree (*valueize)(tree), tre
> >      return valueize (op);
> >    return op;
> >  }
> > +
> > Index: gcc/genmatch.c
> > ===================================================================
> > --- gcc/genmatch.c      (revision 214018)
> > +++ gcc/genmatch.c      (working copy)
> > @@ -822,7 +822,8 @@ void
> >  check_no_user_id (simplify *s)
> >  {
> >    check_no_user_id (s->match);
> > -  check_no_user_id (s->result);
> > +  if (s->result)
> > +    check_no_user_id (s->result);
> >  }
> >
> >  /* Code gen off the AST.  */
> > @@ -1674,6 +1675,8 @@ dt_simplify::gen_gimple (FILE *f)
> >      }
> >        output_line_directive (f, s->result_location);
> >
> > +      if (s->result)
> > +       {
> >        if (s->result->type == operand::OP_EXPR)
> >         {
> >           expr *e = static_cast <expr *> (s->result);
> > @@ -1697,6 +1700,15 @@ dt_simplify::gen_gimple (FILE *f)
> >         }
> >        else
> >         gcc_unreachable ();
> > +       }
> > +      else
> > +       {
> > +         /* ???  We can't statically determine which of the
> > +            n-ary gimple_resimplify routines to call so call
> > +            a dispatcher.  */
> > +         fprintf (f, "gimple_resimplify (seq, res_code, type, "
> > +                  "res_ops, valueize);\n");
> > +       }
> >
> >        fprintf (f, "return true;\n");
> >        if (s->ifexpr_vec != vNULL)
> > @@ -1954,7 +1966,8 @@ write_header (FILE *f, vec<simplify *>&
> >
> >    /* Outline complex C expressions to helper functions.  */
> >    for (unsigned i = 0; i < simplifiers.length (); ++i)
> > -    outline_c_exprs (stdout, simplifiers[i]->result);
> > +    if (simplifiers[i]->result)
> > +      outline_c_exprs (stdout, simplifiers[i]->result);
> >  }
> >
> >
> > @@ -2283,8 +2296,12 @@ parse_simplify (cpp_reader *r, source_lo
> >    operand *ifexpr = parse_c_expr (r, CPP_OPEN_PAREN);
> >    eat_token (r, CPP_CLOSE_PAREN);
> >
> > -  result_loc = peek (r)->src_loc;
> > -  simplify *s = new simplify (id, match, match_location, parse_op (r), result_loc);
> > +  token = peek (r);
> > +  result_loc = token->src_loc;
> > +  operand *result = NULL;
> > +  if (token->type != CPP_CLOSE_PAREN)
> > +    result = parse_op (r);
> > +  simplify *s = new simplify (id, match, match_location, result, result_loc);
> >    s->ifexpr_vec.safe_push (ifexpr);
> >    return s;
> >  }
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend"orffer

Re: [PATCH][RFC][match-and-simplify] "Manually" written patterns

[Richard Biener]

On Fri, 15 Aug 2014, Richard Biener wrote:

> 
> The following introduces "manually" written patterns.  That is,
> part of the matching and the transform are fully manual.  An
> example where this is necessary is when the result isn't really
> an "expression" but a series of statements.
> 
> For example take simplifications of the memset builtin.  With
> the proposal we coud write
> 
> (simplify
>   (BUILT_IN_MEMSET @1 @2 integer_zerop)
>   @1)
> (simplify
>   (BUILT_IN_MEMSET (addr@1 @4) INTEGER_CST_P@2 tree_fits_uhwi_p@3)
>   (if (gimple_simplify_memset (@1, @2, @3, res_code, res_ops, seq, 
> valueize)))
>   /* Note "result" intentionally omitted.  The predicate if applying is
>      supposed to have populated *res_code and *res_ops and seq.  */)
> 
> covering the zero-length case with a regular pattern and the rest
> with a if-expr predicate that also does the transform.  Note
> that parts of the argument constraining is done via regular
> matching predicates and the pattern is inserted into the decision
> tree as usual.
> 
> How gimple_simplify_memset looks like is visible in the patch.
> 
> Note that this exposes the implementation details of the _GIMPLE_
> code-path (so the above doesn't even apply to GENERIC - luckily
> I've not implemented builtin function simplification for GENERIC
> so the above doesn't fall over ;)).
> 
> The syntax for the trailing args could be made nicer, but we use
> 'type' freely as well.
> 
> It clearly "abuses" (if ...) but it fits kind-of well.  Makes
> simply omitting the result pattern in a regular simplify
> fail in interesting ways though...
> 
> Caveat: runs into the issue that it's not possible to
> query the number of arguments to a function (thus no
> re-simplification yet).  I can lookup the decl for the
> builtin and parse its DECL_ARGUMENTS, but well...
> Similar issue exists when parsing built-in calls,
> we can't error on not enough arguments.
> 
> Status: it builds.
> 
> Comments?

No changes but updated patch.  As the important part is being
able to re-simplify calls so we can continue to stage
sprintf_chk -> sprintf -> memcpy I still need to figure out
the best way doing that and implement example patterns exercising
this.

I also need to merge from trunk so I can re-order the
match-and-simplify transform to happen before the rest in
fold_stmt.

Richard.

2014-08-15  Richard Biener  <rguenther@suse.de>

	* match.pd: Add example memset simplification with manual
	implemented part.
	* gimple-fold.c (gimple_simplify_memset): New function.
	* gimple-fold.h (gimple_simplify_memset): Declare.
	* gimple-match-head.c (gimple_resimplify): New function.
	* genmatch.c (check_no_user_id): Guard against NULL result.
	(write_header): Likewise.
	(dt_simplify::gen_gimple): Deal with NULL result.
	(parse_simplify): Allow missing result.

Index: gcc/match.pd
===================================================================
*** gcc/match.pd.orig	2014-08-21 13:54:41.787051398 +0200
--- gcc/match.pd	2014-08-21 14:11:56.196980181 +0200
*************** along with GCC; see the file COPYING3.
*** 127,132 ****
--- 127,150 ----
  #include "match-constant-folding.pd"
  #include "match-comparison.pd"
  
+ 
+ /* "Manual" simplifications but still in the decision tree.
+    Allows us to strip off "easy" parts and (parts of) the
+    pattern/predicate matching.  */
+ 
+ (simplify
+   (BUILT_IN_MEMSET @1 @2 @3)
+   /* Size zero memset simplifies to the destination pointer.  */
+   (if (integer_zerop (@3))
+    @1)
+   (if (TREE_CODE (@1) == ADDR_EXPR
+        && TREE_CODE (@2) == INTEGER_CST
+        && tree_fits_uhwi_p (@3)
+        && gimple_simplify_memset (@1, @2, @3, res_code, res_ops, seq, valueize))
+    /* Note "result" intentionally omitted.  The predicate if applying is
+       supposed to have populated *res_code and *res_ops and seq.  */))
+ 
+ 
  /* ????s
  
     We cannot reasonably match vector CONSTRUCTORs or vector constants
Index: gcc/gimple-fold.c
===================================================================
*** gcc/gimple-fold.c.orig	2014-08-21 13:54:41.801051398 +0200
--- gcc/gimple-fold.c	2014-08-21 14:16:46.148960218 +0200
*************** gimple_fold_builtin_memset (gimple_stmt_
*** 1335,1340 ****
--- 1335,1414 ----
    return true;
  }
  
+ /* Manual simplification example.
+    Fold function call to builtin memset or bzero setting the
+    memory of size LEN to VAL.  Return whether a simplification was made.  */
+ 
+ bool
+ gimple_simplify_memset (tree dest, tree c, tree len,
+ 			code_helper *res_code, tree *res_ops,
+ 			gimple_seq *seq, tree (*)(tree))
+ {
+   tree etype;
+   unsigned HOST_WIDE_INT length, cval;
+ 
+   if (!seq)
+     return false;
+ 
+   /* If the LEN parameter is zero, this is handled by another pattern.
+      But as they are only differing in predicates we can still arrive
+      here (there isn't a integer_nonzerop).  */
+   if (integer_zerop (len))
+     return false;
+ 
+   gcc_assert (tree_fits_uhwi_p (len));
+ 
+   gcc_assert (TREE_CODE (c) == INTEGER_CST);
+ 
+   tree var = dest;
+   gcc_assert (TREE_CODE (var) == ADDR_EXPR);
+ 
+   var = TREE_OPERAND (var, 0);
+   if (TREE_THIS_VOLATILE (var))
+     return false;
+ 
+   etype = TREE_TYPE (var);
+   if (TREE_CODE (etype) == ARRAY_TYPE)
+     etype = TREE_TYPE (etype);
+ 
+   if (!INTEGRAL_TYPE_P (etype)
+       && !POINTER_TYPE_P (etype))
+     return false;
+ 
+   if (! var_decl_component_p (var))
+     return false;
+ 
+   length = tree_to_uhwi (len);
+   if (GET_MODE_SIZE (TYPE_MODE (etype)) != length
+       || get_pointer_alignment (dest) / BITS_PER_UNIT < length)
+     return false;
+ 
+   if (length > HOST_BITS_PER_WIDE_INT / BITS_PER_UNIT)
+     return false;
+ 
+   if (integer_zerop (c))
+     cval = 0;
+   else
+     {
+       if (CHAR_BIT != 8 || BITS_PER_UNIT != 8 || HOST_BITS_PER_WIDE_INT > 64)
+ 	return NULL_TREE;
+ 
+       cval = TREE_INT_CST_LOW (c);
+       cval &= 0xff;
+       cval |= cval << 8;
+       cval |= cval << 16;
+       cval |= (cval << 31) << 1;
+     }
+ 
+   var = fold_build2 (MEM_REF, etype, dest, build_int_cst (ptr_type_node, 0));
+   gimple store = gimple_build_assign (var, build_int_cst_type (etype, cval));
+   gimple_seq_add_stmt_without_update (seq, store);
+   *res_code = TREE_CODE (dest);
+   res_ops[0] = dest;
+ 
+   return true;
+ }
+ 
  
  /* Return the string length, maximum string length or maximum value of
     ARG in LENGTH.
Index: gcc/gimple-fold.h
===================================================================
*** gcc/gimple-fold.h.orig	2014-08-21 13:54:41.813051397 +0200
--- gcc/gimple-fold.h	2014-08-21 13:54:43.813051259 +0200
*************** tree gimple_simplify (enum built_in_func
*** 139,142 ****
--- 139,148 ----
  tree gimple_simplify (enum built_in_function, tree, tree, tree, tree,
  		      gimple_seq *, tree (*)(tree));
  
+ /* Manual simplifiers.  */
+ class code_helper;
+ bool gimple_simplify_memset (tree dest, tree c, tree len,
+ 			     code_helper *res_code, tree *res_ops,
+ 			     gimple_seq *seq, tree (*valueize)(tree));
+ 
  #endif  /* GCC_GIMPLE_FOLD_H */
Index: gcc/gimple-match-head.c
===================================================================
*** gcc/gimple-match-head.c.orig	2014-08-21 13:54:41.813051397 +0200
--- gcc/gimple-match-head.c	2014-08-21 13:54:43.813051259 +0200
*************** gimple_resimplify3 (gimple_seq *seq,
*** 266,271 ****
--- 266,296 ----
    return canonicalized;
  }
  
+ static bool
+ gimple_resimplify (gimple_seq *seq,
+ 		   code_helper *res_code, tree type, tree *res_ops,
+ 		   tree (*valueize)(tree))
+ {
+   if (res_code->is_tree_code ())
+     {
+       switch (TREE_CODE_LENGTH ((tree_code) *res_code))
+ 	{
+ 	case 1:
+ 	  return gimple_resimplify1 (seq, res_code, type, res_ops, valueize);
+ 	case 2:
+ 	  return gimple_resimplify2 (seq, res_code, type, res_ops, valueize);
+ 	case 3:
+ 	  return gimple_resimplify3 (seq, res_code, type, res_ops, valueize);
+ 	default:
+ 	  return false;
+ 	}
+     }
+   else
+     {
+       /* ??? */
+       return false;
+     }
+ }
  
  /* Push the exploded expression described by RCODE, TYPE and OPS
     as a statement to SEQ if necessary and return a gimple value
Index: gcc/genmatch.c
===================================================================
*** gcc/genmatch.c.orig	2014-08-21 13:54:41.815051397 +0200
--- gcc/genmatch.c	2014-08-21 14:02:49.648017810 +0200
*************** void
*** 855,861 ****
  check_no_user_id (simplify *s)
  {
    check_no_user_id (s->match);
!   check_no_user_id (s->result);
  }
  
  /* Code gen off the AST.  */
--- 855,862 ----
  check_no_user_id (simplify *s)
  {
    check_no_user_id (s->match);
!   if (s->result)
!     check_no_user_id (s->result);
  }
  
  /* Code gen off the AST.  */
*************** dt_simplify::gen (FILE *f, bool gimple)
*** 1726,1732 ****
  
    if (gimple)
      {
!       if (s->result->type == operand::OP_EXPR)
  	{
  	  expr *e = static_cast <expr *> (s->result);
  	  fprintf (f, "*res_code = %s;\n", e->operation->op->id);
--- 1727,1743 ----
  
    if (gimple)
      {
!       if (!s->result)
! 	{
! 	  /* If there is no result then a previous if-expression
! 	     has populated res_ops and res_code.
! 	     ???  e can't statically determine which of the
! 	     n-ary gimple_resimplify routines to call so call
! 	     a dispatcher.  */
! 	  fprintf (f, "gimple_resimplify (seq, res_code, type, "
! 		   "res_ops, valueize);\n");
! 	}
!       else if (s->result->type == operand::OP_EXPR)
  	{
  	  expr *e = static_cast <expr *> (s->result);
  	  fprintf (f, "*res_code = %s;\n", e->operation->op->id);
*************** dt_simplify::gen (FILE *f, bool gimple)
*** 1753,1758 ****
--- 1764,1771 ----
      }
    else /* GENERIC */
      {
+       /* Manual matchers are not supported in GENERIC.  */
+       gcc_assert (s->result);
        if (s->result->type == operand::OP_EXPR)
  	{
  	  expr *e = static_cast <expr *> (s->result);
*************** write_header (FILE *f, vec<simplify *>&
*** 1938,1944 ****
  
    /* Outline complex C expressions to helper functions.  */
    for (unsigned i = 0; i < simplifiers.length (); ++i)
!     outline_c_exprs (stdout, simplifiers[i]->result);
  }
  
  
--- 1951,1958 ----
  
    /* Outline complex C expressions to helper functions.  */
    for (unsigned i = 0; i < simplifiers.length (); ++i)
!     if (simplifiers[i]->result)
!       outline_c_exprs (stdout, simplifiers[i]->result);
  }
  
  
*************** parse_simplify (cpp_reader *r, source_lo
*** 2283,2293 ****
--- 2297,2314 ----
      {
        if (token->type == CPP_OPEN_PAREN)
  	{
+ 	  source_location paren_loc = token->src_loc;
  	  eat_token (r, CPP_OPEN_PAREN);
  	  if (peek_ident (r, "if"))
  	    {
  	      eat_ident (r, "if");
  	      ifexprs.safe_push (parse_c_expr (r, CPP_OPEN_PAREN));
+ 	      /* If this if is immediately closed then it contains a
+ 	         manual matcher.  Push it.  */
+ 	      if (peek (r)->type == CPP_CLOSE_PAREN)
+ 	        simplifiers.safe_push
+ 		    (new simplify (id, match, match_location, NULL,
+ 				   paren_loc, copy_reverse (ifexprs)));
  	    }
  	  else
  	    {
*************** parse_for (cpp_reader *r, source_locatio
*** 2382,2388 ****
  	    {
  	      simplify *s = for_simplifiers[j];
  	      operand *match_op = replace_id (s->match, user_id, opers[i]);
! 	      operand *result_op = replace_id (s->result, user_id, opers[i]);
  	      vec<operand *> ifexpr_vec = vNULL;
  	      for (unsigned j = 0; j < s->ifexpr_vec.length (); ++j)
  		ifexpr_vec.safe_push (replace_id (s->ifexpr_vec[j], user_id, opers[i]));
--- 2403,2409 ----
  	    {
  	      simplify *s = for_simplifiers[j];
  	      operand *match_op = replace_id (s->match, user_id, opers[i]);
! 	      operand *result_op = s->result ? replace_id (s->result, user_id, opers[i]) : NULL;
  	      vec<operand *> ifexpr_vec = vNULL;
  	      for (unsigned j = 0; j < s->ifexpr_vec.length (); ++j)
  		ifexpr_vec.safe_push (replace_id (s->ifexpr_vec[j], user_id, opers[i]));