[PATCH 3/5] reassoc: Rewrite floating-point plus/mult trees.

From: Robin Dapp <[email protected]>

This patch adds a wrapper for the multiplicative factors in plus/mult
tree rewriting.  Wrapping plus/mult allows to easily add floating-point
handling to the rewriting functions and also permits extending to
vectors later.  Apart from that, there's no structural change and the
wi::plus/mult operations are done with real_arithmetic instead.
As far as I know there is no further guard necessary as reassoc only
works on floating-point types when -fassociative-math is specified.

	PR tree-optimization/113583

gcc/ChangeLog:

	* tree-ssa-reassoc.cc (constant_maybe_expensive): Add
	floating-point variant.
	(struct mult_factor): Wrapper for multiplicative factor.
	(struct plus_mult_tree_state): Use wrapper for hashmap and
	constant.
	(linearize_plus_mult_tree): Add float handling.
	(expand_plus_mult_tree): Use wrapper.
	(gather_plus_mult_tree_stats): Use wrapper.
	(rewrite_plus_mult_tree): Use wrapper and allow float.
	(reassociate_bb): Allow float for plus/mult.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/reassoc-54.c: New test.
	* gcc.dg/tree-ssa/reassoc-55.c: New test.
---
 gcc/testsuite/gcc.dg/tree-ssa/reassoc-54.c |  18 ++
 gcc/testsuite/gcc.dg/tree-ssa/reassoc-55.c |  30 +++
 gcc/tree-ssa-reassoc.cc                    | 244 +++++++++++++++++----
 3 files changed, 248 insertions(+), 44 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/reassoc-54.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/reassoc-55.c

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-54.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-54.c
new file mode 100644
index 00000000000..e95c677545d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-54.c
@@ -0,0 +1,18 @@
+/* { dg-do compile } */
+/* { dg-additional-options "-O2 -ffast-math -fdump-tree-reassoc-details" } */
+
+double
+foo (double fs)
+{
+  return 0.5 * (fs + 1.0) + 0.25 * (fs + 2.0);
+}
+
+double srcn, feqa, fs;
+
+double
+foo2 (void)
+{
+  return srcn - 0.5 * (4.0 - feqa) + 0.25 * (4.0 + fs);
+}
+
+/* { dg-final { scan-tree-dump-times "Rewriting plus/mult" 2 "reassoc1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-55.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-55.c
new file mode 100644
index 00000000000..e101cbde5b3
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-55.c
@@ -0,0 +1,30 @@
+/* { dg-do compile } */
+/* { dg-additional-options "-O2 -ffast-math -fno-tree-vectorize -fdump-tree-reassoc-details" } */
+
+/* This is from PR tree-optimization/113583  */
+
+#define SX 100
+#define SY 100
+#define SZ 130
+#define NN 20
+#define OMEGA 0.123
+#define LAMBDA (1.0 / (0.5 + 3.0 / (16.0 * (1.0 / OMEGA - 0.5))))
+#define CST1 (1.0 / 3.0)
+#define FEQS (CST1 * (1.0 + 4.5 * 1.0 * 1.0))
+
+void
+foo (double *src, double *dst)
+{
+  double avg_diff;
+  unsigned i = 0;
+
+  for (i = 0; i < SX * SY * SZ * NN; i += NN)
+    {
+      avg_diff = 0.5 * (src[i + 1] + src[i + 2]) - FEQS;
+
+      dst[i] = src[i] - OMEGA * (src[i] - CST1 * 1.0);
+      dst[i + 1] = src[i + 1] - OMEGA * avg_diff - LAMBDA * (0.1 - 0.2);
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "Rewriting plus/mult" 2 "reassoc1" } } */
diff --git a/gcc/tree-ssa-reassoc.cc b/gcc/tree-ssa-reassoc.cc
index 211e8778d6c..440c6271e28 100644
--- a/gcc/tree-ssa-reassoc.cc
+++ b/gcc/tree-ssa-reassoc.cc
@@ -1871,6 +1871,148 @@ constant_maybe_expensive (REAL_VALUE_TYPE)
   return false;
 }
 
