/* Reassociation for trees.
- Copyright (C) 2005, 2007 Free Software Foundation, Inc.
+ Copyright (C) 2005, 2007, 2008, 2009 Free Software Foundation, Inc.
Contributed by Daniel Berlin <dan@dberlin.org>
This file is part of GCC.
#include "system.h"
#include "coretypes.h"
#include "tm.h"
-#include "errors.h"
#include "ggc.h"
#include "tree.h"
#include "basic-block.h"
Thus, this is what we do. When we have three ops left, we check to see
what order to put them in, and call it a day. As a nod to vector sum
- reduction, we check if any of ops are a really a phi node that is a
+ reduction, we check if any of the ops are really a phi node that is a
destructive update for the associating op, and keep the destructive
update together for vector sum reduction recognition. */
return 0;
if (!is_gimple_assign (stmt)
- || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
+ || gimple_vdef (stmt))
return bb_rank[gimple_bb (stmt)->index];
/* If we already have a rank for this expression, use that. */
}
}
+
+static void linearize_expr_tree (VEC(operand_entry_t, heap) **, gimple,
+ bool, bool);
+
+/* Structure for tracking and counting operands. */
+typedef struct oecount_s {
+ int cnt;
+ enum tree_code oecode;
+ tree op;
+} oecount;
+
+DEF_VEC_O(oecount);
+DEF_VEC_ALLOC_O(oecount,heap);
+
+/* The heap for the oecount hashtable and the sorted list of operands. */
+static VEC (oecount, heap) *cvec;
+
+/* Hash function for oecount. */
+
+static hashval_t
+oecount_hash (const void *p)
+{
+ const oecount *c = VEC_index (oecount, cvec, (size_t)p - 42);
+ return htab_hash_pointer (c->op) ^ (hashval_t)c->oecode;
+}
+
+/* Comparison function for oecount. */
+
+static int
+oecount_eq (const void *p1, const void *p2)
+{
+ const oecount *c1 = VEC_index (oecount, cvec, (size_t)p1 - 42);
+ const oecount *c2 = VEC_index (oecount, cvec, (size_t)p2 - 42);
+ return (c1->oecode == c2->oecode
+ && c1->op == c2->op);
+}
+
+/* Comparison function for qsort sorting oecount elements by count. */
+
+static int
+oecount_cmp (const void *p1, const void *p2)
+{
+ const oecount *c1 = (const oecount *)p1;
+ const oecount *c2 = (const oecount *)p2;
+ return c1->cnt - c2->cnt;
+}
+
+/* Walks the linear chain with result *DEF searching for an operation
+ with operand OP and code OPCODE removing that from the chain. *DEF
+ is updated if there is only one operand but no operation left. */
+
+static void
+zero_one_operation (tree *def, enum tree_code opcode, tree op)
+{
+ gimple stmt = SSA_NAME_DEF_STMT (*def);
+
+ do
+ {
+ tree name = gimple_assign_rhs1 (stmt);
+
+ /* If this is the operation we look for and one of the operands
+ is ours simply propagate the other operand into the stmts
+ single use. */
+ if (gimple_assign_rhs_code (stmt) == opcode
+ && (name == op
+ || gimple_assign_rhs2 (stmt) == op))
+ {
+ gimple use_stmt;
+ use_operand_p use;
+ gimple_stmt_iterator gsi;
+ if (name == op)
+ name = gimple_assign_rhs2 (stmt);
+ gcc_assert (has_single_use (gimple_assign_lhs (stmt)));
+ single_imm_use (gimple_assign_lhs (stmt), &use, &use_stmt);
+ if (gimple_assign_lhs (stmt) == *def)
+ *def = name;
+ SET_USE (use, name);
+ if (TREE_CODE (name) != SSA_NAME)
+ update_stmt (use_stmt);
+ gsi = gsi_for_stmt (stmt);
+ gsi_remove (&gsi, true);
+ release_defs (stmt);
+ return;
+ }
+
+ /* Continue walking the chain. */
+ gcc_assert (name != op
+ && TREE_CODE (name) == SSA_NAME);
+ stmt = SSA_NAME_DEF_STMT (name);
+ }
+ while (1);
+}
+
+/* Builds one statement performing OP1 OPCODE OP2 using TMPVAR for
+ the result. Places the statement after the definition of either
+ OP1 or OP2. Returns the new statement. */
+
+static gimple
+build_and_add_sum (tree tmpvar, tree op1, tree op2, enum tree_code opcode)
+{
+ gimple op1def = NULL, op2def = NULL;
+ gimple_stmt_iterator gsi;
+ tree op;
+ gimple sum;
+
+ /* Create the addition statement. */
+ sum = gimple_build_assign_with_ops (opcode, tmpvar, op1, op2);
+ op = make_ssa_name (tmpvar, sum);
+ gimple_assign_set_lhs (sum, op);
+
+ /* Find an insertion place and insert. */
+ if (TREE_CODE (op1) == SSA_NAME)
+ op1def = SSA_NAME_DEF_STMT (op1);
+ if (TREE_CODE (op2) == SSA_NAME)
+ op2def = SSA_NAME_DEF_STMT (op2);
+ if ((!op1def || gimple_nop_p (op1def))
+ && (!op2def || gimple_nop_p (op2def)))
+ {
+ gsi = gsi_start_bb (single_succ (ENTRY_BLOCK_PTR));
+ gsi_insert_before (&gsi, sum, GSI_NEW_STMT);
+ }
+ else if ((!op1def || gimple_nop_p (op1def))
+ || (op2def && !gimple_nop_p (op2def)
+ && stmt_dominates_stmt_p (op1def, op2def)))
+ {
+ if (gimple_code (op2def) == GIMPLE_PHI)
+ {
+ gsi = gsi_start_bb (gimple_bb (op2def));
+ gsi_insert_before (&gsi, sum, GSI_NEW_STMT);
+ }
+ else
+ {
+ if (!stmt_ends_bb_p (op2def))
+ {
+ gsi = gsi_for_stmt (op2def);
+ gsi_insert_after (&gsi, sum, GSI_NEW_STMT);
+ }
+ else
+ {
+ edge e;
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (e, ei, gimple_bb (op2def)->succs)
+ if (e->flags & EDGE_FALLTHRU)
+ gsi_insert_on_edge_immediate (e, sum);
+ }
+ }
+ }
+ else
+ {
+ if (gimple_code (op1def) == GIMPLE_PHI)
+ {
+ gsi = gsi_start_bb (gimple_bb (op1def));
+ gsi_insert_before (&gsi, sum, GSI_NEW_STMT);
+ }
+ else
+ {
+ if (!stmt_ends_bb_p (op1def))
+ {
+ gsi = gsi_for_stmt (op1def);
+ gsi_insert_after (&gsi, sum, GSI_NEW_STMT);
+ }
+ else
+ {
+ edge e;
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (e, ei, gimple_bb (op1def)->succs)
+ if (e->flags & EDGE_FALLTHRU)
+ gsi_insert_on_edge_immediate (e, sum);
+ }
+ }
+ }
+ update_stmt (sum);
+
+ return sum;
+}
+
+/* Perform un-distribution of divisions and multiplications.
+ A * X + B * X is transformed into (A + B) * X and A / X + B / X
+ to (A + B) / X for real X.
+
+ The algorithm is organized as follows.
+
+ - First we walk the addition chain *OPS looking for summands that
+ are defined by a multiplication or a real division. This results
+ in the candidates bitmap with relevant indices into *OPS.
+
+ - Second we build the chains of multiplications or divisions for
+ these candidates, counting the number of occurences of (operand, code)
+ pairs in all of the candidates chains.
+
+ - Third we sort the (operand, code) pairs by number of occurence and
+ process them starting with the pair with the most uses.
+
+ * For each such pair we walk the candidates again to build a
+ second candidate bitmap noting all multiplication/division chains
+ that have at least one occurence of (operand, code).
+
+ * We build an alternate addition chain only covering these
+ candidates with one (operand, code) operation removed from their
+ multiplication/division chain.
+
+ * The first candidate gets replaced by the alternate addition chain
+ multiplied/divided by the operand.
+
+ * All candidate chains get disabled for further processing and
+ processing of (operand, code) pairs continues.
+
+ The alternate addition chains built are re-processed by the main
+ reassociation algorithm which allows optimizing a * x * y + b * y * x
+ to (a + b ) * x * y in one invocation of the reassociation pass. */
+
+static bool
+undistribute_ops_list (enum tree_code opcode,
+ VEC (operand_entry_t, heap) **ops, struct loop *loop)
+{
+ unsigned int length = VEC_length (operand_entry_t, *ops);
+ operand_entry_t oe1;
+ unsigned i, j;
+ sbitmap candidates, candidates2;
+ unsigned nr_candidates, nr_candidates2;
+ sbitmap_iterator sbi0;
+ VEC (operand_entry_t, heap) **subops;
+ htab_t ctable;
+ bool changed = false;
+
+ if (length <= 1
+ || opcode != PLUS_EXPR)
+ return false;
+
+ /* Build a list of candidates to process. */
+ candidates = sbitmap_alloc (length);
+ sbitmap_zero (candidates);
+ nr_candidates = 0;
+ for (i = 0; VEC_iterate (operand_entry_t, *ops, i, oe1); ++i)
+ {
+ enum tree_code dcode;
+ gimple oe1def;
+
+ if (TREE_CODE (oe1->op) != SSA_NAME)
+ continue;
+ oe1def = SSA_NAME_DEF_STMT (oe1->op);
+ if (!is_gimple_assign (oe1def))
+ continue;
+ dcode = gimple_assign_rhs_code (oe1def);
+ if ((dcode != MULT_EXPR
+ && dcode != RDIV_EXPR)
+ || !is_reassociable_op (oe1def, dcode, loop))
+ continue;
+
+ SET_BIT (candidates, i);
+ nr_candidates++;
+ }
+
+ if (nr_candidates < 2)
+ {
+ sbitmap_free (candidates);
+ return false;
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "searching for un-distribute opportunities ");
+ print_generic_expr (dump_file,
+ VEC_index (operand_entry_t, *ops,
+ sbitmap_first_set_bit (candidates))->op, 0);
+ fprintf (dump_file, " %d\n", nr_candidates);
+ }
+
+ /* Build linearized sub-operand lists and the counting table. */
+ cvec = NULL;
+ ctable = htab_create (15, oecount_hash, oecount_eq, NULL);
+ subops = XCNEWVEC (VEC (operand_entry_t, heap) *,
+ VEC_length (operand_entry_t, *ops));
+ EXECUTE_IF_SET_IN_SBITMAP (candidates, 0, i, sbi0)
+ {
+ gimple oedef;
+ enum tree_code oecode;
+ unsigned j;
+
+ oedef = SSA_NAME_DEF_STMT (VEC_index (operand_entry_t, *ops, i)->op);
+ oecode = gimple_assign_rhs_code (oedef);
+ linearize_expr_tree (&subops[i], oedef,
+ associative_tree_code (oecode), false);
+
+ for (j = 0; VEC_iterate (operand_entry_t, subops[i], j, oe1); ++j)
+ {
+ oecount c;
+ void **slot;
+ size_t idx;
+ c.oecode = oecode;
+ c.cnt = 1;
+ c.op = oe1->op;
+ VEC_safe_push (oecount, heap, cvec, &c);
+ idx = VEC_length (oecount, cvec) + 41;
+ slot = htab_find_slot (ctable, (void *)idx, INSERT);
+ if (!*slot)
+ {
+ *slot = (void *)idx;
+ }
+ else
+ {
+ VEC_pop (oecount, cvec);
+ VEC_index (oecount, cvec, (size_t)*slot - 42)->cnt++;
+ }
+ }
+ }
+ htab_delete (ctable);
+
+ /* Sort the counting table. */
+ qsort (VEC_address (oecount, cvec), VEC_length (oecount, cvec),
+ sizeof (oecount), oecount_cmp);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ oecount *c;
+ fprintf (dump_file, "Candidates:\n");
+ for (j = 0; VEC_iterate (oecount, cvec, j, c); ++j)
+ {
+ fprintf (dump_file, " %u %s: ", c->cnt,
+ c->oecode == MULT_EXPR
+ ? "*" : c->oecode == RDIV_EXPR ? "/" : "?");
+ print_generic_expr (dump_file, c->op, 0);
+ fprintf (dump_file, "\n");
+ }
+ }
+
+ /* Process the (operand, code) pairs in order of most occurence. */
+ candidates2 = sbitmap_alloc (length);
+ while (!VEC_empty (oecount, cvec))
+ {
+ oecount *c = VEC_last (oecount, cvec);
+ if (c->cnt < 2)
+ break;
+
+ /* Now collect the operands in the outer chain that contain
+ the common operand in their inner chain. */
+ sbitmap_zero (candidates2);
+ nr_candidates2 = 0;
+ EXECUTE_IF_SET_IN_SBITMAP (candidates, 0, i, sbi0)
+ {
+ gimple oedef;
+ enum tree_code oecode;
+ unsigned j;
+ tree op = VEC_index (operand_entry_t, *ops, i)->op;
+
+ /* If we undistributed in this chain already this may be
+ a constant. */
+ if (TREE_CODE (op) != SSA_NAME)
+ continue;
+
+ oedef = SSA_NAME_DEF_STMT (op);
+ oecode = gimple_assign_rhs_code (oedef);
+ if (oecode != c->oecode)
+ continue;
+
+ for (j = 0; VEC_iterate (operand_entry_t, subops[i], j, oe1); ++j)
+ {
+ if (oe1->op == c->op)
+ {
+ SET_BIT (candidates2, i);
+ ++nr_candidates2;
+ break;
+ }
+ }
+ }
+
+ if (nr_candidates2 >= 2)
+ {
+ operand_entry_t oe1, oe2;
+ tree tmpvar;
+ gimple prod;
+ int first = sbitmap_first_set_bit (candidates2);
+
+ /* Build the new addition chain. */
+ oe1 = VEC_index (operand_entry_t, *ops, first);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Building (");
+ print_generic_expr (dump_file, oe1->op, 0);
+ }
+ tmpvar = create_tmp_var (TREE_TYPE (oe1->op), NULL);
+ add_referenced_var (tmpvar);
+ zero_one_operation (&oe1->op, c->oecode, c->op);
+ EXECUTE_IF_SET_IN_SBITMAP (candidates2, first+1, i, sbi0)
+ {
+ gimple sum;
+ oe2 = VEC_index (operand_entry_t, *ops, i);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " + ");
+ print_generic_expr (dump_file, oe2->op, 0);
+ }
+ zero_one_operation (&oe2->op, c->oecode, c->op);
+ sum = build_and_add_sum (tmpvar, oe1->op, oe2->op, opcode);
+ oe2->op = fold_convert (TREE_TYPE (oe2->op), integer_zero_node);
+ oe2->rank = 0;
+ oe1->op = gimple_get_lhs (sum);
+ }
+
+ /* Apply the multiplication/division. */
+ prod = build_and_add_sum (tmpvar, oe1->op, c->op, c->oecode);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, ") %s ", c->oecode == MULT_EXPR ? "*" : "/");
+ print_generic_expr (dump_file, c->op, 0);
+ fprintf (dump_file, "\n");
+ }
+
+ /* Record it in the addition chain and disable further
+ undistribution with this op. */
+ oe1->op = gimple_assign_lhs (prod);
+ oe1->rank = get_rank (oe1->op);
+ VEC_free (operand_entry_t, heap, subops[first]);
+
+ changed = true;
+ }
+
+ VEC_pop (oecount, cvec);
+ }
+
+ for (i = 0; i < VEC_length (operand_entry_t, *ops); ++i)
+ VEC_free (operand_entry_t, heap, subops[i]);
+ free (subops);
+ VEC_free (oecount, heap, cvec);
+ sbitmap_free (candidates);
+ sbitmap_free (candidates2);
+
+ return changed;
+}
+
+
/* Perform various identities and other optimizations on the list of
operand entries, stored in OPS. The tree code for the binary
operation between all the operands is OPCODE. */
return false;
}
+/* Remove def stmt of VAR if VAR has zero uses and recurse
+ on rhs1 operand if so. */
+
+static void
+remove_visited_stmt_chain (tree var)
+{
+ gimple stmt;
+ gimple_stmt_iterator gsi;
+
+ while (1)
+ {
+ if (TREE_CODE (var) != SSA_NAME || !has_zero_uses (var))
+ return;
+ stmt = SSA_NAME_DEF_STMT (var);
+ if (!is_gimple_assign (stmt)
+ || !gimple_visited_p (stmt))
+ return;
+ var = gimple_assign_rhs1 (stmt);
+ gsi = gsi_for_stmt (stmt);
+ gsi_remove (&gsi, true);
+ release_defs (stmt);
+ }
+}
+
/* Recursively rewrite our linearized statements so that the operators
match those in OPS[OPINDEX], putting the computation in rank
order. */
static void
rewrite_expr_tree (gimple stmt, unsigned int opindex,
- VEC(operand_entry_t, heap) * ops)
+ VEC(operand_entry_t, heap) * ops, bool moved)
{
tree rhs1 = gimple_assign_rhs1 (stmt);
tree rhs2 = gimple_assign_rhs2 (stmt);
gimple_assign_set_rhs1 (stmt, oe1->op);
gimple_assign_set_rhs2 (stmt, oe2->op);
update_stmt (stmt);
+ if (rhs1 != oe1->op && rhs1 != oe2->op)
+ remove_visited_stmt_chain (rhs1);
if (dump_file && (dump_flags & TDF_DETAILS))
{
if (oe->op != rhs2)
{
+ if (!moved)
+ {
+ gimple_stmt_iterator gsinow, gsirhs1;
+ gimple stmt1 = stmt, stmt2;
+ unsigned int count;
+
+ gsinow = gsi_for_stmt (stmt);
+ count = VEC_length (operand_entry_t, ops) - opindex - 2;
+ while (count-- != 0)
+ {
+ stmt2 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt1));
+ gsirhs1 = gsi_for_stmt (stmt2);
+ gsi_move_before (&gsirhs1, &gsinow);
+ gsi_prev (&gsinow);
+ stmt1 = stmt2;
+ }
+ moved = true;
+ }
if (dump_file && (dump_flags & TDF_DETAILS))
{
}
/* Recurse on the LHS of the binary operator, which is guaranteed to
be the non-leaf side. */
- rewrite_expr_tree (SSA_NAME_DEF_STMT (rhs1), opindex + 1, ops);
+ rewrite_expr_tree (SSA_NAME_DEF_STMT (rhs1), opindex + 1, ops, moved);
}
/* Transform STMT, which is really (A +B) + (C + D) into the left
if (TREE_CODE (lhs) == SSA_NAME
&& (immusestmt = get_single_immediate_use (lhs))
&& is_gimple_assign (immusestmt)
- && gimple_assign_rhs_code (immusestmt) == PLUS_EXPR)
+ && (gimple_assign_rhs_code (immusestmt) == PLUS_EXPR
+ || gimple_assign_rhs_code (immusestmt) == MULT_EXPR))
return true;
return false;
}
Place the operands of the expression tree in the vector named OPS. */
static void
-linearize_expr_tree (VEC(operand_entry_t, heap) **ops, gimple stmt)
+linearize_expr_tree (VEC(operand_entry_t, heap) **ops, gimple stmt,
+ bool is_associative, bool set_visited)
{
- gimple_stmt_iterator gsinow, gsilhs;
tree binlhs = gimple_assign_rhs1 (stmt);
tree binrhs = gimple_assign_rhs2 (stmt);
gimple binlhsdef, binrhsdef;
enum tree_code rhscode = gimple_assign_rhs_code (stmt);
struct loop *loop = loop_containing_stmt (stmt);
- gimple_set_visited (stmt, true);
+ if (set_visited)
+ gimple_set_visited (stmt, true);
if (TREE_CODE (binlhs) == SSA_NAME)
{
{
tree temp;
+ /* If this is not a associative operation like division, give up. */
+ if (!is_associative)
+ {
+ add_to_ops_vec (ops, binrhs);
+ return;
+ }
+
if (!binrhsisreassoc)
{
add_to_ops_vec (ops, binrhs);
gcc_assert (TREE_CODE (binrhs) != SSA_NAME
|| !is_reassociable_op (SSA_NAME_DEF_STMT (binrhs),
rhscode, loop));
- gsinow = gsi_for_stmt (stmt);
- gsilhs = gsi_for_stmt (SSA_NAME_DEF_STMT (binlhs));
- gsi_move_before (&gsilhs, &gsinow);
- linearize_expr_tree (ops, SSA_NAME_DEF_STMT (binlhs));
+ linearize_expr_tree (ops, SSA_NAME_DEF_STMT (binlhs),
+ is_associative, set_visited);
add_to_ops_vec (ops, binrhs);
}
/* If this was part of an already processed statement,
we don't need to touch it again. */
if (gimple_visited_p (stmt))
- continue;
+ {
+ /* This statement might have become dead because of previous
+ reassociations. */
+ if (has_zero_uses (gimple_get_lhs (stmt)))
+ {
+ gsi_remove (&gsi, true);
+ release_defs (stmt);
+ /* We might end up removing the last stmt above which
+ places the iterator to the end of the sequence.
+ Reset it to the last stmt in this case which might
+ be the end of the sequence as well if we removed
+ the last statement of the sequence. In which case
+ we need to bail out. */
+ if (gsi_end_p (gsi))
+ {
+ gsi = gsi_last_bb (bb);
+ if (gsi_end_p (gsi))
+ break;
+ }
+ }
+ continue;
+ }
lhs = gimple_assign_lhs (stmt);
rhs1 = gimple_assign_rhs1 (stmt);
continue;
gimple_set_visited (stmt, true);
- linearize_expr_tree (&ops, stmt);
+ linearize_expr_tree (&ops, stmt, true, true);
qsort (VEC_address (operand_entry_t, ops),
VEC_length (operand_entry_t, ops),
sizeof (operand_entry_t),
sort_by_operand_rank);
optimize_ops_list (rhs_code, &ops);
+ if (undistribute_ops_list (rhs_code, &ops,
+ loop_containing_stmt (stmt)))
+ {
+ qsort (VEC_address (operand_entry_t, ops),
+ VEC_length (operand_entry_t, ops),
+ sizeof (operand_entry_t),
+ sort_by_operand_rank);
+ optimize_ops_list (rhs_code, &ops);
+ }
if (VEC_length (operand_entry_t, ops) == 1)
{
fprintf (dump_file, "Transforming ");
print_gimple_stmt (dump_file, stmt, 0, 0);
}
-
+
+ rhs1 = gimple_assign_rhs1 (stmt);
gimple_assign_set_rhs_from_tree (&gsi,
VEC_last (operand_entry_t,
ops)->op);
update_stmt (stmt);
+ remove_visited_stmt_chain (rhs1);
if (dump_file && (dump_flags & TDF_DETAILS))
{
}
}
else
- {
- rewrite_expr_tree (stmt, 0, ops);
- }
+ rewrite_expr_tree (stmt, 0, ops, false);
VEC_free (operand_entry_t, heap, ops);
}
NULL, /* next */
0, /* static_pass_number */
TV_TREE_REASSOC, /* tv_id */
- PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
+ PROP_cfg | PROP_ssa, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
OSDN Git Service
