On Fri, 28 Feb 2014, Marc Glisse wrote:
> On Thu, 27 Feb 2014, Richard Biener wrote:
>
> > I've been hacking on a prototype that generates matching and
> > simplification code from a meta-description. The goal is
> > to provide a single source of transforms currently spread
> > over the compiler, mostly fold-const.c, gimple-fold.c and
> > tree-ssa-forwprop.c. Another goal is to make these transforms
> > (which are most of the form of generating a simpler form of
> > a pattern-matched IL piece) more readily available to passes
> > like value-numbering so they can be used on-the-fly, using
> > information provided by the pass lattice. The ultimate
> > goal is to generate (most of) fold-const.c and gimple-fold.c
> > and tree-ssa-forwprop.c from a single meta description.
> [...]
> > Comments or suggestions?
>
> It is hard to judge from such simple examples. What if I want to do the
> transformation only if CST+CST' doesn't overflow?
We'd probably make the generator possibly fail, eventually adding the
ability for a variant like
/* Match and simplify CST + CST to CST'. */
(define_match_and_simplify baz
(PLUS_EXPR INTEGER_CST_P@0 INTEGER_CST_P@1)
{
captures[0] = int_const_binop (PLUS_EXPR, captures[0], captures[1]);
if (TREE_OVERFLOW (captures[0]))
captures[0] = NULL_TREE;
}
@0)
that is, allow a complete manual transform step with a possible
FAIL outcome.
> Can I make it handle commutative operations cleverly?
As the goal is to allow a state machine to be generated for the matching
(to make the matching O(1) independent of the number of patterns)
the generator would have to duplicate the pattern internally. But yes,
I've thought about commutativeness.
> How do I restrict some subexpression to have
> a single use?
This kind of restrictions come via the valueize() hook - simply
valueize to NULL_TREE to make the match fail (for example
SSA_NAME_OCCURS_IN_ABNORMAL_PHI could be made fail that way).
> If I want to check some flag_*, do I have to create a predicate
> that tests for that as well as whatever other test the specific operand
> needed?
You mean like a pattern that is enabled conditinal on, for example,
flag_unsafe_math_optimizations? Didn't think of that yet, but we
can easily add an optional overall pattern condition like we have
in the RTL md files.
> Won't valueize create a lot of not-so-necessary trees when used on
> gimple?
No, valueize should only valueize to SSA names or constants, not
expressions. It's purpose is to integrate well with a SSA propagator
lattice - for example the tree-ssa-sccvn.c integration (subsume
it's "simplify" implementation) would be
Index: gcc/tree-ssa-sccvn.c
===================================================================
--- gcc/tree-ssa-sccvn.c (revision 208269)
+++ gcc/tree-ssa-sccvn.c (working copy)
@@ -3344,35 +3344,23 @@ try_to_simplify (gimple stmt)
if (code == SSA_NAME)
return NULL_TREE;
- /* First try constant folding based on our current lattice. */
+ /* First try constant folding based on our current lattice.
+ ??? Should be subsumed by gimple_match_and_simplify. */
tem = gimple_fold_stmt_to_constant_1 (stmt, vn_valueize);
if (tem
&& (TREE_CODE (tem) == SSA_NAME
|| is_gimple_min_invariant (tem)))
return tem;
- /* If that didn't work try combining multiple statements. */
- switch (TREE_CODE_CLASS (code))
- {
- case tcc_reference:
- /* Fallthrough for some unary codes that can operate on registers.
*/
- if (!(code == REALPART_EXPR
- || code == IMAGPART_EXPR
- || code == VIEW_CONVERT_EXPR
- || code == BIT_FIELD_REF))
- break;
- /* We could do a little more with unary ops, if they expand
- into binary ops, but it's debatable whether it is worth it. */
- case tcc_unary:
- return simplify_unary_expression (stmt);
-
- case tcc_comparison:
- case tcc_binary:
- return simplify_binary_expression (stmt);
-
- default:
- break;
- }
+ /* If that didn't work try combining multiple statements.
+ ??? Handle multiple stmts being generated by storing
+ at most one in VN_INFO->expr? But then we'd have to
+ transparently support materializing temporary SSA names
+ created by gimple_match_and_simplify - or we never value-number
+ to them. */
+ if (TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME)
+ return gimple_match_and_simplify (gimple_assign_lhs (stmt),
+ NULL, vn_valueize);
return NULL_TREE;
}
> If I write a COND_EXPR matcher, could it generate code for phiopt as
> well?
Not sure, what do you have in mind specifically?
> What is the point of gimple_match (without _and_substitute)? Will it
> clean up the new dead statements after itself?
No, the low-level interface won't. I'm not yet decided if we should
have an alternate interface taking a stmt iterator rather than a
SSA name and sequence pointer (thus perform a in-place substitute
and fold of a stmt). Currently you'd do for tree-ssa-forwprop.c
(lattice missing - sth to add anyway):
@@ -3681,6 +3683,21 @@ ssa_forward_propagate_and_combine (void)
/* Mark stmt as potentially needing revisiting. */
gimple_set_plf (stmt, GF_PLF_1, false);
+ /* ??? Handle calls. */
+ if (is_gimple_assign (stmt))
+ {
+ gimple_seq seq = NULL;
+ tree tem = gimple_match_and_simplify (gimple_get_lhs (stmt),
+ &seq, NULL);
+ if (tem)
+ {
+ changed = true;
+ if (!gimple_seq_empty_p (seq))
+ gsi_insert_seq_before (gsi, seq, GSI_SAME_STMT);
+ gimple_assign_set_rhs_from_tree (tem);
+ }
+ }
+
switch (gimple_code (stmt))
{
case GIMPLE_ASSIGN:
The !empty sequence case should probably be handled more efficiently
by the lowest level interface. I'm going to think about this some
more (re-use the def SSA name of stmt, allowing to gsi_replace
stmt with the last one in the sequence).
> Can I write (PLUS_EXPR@0 @1 @2)
> so I can still refer to this subexpression later?
You can write
(PLUS_EXPR @1 @2)@0
> How do you handle a
> transformation that currently tries to recursively fold something else and
> does the main transformation only if that simplified?
And doesn't do the other folding (because it's not in the IL literally?)?
Similar to the cst without overflow case, by writing custom C code
and allowing that to signal failure.
> I guess most of the answers will become obvious once you have converted a few
> existing transformations and I can look at those...
Yes. I didn't write too many patterns yet (but only looked at
associate_plusminus () in tree-ssa-forwprop.c) as I wanted to
first have some passes actually use the patterns (to weed out
issues with the interfacing and thus possibly code generation).
> Since this is going to require a rewrite of many transformations, I wonder if
> there are things that should be improved before starting so we can write the
> right tests directly. For A+B-B, we can do the transformation if the type is
> an integer for which overflow either wraps or is undefined or
> traps-but-it-is-ok-to-remove-those-traps (but not if it traps and we promise
> to preserve traps, or if the type saturates), or the type is a float and we
> have the unsafe math flag, or the type is a vector/complex and the
> transformation is valid for the element type. Ok, maybe not the best example,
> but we have for instance -ftrapping-math for which a split was discussed (PR
> 53805#c4).
Yeah, how to predicate on types is sth I have been thinking of ...
/* Match and simplify (A - B) + B -> A. */
(define_match_and_simplify foo
(PLUS_EXPR:INTEGRAL_TYPE (MINUS_EXPR integral_op_p@0 @1) @1)
@0)
for example (matching how we handle modes in RTL). Of course
I'm now at a point where having tree codes (and builtin fn codes)
and type kinds enumerated in the parser would be useful ;))
I'll summarize some of the gloals of this in the reply to Diego.
Thanks,
Richard.
