Re: [GSoC] first phase

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

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.

> 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