+static inline bool
+constant_maybe_expensive (tree t)
+{
+  tree type = TREE_TYPE (t);
+  gcc_checking_assert (INTEGRAL_TYPE_P (type)
+			|| SCALAR_FLOAT_TYPE_P (type));
+  if (INTEGRAL_TYPE_P (type))
+    return constant_maybe_expensive (wi::to_wide (t));
+  else
+    return constant_maybe_expensive (TREE_REAL_CST (t));
+}
+
+/* Helper to wrap operations for the constant multiplicative factors in
+   plus/mult trees.  */
+struct mult_factor
+{
+  wide_int cst;
+  REAL_VALUE_TYPE fcst;
+
+  HOST_WIDE_INT prec;
+  tree type;
+  bool is_float;
+
+  bool is_zero ()
+    {
+      if (!is_float)
+	return cst == wi::zero (prec);
+      else
+	return real_equal (&fcst, &dconst0);
+    }
+
+  void mul (tree other)
+    {
+      tree other_type = TREE_TYPE (other);
+      gcc_checking_assert ((!is_float && INTEGRAL_TYPE_P (other_type))
+			   || (is_float && SCALAR_FLOAT_TYPE_P (other_type)));
+      if (!is_float)
+	cst = wi::mul (cst, wi::to_wide (other));
+      else
+	real_arithmetic (&fcst, MULT_EXPR, &fcst,
+			 TREE_REAL_CST_PTR (other));
+    }
+
+  void mul (mult_factor &other)
+    {
+      gcc_checking_assert (is_float == other.is_float);
+      if (!is_float)
+	cst = wi::mul (cst, other.cst);
+      else
+	real_arithmetic (&fcst, MULT_EXPR, &fcst,
+			 &other.fcst);
+    }
+
+  void plus (tree other)
+    {
+      tree other_type = TREE_TYPE (other);
+      gcc_checking_assert ((!is_float && INTEGRAL_TYPE_P (other_type))
+			    || (is_float && SCALAR_FLOAT_TYPE_P (other_type)));
+      if (!is_float)
+	cst = wi::add (cst, wi::to_wide (other));
+      else
+	real_arithmetic (&fcst, PLUS_EXPR, &fcst,
+			 TREE_REAL_CST_PTR (other));
+    }
+
+  void plus (mult_factor &other)
+    {
+      gcc_checking_assert (is_float == other.is_float);
+      if (!is_float)
+	cst = wi::add (cst, other.cst);
+      else
+	real_arithmetic (&fcst, PLUS_EXPR, &fcst,
+			 &other.fcst);
+    }
+
+  void neg ()
+    {
+      if (!is_float)
+	cst = wi::neg (cst);
+      else
+	fcst = real_value_negate (&fcst);
+    }
+
+  bool is_one ()
+    {
+      if (!is_float)
+	return cst == wi::one (prec);
+      else
+	return real_equal (&fcst, &dconst1);
+    }
+
+  bool is_m1 ()
+    {
+      if (!is_float)
+	return cst == wi::minus_one (prec);
+      else
+	return real_equal (&fcst, &dconstm1);
+    }
+
+  bool maybe_expensive ()
+    {
+      if (!is_float)
+	return constant_maybe_expensive (cst);
+      else
+	return constant_maybe_expensive (fcst);
+    }
+
+  tree to_tree ()
+    {
+      if (!is_float)
+	return wide_int_to_tree (type, cst);
+      else
+	{
+	  REAL_VALUE_TYPE r;
+	  real_convert (&r, TYPE_MODE (type), &fcst);
+	  return build_real (type, r);
+	}
+    }
+
+  mult_factor (tree t)
+    {
+      type = TREE_TYPE (t);
+      prec = TYPE_PRECISION (type);
+      if (INTEGRAL_TYPE_P (type))
+	{
+	  is_float = false;
+	  cst = wi::to_wide (t);
+	  fcst = dconst0;
+	}
+      else if (SCALAR_FLOAT_TYPE_P (type))
+	{
+	  is_float = true;
+	  fcst = TREE_REAL_CST (t);
+	}
+      else
+	gcc_unreachable ();
+    }
+
+  mult_factor ()
+    : fcst (dconst0), prec (0), type (NULL_TREE), is_float (false) {}
+};
+
 struct plus_mult_tree_state
 {
   /* Stats for costing.  */
@@ -1888,21 +2030,21 @@ struct plus_mult_tree_state
   /* Operands of the cst/plus/mult sequence in program order.  */
   auto_vec<tree> ops;
   /* Maps SSA names to their multiplicative factors.  */
-  hash_map<tree, wide_int> op_factor_map;
+  hash_map<tree, mult_factor> op_factor_map;
 
   /* Constant factor without SSA name.  */
-  wide_int cst;
+  mult_factor cst;
 
   /* Visited statements.  */
   auto_vec<gimple *> visited;
 
-  plus_mult_tree_state (HOST_WIDE_INT prec)
+  plus_mult_tree_state (tree type)
     : mults_before (0), mults_after (0),
       plus_before (0), plus_after (0),
       maybe_expensive_constants_before (0),
       maybe_expensive_constants_after (0),
       changed (false),
-      cst (wi::zero (prec)) {}
+      cst (build_zero_cst (type)) {}
 };
 
 /* Recursively walk a tree of additions, products, as well as constants
@@ -1916,19 +2058,18 @@ struct plus_mult_tree_state
    of is passed in LOOP.  */
 
 static void
