This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] PR23948 et al., take 2
- From: Paolo Bonzini <paolo dot bonzini at lu dot unisi dot ch>
- To: GCC Patches <gcc-patches at gcc dot gnu dot org>, Diego Novillo <dnovillo at redhat dot com>, Richard Guenther <rguenther at suse dot de>
- Date: Mon, 09 Jan 2006 06:33:13 +0100
- Subject: [PATCH] PR23948 et al., take 2
This patch is a reissue of the tree-ssa-math-opts.c rewrite. The
biggest changes are:
- I changed almost every occurrence of "divide" to "division".
- I include documentation about the algorithm and complexity at the top
of the file.
- I check and assert that execute_cse_reciprocals_1's argument is a
floating-point register.
- I dropped the first basic_block argument to insert_bb (which was not
documented either), and improved the comments in that routine.
- I moved single_noncomplex_succ to tree-cfg.c.
- All the tests pass the new param correctly, if necessary.
Bootstrapped/regtested powerpc-apple-darwin8.3.0, ok for mainline?
Paolo
2006-01-07 Paolo Bonzini <bonzini@gnu.org>
PR tree-optimization/23109
PR tree-optimization/23948
PR tree-optimization/24123
* Makefile.in (tree-ssa-math-opts.o): Adjust dependencies.
* tree-cfg.c (single_noncomplex_succ): New.
* tree-flow.h (single_noncomplex_succ): Declare it.
* tree-ssa-math-opts.c (enum place_reciprocal): Remove.
* tree-ssa-math-opts.c (enum place_reciprocal): Remove.
(struct occurrence, occ_head, occ_pool, is_divide_by, compute_merit,
insert_bb, register_division_in, insert_reciprocals,
replace_reciprocal, free_bb): New.
(execute_cse_reciprocals_1): Rewritten.
(execute_cse_reciprocals): Adjust calls to execute_cse_reciprocals_1.
Do not commit any edge insertion. Always compute dominators and
create the allocation pool.
* params.def (PARAM_MIN_DIVISIONS_FOR_RECIP_MUL): New.
* params.h (MIN_DIVISIONS_FOR_RECIP_MUL): New.
* passes.c (init_optimization_passes): Run recip after tree loop
optimizations.
* doc/invoke.texi (--param): Add the min-divisions-for-recip-mul
parameter.
2006-01-07 Paolo Bonzini <bonzini@gnu.org>
PR tree-optimization/23109
PR tree-optimization/23948
PR tree-optimization/24123
* gcc.dg/tree-ssa/recip-3.c, gcc.dg/tree-ssa/recip-4.c,
gcc.dg/tree-ssa/recip-5.c, gcc.dg/tree-ssa/recip-6.c,
gcc.dg/tree-ssa/recip-7.c, gcc.dg/tree-ssa/pr23109.c,
g++.dg/tree-ssa/pr23948.C: New testcases.
* gcc.dg/tree-ssa/pr23234.c: Add --param min-divisions-for-recip-mul=2.
Index: Makefile.in
===================================================================
--- Makefile.in (revision 109374)
+++ Makefile.in (working copy)
@@ -1969,7 +1969,8 @@ tree-ssa-loop-im.o : tree-ssa-loop-im.c
$(TREE_DUMP_H) tree-pass.h $(FLAGS_H) real.h $(BASIC_BLOCK_H) \
hard-reg-set.h
tree-ssa-math-opts.o : tree-ssa-math-opts.c $(TREE_FLOW_H) $(CONFIG_H) \
- $(SYSTEM_H) $(TREE_H) $(TIMEVAR_H) tree-pass.h $(TM_H) $(FLAGS_H)
+ $(SYSTEM_H) $(TREE_H) $(TIMEVAR_H) tree-pass.h $(TM_H) $(FLAGS_H) \
+ alloc-pool.h $(BASIC_BLOCK_H) $(PARAMS_H)
tree-ssa-alias.o : tree-ssa-alias.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
$(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) tree-inline.h $(FLAGS_H) \
function.h $(TIMEVAR_H) convert.h $(TM_H) coretypes.h langhooks.h \
Index: tree-ssa-math-opts.c
===================================================================
--- tree-ssa-math-opts.c (revision 109374)
+++ tree-ssa-math-opts.c (working copy)
@@ -35,7 +35,55 @@ Software Foundation, 51 Franklin Street,
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,406 @@ Software Foundation, 51 Franklin Street,
#include "real.h"
#include "timevar.h"
#include "tree-pass.h"
+#include "alloc-pool.h"
+#include "basic-block.h"
+#include "params.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;
+
+ 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 and construct the new list of children. */
+ *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 create a new
+ struct for 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. */
-/* 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.
-
- 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)
+{
+ 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 >= MIN_DIVISIONS_FOR_RECIP_MUL)
+ {
+ /* 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;
+ 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);
+}
+
+
+/* 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;
- /* 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);
+ 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. */
- FOR_EACH_IMM_USE_SAFE (use_p, use_iter, def)
+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;
+
+ 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))
+ {
+ register_division_in (bb_for_stmt (use_stmt));
+ count++;
+ }
+ }
+
+ /* Do the expensive part only if we can hope to optimize something. */
+ if (count >= MIN_DIVISIONS_FOR_RECIP_MUL)
+ {
+ for (occ = occ_head; occ; occ = occ->next)
+ {
+ compute_merit (occ);
+ insert_reciprocals (def_bsi, occ, def, NULL);
+ }
+
+ FOR_EACH_IMM_USE_SAFE (use_p, use_iter, def)
{
- TREE_SET_CODE (TREE_OPERAND (use_stmt, 1), MULT_EXPR);
- SET_USE (use_p, t);
+ 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 =
Index: params.def
===================================================================
--- params.def (revision 109374)
+++ params.def (working copy)
@@ -202,7 +202,7 @@ DEFPARAM(PARAM_MAX_GCSE_MEMORY,
DEFPARAM(PARAM_MAX_GCSE_PASSES,
"max-gcse-passes",
"The maximum number of passes to make when doing GCSE",
- 1, 1, 0)
+ 2, 1, 0)
/* This is the threshold ratio when to perform partial redundancy
elimination after reload. We perform partial redundancy elimination
when the following holds:
@@ -552,6 +552,11 @@ DEFPARAM (PARAM_MAX_JUMP_THREAD_DUPLICAT
"Maximum number of statements allowed in a block that needs to be duplicated when threading jumps",
15, 0, 0)
+DEFPARAM (PARAM_MIN_DIVISIONS_FOR_RECIP_MUL,
+ "min-divisions-for-recip-mul",
+ "The minimum numbers of divisions with a common divisor, for which it is profitable to instead multiply by the reciprocal",
+ 3, 2, 0)
+
/*
Local variables:
mode:c
Index: params.h
===================================================================
--- params.h (revision 109374)
+++ params.h (working copy)
@@ -145,4 +145,6 @@ typedef enum compiler_param
PARAM_VALUE (PARAM_MIN_VIRTUAL_MAPPINGS)
#define VIRTUAL_MAPPINGS_TO_SYMS_RATIO \
PARAM_VALUE (PARAM_VIRTUAL_MAPPINGS_TO_SYMS_RATIO)
+#define MIN_DIVISIONS_FOR_RECIP_MUL \
+ PARAM_VALUE (PARAM_MIN_DIVISIONS_FOR_RECIP_MUL)
#endif /* ! GCC_PARAMS_H */
Index: passes.c
===================================================================
--- passes.c (revision 109374)
+++ passes.c (working copy)
@@ -551,12 +529,12 @@ init_optimization_passes (void)
we add may_alias right after fold builtins
which can create arbitrary GIMPLE. */
NEXT_PASS (pass_may_alias);
- NEXT_PASS (pass_cse_reciprocals);
NEXT_PASS (pass_split_crit_edges);
NEXT_PASS (pass_pre);
NEXT_PASS (pass_may_alias);
NEXT_PASS (pass_sink_code);
NEXT_PASS (pass_tree_loop);
+ NEXT_PASS (pass_cse_reciprocals);
NEXT_PASS (pass_reassoc);
NEXT_PASS (pass_dominator);
Index: tree-cfg.c
===================================================================
--- tree-cfg.c (revision 109374)
+++ tree-cfg.c (working copy)
@@ -1389,6 +1389,30 @@ tree_merge_blocks (basic_block a, basic_
}
+/* Return the one of two successors of BB that is not reachable by a
+ reached by a complex edge, if there is one. Else, return BB. We use
+ this in optimizations that use post-dominators for their heuristics,
+ to catch the cases in C++ where function calls are involved. */
+
+basic_block
+single_noncomplex_succ (basic_block bb)
+{
+ edge e0, e1;
+ if (EDGE_COUNT (bb->succs) != 2)
+ return bb;
+
+ e0 = EDGE_SUCC (bb, 0);
+ e1 = EDGE_SUCC (bb, 1);
+ if (e0->flags & EDGE_COMPLEX)
+ return e1->dest;
+ if (e1->flags & EDGE_COMPLEX)
+ return e0->dest;
+
+ return bb;
+}
+
+
+
/* Walk the function tree removing unnecessary statements.
* Empty statement nodes are removed
Index: tree-flow.h
===================================================================
--- tree-flow.h (revision 109374)
+++ tree-flow.h (working copy)
@@ -487,6 +487,7 @@ extern bool is_ctrl_stmt (tree);
extern bool is_ctrl_altering_stmt (tree);
extern bool computed_goto_p (tree);
extern bool simple_goto_p (tree);
+extern basic_block single_noncomplex_succ (basic_block bb);
extern void tree_dump_bb (basic_block, FILE *, int);
extern void debug_tree_bb (basic_block);
extern basic_block debug_tree_bb_n (int);
Index: doc/invoke.texi
===================================================================
--- doc/invoke.texi (revision 109374)
+++ doc/invoke.texi (working copy)
@@ -6144,6 +6144,14 @@ protection when @option{-fstack-protecti
@item max-jump-thread-duplication-stmts
Maximum number of statements allowed in a block that needs to be
duplicated when threading jumps.
+
+@item min-divisions-for-recip-mul
+When @option{-ffast-math} is in effect, GCC tries to optimize
+divisions by the same divisor, by turning them into multiplications by
+the reciprocal. This parameter sets the minimum number of divisions
+that should be there for GCC to perform the optimization. The default
+is 3.
+
@end table
@end table
Index: testsuite/g++.dg/tree-ssa/pr23948.C
===================================================================
RCS file: testsuite/g++.dg/tree-ssa/pr23948.C
diff -N testsuite/g++.dg/tree-ssa/pr23948.C
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ testsuite/g++.dg/tree-ssa/pr23948.C 12 Oct 2005 10:59:27 -0000
@@ -0,0 +1,18 @@
+/* { dg-options "-O1 -ffast-math -fdump-tree-recip --param min-divisions-for-recip-mul=2" } */
+/* { dg-do compile } */
+
+struct MIOFILE {
+ ~MIOFILE();
+};
+double potentially_runnable_resource_share();
+void f1(double);
+int make_scheduler_request(double a)
+{
+ MIOFILE mf;
+ double prrs = potentially_runnable_resource_share();
+ f1(a/prrs);
+ f1(1/prrs);
+}
+
+/* { dg-final { scan-tree-dump-times " / " 1 "recip" } } */
+/* { dg-final { cleanup-tree-dump "recip" } } */
Index: testsuite/gcc.dg/tree-ssa/pr23109.c
===================================================================
RCS file: testsuite/gcc.dg/tree-ssa/pr23109.c
diff -N testsuite/gcc.dg/tree-ssa/pr23109.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ testsuite/gcc.dg/tree-ssa/pr23109.c 12 Oct 2005 10:59:28 -0000
@@ -0,0 +1,34 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -funsafe-math-optimizations -fdump-tree-recip" } */
+
+double F[2] = { 0., 0. }, e = 0.;
+
+int main()
+{
+ int i;
+ double E, W, P, d;
+
+ /* make sure the program crashes on FP exception */
+ unsigned short int Mask;
+
+ W = 1.;
+ d = 2.*e;
+ E = 1. - d;
+
+ for( i=0; i < 2; i++ )
+ if( d > 0.01 )
+ {
+ P = ( W < E ) ? (W - E)/d : (E - W)/d;
+ F[i] += P;
+ }
+
+ return 0;
+}
+
+/* LIM only performs the transformation in the no-trapping-math case. In
+ the future we will do it for trapping-math as well in recip, check that
+ this is not wrongly optimized. */
+/* { dg-final { scan-tree-dump-not "reciptmp" "lim" } } */
+/* { dg-final { scan-tree-dump-not "reciptmp" "recip" } } */
+/* { dg-final { cleanup-tree-dump "recip" } } */
+
Index: testsuite/gcc.dg/tree-ssa/pr23234.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/testsuite/gcc.dg/tree-ssa/pr23234.c,v
retrieving revision 1.1
diff -p -u -u -r1.1 pr23234.c
--- testsuite/gcc.dg/tree-ssa/pr23234.c 9 Aug 2005 03:28:38 -0000 1.1
+++ testsuite/gcc.dg/tree-ssa/pr23234.c 12 Oct 2005 10:59:28 -0000
@@ -1,7 +1,7 @@
/* The problem in this PR was mostly finding a suitable place to insert
the reciprocals of the function arguments. This test case tries to
test three possible ways of how this may go wrong. */
-/* { dg-options "-O2 -ffast-math" } */
+/* { dg-options "-O2 -ffast-math --param min-divisions-for-recip-mul=2" } */
/* { dg-do compile } */
/* The original test case. */
Index: testsuite/gcc.dg/tree-ssa/recip-2.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/testsuite/gcc.dg/tree-ssa/recip-2.c,v
retrieving revision 1.1
diff -p -u -u -r1.1 recip-2.c
--- testsuite/gcc.dg/tree-ssa/recip-2.c 17 May 2005 09:55:44 -0000 1.1
+++ testsuite/gcc.dg/tree-ssa/recip-2.c 12 Oct 2005 10:59:28 -0000
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-O1 -funsafe-math-optimizations -fdump-tree-recip" } */
+/* { dg-options "-O1 -funsafe-math-optimizations -fdump-tree-recip --param min-divisions-for-recip-mul=2" } */
float e(float a, float b, float c, float d, float e, float f)
{
Index: testsuite/gcc.dg/tree-ssa/recip-3.c
===================================================================
RCS file: testsuite/gcc.dg/tree-ssa/recip-3.c
diff -N testsuite/gcc.dg/tree-ssa/recip-3.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ testsuite/gcc.dg/tree-ssa/recip-3.c 12 Oct 2005 10:59:28 -0000
@@ -0,0 +1,27 @@
+/* { dg-do compile } */
+/* { dg-options "-O1 -fno-trapping-math -funsafe-math-optimizations -fdump-tree-recip" } */
+
+double F[2] = { 0.0, 0.0 }, e;
+
+/* In this case the optimization is interesting. */
+float h ()
+{
+ int i;
+ double E, W, P, d;
+
+ W = 1.;
+ d = 2.*e;
+ E = 1. - d;
+
+ for( i=0; i < 2; i++ )
+ if( d > 0.01 )
+ {
+ P = ( W < E ) ? (W - E)/d : (E - W)/d;
+ F[i] += P;
+ }
+
+ F[0] += E / d;
+}
+
+/* { dg-final { scan-tree-dump-times " / " 1 "recip" } } */
+/* { dg-final { cleanup-tree-dump "recip" } } */
Index: testsuite/gcc.dg/tree-ssa/recip-4.c
===================================================================
RCS file: testsuite/gcc.dg/tree-ssa/recip-4.c
diff -N testsuite/gcc.dg/tree-ssa/recip-4.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ testsuite/gcc.dg/tree-ssa/recip-4.c 12 Oct 2005 10:59:28 -0000
@@ -0,0 +1,45 @@
+/* { dg-do compile } */
+/* { dg-options "-O1 -fno-trapping-math -funsafe-math-optimizations -fdump-tree-recip" } */
+
+/* based on the test case in pr23109 */
+
+double F[2] = { 0., 0. }, e = 0.;
+
+/* Nope, we cannot prove the optimization is worthwhile in this case. */
+void f ()
+{
+ int i;
+ double E, W, P, d;
+
+ W = 1.;
+ d = 2.*e;
+ E = 1. - d;
+
+ if( d > 0.01 )
+ {
+ P = ( W < E ) ? (W - E)/d : (E - W)/d;
+ F[i] += P;
+ }
+}
+
+/* We also cannot prove the optimization is worthwhile in this case. */
+float g ()
+{
+ int i;
+ double E, W, P, d;
+
+ W = 1.;
+ d = 2.*e;
+ E = 1. - d;
+
+ if( d > 0.01 )
+ {
+ P = ( W < E ) ? (W - E)/d : (E - W)/d;
+ F[i] += P;
+ }
+
+ return 1.0 / d;
+}
+
+/* { dg-final { scan-tree-dump-not "reciptmp" "recip" } } */
+/* { dg-final { cleanup-tree-dump "recip" } } */
Index: testsuite/gcc.dg/tree-ssa/recip-5.c
===================================================================
RCS file: testsuite/gcc.dg/tree-ssa/recip-5.c
diff -N testsuite/gcc.dg/tree-ssa/recip-5.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ testsuite/gcc.dg/tree-ssa/recip-5.c 12 Oct 2005 10:59:28 -0000
@@ -0,0 +1,30 @@
+/* { dg-options "-O1 -funsafe-math-optimizations -ftrapping-math -fdump-tree-recip -fdump-tree-optimized --param min-divisions-for-recip-mul=2" } */
+/* { dg-do compile } */
+
+/* Test the reciprocal optimizations together with trapping math. */
+
+extern int g();
+
+double f(double y, double z, double w)
+{
+ double b, c, d, e;
+
+ if (g ())
+ /* inserts one division here */
+ b = 1 / y, c = z / y;
+ else
+ /* one division here */
+ b = 3 / y, c = w / y;
+
+ /* and one here, that should be removed afterwards */
+ d = b / y;
+ e = c / y;
+
+ return b + c + d + e;
+}
+
+/* { dg-final { scan-tree-dump-times " / " 3 "recip" } } */
+/* { dg-final { scan-tree-dump-times " / " 2 "optimized" { xfail *-*-* } } } */
+/* { dg-final { cleanup-tree-dump "recip" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
+
Index: testsuite/gcc.dg/tree-ssa/recip-6.c
===================================================================
RCS file: testsuite/gcc.dg/tree-ssa/recip-6.c
diff -N testsuite/gcc.dg/tree-ssa/recip-6.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ testsuite/gcc.dg/tree-ssa/recip-6.c 12 Oct 2005 10:59:28 -0000
@@ -0,0 +1,25 @@
+/* { dg-options "-O1 -funsafe-math-optimizations -fno-trapping-math -fdump-tree-recip --param min-divisions-for-recip-mul=2" } */
+/* { dg-do compile } */
+
+/* Test inserting in a block that does not contain a division. */
+
+extern int g();
+
+double f(double y, double z, double w)
+{
+ double b, c, d, e;
+
+ if (g ())
+ b = 1 / y, c = z / y;
+ else
+ b = 3 / y, c = w / y;
+
+ d = b / y;
+ e = c / y;
+
+ return b + c + d + e;
+}
+
+/* { dg-final { scan-tree-dump-times " / " 1 "recip" } } */
+/* { dg-final { cleanup-tree-dump "recip" } } */
+
Index: testsuite/gcc.dg/tree-ssa/recip-7.c
===================================================================
RCS file: testsuite/gcc.dg/tree-ssa/recip-7.c
diff -N testsuite/gcc.dg/tree-ssa/recip-7.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ testsuite/gcc.dg/tree-ssa/recip-7.c 12 Oct 2005 10:59:28 -0000
@@ -0,0 +1,26 @@
+/* { dg-options "-O1 -funsafe-math-optimizations -fno-trapping-math -fdump-tree-recip --param min-divisions-for-recip-mul=2" } */
+/* { dg-do compile } */
+
+/* Test inserting in a block that does not contain a division. */
+
+extern double h();
+
+double f(int x, double z, double w)
+{
+ double b, c, d, e;
+ double y = h ();
+
+ if (x)
+ b = 1 / y, c = z / y;
+ else
+ b = 3 / y, c = w / y;
+
+ d = b / y;
+ e = c / y;
+
+ return b + c + d + e;
+}
+
+/* { dg-final { scan-tree-dump-times " / " 1 "recip" } } */
+/* { dg-final { cleanup-tree-dump "recip" } } */
+