Re: [PATCH][match-and-simplify] User defined predicates

[Richard Biener <rguenther at suse dot de>]

On Tue, 16 Sep 2014, Marc Glisse wrote:

> On Tue, 16 Sep 2014, Richard Biener wrote:
> 
> > The following adds the ability to write predicates using patterns
> > with an example following negate_expr_p which already has a
> > use in comparison folding (via its if c-expr).
> > 
> > The syntax is as follows:
> > 
> > (match negate_expr_p
> > INTEGER_CST
> > (if (TYPE_OVERFLOW_WRAPS (type)
> >      || may_negate_without_overflow_p (t))))
> > (match negate_expr_p
> > (bit_not @0)
> > (if (INTEGRAL_TYPE_P (type) && TYPE_OVERFLOW_WRAPS (type))))
> > (match negate_expr_p
> > FIXED_CST)
> > (match negate_expr_p
> > (negate @0))
> > ...
> > 
> > that is, you write '(match <id>' instead of '(simplify' and then
> > follow with a pattern and optional conditionals.  There should
> > be no transform pattern (unchecked yet).  Multiple matches for
> > the same <id> simply add to what is recognized as <id>.
> > The predicate is applied to a single 'tree' operand and looks
> > up SSA defs and utilizes the optional valueize hook.
> > 
> > Currently both GENERIC and GIMPLE variants result in name-mangling
> > and the proptotypes (unprototyped anywhere)
> > 
> > bool tree_negate_expr_p (tree t);
> > bool gimple_negate_expr_p (tree t, tree (*valueize)(tree) = NULL);
> 
> Ah, I haven't looked at the generated code, but I was expecting something
> roughly like:
> 
> struct matcher
> {
>   std::function<tree(tree)> valueize;
>   bool negate_expr(tree);
>   ...
> };
> 
> where we can call negate_expr recursively without caring about passing
> valueize (if there are 2 matchers, one without a valueize function,
> negate_expr can be static in that version). Although recursive calls sound
> potentially slow, and having a thread_local counter in valueize to limit the
> call depth may not be ideal.
> 
> Please note that I am not at all saying the above is a good design, just
> dropping a random thought.

Yeah, abstracting a bit from the low-level interface might be nice.

Note that I wouldn't recommend using recursive predicates as on GIMPLE
this easily can result in exponential runtime behavior (and capping
on a recursion limit looks ugly).  Instead of using recursive predicates
a lattice of predicate results should be provided by the caller
(which would ask for a lattice abstraction as well).  So you'd have
sth like

struct lattice
{
  tree valueize (tree);
  bool negate_expr_p (tree);
  bool nonnegative_p (tree);
  ...
};

note that the fold-const.c negate_expr_p is really a predicate on
whether negate_expr will be able to simplify.  Yes, fold-const.c
has "recursive" transforms, something match-and-simplify doesn't
support either.  Here the proper way is to implement this kind
of stuff in a real pass.

I'll rip out the recursive parts of negate_expr_p again at some point,
I just put it there as an exercise ;)

Richard.