This hooks the machinery into fold_stmt (but not allowed to traverse
SSA use-def chains by default) and provides a new overload to
provide a valueization hook. With the patch tree-ssa-forwprop.c
makes use of that new overload, first folding all statements
while keeping a simple const-and-copy lattice.
Once all "toplevel" patterns are in place (patterns with
a single operation) we can remove the dispatch to GENERIC
folding from fold_stmt.
A question is whether to really do as the patch does and simplify
all statements or whether I should restrict this to stmts that
were previously covered by its manual patterns (which further
patches will transition to match-and-simplify patterns).
As for the GENERIC part, here is what the simplification routine
looks like for
/* fold_negate_exprs convert - (~A) to A + 1. */
(simplify
(negate (bit_not @0))
(if (INTEGRAL_TYPE_P (type))
(plus @0 { build_int_cst (TREE_TYPE (@0), 1); } )))
static bool
gimple_simplify (code_helper *res_code, tree *res_ops,
gimple_seq *seq, tree (*valueize)(tree),
code_helper code, tree type, tree op0)
{
switch (code.get_rep())
{
...
case NEGATE_EXPR:
{
switch (TREE_CODE (op0))
{
case SSA_NAME:
{
gimple def_stmt = SSA_NAME_DEF_STMT (op0);
if (is_gimple_assign (def_stmt))
switch (gimple_assign_rhs_code (def_stmt))
{
case BIT_NOT_EXPR:
{
tree o20 = gimple_assign_rhs1 (def_stmt);
if ((o20 = do_valueize (valueize, o20)) != 0)
{
{
/* #line 136
"/space/rguenther/src/svn/match-and-simplify/gcc/match.pd" */
tree captures[2] ATTRIBUTE_UNUSED = {};
captures[0] = o20;
/* #line 135
"/space/rguenther/src/svn/match-and-simplify/gcc/match.pd" */
if (INTEGRAL_TYPE_P (type))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Applying pattern match.pd:136, %s:%d\n", __FILE__,
__LINE__);
*res_code = PLUS_EXPR;
res_ops[0] = captures[0];
res_ops[1] = build_int_cst (TREE_TYPE
(captures[0]), 1);
gimple_resimplify2 (seq, res_code, type,
res_ops, valueize);
return true;
}
}
}
break;
}
...
As you can see we use gimple_resimplify2 for re-simplification and
code-generation and the toplevel expression of the result is
kept in pieces. gimple_resimplify2 in turn ends up calling
gimple_simplify again and fold to get the "real" constant folding cases.
Boostrap and regtest is pending on x86_64-unknown-linux-gnu.
Ok for trunk?
Thanks,
Richard.
2014-10-15 Richard Biener <[email protected]>
* gimple-fold.h (fold_stmt): New overload with valueization hook.
(no_follow_ssa_edges): Declare.
* gimple-fold.c: Include tree-eh.h and gimple-match.h.
(fold_stmt_1): Add valueization hook parameter. Dispatch to
gimple_simplify after canonicalization.
(no_follow_ssa_edges): New function.
(fold_stmt): New overload and adjust.
(fold_stmt_inplace): Adjust.
* tree-ssa-forwprop.c: Include tree-cfgcleanup.h and tree-into-ssa.h.
(lattice): New global.
(fwprop_ssa_val): New function.
(pass_forwprop::execute): Do a first pass over all stmts in
dominator order simplifying all statements while keeping
a simple const-and-copy lattice up-to-date.
Index: gcc/gimple-fold.h
===================================================================
*** gcc/gimple-fold.h.orig 2014-10-15 13:01:41.548100887 +0200
--- gcc/gimple-fold.h 2014-10-15 13:57:05.627872029 +0200
*************** extern tree canonicalize_constructor_val
*** 26,36 ****
--- 26,38 ----
extern tree get_symbol_constant_value (tree);
extern void gimplify_and_update_call_from_tree (gimple_stmt_iterator *, tree);
extern bool fold_stmt (gimple_stmt_iterator *);
+ extern bool fold_stmt (gimple_stmt_iterator *, tree (*) (tree));
extern bool fold_stmt_inplace (gimple_stmt_iterator *);
extern tree maybe_fold_and_comparisons (enum tree_code, tree, tree,
enum tree_code, tree, tree);
extern tree maybe_fold_or_comparisons (enum tree_code, tree, tree,
enum tree_code, tree, tree);
+ extern tree no_follow_ssa_edges (tree);
extern tree gimple_fold_stmt_to_constant_1 (gimple, tree (*) (tree));
extern tree gimple_fold_stmt_to_constant (gimple, tree (*) (tree));
extern tree fold_const_aggregate_ref_1 (tree, tree (*) (tree));
Index: gcc/gimple-fold.c
===================================================================
*** gcc/gimple-fold.c.orig 2014-10-15 13:02:08.158099055 +0200
--- gcc/gimple-fold.c 2014-10-15 13:56:20.710875121 +0200
*************** along with GCC; see the file COPYING3.
*** 55,60 ****
--- 55,63 ----
#include "dbgcnt.h"
#include "builtins.h"
#include "output.h"
+ #include "tree-eh.h"
+ #include "gimple-match.h"
+
/* Return true when DECL can be referenced from current unit.
*************** maybe_canonicalize_mem_ref_addr (tree *t
*** 2811,2817 ****
distinguishes both cases. */
static bool
! fold_stmt_1 (gimple_stmt_iterator *gsi, bool inplace)
{
bool changed = false;
gimple stmt = gsi_stmt (*gsi);
--- 2814,2820 ----
distinguishes both cases. */
static bool
! fold_stmt_1 (gimple_stmt_iterator *gsi, bool inplace, tree (*valueize) (tree))
{
bool changed = false;
gimple stmt = gsi_stmt (*gsi);
*************** fold_stmt_1 (gimple_stmt_iterator *gsi,
*** 2889,2894 ****
--- 2892,3017 ----
default:;
}
+ /* Dispatch to pattern-based folding. */
+ /* ??? Change "inplace" semantics to allow replacing a stmt if
+ no further stmts need to be inserted (basically disallow
+ creating of new SSA names). */
+ if (!inplace
+ || is_gimple_assign (stmt)
+ || gimple_code (stmt) == GIMPLE_COND)
+ {
+ gimple_seq seq = NULL;
+ code_helper rcode;
+ tree ops[3] = {};
+ if (gimple_simplify (stmt, &rcode, ops, inplace ? NULL : &seq,
valueize))
+ {
+ if (gimple_code (stmt) == GIMPLE_COND)
+ {
+ gcc_assert (rcode.is_tree_code ());
+ if (TREE_CODE_CLASS ((enum tree_code)rcode) == tcc_comparison
+ /* GIMPLE_CONDs condition may not throw. */
+ /* ??? Not sure how we want to deal with combining
+ from possibly throwing statements. Trivial
+ simplifications may lead to DCEing an internal
+ throw. But we probably still want to simplify
+ things to a constant for example? Similar to
+ abnormals we could discard the simplification
+ result if we ever push a could-throw stmt to
+ the sequence. */
+ && (!flag_exceptions
+ || !cfun->can_throw_non_call_exceptions
+ || !operation_could_trap_p (rcode, FLOAT_TYPE_P
(TREE_TYPE (ops[0])), false, NULL_TREE)))
+ gimple_cond_set_condition (stmt, rcode, ops[0], ops[1]);
+ else if (rcode == SSA_NAME)
+ gimple_cond_set_condition (stmt, NE_EXPR, ops[0],
+ build_zero_cst (TREE_TYPE (ops[0])));
+ else if (rcode == INTEGER_CST)
+ {
+ if (integer_zerop (ops[0]))
+ gimple_cond_make_false (stmt);
+ else
+ gimple_cond_make_true (stmt);
+ }
+ else if (!inplace)
+ {
+ tree res = maybe_push_res_to_seq (rcode, boolean_type_node,
+ ops, &seq);
+ if (!res)
+ goto fail;
+ gimple_cond_set_condition (stmt, NE_EXPR, res,
+ build_zero_cst (TREE_TYPE (res)));
+ }
+ else
+ goto fail;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "gimple_simplified to ");
+ if (!gimple_seq_empty_p (seq))
+ print_gimple_seq (dump_file, seq, 0, TDF_SLIM);
+ print_gimple_stmt (dump_file, gsi_stmt (*gsi),
+ 0, TDF_SLIM);
+ }
+ gsi_insert_seq_before (gsi, seq, GSI_SAME_STMT);
+ changed = true;
+ fail:
+ ;
+ }
+ else if (is_gimple_assign (stmt)
+ && rcode.is_tree_code ())
+ {
+ if ((!inplace
+ || gimple_num_ops (stmt) <= get_gimple_rhs_num_ops (rcode))
+ /* Play safe and do not allow abnormals to be mentioned in
+ newly created statements. */
+ && !((TREE_CODE (ops[0]) == SSA_NAME
+ && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ops[0]))
+ || (ops[1]
+ && TREE_CODE (ops[1]) == SSA_NAME
+ && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ops[1]))
+ || (ops[2]
+ && TREE_CODE (ops[2]) == SSA_NAME
+ && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ops[2]))))
+ {
+ maybe_build_generic_op (rcode,
+ TREE_TYPE (gimple_assign_lhs (stmt)),
+ &ops[0], ops[1], ops[2]);
+ gimple_assign_set_rhs_with_ops_1 (gsi, rcode,
+ ops[0], ops[1], ops[2]);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "gimple_simplified to ");
+ if (!gimple_seq_empty_p (seq))
+ print_gimple_seq (dump_file, seq, 0, TDF_SLIM);
+ print_gimple_stmt (dump_file, gsi_stmt (*gsi),
+ 0, TDF_SLIM);
+ }
+ gsi_insert_seq_before (gsi, seq, GSI_SAME_STMT);
+ changed = true;
+ }
+ }
+ else if (!inplace)
+ {
+ if (gimple_has_lhs (stmt))
+ {
+ tree lhs = gimple_get_lhs (stmt);
+ maybe_push_res_to_seq (rcode, TREE_TYPE (lhs),
+ ops, &seq, lhs);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "gimple_simplified to ");
+ print_gimple_seq (dump_file, seq, 0, TDF_SLIM);
+ }
+ gsi_replace_with_seq_vops (gsi, seq);
+ changed = true;
+ }
+ else
+ gcc_unreachable ();
+ }
+ }
+ }
+
+ stmt = gsi_stmt (*gsi);
+
/* Fold the main computation performed by the statement. */
switch (gimple_code (stmt))
{
*************** fold_stmt_1 (gimple_stmt_iterator *gsi,
*** 3028,3033 ****
--- 3151,3164 ----
return changed;
}
+ /* Valueziation callback that ends up not following SSA edges. */
+
+ tree
+ no_follow_ssa_edges (tree)
+ {
+ return NULL_TREE;
+ }
+
/* Fold the statement pointed to by GSI. In some cases, this function may
replace the whole statement with a new one. Returns true iff folding
makes any changes.
*************** fold_stmt_1 (gimple_stmt_iterator *gsi,
*** 3038,3044 ****
bool
fold_stmt (gimple_stmt_iterator *gsi)
{
! return fold_stmt_1 (gsi, false);
}
/* Perform the minimal folding on statement *GSI. Only operations like
--- 3169,3181 ----
bool
fold_stmt (gimple_stmt_iterator *gsi)
{
! return fold_stmt_1 (gsi, false, no_follow_ssa_edges);
! }
!
! bool
! fold_stmt (gimple_stmt_iterator *gsi, tree (*valueize) (tree))
! {
! return fold_stmt_1 (gsi, false, valueize);
}
/* Perform the minimal folding on statement *GSI. Only operations like
*************** bool
*** 3053,3059 ****
fold_stmt_inplace (gimple_stmt_iterator *gsi)
{
gimple stmt = gsi_stmt (*gsi);
! bool changed = fold_stmt_1 (gsi, true);
gcc_assert (gsi_stmt (*gsi) == stmt);
return changed;
}
--- 3190,3196 ----
fold_stmt_inplace (gimple_stmt_iterator *gsi)
{
gimple stmt = gsi_stmt (*gsi);
! bool changed = fold_stmt_1 (gsi, true, no_follow_ssa_edges);
gcc_assert (gsi_stmt (*gsi) == stmt);
return changed;
}
Index: gcc/tree-ssa-forwprop.c
===================================================================
*** gcc/tree-ssa-forwprop.c.orig 2014-10-14 15:49:39.836355545 +0200
--- gcc/tree-ssa-forwprop.c 2014-10-15 13:56:20.725875120 +0200
*************** along with GCC; see the file COPYING3.
*** 54,59 ****
--- 54,61 ----
#include "tree-ssa-propagate.h"
#include "tree-ssa-dom.h"
#include "builtins.h"
+ #include "tree-cfgcleanup.h"
+ #include "tree-into-ssa.h"
/* This pass propagates the RHS of assignment statements into use
sites of the LHS of the assignment. It's basically a specialized
*************** simplify_mult (gimple_stmt_iterator *gsi
*** 3586,3591 ****
--- 3588,3613 ----
return false;
}
+
+
+ static vec<tree> lattice;
+
+ /* Primitive "lattice" function for gimple_simplify to discard
+ matches on names whose definition contains abnormal SSA names. */
+
+ static tree
+ fwprop_ssa_val (tree name)
+ {
+ if (TREE_CODE (name) == SSA_NAME
+ && SSA_NAME_VERSION (name) < lattice.length ())
+ {
+ tree val = lattice[SSA_NAME_VERSION (name)];
+ if (val)
+ return val;
+ }
+ return name;
+ }
+
/* Main entry point for the forward propagation and statement combine
optimizer. */
*************** pass_forwprop::execute (function *fun)
*** 3626,3631 ****
--- 3648,3708 ----
cfg_changed = false;
+ /* Combine stmts with the stmts defining their operands. Do that
+ in an order that guarantees visiting SSA defs before SSA uses. */
+ lattice.create (num_ssa_names);
+ lattice.quick_grow_cleared (num_ssa_names);
+ int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (fun));
+ int postorder_num = inverted_post_order_compute (postorder);
+ for (int i = 0; i < postorder_num; ++i)
+ {
+ bb = BASIC_BLOCK_FOR_FN (fun, postorder[i]);
+ /* ??? Maybe want to handle degenerate PHIs to populate
+ the lattice more optimistically. */
+ for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
+ !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple stmt = gsi_stmt (gsi);
+ gimple orig_stmt = stmt;
+
+ if (fold_stmt (&gsi, fwprop_ssa_val))
+ {
+ stmt = gsi_stmt (gsi);
+ if (maybe_clean_or_replace_eh_stmt (orig_stmt, stmt)
+ && gimple_purge_dead_eh_edges (bb))
+ cfg_changed = true;
+ update_stmt (stmt);
+ }
+
+ /* Fill up the lattice. */
+ if (gimple_assign_single_p (stmt))
+ {
+ tree lhs = gimple_assign_lhs (stmt);
+ tree rhs = gimple_assign_rhs1 (stmt);
+ if (TREE_CODE (lhs) == SSA_NAME)
+ {
+ if (TREE_CODE (rhs) == SSA_NAME)
+ lattice[SSA_NAME_VERSION (lhs)] = fwprop_ssa_val (rhs);
+ else if (is_gimple_min_invariant (rhs))
+ lattice[SSA_NAME_VERSION (lhs)] = rhs;
+ else
+ lattice[SSA_NAME_VERSION (lhs)] = lhs;
+ }
+ }
+ }
+ }
+ free (postorder);
+ lattice.release ();
+
+ /* ??? Code below doesn't expect non-renamed VOPs and the above
+ doesn't keep virtual operand form up-to-date. */
+ if (cfg_changed)
+ {
+ cleanup_tree_cfg ();
+ cfg_changed = false;
+ }
+ update_ssa (TODO_update_ssa_only_virtuals);
+
FOR_EACH_BB_FN (bb, fun)
{
gimple_stmt_iterator gsi;
