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.
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
