Re: [gsoc 2014] moving fold-const patterns to gimple

[Richard Biener <richard dot guenther at gmail dot com>]

On Mon, Mar 10, 2014 at 7:29 PM, Prathamesh Kulkarni
<bilbotheelffriend@gmail.com> wrote:
> Hi Richard,
> Sorry for the late reply. I would like to have few clarifications
> regarding the following points:
>
> a) Pattern matching: Currently, gimple_match_and_simplify() matches
> patterns one-by-one. Could we use a decision tree to do the matching
> instead (similar to insn-recog.c) ?
> For the moment, let's consider pattern matching on only unary
> expressions without valueize and predicates:
> pattern 1: (negate (negate @0))
> pattern 2: (negate (bit_not @0))
>
> from the two AST's corresponding to patterns (match::op), we can build
> a decision tree:
> Some-thing similar to:
>                        NEGATE_EXPR
>         NEGATE_EXPR            BIT_NOT_EXPR
>
> and then generate code corresponding to this decision tree in gimple-match.c
> so the generated code should look something similar to:
>
> tree
> gimple_match_and_simplify (enum tree_code code, tree type, tree op0,
> gimple_seq *seq, tree (*valueize)(tree))
> {
>   if (code == NEGATE_EXPR)
>     {
>       tree captures[4] = {};
>       if (TREE_CODE (op0) != SSA_NAME)
>         return NULL_TREE;
>       gimple def_stmt = SSA_NAM_DEF_STMT (op0);
>       if (!is_gimple_assign (def_stmt))
>         return NULL_TREE;
>       tree op = gimple_assign_rhs1 (def_stmt);
>       if (gimple_assign_rhs_code (op) == NEGATE_EXPR)
>         {
>            /* pattern (negate (negate @0)) matched */
>         }
>       else if (gimple_assign_rhs_code (op) == BIT_NOT_EXPR)
>         {
>            /* pattern (negate (bit_not_expr @0)) matched */
>         }
>       else
>            return NULL_TREE;
>      }
>   else
>      return NULL_TREE;
> }
>
> For commutative ops, the pattern can be duplicated by walking the
> children of the node in reverse order.
> (I am not exactly clear so far about representing binary operators in a decision
> tree) Is this the right way to go ? I shall try to shortly post a patch that
> implements this.

Yes, that's the way to go (well, I'd even use a switch ()).

> b) Targeting GENERIC, separating AST from gimple/generic:
> For generating a GENERIC pattern should there be another pattern
> something like match_and_simplify_generic ?

Yes, there is an existing API in GCC for this that operates on GENERIC.
It's fold_unary_loc, fold_binary_loc, fold_ternary_loc.  The interface
the GENERIC match_and_simplify variant provides should match
that one.

> Currently, the AST data structures (operand, expr, etc.)
> are tied to gimple (gen_gimple_match, gen_gimple_transform).
> We could also have similar functions: gen_generic_match,
> gen_generic_transform for generating GENERIC ?

Yeah, but I'm not sure if keeping the (virtual) methods for generating
code makes much sense with a rewritten code generator.

> Instead will it be better if we separate the AST
> from target IR (generic/gimple) and make simplify a visitor on AST
> (make simplify
> abstract class, with simplify_generic and simplify_gimple visitor
> classes that generate corresponding IR code) ?

Yes.  Keep in mind the current state of genmatch.c is "quick hack
to make playing with the API side and with patterns possible" ;)

> c) Shall it be a good idea in define_match <name> <pattern>, for
> name to act as a substitute for pattern (similar to flex pattern
> definitions), so the name can be used in bigger patterns ?

Maybe, I suppose we'll see when adding more patterns.

> d) This is silly, but maybe use constants to denote corresponding tree nodes ?
> for example instead of { build_int_cst (integer_type_node, 0); }, one
> could directly write 0, to denote a INTEGER_CST node with value 0.

Yes, that might be possible - though it will require more knowledge
in the pattern matcher (you also want to match '0'?) and the code
generator.

> e) There was a mention on the thread, regarding testing of patterns
> integrated into DSL. I wasn't able to understand that clearly. Could
> you explain that briefly ?

DSL?  Currently I'd say it would be nice to make sure each pattern
is triggered by at least one GCC testcase - this requires looking
at a particular pass dump (that of forwprop or ccp are probably most suitable
as they are run very early).  I mentioned the possibility to do offline
(thus not with C testcases) testing but that would require some tool
to do that and it would be correctness testing (some automatic proof
generation tool - ISTR academics have this kind of stuff).  But that was
just an idea.

> Regarding gsoc proposal, I would like to align it on the following points:
> a) Pattern matching using decision tree

good.

> b) Generate GIMPLE folding patterns (tree-ssa-forwprop,
> tree-ssa-sccvn, gimple-fold)

