[RFC] Meta-description for tree and gimple folding

[Georg-Johann Lay]

Am 02/27/2014 03:34 PM, schrieb Richard Biener:
>
> I've been hacking on a prototype that generates matching and
> simplification code from a meta-description.  The goal is
> to provide a single source of transforms currently spread
> over the compiler, mostly fold-const.c, gimple-fold.c and
> tree-ssa-forwprop.c.  Another goal is to make these transforms
> (which are most of the form of generating a simpler form of
> a pattern-matched IL piece) more readily available to passes
> like value-numbering so they can be used on-the-fly, using
> information provided by the pass lattice.  The ultimate
> goal is to generate (most of) fold-const.c and gimple-fold.c
> and tree-ssa-forwprop.c from a single meta description.
>
> Currently the prototype can generate code to match and simplify
> on the GIMPLE IL and it uses a very simple description right now
> (following the lispy style we have for machine descriptions).
> For example
>
> (define_match_and_simplify foo
>    (PLUS_EXPR (MINUS_EXPR integral_op_p@0 @1) @1)
>    @0)
>
> Matches (A - B) + B and transforms it to A.  More complex
> replacements involving modifying of matches operands can be
> done with inlined C code:
>
> (define_match_and_simplify bar
>    (PLUS_EXPR INTEGER_CST_P@0 (PLUS_EXPR @1 INTEGER_CST_P@2))
>    (PLUS_EXPR { int_const_binop (PLUS_EXPR, captures[0], captures[2]); } @1))
>
> which matches CST1 + (X + CST2) and transforms it to (CST1 + CST2) + X
> (thus it reassociates but it also simplifies the constant part).

Hi Richard,

in the past there were some bugs in folding that introduced undefined behaviour 
because they produced different signed overflow.

One example is PR56899 that folded

    (1 - X) * CST1

to

    X * (-CST1) + CST1

How is this expressed in the pattern. Is there something like a condition (like 
in insns)? Or will this be encoded in the operation?

Johann

> Writing patterns will require a few new predicates like
> INTEGER_CST_P or integral_op_p.
>
> At this point I'll try integrating the result into a few
> GIMPLE passes (forwprop and SCCVN) to see if the interface
> works well enough.  Currently the GIMPLE interface is
>
> tree
> gimple_match_and_simplify (tree name, gimple_seq *seq,
> 			   tree (*valueize)(tree));
>
> where the simplification happens on the defining statement
> of the SSA name name and a is_gimple_val result is returned.
> Any intermediate stmts are appended to 'seq' (or NULL_TREE
> is returned if that would be necessary and 'seq' is NULL)
> and all SSA names matched and generated are valueized using
> the valueize callback (if not NULL).  Thus for the first
> example above we'd return A and do not touch seq while
> for the second example we'd return a new temporary SSA
> name and append name = CST' + X to seq (we might want
> to allow in-place modification of the def stmt of name
> as well, I'm not sure yet - that's the forwprop way of operation)
>
> Patch below for reference.
>
> Comments or suggestions?
>
> Thanks,
> Richard.