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

[Prathamesh Kulkarni <bilbotheelffriend at gmail dot com>]

On Fri, Mar 7, 2014 at 2:38 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Thu, Mar 6, 2014 at 7:17 PM, Prathamesh Kulkarni
> <bilbotheelffriend@gmail.com> wrote:
>> On Thu, Mar 6, 2014 at 6:13 PM, Richard Biener
>> <richard.guenther@gmail.com> wrote:
>>> On Thu, Mar 6, 2014 at 1:11 PM, Prathamesh Kulkarni
>>> <bilbotheelffriend@gmail.com> wrote:
>>>> On Mon, Mar 3, 2014 at 3:32 PM, Richard Biener
>>>> <richard.guenther@gmail.com> wrote:
>>>>> On Sun, Mar 2, 2014 at 9:13 PM, Prathamesh Kulkarni
>>>>> <bilbotheelffriend@gmail.com> wrote:
>>>>>> Hi, I am an undergraduate student at University of Pune, India, and would
>>>>>> like to work on moving folding patterns from fold-const.c to gimple.
>>>>>
>>>>> I've seen the entry on our GSoC project page and edited it to discourage
>>>>> people from working on that line.  See
>>>>>
>>>>> http://gcc.gnu.org/ml/gcc/2014-02/msg00516.html
>>>>>
>>>>> for why.  I think that open-coding the transforms isn't maintainable
>>>>> in the long run.
>>>>>
>>>>>> If I understand correctly, constant folding is done on GENERIC (by
>>>>>> routines in fold-const.c), and then GENERIC is lowered to GIMPLE. The
>>>>>> purpose of this project,
>>>>>> is to have constant folding to be performed on GIMPLE instead (in
>>>>>> gimple-fold.c?)
>>>>>>
>>>>>> I have a few elementary questions to ask:
>>>>>>
>>>>>> a) A contrived example:
>>>>>> Consider a C expression, a = ~0 (assume a is int)
>>>>>> In GENERIC, this would roughly be represented as:
>>>>>> modify_expr<var_decl "a", <bit_not_expr<integer_cst 0>>>
>>>>>> this gets folded to:
>>>>>> modify_expr<var_decl "a", integer_cst -1>
>>>>>> and the corresponding gimple tuple generated is (-fdump-tree-gimple-raw):
>>>>>> gimple_assign <integer_cst, x, -1, NULL, NULL>
>>>>>>
>>>>>> So, instead of folding performed on GENERIC, it should be
>>>>>> done on GIMPLE.
>>>>>> So a tuple like the following should be generated by gimplification:
>>>>>> <bit_not_expr, a, 0, NULL, NULL>
>>>>>> and folded to (by call to fold_stmt):
>>>>>> <integer_cst, a, -1, NUL, NULL>
>>>>>> Is this the expected behavior ?
>>>>>>
>>>>>> I have attached a rough/incomplete patch (only stage1 compiled cc1), that
>>>>>> does the following foldings on bit_not_expr:
>>>>>> a) ~ INTEGER_CST => folded
>>>>>> b) ~~x => x
>>>>>> c) ~(-x) => x - 1
>>>>>> (For the moment, I put case BIT_NOT_EXPR: return NULL_TREE
>>>>>> in fold_unary_loc to avoid folding in GENERIC on bit_not_expr)
>>>>>>
>>>>>> Is the patch going in the correct direction ? Or have I completely missed
>>>>>> the point here ? I would be grateful to receive suggestions, and start working
>>>>>> on a fair patch.
>>>>>
>>>>> I think you implement what was suggested by Kai (and previously
>>>>> by me and Andrew, before I changed my mind).
>>>>>
>>>> Hi Richard,
>>>> Thanks for your reply and for pointing me out to this thread
>>>> http://gcc.gnu.org/ml/gcc/2014-02/msg00516.html
>>>>
>>>> I agree it's better to generate patterns from a meta-description
>>>> instead of hand-coding, and the idea seems interesting to me.
>>>>
>>>> I was playing around with the patch and did few trivial modifications
>>>> (please find the patch attached):
>>>> a) use obstack in parse_c_expr.
>>>>
>>>> b) use @ inside c code, instead of directly writing captures
>>>> (like $<num> in bison):
>>>> example:
>>>> /* Match and simplify CST + CST to CST'.  */
>>>> (define_match_and_simplify baz
>>>>   (PLUS_EXPR INTEGER_CST_P@0 INTEGER_CST_P@1)
>>>>   { int_const_binop (PLUS_EXPR, @0, @1); })
>>>>
>>>> c) Not sure if this is a good idea, conditional matching.
>>>> for example:
>>>> /* match (A * B) and simplify to
>>>>  * B if integer_zerop B is true ( A * 0 => 0)
>>>>  * A if integer_onep B is true  (A * 1 => A)
>>>>  */
>>>> (define_match_and_simplify multexpr
>>>>   (MULT_EXPR integral_op_p@0 integral_op_p@1)
>>>>   [
>>>>     (integer_zerop@1 @1)
>>>>     (integer_onep@1  @0)
>>>>   ])
>>>> Maybe condition can be generalized to be any operand instead of
>>>> testing predicate on capture operand ?
>>>>
>>>> I would be grateful to receive some direction for working on this project.
>>>> From the thread, I see a few possibilities:
>>>> a) Moving patterns from tree-ssa-forwprop
>>>> b) Extending the DSL (handle commutative operators, conditionally
>>>> enabling patterns ?)
>>>> c) Targeting GENERIC (Generating patterns in fold-const.c from the
>>>> description ?)
>>>> d) This is a bit silly, but maybe perform more error checking ?
>>>> for example the following pattern is currently accepted:
>>>> (define_match px
>>>>   (PLUS_EXPR @0 @1 @2))
>>>
>>> Note that I'm currently still hacking on this (see attachment for what
>>> I have right now).  The grammar is still in flux but I'd like to keep it
>>> simple for now (so no conditional replacement).
>>>
>>> I have changed quite some bits so d) should be easily possible
>>> now and I've done b) from your list as well.
>>>
>>> For the moment I'm trying to see whether the design is sound,
>>> especially the GCC-side APIs.  I hope to finish this this week
>>> (fingers crossing), and also settle on the syntax (see variants in
>>> the .pd).
>>>
>>> As for opening this up for a GSOC project to "finish" or work on
>>> that's a good idea.  In addition to a) Moving patterns from tree-ssa-forwprop
>>> which I think is the place where its easiest to plug this in without
>>> regressions it would be nice if you could work on e) Generate a
>>> state machine for the matching part, instead of trying one pattern
>>> after each other (see how insn-recog.c is produced).  I hope to
>>> cleanup the parser AST implementation a bit so that b) handling
>>> of commutative ops is possible as a pattern-duplication step.
>>> I've already added the ability to conditionally enable patterns.
>>> Doing c) would also be nice - another target besides the patterns
>>> in forwprop is the simplifications done by fold_comparison
>>> (and fold_binary on comparison ops) - because forwprop depends
>>> on those.
>>>
>>>> I wanted to apply to gsoc for this project and I was wondering if you
>>>> would you be willing to mentor me if I did?
>>>
>>> Sure.  I'd say e) and doing the related (commutative) AST ops
>>> would qualify best.  Not sure if mechanically moving patterns
>>> would qualify alone.
>>>
>> Thanks, I am eager to work on it. I shall get back within
>> a couple of days, with something to show.
>> Thanks once again.
>
> You can certainly experiment a bit, but I'm still in hacking mode
> so anything you produce now will conflict with changes I am doing.
> So eventually you want to wait a bit until I settled with the internal
> interfacing ;)
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.

b) Targeting GENERIC, separating AST from gimple/generic:
For generating a GENERIC pattern should there be another pattern
something like match_and_simplify_generic ?
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 ?
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) ?

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 ?

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.

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 ?

Regarding gsoc proposal, I would like to align it on the following points:
a) Pattern matching using decision tree
b) Generate GIMPLE folding patterns (tree-ssa-forwprop,
tree-ssa-sccvn, gimple-fold)
c) Generate GENERIC folding patterns (fold-const)
Is that fine ? I would like to hear about any changes that you feel should be
made.

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 ?

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