[GNU Tools Cauldron 2014] Unifying GENERIC and GIMPLE folding with pattern description

[Prathamesh Kulkarni]

Sorry for the double-post, forgot to set "plain-text" mode.

Hi,
    Please find my note attached for the presentation on "Unifying
GENERIC and GIMPLE folding with pattern description" at Cauldron.
I would be grateful if you would review it for me.

Thanks,
Prathamesh.
-------------- next part --------------
Unifiying GENERIC and GIMPLE folding with pattern description:

Author - Richard Biener

    The purpose of this project is to write a tool that reads pattern descriptions written in a lisp-style DSL and generates simplification C code for folding on GIMPLE and GENERIC. Another goal is to provide an interface for other SSA propogation passes (eg: forwprop)
for performing folding on-the-fly, using information from the pass lattice. This project aims to provide a single API for
simplifications on GIMPLE and GENERIC.

DSL:
    Similar to other DSL's in gcc, it is designed to have lispy syntax.
Since it's intended to target GENERIC and GIMPLE, it exposes common implementation details
like
- tree codes and built-in function codes as operators
- trees as operands
- tree predicates as predicates
- plain C code for simplification valid for both GENERIC and GIMPLE.

Example:
(match_and_simplify
  (bit_and:c integral_op_p@0
             (bit_ior:c (bit_not @0) @1))
  (bit_and @1 @0))

The above pattern simplifies X & (~X | Y) -> Y & X.
Flag ":c" indicates that bit_and is marked commutative and correspondingly matches the commutative variant.

Implementation:
    genmatch reads match.pd and generates generic-match.c which contains rountines for GENERIC simplification
and gimple-match.c for GIMLPLE simplification.

Pattern representation.
    A match_and_simplify pattern fundamentally consists of 3 parts (struct simplify):
a) "match" operand that is used for performing GIMPLE/GENERIC matching.
b) an optional ifexpr
c) "simplification" operand used for performing GIMPLE/GENERIC simplification

AST and Decision Tree:
    All operands are represented by an AST (struct operand), which serves as an intermediate representation
before generating simplifiaction code. Decision tree (struct decision_tree) is used to store prefixes of preorder traversals of different match-operands, to avoid repeated pattern matching. commutative ops and other "high level" constructs are lowered to 
"plain" AST's, before inserting into decision tree. 

Code generation:
    Code generation for "match" operand is done off the decision tree, and for simplification off the AST.
The entry point for GIMPLE code generation is decision_tree::gen_gimple and for GENERIC decision_tree::gen_generic.
GIMPLE simplification follows SSA edges. GENERIC variant rejects operands with side-effects.

Patterns:
  Patterns are implemented in match*.pd files in match-and-simplify branch. However this might get changed.

Merge Proposal for next GCC release:
- merge infrastructure
- merge forwprop changes
- merge sccvn changes
- merge gimple_build API and selected gimple_build API uses
- merge gimple_fold_stmt_to_constant refactoring