public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [PATCH] Factor out division by squares and remove division around comparisons (2/2)
@ 2017-08-10 16:39 Jackson Woodruff
  2017-08-15 14:22 ` Richard Biener
  0 siblings, 1 reply; 6+ messages in thread
From: Jackson Woodruff @ 2017-08-10 16:39 UTC (permalink / raw)
  To: wilco.dijkstra, richard.guenther, kyrylo.tkachov, joseph; +Cc: gcc-patches

[-- Attachment #1: Type: text/plain, Size: 865 bytes --]

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.woodruff@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.woodruff@arm.com>

	PR 71026/tree-optimization
	* gcc.dg/associate_division_1.c: New.


[-- Attachment #2: patchfile-2 --]
[-- Type: text/plain, Size: 8174 bytes --]

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);
+	    }
 	}
     }
 

^ permalink raw reply	[flat|nested] 6+ messages in thread
end of thread, other threads:[~2017-11-20  3:11 UTC | newest]

Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-08-10 16:39 [PATCH] Factor out division by squares and remove division around comparisons (2/2) Jackson Woodruff
2017-08-15 14:22 ` Richard Biener
2017-08-30 17:08   ` Jackson Woodruff
2017-09-06  9:55     ` Jackson Woodruff
2017-11-16 14:33       ` Wilco Dijkstra
2017-11-20  3:34       ` Jeff Law

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).