This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [GSoC] Generating patterns from meta-description

On Tue, Apr 22, 2014 at 6:39 PM, Prathamesh Kulkarni
<> wrote:
> Hi,
>     Thank-you for selecting me for GSoC 2014, I am looking forward to
> working with GCC community. I am grateful to Richard Biener and Diego Novillo
> for choosing to mentor me for this project. Unfortunately, I couldn't
> reply last week because I am in the middle of university exams, I
> apologize for that.
> * Time Commitments:
> I have university exams up-to 5th May, and couple of exams on 24th may
> and 27th may. Thereafter I am completely free, and can commit up-to
> 50 hours per week on average.
> * Few questions regarding genmatch:
> a) Lexical analysis and Parsing:
> I believe this is already in place. We would continue with
> hand-written recursive descent parser.

That's correct.  Cleanups/extensions can be applied as necessary.

> b) Intermediate representations:
> For representing "matching" operands
> we will need to use a decision tree (I am not yet decided on how it would be
> implemented). For "simplification" operands, we can use AST (struct operand).
> For example:
> (match_and_simplify
>   (negate (negate @0))
>   @0)
> (match_and_simplify
>   (negate (bit_not @0))
>   (minus @0 { integer_one_node; }))
> There would be 2 AST's to represent @0 and (minus @0 { integer_one_node; } ).
> And one decision tree representing matching operands for both expressions.
> Something like:
>           negate
> negate        minus
> @0             @0   { integer_one_node' }


> c) Code generation:
> Currently code-generation is done for gimple by walking the AST by
> calling .gen_gimple_match and .gen_gimple_transform on each node.
> Would it be a good idea to separate code gen interfaces
> (.gen_gimple_match and .gen_gimple_transform) from AST ?
> We would be having two IR's (decision-tree and AST) and two targets
> (generic and gimple). Code-generation for pattern-matching shall be
> performed by tree-walk
> of decision tree and for transforms by tree-walk of AST.

Yeah, not using virtual methods here is fine with me.  Certainly the
current code generator is a quick hack used for prototyping.  You
can completely rewrite it using modern C++ techniques if you like
(you have to stick to C++04 though).

> d) Handling Commutative operators:
> Should it be hard-coded in genmatch which operators are commutative ?
> Internally the pattern would be duplicated with operands reversed.

First, for some operand kinds GCC already presents you with a canonicalized
operand order - see gimple-match-head.c and how it calls
commutative_tree_code (code) && tree_swap_operands_p ().  That usually
applies to 'leafs' only (at least on GIMPLE where the ops are just two
SSA names for complex expressions).

But that already gives you the idea of what tree codes are commutative
(though that's not exposed to the parser / AST in a useful way).  Ideally
we'd extend tree.def with a 'commutative' flag so we can implement
commutative_tree_code by clever preprocessing and do the same in

That leaves the question on what pattens (and which nodes of the
pattern tree) to actually apply the commutation (given that the
number of permutations to try grows exponentially with expression

We have two choices here - explicitely mark to commutate nodes
somehow, like for example with '+' on the operator

  (MINUS_EXPR (+PLUS_EXPR @0 @1) @0)

or we only commutate the outermost node (doesn't catch the example)
or we only commutate leaf nodes (usually not necessary due to
the code in gimple-match-head.c).

Explicit marking at least doesn't require us to solve the "what operators
are commutative" problem, so I'd go with that (for now).

> e) Finalizing syntax:
> For example: plus vs PLUS vs PLUS_EXPR, currently all of them are accepted.
> (I would prefer lowercase version). Similarly free-form if vs
> lisp-style (if ...) etc.

Yes.  I also prefer the lowercase version without the _EXPR part.
Similar for the function call matching - use 'cabs', not BUILT_IN_CABS.
Leaves us with the ambiguity of BUILT_IN_ABS and ABS_EXPR ... ;)
I believe they have compatible behavior (but for -ftrapv/-fwrapv they
differ in handling of the most negative integer).  Let's defer that issue
(I thought of requiring to say abs_expr / built_in_abs on conflict).

> * Upto 19th may:
> I plan to do the following upto 19th May:
> a) Separate code-gen interfaces from AST and add simple fixes to genmatch.

Good.  It would also be nice to do e) from above - settle on the lower-case
without _expr and built_in_ suffix/prefix variants.

> b) Study forwprop patterns.
> c) Try to solve missed optimization bugs.
> If there's something else I would need to do, I would be happy to hear
> about that.

I'd say take the existing match.pd (which is really just a "testcase"
for genmatch right now, apart from the bits commented with
Transforms formerly done by tree-ssa-forwprop.c:associate_plusminus),
strip it down and make sure we have a testcase for each transform
we apply (trigger it in forwprop).


> Let me thank-you once again for selecting me for GSoC, and
> I hope I would be able to complete the project successfully within given time.
> Thanks and Regards,
> Prathamesh

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]