diff options
author | eraman <eraman@138bc75d-0d04-0410-961f-82ee72b054a4> | 2013-05-18 01:35:04 +0000 |
---|---|---|
committer | eraman <eraman@138bc75d-0d04-0410-961f-82ee72b054a4> | 2013-05-18 01:35:04 +0000 |
commit | a2bd0c99b983cc804fca616eea3408b17426c978 (patch) | |
tree | 0ab6c75725936898fe585bb03325c1060de6e24e | |
parent | e1a95a30baafa57b2037ed762b93317cfdd6ddd6 (diff) | |
download | gcc-a2bd0c99b983cc804fca616eea3408b17426c978.tar.gz |
2013-05-17 Easwaran Raman <eraman@google.com>
* tree-ssa-reassoc.c (find_insert_point): New function.
(insert_stmt_after): Likewise.
(get_def_stmt): Likewise.
(ensure_ops_are_available): Likewise.
(not_dominated_by): Likewise.
(rewrite_expr_tree): Do not move statements beyond what is
necessary. Remove call to swap_ops_for_binary_stmt...
(reassociate_bb): ... and move it here.
(build_and_add_sum): Assign UIDs for new statements.
(linearize_expr): Likewise.
(do_reassoc): Renumber gimple statement UIDs.
testsuite/ChangeLog:
2013-05-17 Easwaran Raman <eraman@google.com>
* gcc.dg/tree-ssa/reassoc-28.c: New testcase.
git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@199048 138bc75d-0d04-0410-961f-82ee72b054a4
-rw-r--r-- | gcc/ChangeLog | 15 | ||||
-rw-r--r-- | gcc/testsuite/ChangeLog | 4 | ||||
-rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/reassoc-28.c | 37 | ||||
-rw-r--r-- | gcc/tree-ssa-reassoc.c | 167 |
4 files changed, 203 insertions, 20 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 5cc09ae4ddd..4536e6279a1 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,17 @@ +2013-05-17 Easwaran Raman <eraman@google.com> + + * tree-ssa-reassoc.c (find_insert_point): New function. + (insert_stmt_after): Likewise. + (get_def_stmt): Likewise. + (ensure_ops_are_available): Likewise. + (not_dominated_by): Likewise. + (rewrite_expr_tree): Do not move statements beyond what is + necessary. Remove call to swap_ops_for_binary_stmt... + (reassociate_bb): ... and move it here. + (build_and_add_sum): Assign UIDs for new statements. + (linearize_expr): Likewise. + (do_reassoc): Renumber gimple statement UIDs. + 2013-05-17 Jan Hubicka <jh@suse.cz> * lto-symtab.c (lto_symtab_merge_cgraph_nodes): Resolve cross module @@ -156,6 +170,7 @@ * Makefile.in (tree-switch-conversion.o): Depend on $(OPTABS_H). +>>>>>>> .r199043 2013-05-16 Uros Bizjak <ubizjak@gmail.com> * config/i386/driver-i386.c (host_detect_local_cpu): Determine diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index ec5cbde7329..6fd1b2ed3a6 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2013-05-17 Easwaran Raman <eraman@google.com> + + * gcc.dg/tree-ssa/reassoc-28.c: New testcase. + 2013-05-17 Marc Glisse <marc.glisse@inria.fr> PR testsuite/57313 diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-28.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-28.c new file mode 100644 index 00000000000..3d10b49ccaf --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-28.c @@ -0,0 +1,37 @@ +/* { dg-do run} */ +/* { dg-options "-O2 -fdump-tree-reassoc1-details" } */ + +#define LENGTH 4 +void abort (void); +unsigned +__attribute__ ((noinline)) foo (unsigned char *buf, int n) +{ + unsigned sum = 0, i = 0; + do { + sum +=(buf)[n-1]; + /* Split the BB to test statements are correctly moved to + satisfy dependences. */ + if (n > LENGTH) + i++; + sum += buf[n-2]; + sum += buf[n-3]; + sum += buf[n-4]; + n = n-4; + } while (n > 0); + + return sum + i; +} + +unsigned char a[] = {1, 1, 1, 1}; + +int main() { + int sum = foo (a, LENGTH); + if (sum != 4) + abort (); + return 0; +} + +/* Verify one stmt has been moved to another BB to ensure correct dependences. */ +/* { dg-final { scan-tree-dump-times "to a different BB" 1 "reassoc1"} }*/ +/* { dg-final { scan-tree-dump-times "within same BB" 2 "reassoc1"} }*/ +/* { dg-final { cleanup-tree-dump "reassoc1" } } */ diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c index 4fc19cb551e..29c9dff2868 100644 --- a/gcc/tree-ssa-reassoc.c +++ b/gcc/tree-ssa-reassoc.c @@ -1166,6 +1166,7 @@ build_and_add_sum (tree type, tree op1, tree op2, enum tree_code opcode) && (!op2def || gimple_nop_p (op2def))) { gsi = gsi_after_labels (single_succ (ENTRY_BLOCK_PTR)); + gimple_set_uid (sum, gimple_uid (gsi_stmt (gsi))); gsi_insert_before (&gsi, sum, GSI_NEW_STMT); } else if ((!op1def || gimple_nop_p (op1def)) @@ -1175,6 +1176,7 @@ build_and_add_sum (tree type, tree op1, tree op2, enum tree_code opcode) if (gimple_code (op2def) == GIMPLE_PHI) { gsi = gsi_after_labels (gimple_bb (op2def)); + gimple_set_uid (sum, gimple_uid (gsi_stmt (gsi))); gsi_insert_before (&gsi, sum, GSI_NEW_STMT); } else @@ -1182,6 +1184,7 @@ build_and_add_sum (tree type, tree op1, tree op2, enum tree_code opcode) if (!stmt_ends_bb_p (op2def)) { gsi = gsi_for_stmt (op2def); + gimple_set_uid (sum, gimple_uid (op2def)); gsi_insert_after (&gsi, sum, GSI_NEW_STMT); } else @@ -1200,6 +1203,7 @@ build_and_add_sum (tree type, tree op1, tree op2, enum tree_code opcode) if (gimple_code (op1def) == GIMPLE_PHI) { gsi = gsi_after_labels (gimple_bb (op1def)); + gimple_set_uid (sum, gimple_uid (op1def)); gsi_insert_before (&gsi, sum, GSI_NEW_STMT); } else @@ -1207,6 +1211,7 @@ build_and_add_sum (tree type, tree op1, tree op2, enum tree_code opcode) if (!stmt_ends_bb_p (op1def)) { gsi = gsi_for_stmt (op1def); + gimple_set_uid (sum, gimple_uid (op1def)); gsi_insert_after (&gsi, sum, GSI_NEW_STMT); } else @@ -2841,6 +2846,135 @@ swap_ops_for_binary_stmt (vec<operand_entry_t> ops, } } +/* Determine if stmt A is not dominated by stmt B. If A and B are in + same basic block, then A's UID has to be less than B. If they are + in different BB's, then A's BB must not be dominated by B's BB. */ + +static inline bool +not_dominated_by (gimple a, gimple b) +{ + basic_block bb_a, bb_b; + bb_a = gimple_bb (a); + bb_b = gimple_bb (b); + return ((bb_a == bb_b && gimple_uid (a) < gimple_uid (b)) + || (bb_a != bb_b + && !dominated_by_p (CDI_DOMINATORS, bb_a, bb_b))); + +} + +/* Find the statement after which STMT must be moved so that the + dependency from DEP_STMT to STMT is maintained. */ + +static gimple +find_insert_point (gimple stmt, gimple dep_stmt) +{ + gimple insert_stmt = stmt; + if (dep_stmt == NULL) + return stmt; + if (not_dominated_by (insert_stmt, dep_stmt)) + insert_stmt = dep_stmt; + return insert_stmt; +} + +/* Insert STMT after INSERT_POINT. */ + +static void +insert_stmt_after (gimple stmt, gimple insert_point) +{ + imm_use_iterator iter; + tree lhs; + gimple use_stmt; + gimple_stmt_iterator gsistmt = gsi_for_stmt (stmt), gsi_insert; + basic_block insert_bb = gimple_bb (insert_point); + bool insert_bb_different = (insert_bb != gimple_bb (stmt)); + lhs = gimple_assign_lhs (stmt); + /* If there are any debug uses of LHS, reset them. */ + FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs) + { + if (is_gimple_debug (use_stmt) + && not_dominated_by (use_stmt, insert_point)) + { + gimple_debug_bind_reset_value (use_stmt); + update_stmt (use_stmt); + } + } + /* If INSERT_STMT is a phi node, then do not insert just after that statement. + Instead, find the first non-label gimple statement in BB and insert before + that. */ + if (gimple_code (insert_point) == GIMPLE_PHI) + { + gsi_insert = gsi_after_labels (insert_bb); + gsi_move_before (&gsistmt, &gsi_insert); + } + /* Statements marked for throw can not be in the middle of a basic block. So + we can not insert a statement (not marked for throw) immediately after. */ + else if (stmt_ends_bb_p (insert_point)) + { + edge succ_edge = find_fallthru_edge (insert_bb->succs); + insert_bb = succ_edge->dest; + insert_bb_different = (insert_bb != gimple_bb (stmt)); + /* Insert STMT at the beginning of the successor basic block. */ + gsi_insert = gsi_after_labels (insert_bb); + gsi_move_before (&gsistmt, &gsi_insert); + } + else + { + gsi_insert = gsi_for_stmt (insert_point); + gsi_move_after (&gsistmt, &gsi_insert); + } + /* Set the UID of STMT to that of INSERT_POINT so that subsequent comparisons + of UIDs to determine dominance within a basic block works. */ + gimple_set_uid (stmt, gimple_uid (insert_point)); + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Moved stmt "); + print_gimple_stmt (dump_file, stmt, 0, 0); + fprintf (dump_file, " %s to satisfy dependences\n", + insert_bb_different ? "to a different BB" : "within same BB"); + } + +} + +/* If OP is a SSA variable and is not the default definition, return the + gimple statement that defines OP. Else return NULL. */ + +static inline gimple +get_def_stmt (tree op) +{ + if (TREE_CODE (op) == SSA_NAME + && !SSA_NAME_IS_DEFAULT_DEF (op)) + return SSA_NAME_DEF_STMT (op); + else + return NULL; +} + +/* Ensure that operands in the OPS vector are available for STMT and all + gimple statements on which STMT depends. */ + +static void +ensure_ops_are_available (gimple stmt, vec<operand_entry_t> ops, int opindex) +{ + unsigned int len = ops.length (); + gimple insert_stmt = stmt; + gimple dep_stmts[2]; + dep_stmts[0] = get_def_stmt (ops[opindex]->op); + if (len - opindex == 2) + { + dep_stmts[1] = get_def_stmt (ops[opindex + 1]->op); + } + else + { + gimple stmt1 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt)); + ensure_ops_are_available (stmt1, ops, opindex + 1); + dep_stmts[1] = stmt1; + } + for (int i = 0; i < 2; i++) + insert_stmt = find_insert_point (insert_stmt, dep_stmts[i]); + + if (insert_stmt != stmt) + insert_stmt_after (stmt, insert_stmt); +} + /* Recursively rewrite our linearized statements so that the operators match those in OPS[OPINDEX], putting the computation in rank order. */ @@ -2853,11 +2987,6 @@ rewrite_expr_tree (gimple stmt, unsigned int opindex, tree rhs2 = gimple_assign_rhs2 (stmt); operand_entry_t oe; - /* If we have three operands left, then we want to make sure the ones - that get the double binary op are chosen wisely. */ - if (opindex + 3 == ops.length ()) - swap_ops_for_binary_stmt (ops, opindex, stmt); - /* The final recursion case for this function is that you have exactly two operations left. If we had one exactly one op in the entire list to start with, we @@ -2903,20 +3032,7 @@ rewrite_expr_tree (gimple stmt, unsigned int opindex, { if (!moved) { - gimple_stmt_iterator gsinow, gsirhs1; - gimple stmt1 = stmt, stmt2; - unsigned int count; - - gsinow = gsi_for_stmt (stmt); - count = ops.length () - 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; - } + ensure_ops_are_available (stmt, ops, opindex); moved = true; } @@ -3128,6 +3244,7 @@ linearize_expr (gimple stmt) gsinow = gsi_for_stmt (stmt); gsirhs = gsi_for_stmt (binrhs); gsi_move_before (&gsirhs, &gsinow); + gimple_set_uid (binrhs, gimple_uid (stmt)); gimple_assign_set_rhs2 (stmt, gimple_assign_rhs1 (binrhs)); gimple_assign_set_rhs1 (binrhs, gimple_assign_lhs (binlhs)); @@ -4134,7 +4251,16 @@ reassociate_bb (basic_block bb) && ops.length () > 3) rewrite_expr_tree_parallel (stmt, width, ops); else - rewrite_expr_tree (stmt, 0, ops, false); + { + /* When there are three operands left, we want + to make sure the ones that get the double + binary op are chosen wisely. */ + int len = ops.length (); + if (len >= 3) + swap_ops_for_binary_stmt (ops, len - 3, stmt); + + rewrite_expr_tree (stmt, 0, ops, false); + } /* If we combined some repeated factors into a __builtin_powi call, multiply that result by the @@ -4195,6 +4321,7 @@ static void do_reassoc (void) { break_up_subtract_bb (ENTRY_BLOCK_PTR); + renumber_gimple_stmt_uids (); reassociate_bb (EXIT_BLOCK_PTR); } |