-linearize_plus_mult_tree (tree op, wide_int factor,
+linearize_plus_mult_tree (tree op, mult_factor factor,
 			  struct plus_mult_tree_state *state,
 			  class loop *loop)
 {
   /* Add constants to the "global" constant.  */
-  if (TREE_CODE (op) == INTEGER_CST)
+  if (TREE_CODE (op) == INTEGER_CST || TREE_CODE (op) == REAL_CST)
     {
-      wide_int wcst = wi::to_wide (op);
-      if (constant_maybe_expensive (wcst))
+      if (constant_maybe_expensive (op))
 	state->maybe_expensive_constants_before++;
-      state->cst += wi::mul (wcst, factor);
-      if (state->cst != wi::zero (state->cst.get_precision ())
-	  || factor != wi::one (state->cst.get_precision ()))
+      factor.mul (op);
+      state->cst.plus (factor);
+      if (!state->cst.is_zero () || !factor.is_one ())
 	state->changed = true;
       return;
     }
@@ -1937,7 +2078,9 @@ linearize_plus_mult_tree (tree op, wide_int factor,
   if (TREE_CODE (op) == SSA_NAME
       && can_reassociate_op_p (op)
       && has_single_use (op)
-      && TYPE_OVERFLOW_WRAPS (TREE_TYPE (op)))
+      && ((INTEGRAL_TYPE_P (TREE_TYPE (op))
+	   && TYPE_OVERFLOW_WRAPS (TREE_TYPE (op)))
+	  || SCALAR_FLOAT_TYPE_P (TREE_TYPE (op))))
     {
       gimple *stmt = SSA_NAME_DEF_STMT (op);
       basic_block bb;
@@ -1953,13 +2096,14 @@ linearize_plus_mult_tree (tree op, wide_int factor,
 	  if (can_reassociate_op_p (rhs1)
 	      && (!rhs2 || can_reassociate_op_p (rhs2)))
 	    {
-	      if (opcode == MULT_EXPR && TREE_CODE (rhs2) == INTEGER_CST)
+	      if (opcode == MULT_EXPR
+		  && (TREE_CODE (rhs2) == INTEGER_CST
+		      || TREE_CODE (rhs2) == REAL_CST))
 		{
 		  state->mults_before++;
 		  state->visited.safe_push (stmt);
-		  wide_int wcst = wi::to_wide (rhs2);
-		  linearize_plus_mult_tree (rhs1, wi::mul (wcst, factor),
-					    state, loop);
+		  factor.mul (rhs2);
+		  linearize_plus_mult_tree (rhs1, factor, state, loop);
 		  return;
 		}
 	      else if (opcode == PLUS_EXPR)
@@ -1973,10 +2117,8 @@ linearize_plus_mult_tree (tree op, wide_int factor,
 	      else if (opcode == NEGATE_EXPR)
 		{
 		  state->visited.safe_push (stmt);
-		  wide_int negated
-		    = wi::mul (wi::minus_one (state->cst.get_precision ()),
-			       factor);
-		  linearize_plus_mult_tree (rhs1, negated, state, loop);
+		  factor.neg ();
+		  linearize_plus_mult_tree (rhs1, factor, state, loop);
 		  return;
 		}
 	    }
@@ -1986,8 +2128,12 @@ linearize_plus_mult_tree (tree op, wide_int factor,
   /* We have a leaf.  If we have seen it before, adjust its factor.
      Otherwise, add it to the cache.  */
   bool existed;
-  wide_int &slot = state->op_factor_map.get_or_insert (op, &existed);
-  slot = existed ? slot + factor : factor;
+  mult_factor &slot = state->op_factor_map.get_or_insert (op, &existed);
+  if (existed)
+    slot.plus (factor);
+  else
+    slot = factor;
+
   if (!existed)
     state->ops.safe_push (op);
   else
@@ -2006,7 +2152,6 @@ expand_plus_mult_tree (gimple *stmt, plus_mult_tree_state *state)
 
   tree old_lhs = gimple_get_lhs (stmt);
   tree type = TREE_TYPE (old_lhs);
-  wide_int zero = wi::zero (state->cst.get_precision ());
 
   gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
   location_t loc = gimple_location (stmt);
@@ -2015,10 +2160,12 @@ expand_plus_mult_tree (gimple *stmt, plus_mult_tree_state *state)
   auto_vec<tree> sum_factors;
   for (tree op : state->ops)
     {
-      wide_int factor = *state->op_factor_map.get (op);
-      if (factor == zero)
+      mult_factor &factor = *state->op_factor_map.get (op);
+
+      if (factor.is_zero ())
 	continue;
-      if (factor == wi::minus_one (factor.get_precision ()))
+
+      if (factor.is_m1 ())
 	{
 	  tree nlhs = make_ssa_name (type);
 	  gimple *neg = gimple_build_assign (nlhs, NEGATE_EXPR, op);
@@ -2028,9 +2175,9 @@ expand_plus_mult_tree (gimple *stmt, plus_mult_tree_state *state)
 	  gimple_set_location (neg, loc);
 	  sum_factors.safe_push (gimple_get_lhs (neg));
 	}
-      else if (factor != wi::one (factor.get_precision ()))
+      else if (!factor.is_one ())
 	{
-	  tree cst = wide_int_to_tree (type, factor);
+	  tree cst = factor.to_tree ();
 	  tree nlhs = make_ssa_name (type);
 	  gimple *prod = gimple_build_assign (nlhs, MULT_EXPR, op, cst);
 	  gsi_insert_before (&gsi, prod, GSI_SAME_STMT);
@@ -2044,9 +2191,9 @@ expand_plus_mult_tree (gimple *stmt, plus_mult_tree_state *state)
     }
 
   /* Include the constant factor if there is one.  */
-  if (state->cst != zero)
+  if (!state->cst.is_zero ())
     {
-      tree tcst = wide_int_to_tree (type, state->cst);
+      tree tcst = state->cst.to_tree ();
       sum_factors.safe_push (tcst);
     }
 
@@ -2054,7 +2201,7 @@ expand_plus_mult_tree (gimple *stmt, plus_mult_tree_state *state)
   /* Nothing to be done, zero the old LHS.  */
   if (!n)
     {
-      gimple_assign_set_rhs_from_tree (&gsi, wide_int_to_tree (type, zero));
+      gimple_assign_set_rhs_from_tree (&gsi, build_zero_cst (type));
       update_stmt (stmt);
     }
   /* If we only have one factor, just assign it to the old LHS.  */
@@ -2115,21 +2262,22 @@ gather_plus_mult_tree_stats (struct plus_mult_tree_state *state)
   gcc_checking_assert (state->plus_after == 0);
   gcc_checking_assert (state->mults_after == 0);
 
-  HOST_WIDE_INT prec = state->cst.get_precision ();
-  if (constant_maybe_expensive (state->cst))
+  if (state->cst.maybe_expensive ())
     state->maybe_expensive_constants_after = 1;
+
   for (auto it : state->op_factor_map)
     {
-      if (constant_maybe_expensive (it.second))
+      if (it.second.maybe_expensive ())
 	state->maybe_expensive_constants_after++;
-      if (it.second != wi::zero (prec)
-	  && it.second != wi::one (prec)
-	  && it.second != wi::minus_one (prec))
+      if (!it.second.is_zero ()
+	  && !it.second.is_one ()
+	  && !it.second.is_m1 ())
 	state->mults_after++;
-      if (it.second != wi::zero (prec))
+      if (!it.second.is_zero ())
 	state->plus_after++;
     }
-  if (state->cst != wi::zero (prec))
+
+  if (!state->cst.is_zero ())
     state->plus_after++;
   state->plus_after--;
 }
@@ -2172,14 +2320,19 @@ static bool
 rewrite_plus_mult_tree (gimple *stmt)
 {
   tree lhs = gimple_get_lhs (stmt);
-  gcc_checking_assert (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+  gcc_checking_assert ((INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+			|| (SCALAR_FLOAT_TYPE_P (TREE_TYPE (lhs))
+			    && !HONOR_NANS (TREE_TYPE (lhs))
+			    && !HONOR_SIGNED_ZEROS (TREE_TYPE (lhs))))
 		       && has_single_use (lhs));
 
-  HOST_WIDE_INT prec = TYPE_PRECISION (TREE_TYPE (lhs));
-  plus_mult_tree_state state (prec);
+  tree type = TREE_TYPE (lhs);
+  plus_mult_tree_state state (type);
+
+  mult_factor one (build_one_cst (type));
 
   /* Linearize the tree and gather stats about it.  */
-  linearize_plus_mult_tree (lhs, wi::one (prec), &state,
+  linearize_plus_mult_tree (lhs, one, &state,
 			    loop_containing_stmt (stmt));
   if (!state.changed)
     return false;
@@ -7506,7 +7659,10 @@ reassociate_bb (basic_block bb)
 		 sum = cst + cst1 * A + cst2 * B + ...
 		 do so.  While at it, remove 0-factor elements.  */
 	      if ((rhs_code == PLUS_EXPR || rhs_code == MULT_EXPR)
-		  && INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+		  && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+		      || (SCALAR_FLOAT_TYPE_P (TREE_TYPE (lhs))
+			  && !HONOR_NANS (TREE_TYPE (lhs))
+			  && !HONOR_SIGNED_ZEROS (TREE_TYPE (lhs))))
 		  && has_single_use (lhs)
 		  && !type_can_overflow)
 		{
-- 
2.54.0