I'd narrow it down a bit, you can optionally do more if time permits.
I'd say
  0) add basic arithmetic identities (x + 0, x  * 1, x / 1, etc., correctly
for all types - you can look into fold-const.c which handles all of them)
  1) target as much as possible of the existing transforms in forwprop
  2) pieces of fold-const.c: most interesting user is
gimple_fold_stmt_to_constant_1 (used by CCP and SCCVN and maybe
others)
  3) fold-const.c's fold_comparison (and fold_binary parts handling
comparison codes), this is also necessary for quite important parts of
forwprop

> c) Generate GENERIC folding patterns (fold-const)
> Is that fine ? I would like to hear about any changes that you feel should be
> made.

This isn't easily distinguishable from b), instead we might want to

  c) Remove parts of fold-const.c that can be subsumed by the GENERIC
variant of the folding patterns

> I have been mostly experimenting with the patch, by adding few patterns
> from tree-ssa-forwprop, and shall try to do pattern matching by a decision tree.
> Is there anything else you would like to suggest that
> can help me get comfortable with the code-base and the project-idea and
> could possibly help me strengthen my proposal ?

Nothing off my head right now - there is always bugzilla to look for
missed optimization bugs.

I've created svn//gcc.gnu.org/svn/gcc/branches/match-and-simplify now
and committed my current patch state.  I've used gcc/ChangeLog.mas
to log changes to the branch.

Thanks,
Richard.

> Thanks and Regards,
> Prathamesh
>>
>> Richard.
>>
>>>> Thanks,
>>>> Richard.
>>>>
>>>>> I have a fluent grasp on C and working knowledge of flex, bison, C++,
>>>>> POSIX api, binutils and shell scripting (bash),
>>>>> I have been through most of dragon book, built an interpreter
>>>>> for a "c-like" language and a C-code generator for a toy language
>>>>> similar to python.
>>>>>
>>>>> As far as gcc goes, I had attended IIT Bombay gcc workshop 2013:
>>>>> http://www.cse.iitb.ac.in/grc/gcc-workshop-13/
>>>>> and have been through the online docs.
>>>>>
>>>>> I have a couple of one-liner patches committed:
>>>>> http://gcc.gnu.org/ml/gcc-patches/2014-02/msg00490.html
>>>>> http://gcc.gnu.org/ml/gcc-patches/2014-02/msg01144.html
>>>>>
>>>>> A few pending patches:
>>>>> http://gcc.gnu.org/ml/gcc-patches/2014-02/msg00143.html
>>>>> http://gcc.gnu.org/ml/gcc-patches/2014-02/msg00143.html
>>>>> http://gcc.gnu.org/ml/gcc-patches/2014-02/msg01220.html
>>>>> http://gcc.gnu.org/ml/gcc/2014-01/msg00268.html
>>>>>
>>>>> and a couple of rejected ones:
>>>>> http://gcc.gnu.org/ml/gcc-patches/2014-02/msg00957.html
>>>>> http://gcc.gnu.org/ml/gcc-patches/2014-02/msg01366.html
>>>>>
>>>>> Please do let me know what you think.
>>>>>
>>>>> Thanks and Regards,
>>>>> Prathamesh
>>>>>
>>>>>> Richard.
>>>>>>
>>>>>>> On the following test-case:
>>>>>>> int main()
>>>>>>> {
>>>>>>>   int a, b, c;
>>>>>>>   a = ~~~~b;
>>>>>>>   c = ~-a;
>>>>>>>   return 0;
>>>>>>> }
>>>>>>>
>>>>>>> The following GIMPLE is generated:
>>>>>>> main ()
>>>>>>> gimple_bind <
>>>>>>>   int D.1748;
>>>>>>>   int D.1749;
>>>>>>>   int D.1750;
>>>>>>>   int D.1751;
>>>>>>>   int D.1752;
>>>>>>>   int a;
>>>>>>>   int b;
>>>>>>>   int c;
>>>>>>>
>>>>>>>   gimple_assign <var_decl, D.1749, b, NULL, NULL>
>>>>>>>   gimple_assign <var_decl, a, D.1749, NULL, NULL>
>>>>>>>   gimple_assign <plus_expr, c, a, -1, NULL>
>>>>>>>   gimple_assign <integer_cst, D.1752, 0, NULL, NULL>
>>>>>>>   gimple_return <D.1752>
>>>>>>>>
>>>>>>>
>>>>>>> The patch generates two tuples for a = ~~~~b,
>>>>>>> where only one is needed, and extra temporaries, which
>>>>>>> are not removed after the folding. How should I go about
>>>>>>> removing that (should I worry about that since subsequent passes,
>>>>>>> shall remove those ?)
>>>>>>>
>>>>>>> b) Some front-ends, C, for example, requires constant folding in certain places,
>>>>>>> like case statement. If constant folding is completely moved off to gimple,
>>>>>>> how shall this be handled ? Shall we gimplify the expression immediately if
>>>>>>> it's required to be evaluated ?
>>>>>>>
>>>>>>> Thanks and Regards,
>>>>>>> Prathamesh