diff options
Diffstat (limited to 'gcc-4.2.1-5666.3/gcc/tree-ssa-math-opts.c')
| -rw-r--r-- | gcc-4.2.1-5666.3/gcc/tree-ssa-math-opts.c | 523 |
1 files changed, 523 insertions, 0 deletions
diff --git a/gcc-4.2.1-5666.3/gcc/tree-ssa-math-opts.c b/gcc-4.2.1-5666.3/gcc/tree-ssa-math-opts.c new file mode 100644 index 000000000..1ff06285d --- /dev/null +++ b/gcc-4.2.1-5666.3/gcc/tree-ssa-math-opts.c @@ -0,0 +1,523 @@ +/* Global, SSA-based optimizations using mathematical identities. + Copyright (C) 2005 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by the +Free Software Foundation; either version 2, or (at your option) any +later version. + +GCC is distributed in the hope that it will be useful, but WITHOUT +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING. If not, write to the Free +Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301, USA. */ + +/* Currently, the only mini-pass in this file tries to CSE reciprocal + operations. These are common in sequences such as this one: + + modulus = sqrt(x*x + y*y + z*z); + x = x / modulus; + y = y / modulus; + z = z / modulus; + + that can be optimized to + + modulus = sqrt(x*x + y*y + z*z); + rmodulus = 1.0 / modulus; + x = x * rmodulus; + y = y * rmodulus; + 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. + + 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" +#include "coretypes.h" +#include "tm.h" +#include "flags.h" +#include "tree.h" +#include "tree-flow.h" +#include "real.h" +#include "timevar.h" +#include "tree-pass.h" +#include "alloc-pool.h" +#include "basic-block.h" +#include "target.h" + + +/* 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) +{ + struct occurrence *occ; + + occ = bb->aux = pool_alloc (occ_pool); + memset (occ, 0, sizeof (struct occurrence)); + + occ->bb = bb; + occ->children = children; + return occ; +} + + +/* 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) +{ + struct occurrence *occ, **p_occ; + + 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. */ + +static void +compute_merit (struct occurrence *occ) +{ + struct occurrence *occ_child; + basic_block dom = occ->bb; + + for (occ_child = occ->children; occ_child; occ_child = occ_child->next) + { + 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_one_cst (type), + 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) + { + /* 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); + } + 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; + } + + 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 + { + 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; + + 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 (is_division_by (use_stmt, def)) + { + 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) + { + tree use_stmt; + for (occ = occ_head; occ; occ = occ->next) + { + compute_merit (occ); + insert_reciprocals (def_bsi, occ, def, NULL, threshold); + } + + FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, def) + { + if (is_division_by (use_stmt, def)) + { + FOR_EACH_IMM_USE_ON_STMT (use_p, use_iter) + 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 unsigned int +execute_cse_reciprocals (void) +{ + basic_block bb; + tree arg; + + occ_pool = create_alloc_pool ("dominators for recip", + sizeof (struct occurrence), + n_basic_blocks / 3 + 1); + + calculate_dominance_info (CDI_DOMINATORS); + calculate_dominance_info (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 (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 (NULL, def); + } + + 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); + } + } + + free_dominance_info (CDI_DOMINATORS); + free_dominance_info (CDI_POST_DOMINATORS); + free_alloc_pool (occ_pool); + return 0; +} + +struct tree_opt_pass pass_cse_reciprocals = +{ + "recip", /* name */ + gate_cse_reciprocals, /* gate */ + execute_cse_reciprocals, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + 0, /* tv_id */ + PROP_ssa, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_dump_func | TODO_update_ssa | TODO_verify_ssa + | TODO_verify_stmts, /* todo_flags_finish */ + 0 /* letter */ +}; |