diff options
Diffstat (limited to 'gcc/tree-ssa-math-opts.c')
-rw-r--r-- | gcc/tree-ssa-math-opts.c | 481 |
1 files changed, 397 insertions, 84 deletions
diff --git a/gcc/tree-ssa-math-opts.c b/gcc/tree-ssa-math-opts.c index 456043fc3f4..825c0bdec61 100644 --- a/gcc/tree-ssa-math-opts.c +++ b/gcc/tree-ssa-math-opts.c @@ -35,7 +35,55 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA z = z * rmodulus; We do this for loop invariant divisors, and with this pass whenever - we notice that a division has the same divisor multiple times. */ + we notice that a division has the same divisor multiple times. + + Of course, like in PRE, we don't insert a division if a dominator + already has one. However, this cannot be done as an extension of + PRE for several reasons. + + First of all, with some experiments it was found out that the + transformation is not always useful if there are only two divisions + hy the same divisor. This is probably because modern processors + can pipeline the divisions; on older, in-order processors it should + still be effective to optimize two divisions by the same number. + We make this a param, and it shall be called N in the remainder of + this comment. + + Second, if trapping math is active, we have less freedom on where + to insert divisions: we can only do so in basic blocks that already + contain one. (If divisions don't trap, instead, we can insert + divisions elsewhere, which will be in blocks that are common dominators + of those that have the division). + + We really don't want to compute the reciprocal unless a division will + be found. To do this, we won't insert the division in a basic block + that has less than N divisions *post-dominating* it. + + The algorithm constructs a subset of the dominator tree, holding the + blocks containing the divisions and the common dominators to them, + and walk it twice. The first walk is in post-order, and it annotates + each block with the number of divisions that post-dominate it: this + gives information on where divisions can be inserted profitably. + The second walk is in pre-order, and it inserts divisions as explained + above, and replaces divisions by multiplications. + + In the best case, the cost of the pass is O(n_statements). In the + worst-case, the cost is due to creating the dominator tree subset, + with a cost of O(n_basic_blocks ^ 2); however this can only happen + for n_statements / n_basic_blocks statements. So, the amortized cost + of creating the dominator tree subset is O(n_basic_blocks) and the + worst-case cost of the pass is O(n_statements * n_basic_blocks). + + More practically, the cost will be small because there are few + divisions, and they tend to be in the same basic block, so insert_bb + is called very few times. + + If we did this using domwalk.c, an efficient implementation would have + to work on all the variables in a single pass, because we could not + work on just a subset of the dominator tree, as we do now, and the + cost would also be something like O(n_statements * n_basic_blocks). + The data structures would be more complex in order to work on all the + variables in a single pass. */ #include "config.h" #include "system.h" @@ -47,142 +95,407 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA #include "real.h" #include "timevar.h" #include "tree-pass.h" +#include "alloc-pool.h" +#include "basic-block.h" +#include "target.h" -static bool -gate_cse_reciprocals (void) + +/* This structure represents one basic block that either computes a + division, or is a common dominator for basic block that compute a + division. */ +struct occurrence { + /* The basic block represented by this structure. */ + basic_block bb; + + /* If non-NULL, the SSA_NAME holding the definition for a reciprocal + inserted in BB. */ + tree recip_def; + + /* If non-NULL, the MODIFY_EXPR for a reciprocal computation that + was inserted in BB. */ + tree recip_def_stmt; + + /* Pointer to a list of "struct occurrence"s for blocks dominated + by BB. */ + struct occurrence *children; + + /* Pointer to the next "struct occurrence"s in the list of blocks + sharing a common dominator. */ + struct occurrence *next; + + /* The number of divisions that are in BB before compute_merit. The + number of divisions that are in BB or post-dominate it after + compute_merit. */ + int num_divisions; + + /* True if the basic block has a division, false if it is a common + dominator for basic blocks that do. If it is false and trapping + math is active, BB is not a candidate for inserting a reciprocal. */ + bool bb_has_division; +}; + + +/* The instance of "struct occurrence" representing the highest + interesting block in the dominator tree. */ +static struct occurrence *occ_head; + +/* Allocation pool for getting instances of "struct occurrence". */ +static alloc_pool occ_pool; + + + +/* Allocate and return a new struct occurrence for basic block BB, and + whose children list is headed by CHILDREN. */ +static struct occurrence * +occ_new (basic_block bb, struct occurrence *children) { - return optimize && !optimize_size && flag_unsafe_math_optimizations; + struct occurrence *occ; + + occ = bb->aux = pool_alloc (occ_pool); + memset (occ, 0, sizeof (struct occurrence)); + + occ->bb = bb; + occ->children = children; + return occ; } -/* Where to put the statement computing a reciprocal. */ -enum place_reciprocal + +/* Insert NEW_OCC into our subset of the dominator tree. P_HEAD points to a + list of "struct occurrence"s, one per basic block, having IDOM as + their common dominator. + + We try to insert NEW_OCC as deep as possible in the tree, and we also + insert any other block that is a common dominator for BB and one + block already in the tree. */ + +static void +insert_bb (struct occurrence *new_occ, basic_block idom, + struct occurrence **p_head) { - PR_BEFORE_BSI, /* Put it using bsi_insert_before. */ - PR_AFTER_BSI, /* Put it using bsi_insert_after. */ - PR_ON_ENTRY_EDGE /* Put it on the edge between the entry - and the first basic block. */ -}; + struct occurrence *occ, **p_occ; -/* Check if DEF's uses include more than one floating-point division, - and if so replace them by multiplications with the reciprocal. Add - the statement computing the reciprocal according to WHERE. + for (p_occ = p_head; (occ = *p_occ) != NULL; ) + { + basic_block bb = new_occ->bb, occ_bb = occ->bb; + basic_block dom = nearest_common_dominator (CDI_DOMINATORS, occ_bb, bb); + if (dom == bb) + { + /* BB dominates OCC_BB. OCC becomes NEW_OCC's child: remove OCC + from its list. */ + *p_occ = occ->next; + occ->next = new_occ->children; + new_occ->children = occ; + + /* Try the next block (it may as well be dominated by BB). */ + } + + else if (dom == occ_bb) + { + /* OCC_BB dominates BB. Tail recurse to look deeper. */ + insert_bb (new_occ, dom, &occ->children); + return; + } + + else if (dom != idom) + { + gcc_assert (!dom->aux); + + /* There is a dominator between IDOM and BB, add it and make + two children out of NEW_OCC and OCC. First, remove OCC from + its list. */ + *p_occ = occ->next; + new_occ->next = occ; + occ->next = NULL; + + /* None of the previous blocks has DOM as a dominator: if we tail + recursed, we would reexamine them uselessly. Just switch BB with + DOM, and go on looking for blocks dominated by DOM. */ + new_occ = occ_new (dom, new_occ); + } + + else + { + /* Nothing special, go on with the next element. */ + p_occ = &occ->next; + } + } + + /* No place was found as a child of IDOM. Make BB a sibling of IDOM. */ + new_occ->next = *p_head; + *p_head = new_occ; +} + +/* Register that we found a division in BB. */ + +static inline void +register_division_in (basic_block bb) +{ + struct occurrence *occ; + + occ = (struct occurrence *) bb->aux; + if (!occ) + { + occ = occ_new (bb, NULL); + insert_bb (occ, ENTRY_BLOCK_PTR, &occ_head); + } + + occ->bb_has_division = true; + occ->num_divisions++; +} + + +/* Compute the number of divisions that postdominate each block in OCC and + its children. */ - Does not check the type of DEF, nor that DEF is a GIMPLE register. - This is done in the caller for speed, because otherwise this routine - would be called for every definition and phi node. */ static void -execute_cse_reciprocals_1 (block_stmt_iterator *bsi, tree def, - enum place_reciprocal where) +compute_merit (struct occurrence *occ) { - use_operand_p use_p; - imm_use_iterator use_iter; - tree t, new_stmt, type; - int count = 0; - bool ok = !flag_trapping_math; + struct occurrence *occ_child; + basic_block dom = occ->bb; - /* Find uses. */ - FOR_EACH_IMM_USE_FAST (use_p, use_iter, def) + for (occ_child = occ->children; occ_child; occ_child = occ_child->next) { - tree use_stmt = USE_STMT (use_p); - if (TREE_CODE (use_stmt) == MODIFY_EXPR - && TREE_CODE (TREE_OPERAND (use_stmt, 1)) == RDIV_EXPR - && TREE_OPERAND (TREE_OPERAND (use_stmt, 1), 1) == def) + basic_block bb; + if (occ_child->children) + compute_merit (occ_child); + + if (flag_exceptions) + bb = single_noncomplex_succ (dom); + else + bb = dom; + + if (dominated_by_p (CDI_POST_DOMINATORS, bb, occ_child->bb)) + occ->num_divisions += occ_child->num_divisions; + } +} + + +/* Return whether USE_STMT is a floating-point division by DEF. */ +static inline bool +is_division_by (tree use_stmt, tree def) +{ + return TREE_CODE (use_stmt) == MODIFY_EXPR + && TREE_CODE (TREE_OPERAND (use_stmt, 1)) == RDIV_EXPR + && TREE_OPERAND (TREE_OPERAND (use_stmt, 1), 1) == def; +} + +/* Walk the subset of the dominator tree rooted at OCC, setting the + RECIP_DEF field to a definition of 1.0 / DEF that can be used in + the given basic block. The field may be left NULL, of course, + if it is not possible or profitable to do the optimization. + + DEF_BSI is an iterator pointing at the statement defining DEF. + If RECIP_DEF is set, a dominator already has a computation that can + be used. */ + +static void +insert_reciprocals (block_stmt_iterator *def_bsi, struct occurrence *occ, + tree def, tree recip_def, int threshold) +{ + tree type, new_stmt; + block_stmt_iterator bsi; + struct occurrence *occ_child; + + if (!recip_def + && (occ->bb_has_division || !flag_trapping_math) + && occ->num_divisions >= threshold) + { + /* Make a variable with the replacement and substitute it. */ + type = TREE_TYPE (def); + recip_def = make_rename_temp (type, "reciptmp"); + new_stmt = build2 (MODIFY_EXPR, void_type_node, recip_def, + fold_build2 (RDIV_EXPR, type, + build_real (type, dconst1), def)); + + + if (occ->bb_has_division) + { + /* Case 1: insert before an existing division. */ + bsi = bsi_after_labels (occ->bb); + while (!bsi_end_p (bsi) && !is_division_by (bsi_stmt (bsi), def)) + bsi_next (&bsi); + + bsi_insert_before (&bsi, new_stmt, BSI_SAME_STMT); + } + else if (def_bsi && occ->bb == def_bsi->bb) { - ++count; - /* Check if this use post-dominates the insertion point. */ - if (ok || dominated_by_p (CDI_POST_DOMINATORS, bsi->bb, - bb_for_stmt (use_stmt))) - ok = true; + /* Case 2: insert right after the definition. Note that this will + never happen if the definition statement can throw, because in + that case the sole successor of the statement's basic block will + dominate all the uses as well. */ + bsi_insert_after (def_bsi, new_stmt, BSI_NEW_STMT); } - if (count >= 2 && ok) - break; + else + { + /* Case 3: insert in a basic block not containing defs/uses. */ + bsi = bsi_after_labels (occ->bb); + bsi_insert_before (&bsi, new_stmt, BSI_SAME_STMT); + } + + occ->recip_def_stmt = new_stmt; } - if (count < 2 || !ok) - return; - - /* Make a variable with the replacement and substitute it. */ - type = TREE_TYPE (def); - t = make_rename_temp (type, "reciptmp"); - new_stmt = build2 (MODIFY_EXPR, void_type_node, t, - fold_build2 (RDIV_EXPR, type, build_real (type, dconst1), - def)); - - if (where == PR_BEFORE_BSI) - bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT); - else if (where == PR_AFTER_BSI) - bsi_insert_after (bsi, new_stmt, BSI_NEW_STMT); - else if (where == PR_ON_ENTRY_EDGE) - bsi_insert_on_edge (single_succ_edge (ENTRY_BLOCK_PTR), new_stmt); + occ->recip_def = recip_def; + for (occ_child = occ->children; occ_child; occ_child = occ_child->next) + insert_reciprocals (def_bsi, occ_child, def, recip_def, threshold); +} + + +/* Replace the division at USE_P with a multiplication by the reciprocal, if + possible. */ + +static inline void +replace_reciprocal (use_operand_p use_p) +{ + tree use_stmt = USE_STMT (use_p); + basic_block bb = bb_for_stmt (use_stmt); + struct occurrence *occ = (struct occurrence *) bb->aux; + + if (occ->recip_def && use_stmt != occ->recip_def_stmt) + { + TREE_SET_CODE (TREE_OPERAND (use_stmt, 1), MULT_EXPR); + SET_USE (use_p, occ->recip_def); + fold_stmt_inplace (use_stmt); + update_stmt (use_stmt); + } +} + + +/* Free OCC and return one more "struct occurrence" to be freed. */ + +static struct occurrence * +free_bb (struct occurrence *occ) +{ + struct occurrence *child, *next; + + /* First get the two pointers hanging off OCC. */ + next = occ->next; + child = occ->children; + occ->bb->aux = NULL; + pool_free (occ_pool, occ); + + /* Now ensure that we don't recurse unless it is necessary. */ + if (!child) + return next; else - gcc_unreachable (); + { + while (next) + next = free_bb (next); + + return child; + } +} + + +/* Look for floating-point divisions among DEF's uses, and try to + replace them by multiplications with the reciprocal. Add + as many statements computing the reciprocal as needed. + + DEF must be a GIMPLE register of a floating-point type. */ + +static void +execute_cse_reciprocals_1 (block_stmt_iterator *def_bsi, tree def) +{ + use_operand_p use_p; + imm_use_iterator use_iter; + struct occurrence *occ; + int count = 0, threshold; - FOR_EACH_IMM_USE_SAFE (use_p, use_iter, def) + gcc_assert (FLOAT_TYPE_P (TREE_TYPE (def)) && is_gimple_reg (def)); + + FOR_EACH_IMM_USE_FAST (use_p, use_iter, def) { tree use_stmt = USE_STMT (use_p); - if (use_stmt != new_stmt - && TREE_CODE (use_stmt) == MODIFY_EXPR - && TREE_CODE (TREE_OPERAND (use_stmt, 1)) == RDIV_EXPR - && TREE_OPERAND (TREE_OPERAND (use_stmt, 1), 1) == def) + if (is_division_by (use_stmt, def)) { - TREE_SET_CODE (TREE_OPERAND (use_stmt, 1), MULT_EXPR); - SET_USE (use_p, t); + register_division_in (bb_for_stmt (use_stmt)); + count++; } } + + /* Do the expensive part only if we can hope to optimize something. */ + threshold = targetm.min_divisions_for_recip_mul (TYPE_MODE (TREE_TYPE (def))); + if (count >= threshold) + { + for (occ = occ_head; occ; occ = occ->next) + { + compute_merit (occ); + insert_reciprocals (def_bsi, occ, def, NULL, threshold); + } + + FOR_EACH_IMM_USE_SAFE (use_p, use_iter, def) + { + tree use_stmt = USE_STMT (use_p); + if (is_division_by (use_stmt, def)) + replace_reciprocal (use_p); + } + } + + for (occ = occ_head; occ; ) + occ = free_bb (occ); + + occ_head = NULL; } + +static bool +gate_cse_reciprocals (void) +{ + return optimize && !optimize_size && flag_unsafe_math_optimizations; +} + + +/* Go through all the floating-point SSA_NAMEs, and call + execute_cse_reciprocals_1 on each of them. */ static void execute_cse_reciprocals (void) { basic_block bb; tree arg; - if (flag_trapping_math) - calculate_dominance_info (CDI_POST_DOMINATORS); + occ_pool = create_alloc_pool ("dominators for recip", + sizeof (struct occurrence), + n_basic_blocks / 3 + 1); - if (single_succ_p (ENTRY_BLOCK_PTR)) - for (arg = DECL_ARGUMENTS (cfun->decl); arg; arg = TREE_CHAIN (arg)) - if (default_def (arg)) - { - block_stmt_iterator bsi; - bsi = bsi_start (single_succ (ENTRY_BLOCK_PTR)); - execute_cse_reciprocals_1 (&bsi, default_def (arg), - PR_ON_ENTRY_EDGE); - } + calculate_dominance_info (CDI_DOMINATORS | CDI_POST_DOMINATORS); + +#ifdef ENABLE_CHECKING + FOR_EACH_BB (bb) + gcc_assert (!bb->aux); +#endif + + for (arg = DECL_ARGUMENTS (cfun->decl); arg; arg = TREE_CHAIN (arg)) + if (default_def (arg) + && FLOAT_TYPE_P (TREE_TYPE (arg)) + && is_gimple_reg (arg)) + execute_cse_reciprocals_1 (NULL, default_def (arg)); FOR_EACH_BB (bb) { block_stmt_iterator bsi; tree phi, def; - for (bsi = bsi_start (bb); - !bsi_end_p (bsi) && TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR; - bsi_next (&bsi)) - ; for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) { def = PHI_RESULT (phi); if (FLOAT_TYPE_P (TREE_TYPE (def)) && is_gimple_reg (def)) - execute_cse_reciprocals_1 (&bsi, def, PR_BEFORE_BSI); + execute_cse_reciprocals_1 (NULL, def); } - for (; !bsi_end_p (bsi); bsi_next (&bsi)) + for (bsi = bsi_after_labels (bb); !bsi_end_p (bsi); bsi_next (&bsi)) { tree stmt = bsi_stmt (bsi); if (TREE_CODE (stmt) == MODIFY_EXPR && (def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF)) != NULL && FLOAT_TYPE_P (TREE_TYPE (def)) && TREE_CODE (def) == SSA_NAME) - execute_cse_reciprocals_1 (&bsi, def, PR_AFTER_BSI); + execute_cse_reciprocals_1 (&bsi, def); } } - if (flag_trapping_math) - free_dominance_info (CDI_POST_DOMINATORS); - - if (single_succ_p (ENTRY_BLOCK_PTR)) - bsi_commit_one_edge_insert (single_succ_edge (ENTRY_BLOCK_PTR), NULL); + free_dominance_info (CDI_DOMINATORS | CDI_POST_DOMINATORS); + free_alloc_pool (occ_pool); } struct tree_opt_pass pass_cse_reciprocals = |