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, 0 insertions, 523 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 deleted file mode 100644 index 1ff06285d..000000000 --- a/gcc-4.2.1-5666.3/gcc/tree-ssa-math-opts.c +++ /dev/null @@ -1,523 +0,0 @@ -/* 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 */ -}; |