Re: [GSoC] first phase

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

On Tue, May 20, 2014 at 2:59 PM, Prathamesh Kulkarni
<bilbotheelffriend@gmail.com> wrote:
> On Tue, May 20, 2014 at 5:46 PM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On Mon, May 19, 2014 at 7:30 PM, Prathamesh Kulkarni
>> <bilbotheelffriend@gmail.com> wrote:
>>> Hi,
>>>    Unfortunately I shall need to take this week off, due to university exams,
>>> which are up-to 27th May. I will start working from 28th on pattern
>>> matching with decision tree, and try to cover up for the first week. I
>>> am extremely sorry about this.
>>> I thought I would be able to do both during exam week, but the exam
>>> load has become too much -:(
>>
>> Ok.
>>
>>> In the first phase (up-to 23rd June), I hope to get genmatch ready:
>>> a) pattern matching with decision tree.
>>> b) Add patterns to test genmatch.
>>> c) Depending upon the patterns, extending the meta-description
>>> d) Other fixes:
>>>
>>> * capturing outermost expressions.
>>> For example this pattern does not get simplified
>>> (match_and_simplify
>>>   (plus@2 (negate @0) @1)
>>>   if (!TYPE_SATURATING (TREE_TYPE (@2)))
>>>   (minus @1 @0))
>>> I guess this happens because in write_nary_simplifiers:
>>>   if (s->match->type != OP_EXPR)
>>>     continue;
>>
>> Yeah.
>>
>>> Maybe this is not correct way to fix this, should we also pass lhs to
>>> generated gimple_match_and_simplify ? I guess that would be the capture
>>> for outermost expression.
>>
>> Unfortunately it is not available for all API entries.  The type of the
>> expression is, though.
>>
>> I lean towards rejecting the capture at parsing time and providing
>> a "special" capture (for example @@, or just @0, or @T to denote
>> it's a type, or just refer "magically" to 'type').  That is,
>>
>> (match_and_simplify
>>   (plus (negate @0) @1)
>>   if (!TYPE_SATURATING (type))
>>   (minus @1 @0))
>>
>> works for me.
>>
>>> For above pattern, I guess @2 represents lhs.
>>>
>>> So for this test-case:
>>> int foo (int x, int y)
>>> {
>>>   int t1 = -x;
>>>   int t2 = t1 + y;
>>>   return t2;
>>> }
>>> t2 would be @2, t1 would be @0 and y would be @1.
>>> Is that correct ?
>>> This would create issues when lhs is NULL, for example,
>>> in call to built-in functions ?
>>
>> Yeah, or if the machinery is called via gimple_build () where
>> there is no existing lhs.
>>
>>> * avoid using statement expressions for code gen of expression
>>> * rewriting code-generator using visitor classes, and other refactoring
>>> (using std::string for example), etc.
>>>
>>> I have a very rough time-line in mind, for completing tasks:
>>> 28th may - 31st may
>>> a) Have test-case for each pattern present (except COND_EXPR) in match.pd
>>> I guess most of it is already done, a few patterns are remaining.
>>
>> Good.
>>
>>> b) Small fixes (for example, those mentioned above).
>>
>> Good.
>>
>>> c) Have an initial idea/prototype for implementing decision tree
>>>
>>> 1st June - 15th June
>>> a) Implementing decision tree
>>> b) Adding patterns in match.pd to test the decision tree in match.pd,
>>> and accompanying test-cases in tree-ssa/match-*.c
>>>
>>> 16th June - 23rd June
>>> a) Support for GENERIC code generation.
>>> b) Refactoring and backup time for backlog.
>>>
>>> GENERIC code generation:
>>> I am a bit confused about this. Currently, pattern matching is
>>> implemented for GENERIC. However I believe simplification is done on
>>> GIMPLE.
>>> For example:
>>> (match_and_simplify
>>>   (plus (negate @0) @1)
>>>   (minus @0 @1))
>>> If given input is GENERIC , it would do matching on GENERIC, but shall
>>> transform (minus @0 @1) to it's GIMPLE equivalent.
>>> Is that correct ?
>>
>> Correct.  Err, not sure what it will do - I implemented it only to support
>> the weird cases where GENERIC is nested inside GIMPLE, like for
>> a_2 = b_3 < 0 ? c_4 : d_5;  thus the comment in match.pd:
>>
>> /* Due to COND_EXPRs weirdness in GIMPLE the following won't work
>>    without some hacks in the code generator.  */
>> (match_and_simplify
>>   (cond (bit_not @0) @1 @2)
>>   (cond @0 @2 @1))
>>
>> the code generator would need to know that COND_EXPR has
>> a GENERIC op0 ... same applies to REALPART_EXPR, but there
>> the hacks are already in place ;)
>>
>>>
>>> * Should we have a separate GENERIC match-and-simplify API like for gimple
>>> instead of having GENERIC matching in gimple_match_and_simplify ?
>>
>> Yes.  The GENERIC API follows the API of fold_{unary,binary,ternary}.
>> I suppose we simply provide a slightly different name for them
>> (but use the original API for recursing and call ourselves from the original
>> API).
>>
>>> * Do we add another pattern type, something like
>>> generic_match_and_simplify that will do the transform on GENERIC
>>> for example:
>>> (generic_match_and_simplify
>>>   (plus (negate @0) @1)
>>>   (minus @0 @1))
>>> would produce GENERIC equivalent of (minus @0 @1).
>>>
>>> or maybe keep match_and_simplify, and tell the transform operand
>>> to produce GENERIC.
>>> Something like:
>>> (match_and_simplify
>>>   (plus (negate @0) @1)
>>>   GENERIC: (minus @0 @1))
>>
>> we simply process each pattern twice, once we generate the
>> GIMPLE match-and-simplify routine and once we generate the
>> GENERIC match-and-simplify routine.  The patterns are supposed
>> to be the same for both and always apply to both.
> Yes, for  patterns where transform operand is not c-code.
> I guess this wouldn't work for transforms written as c-code that uses
> IR-specific API ?
> As long as c-code is common to both GENERIC and GIMPLE
> (for example contains only call to build_* functions like {
> build_int_cst(); }), that would be fine,
> but for example if the c-code contains gimple-specific API, like {
> SSA_NAME_DEF_STMT (@0) },
> for these cases we could only generate IR-specific transforms ?
> so I guess we would need some way in pattern description to tell if
> it's GIMPLE or GENERIC ?

That's true.  We should try to provide enough infrastructure to
avoid the need to do this though.

So as usual - ignore the issue until it pops up ;)

Richard.

>>
>>> Another thing I would like to do in first phase is figure out dependencies
>>> of tree-ssa-forwprop on GENERIC folding (for instance fold_comparison patterns).
>>
>> Yeah.  Having patterns for comparison simplification is important for
>> other parts of the compiler as well, thus my idea of tackling those
>> as part of the project.  Look at forward_propagate_into_comparison_1
>> and combine_cond_expr_cond which dispatches to fold_binary
>> with tcc_comparison tree class codes (and fold_binary has
>> most (but not all ...) comparison-class handling in fold_comparison).
>>
>> Richard.
>>
>>>
>>> Thanks and Regards,
>>> Prathamesh