Hi all,
The patch implements the some of the division optimizations discussed in
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71026 .
We now reassociate (as discussed in the bug report):
x / (y * y) -> x * (1 / y) * (1 / y)
If it is reasonable to do so. This is done with
-funsafe-math-optimizations.
Bootstrapped and regtested with part (1/2). OK for trunk?
Jackson
gcc/
2017-08-03 Jackson Woodruff <jackson.woodr...@arm.com>
PR 71026/tree-optimization
* tree-ssa-math-opts (is_division_by_square,
is_square_of, insert_sqaure_reciprocals): New.
(insert_reciprocals): Change to insert reciprocals
before a division by a square.
(execute_cse_reciprocals_1): Change to consider
division by a square.
gcc/testsuite
2017-08-03 Jackson Woodruff <jackson.woodr...@arm.com>
PR 71026/tree-optimization
* gcc.dg/associate_division_1.c: New.
diff --git a/gcc/testsuite/gcc.dg/associate_division_1.c
b/gcc/testsuite/gcc.dg/associate_division_1.c
new file mode 100644
index
0000000000000000000000000000000000000000..187d3597af8825a6a43f29bfaa68b089d2d5bbfe
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/associate_division_1.c
@@ -0,0 +1,46 @@
+/* { dg-do compile } */
+/* { dg-options "-Ofast -fdump-tree-optimized" } */
+
+float
+extract_square (float x, float y, float *a, float *b)
+{
+ *a = 3 / (y * y);
+ *b = 5 / (y * y);
+
+ return x / (y * y);
+}
+
+/* Don't expect the 'powmult' (calculation of y * y)
+ to be deleted until a later pass, so look for one
+ more multiplication than strictly necessary. */
+float
+extract_recip (float *w, float x, float y, float z)
+{
+ *w = 7 / y;
+
+ return x / (y * y) + z / y;
+}
+
+float
+neg_recip (float x, float y, float z)
+{
+ return (x / y) + (z / -y);
+}
+
+float
+const_divisor (float *w, float x, float y, float z)
+{
+ *w = 5 / y;
+ return x / (y * 3.0f) + z / y;
+}
+
+/* 4 For the pointers to a, b, w and w, 4 multiplications in 'extract_square',
+ 5 multiplications in 'extract_recip', 0 multiplications
+ in 'neg_recip', 3 multiplcations in 'const_divisor' expected. */
+/* { dg-final { scan-tree-dump-times " \\* " 14 "optimized" } } */
+
+/* 1 division in 'extract_square', 1 division in 'extract_recip',
+ 1 division in 'neg_recip', 1 division in 'const_divisor'. */
+/* { dg-final { scan-tree-dump-times " / " 4 "optimized" } } */
+
+
diff --git a/gcc/tree-ssa-math-opts.c b/gcc/tree-ssa-math-opts.c
index
7ac1659fa0670b7080685f3f9513939807073a63..0db160f68001ffb90942c4002703625430128b9f
100644
--- a/gcc/tree-ssa-math-opts.c
+++ b/gcc/tree-ssa-math-opts.c
@@ -340,6 +340,38 @@ is_division_by (gimple *use_stmt, tree def)
&& gimple_assign_rhs1 (use_stmt) != def;
}
+/* Return whether USE_STMT is DEF * DEF. */
+static inline bool
+is_square_of (gimple *use_stmt, tree def)
+{
+ if (gimple_code (use_stmt) == GIMPLE_ASSIGN
+ && gimple_assign_rhs_code (use_stmt) == MULT_EXPR)
+ {
+ tree op0 = gimple_assign_rhs1 (use_stmt);
+ tree op1 = gimple_assign_rhs2 (use_stmt);
+
+ return op0 == op1 && op0 == def;
+ }
+ return 0;
+}
+
+/* Return whether USE_STMT is a floating-point division by
+ DEF * DEF. */
+static inline bool
+is_division_by_square (gimple *use_stmt, tree def)
+{
+ if (gimple_code (use_stmt) == GIMPLE_ASSIGN
+ && gimple_assign_rhs_code (use_stmt) == RDIV_EXPR)
+ {
+ tree denominator = gimple_assign_rhs2 (use_stmt);
+ if (TREE_CODE (denominator) == SSA_NAME)
+ {
+ return is_square_of (SSA_NAME_DEF_STMT (denominator), def);
+ }
+ }
+ return 0;
+}
+
/* 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,
@@ -369,14 +401,16 @@ insert_reciprocals (gimple_stmt_iterator *def_gsi, struct
occurrence *occ,
build_one_cst (type), def);
if (occ->bb_has_division)
- {
- /* Case 1: insert before an existing division. */
- gsi = gsi_after_labels (occ->bb);
- while (!gsi_end_p (gsi) && !is_division_by (gsi_stmt (gsi), def))
+ {
+ /* Case 1: insert before an existing division. */
+ gsi = gsi_after_labels (occ->bb);
+ while (!gsi_end_p (gsi)
+ && (!is_division_by (gsi_stmt (gsi), def))
+ && (!is_division_by_square (gsi_stmt (gsi), def)))
gsi_next (&gsi);
- gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
- }
+ gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
+ }
else if (def_gsi && occ->bb == def_gsi->bb)
{
/* Case 2: insert right after the definition. Note that this will
@@ -403,6 +437,80 @@ insert_reciprocals (gimple_stmt_iterator *def_gsi, struct
occurrence *occ,
}
+/* Walk the tree until we find the first division by a square. Insert
+ the definition of the reciprocal there. This returns that definition,
+ or if there is an alternate definition earlier, then it returns that
+ instead. */
+
+static tree
+insert_square_reciprocals (struct occurrence *occ, tree def)
+{
+ gimple_stmt_iterator gsi = gsi_after_labels (occ->bb);
+
+ while (!gsi_end_p (gsi)
+ && !is_division_by (gsi_stmt (gsi), def)
+ /* Check to see if a calculation statement has already
+ been inserted. */
+ && !is_square_of (gsi_stmt (gsi), occ->recip_def))
+ gsi_next (&gsi);
+
+ if (gsi_end_p (gsi))
+ return NULL;
+ else if (is_square_of (gsi_stmt (gsi), occ->recip_def))
+ return gimple_assign_lhs (gsi_stmt (gsi));
+ else
+ {
+ tree type = TREE_TYPE (def);
+ tree recip_square_def = create_tmp_reg (type, "powmult_reciptmp");
+ gassign *new_stmt = gimple_build_assign (recip_square_def, MULT_EXPR,
+ occ->recip_def, occ->recip_def);
+ gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
+ return recip_square_def;
+ }
+}
+
+/* Replace occurrences of expr / (x * x) with expr * ((1 / x) * (1 / x)).
+ Unlike replace_reciprocals, we expect use_p to be a square definition
+ (i.e. use_p is _ = x * x). Iterate though all uses of this square
+ and replace them. */
+static inline void
+replace_reciprocal_squares (use_operand_p use_p)
+{
+ gimple *use_stmt = USE_STMT (use_p);
+ basic_block bb = gimple_bb (use_stmt);
+ struct occurrence *occ = (struct occurrence *) bb->aux;
+ imm_use_iterator use_iter;
+ tree def_name = gimple_assign_lhs (use_stmt);
+ use_operand_p square_use_p;
+ tree squared_reciprocal = insert_square_reciprocals (occ, def_name);
+
+ if (optimize_bb_for_speed_p (bb) && squared_reciprocal
+ && occ->recip_def && use_stmt != occ->recip_def_stmt)
+ {
+
+ /* Find all occurrences of the use name and replace
+ them by multiplications of this new inverse. */
+ FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, def_name)
+ {
+ FOR_EACH_IMM_USE_ON_STMT (square_use_p, use_iter)
+ {
+ gimple *square_use = USE_STMT (square_use_p);
+
+ if (gimple_assign_rhs_code (square_use) == RDIV_EXPR)
+ {
+ gimple_assign_set_rhs_code (square_use, MULT_EXPR);
+ gimple_assign_set_rhs2 (square_use, squared_reciprocal);
+ SET_USE (square_use_p, squared_reciprocal);
+
+ reciprocal_stats.rdivs_inserted++;
+ update_stmt (square_use);
+ }
+ }
+ }
+ }
+}
+
+
/* Replace the division at USE_P with a multiplication by the reciprocal, if
possible. */
@@ -460,10 +568,12 @@ free_bb (struct occurrence *occ)
static void
execute_cse_reciprocals_1 (gimple_stmt_iterator *def_gsi, tree def)
{
- use_operand_p use_p;
- imm_use_iterator use_iter;
+ use_operand_p use_p, square_use_p;
+ imm_use_iterator use_iter, square_use_iter;
+ tree square_def;
struct occurrence *occ;
int count = 0, threshold;
+ int square_recip_count = 0;
gcc_assert (FLOAT_TYPE_P (TREE_TYPE (def)) && is_gimple_reg (def));
@@ -475,11 +585,26 @@ execute_cse_reciprocals_1 (gimple_stmt_iterator *def_gsi,
tree def)
register_division_in (gimple_bb (use_stmt));
count++;
}
+
+ if (is_square_of (use_stmt, def))
+ {
+ square_def = gimple_assign_lhs (use_stmt);
+ FOR_EACH_IMM_USE_FAST (square_use_p, square_use_iter, square_def)
+ {
+ gimple *square_use_stmt = USE_STMT (square_use_p);
+ if (is_division_by (square_use_stmt, square_def))
+ {
+ register_division_in (gimple_bb (square_use_stmt));
+ square_recip_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)
+ if (count + square_recip_count >= threshold
+ && count >= 1)
{
gimple *use_stmt;
for (occ = occ_head; occ; occ = occ->next)
@@ -495,6 +620,11 @@ execute_cse_reciprocals_1 (gimple_stmt_iterator *def_gsi,
tree def)
FOR_EACH_IMM_USE_ON_STMT (use_p, use_iter)
replace_reciprocal (use_p);
}
+ else if (is_square_of (use_stmt, def))
+ {
+ FOR_EACH_IMM_USE_ON_STMT (use_p, use_iter)
+ replace_reciprocal_squares (use_p);
+ }
}
}
