[PATCH 1/5] reassoc: Linearize mixed plus/mult trees.

From: Robin Dapp <[email protected]>

This patch adds a second on-the-side linearization method to reassoc.
Regular linearization only ever descends into tree with the same
operand with the exception of depth-1 cases like
 a + b * b * b + c + d * d * d.

Here, however, we are after cases like
 a + 3 * (a + b + 1) + 2,
turning them into
 4 * a + 3 * b + 3.

As long as we only permit multiplications with constants, this allows us
to reduce the number of multiplications in the tree as well as confound
individual constants (that wouldn't be reachable otherwise) into one.

The approach actually builds upon something I started over two years
ago for PR113583 where a similar tree is seen in lbm's hot loop.
That one is a floating-point example, though, and this patch only starts
with unsigned integers.  Back when I first started, my idea was to
extend linearize_expr_tree and allow it to descend into the trees we are
interested here.  My old approach leads to significantly more complicated
handling down-stream and I was never happy with it.  On top, costing was
complicated.

Once I painfully realized my backprop patch doesn't help with PR122209
I got back at the problem from a reassoc point of view.
This lead me to a dedicated linearization approach just for mixed plus/mult
trees.  It can be costed separately and serves as a preprocessing step for
the regular reassoc handling.

One costing issue is that combining multiplicative constants apriori
inhibits strength reduction.  Consider (slsr-5.c):

  a1 = 2 * s;
  x1 = c + a1;
  a2 = 4 * s;
  x2 = c + a2;
  a3 = 6 * s;
  x3 = c + a3;

where the multiplies are mostly simple shifts that targets have
shift/add instructions for.  We now conflate S's
factors to
  _10 = 12 * s
where 12 is no simple shift.  We need to decompose 12 into shifts and
adds again.  I didn't observe cases where we do actually worse now but
it can happen that we conflate factors, just to decompose them again.

Natural follow ups to this patch are floating-point support as well as
signed int support.  For the latter (i.e. for PR122209 to be solved),
a simple approach is to use global range information and check
each step for possible overflow.  This fits in nicely with the
linearization approach but makes the code less clean.  Therefore I'm
deferring it to a separate patch.

gcc/ChangeLog:

	* tree-ssa-reassoc.cc (constant_maybe_expensive): New function.
	(struct plus_mult_tree_state): Ditto.
	(linearize_plus_mult_tree): Ditto.
	(expand_plus_mult_tree): Ditto.
	(gather_plus_mult_tree_stats): Ditto.
	(cost_plus_mult_tree): Ditto.
	(rewrite_plus_mult_tree): Ditto.
	(reassociate_bb): Call rewrite_plus_mult_tree.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/reassoc-45.c: Adjust test expectation.
	* gcc.dg/tree-ssa/reassoc-52.c: New test.
	* gcc.dg/tree-ssa/reassoc-53.c: New test.
---
 gcc/testsuite/gcc.dg/tree-ssa/reassoc-45.c |   4 +-
 gcc/testsuite/gcc.dg/tree-ssa/reassoc-52.c |  49 +++
 gcc/testsuite/gcc.dg/tree-ssa/reassoc-53.c |  30 ++
 gcc/tree-ssa-reassoc.cc                    | 386 ++++++++++++++++++++-
 4 files changed, 466 insertions(+), 3 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/reassoc-52.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/reassoc-53.c

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-45.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-45.c
index 48f6b74e39f..312ddbd6a24 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-45.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-45.c
@@ -1,6 +1,6 @@
 /* PR/71352 */
 /* { dg-do compile } */
-/* { dg-options "-O -fdump-tree-reassoc1" } */
+/* { dg-options "-O -fdump-tree-optimized" } */
 
 unsigned a, b, c, d, e;
 
@@ -12,4 +12,4 @@ fn1 ()
 }
 
 /* Check that we factor -1 and create -(d * b + a * c).  */
-/* { dg-final { scan-tree-dump-times " = -" 1 "reassoc1" } } */
+/* { dg-final { scan-tree-dump-times " = -" 1 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-52.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-52.c
new file mode 100644
index 00000000000..5a194a8c9dd
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-52.c
@@ -0,0 +1,49 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+/* Signed and unsigned reassociation plus/mult-tree rewrite tests.
+   The signed tests are xfailed for now.  */
+
+unsigned int
+bar (unsigned int fs)
+{
+  return 3u * (fs + 1u) + 4u * (fs + 2u);
+}
+
+unsigned int
+foo1 (unsigned int fs)
+{
+  return 2u * (3u * (fs + 1u) + 4u * (fs + 2u));
+}
+
+unsigned int
+foo2 (unsigned int fs)
+{
+  return 2u * (3u * (2u * (fs + 1u) + 2u * (fs + 2u)) + fs);
+}
+
+unsigned int
+foo3 (unsigned int fs)
+{
+  unsigned int tmp = 3u * (fs + 1u);
+  return fs + 2u * (tmp + 4u) - 3u * (fs + 2u) + 5u + fs;
+}
+
+int
+foo (char fs)
+{
+  return 2 * (fs + 1) + 4 * (fs + 2);
+}
+
+int
+baz (char fs)
+{
+  return 16 * (fs + 1) + 64 * (fs + 2);
+}
+
+/* { dg-final { scan-tree-dump-times "\\* 7;" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "\\* 14;" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "\\* 26;" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "\\* 5;" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "\\* 6;" 1 "optimized" { xfail *-*-* } } } */
+/* { dg-final { scan-tree-dump-times "\\* 80;" 1 "optimized" { xfail *-*-* } } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-53.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-53.c
new file mode 100644
index 00000000000..d84625f42b5
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-53.c
@@ -0,0 +1,30 @@
+/* { dg-do compile } */
+/* { dg-additional-options "-O2 -fdump-tree-reassoc-details -fdump-tree-optimized" } */
+
+unsigned int
+foo (unsigned int t)
+{
+  t += 3 + 3 * t;
+  t &= 0xFFF;
+  t += 3 + 3 * t;
+  t &= 0xFFF;
+  t += 3 + 3 * t;
+  t &= 0xFFF;
+  t += 3 + 3 * t;
+  t &= 0xFFF;
+  t += 3 + 3 * t;
+  t &= 0xFFF;
+  t += 3 + 3 * t;
+  t &= 0xFFF;
+  t += 3 + 3 * t;
+  t &= 0xFFF;
+  t += 3 + 3 * t;
+  t &= 0xFFF;
+  t += 3 + 3 * t;
+  t &= 0xFFF;
+
+  return t;
+}
+
+/* { dg-final { scan-tree-dump "4095" "optimized" } } */
+/* { dg-final { scan-tree-dump-times "Rewriting plus/mult" 9 "reassoc1" } } */
diff --git a/gcc/tree-ssa-reassoc.cc b/gcc/tree-ssa-reassoc.cc
index dec64883891..f570c0164f4 100644
--- a/gcc/tree-ssa-reassoc.cc
+++ b/gcc/tree-ssa-reassoc.cc
@@ -1856,6 +1856,369 @@ undistribute_ops_list (enum tree_code opcode,
   return changed;
 }
 
+/* Simplistic function to estimate whether a constant might be expensive to
+   materialize.  */
+static inline bool
+constant_maybe_expensive (wide_int cst)
+{
+  return wi::gts_p (wi::abs (cst), 2048) && wi::popcount (cst) > 1;
+}
+
+static inline bool
+constant_maybe_expensive (REAL_VALUE_TYPE)
+{
+  return false;
+}
+
+struct plus_mult_tree_state
+{
+  /* Stats for costing.  */
+  int mults_before;
+  int mults_after;
+  int plus_before;
+  int plus_after;
+  int maybe_expensive_constants_before;
+  int maybe_expensive_constants_after;
+
+  /* True if we made any change at all.  The change can still
+     be considered not worthwhile according to costing.  */
+  bool changed;
+
+  /* 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;
+
+  /* Constant factor without SSA name.  */
+  wide_int cst;
+
+  /* Visited statements.  */
+  auto_vec<gimple *> visited;
+
+  plus_mult_tree_state (HOST_WIDE_INT prec)
+    : 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)) {}
+};
+
+/* Recursively walk a tree of additions, products, as well as constants
+   and negates, collecting constant coefficients and storing them in a
+   cache inside STATE.  The idea is to descend into (A + B), A * cst, and
+   -A while keeping track of the constant factor for each variable.
+   That way we can condense all multiplicative factors of the same SSA
+   name into just one.
+   The linearization starts at OP with a multiplicative factor FACTOR.
+   Bookkeeping is done in STATE.  The loop the initial statement was part
+   of is passed in LOOP.  */
+
+static void
+linearize_plus_mult_tree (tree op, wide_int factor,
+			  struct plus_mult_tree_state *state,
+			  class loop *loop)
+{
+  /* Add constants to the "global" constant.  */
+  if (TREE_CODE (op) == INTEGER_CST)
+    {
+      wide_int wcst = wi::to_wide (op);
+      if (constant_maybe_expensive (wcst))
+	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 ()))
+	state->changed = true;
+      return;
+    }
+
+  /* Check if we can descend further.  */
+  if (TREE_CODE (op) == SSA_NAME
+      && can_reassociate_op_p (op)
+      && has_single_use (op)
+      && TYPE_OVERFLOW_WRAPS (TREE_TYPE (op)))
+    {
+      gimple *stmt = SSA_NAME_DEF_STMT (op);
+      basic_block bb;
+      if (is_gimple_assign (stmt)
+	  && (bb = gimple_bb (stmt))
+	  && flow_bb_inside_loop_p (loop, bb))
+	{
+	  enum tree_code opcode = gimple_assign_rhs_code (stmt);
+	  tree rhs1 = gimple_assign_rhs1 (stmt);
+	  tree rhs2 = gimple_assign_rhs2 (stmt);
+
+	  /* Descend into mult, plus, neg, adjusting FACTOR.  */
+	  if (can_reassociate_op_p (rhs1)
+	      && (!rhs2 || can_reassociate_op_p (rhs2)))
+	    {
+	      if (opcode == MULT_EXPR && TREE_CODE (rhs2) == INTEGER_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);
+		  return;
+		}
+	      else if (opcode == PLUS_EXPR)
+		{
+		  state->plus_before++;
+		  state->visited.safe_push (stmt);
+		  linearize_plus_mult_tree (rhs1, factor, state, loop);
+		  linearize_plus_mult_tree (rhs2, factor, state, loop);
+		  return;
+		}
+	      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);
+		  return;
+		}
+	    }
+	}
+    }
+
+  /* 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;
+  if (!existed)
+    state->ops.safe_push (op);
+  else
+    state->changed = true;
+}
+
+/* Multiply out/expand a linearized plus/mult tree starting at STMT.
+   The linearization is described by the hash map in STATE as well as
+   the constant factor CST.  Return true if we performed the expansion.  */
+
+static bool
+expand_plus_mult_tree (gimple *stmt, plus_mult_tree_state *state)
+{
+  if (!state->op_factor_map.elements ())
+    return false;
+
+  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);
+
+  /* Prepare all the multiplicative factors.  */
+  auto_vec<tree> sum_factors;
+  for (tree op : state->ops)
+    {
+      wide_int factor = *state->op_factor_map.get (op);
+      if (factor == zero)
+	continue;
+      if (factor == wi::minus_one (factor.get_precision ()))
+	{
+	  tree nlhs = make_ssa_name (type);
+	  gimple *neg = gimple_build_assign (nlhs, NEGATE_EXPR, op);
+	  gsi_insert_before (&gsi, neg, GSI_SAME_STMT);
+	  gimple_set_uid (neg, gimple_uid (stmt));
+	  gimple_set_visited (neg, true);
+	  gimple_set_location (neg, loc);
+	  sum_factors.safe_push (gimple_get_lhs (neg));
+	}
+      else if (factor != wi::one (factor.get_precision ()))
+	{
+	  tree cst = wide_int_to_tree (type, factor);
+	  tree nlhs = make_ssa_name (type);
+	  gimple *prod = gimple_build_assign (nlhs, MULT_EXPR, op, cst);
+	  gsi_insert_before (&gsi, prod, GSI_SAME_STMT);
+	  gimple_set_uid (prod, gimple_uid (stmt));
+	  gimple_set_visited (prod, true);
+	  gimple_set_location (prod, loc);
+	  sum_factors.safe_push (gimple_get_lhs (prod));
+	}
+      else
+	  sum_factors.safe_push (op);
+    }
+
+  /* Include the constant factor if there is one.  */
+  if (state->cst != zero)
+    {
+      tree tcst = wide_int_to_tree (type, state->cst);
+      sum_factors.safe_push (tcst);
+    }
+
+  int n = sum_factors.length ();
+  /* Nothing to be done, zero the old LHS.  */
+  if (!n)
+    {
+      gimple_assign_set_rhs_from_tree (&gsi, wide_int_to_tree (type, zero));
+      update_stmt (stmt);
+    }
+  /* If we only have one factor, just assign it to the old LHS.  */
+  else if (n == 1)
+    {
+      gimple_assign_set_rhs_from_tree (&gsi, sum_factors[0]);
+      update_stmt (stmt);
+    }
+  else
+    {
+      /* Otherwise start with a pair, sum it, and then successively add to the
+	 previous result.  Finally, wire the new chain up with the statement we
+	 are modifying.  */
+      tree cur_lhs;
+      tree prev_lhs;
+      if (n == 2)
+	prev_lhs = sum_factors[0];
+      else
+	{
+	  cur_lhs = make_ssa_name (type);
+	  prev_lhs = cur_lhs;
+	  gimple *first_sum = gimple_build_assign
+	    (cur_lhs, PLUS_EXPR, sum_factors[0], sum_factors[1]);
+	  gimple_set_uid (first_sum, gimple_uid (stmt));
+	  gimple_set_visited (first_sum, true);
+	  gimple_set_location (first_sum, loc);
+	  gsi_insert_before (&gsi, first_sum, GSI_SAME_STMT);
+	}
+      for (int i = 2; i < n - 1; i++)
+	{
+	  cur_lhs = make_ssa_name (type);
+	  gimple *sum = gimple_build_assign (cur_lhs, PLUS_EXPR, prev_lhs,
+					     sum_factors[i]);
+	  gimple_set_uid (sum, gimple_uid (stmt));
+	  gimple_set_visited (sum, true);
+	  gimple_set_location (sum, loc);
+	  gsi_insert_before (&gsi, sum, GSI_SAME_STMT);
+	  prev_lhs = cur_lhs;
+	}
+
+      gimple_assign_set_rhs_code (stmt, PLUS_EXPR);
+      gimple_assign_set_rhs1 (stmt, prev_lhs);
+      gimple_assign_set_rhs2 (stmt, sum_factors[n - 1]);
+      update_stmt (stmt);
+    }
+
+  return true;
+}
+
+/* Collect how many potentially expensive constants as well as how many
+   plus/mults the tree has after linearization.  Store the result in
+   STATE as well.  */
+
+static void
+gather_plus_mult_tree_stats (struct plus_mult_tree_state *state)
+{
+  gcc_checking_assert (state->maybe_expensive_constants_after == 0);
+  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))
+    state->maybe_expensive_constants_after = 1;
+  for (auto it : state->op_factor_map)
+    {
+      if (constant_maybe_expensive (it.second))
+	state->maybe_expensive_constants_after++;
+      if (it.second != wi::zero (prec)
+	  && it.second != wi::one (prec)
+	  && it.second != wi::minus_one (prec))
+	state->mults_after++;
+      if (it.second != wi::zero (prec))
+	state->plus_after++;
+    }
+  if (state->cst != wi::zero (prec))
+    state->plus_after++;
+  state->plus_after--;
+}
+
+/* Perform basic cost analysis on the stats of a plus/mult tree linearization
+   stored in STATE.  Return true if the costs seem worthwhile.  */
+
+static bool
+cost_plus_mult_tree (plus_mult_tree_state *state)
+{
+  bool worthwhile;
+  bool no_new_expensive_constants
+    = state->maybe_expensive_constants_after
+    <= state->maybe_expensive_constants_before;
+  if (state->mults_after > state->mults_before)
+    worthwhile = false;
+  else if (state->mults_after < state->mults_before)
+    worthwhile = true;
+  else if (state->plus_after < state->plus_before)
+    worthwhile = no_new_expensive_constants;
+  else
+    worthwhile = false;
+  return worthwhile;
+}
+
+/* Try to rewrite/expand a tree consisting of additions, multiplications
+   by constants, and negates like
+     a + 3 * (a + b + 1) + 2
+   into
+     4 * a + 3 * b + 5.
+   This helps getting rid of multiplications and with gathering constants that
+   would stay hidden with our regular linearization flow which only linearizes
+   trees with the same operand.  After expanding the tree, hopefully exposing
+   more optimization opportunities, the resulting gimple should be linearized
+   in the conventional way in order to be optimized.
+   STMT is the gimple statement to start at.
+   Return true if we expanded the tree and false otherwise.  */
+
+static bool
+rewrite_plus_mult_tree (gimple *stmt)
+{
+  tree lhs = gimple_get_lhs (stmt);
+  gcc_checking_assert (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+		       && has_single_use (lhs));
+
+  HOST_WIDE_INT prec = TYPE_PRECISION (TREE_TYPE (lhs));
+  plus_mult_tree_state state (prec);
+
+  /* Linearize the tree and gather stats about it.  */
+  linearize_plus_mult_tree (lhs, wi::one (prec), &state,
+			    loop_containing_stmt (stmt));
+  if (!state.changed)
+    return false;
+
+  gather_plus_mult_tree_stats (&state);
+
+  /* Check if it's worthwhile to follow through with the expansion.  */
+  bool worthwhile = cost_plus_mult_tree (&state);
+
+  if (!worthwhile)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "Not rewriting plus/mult tree at ");
+	  print_generic_expr (dump_file, lhs);
+	  fprintf (dump_file,  ": not worthwhile.\n");
+	}
+      return false;
+    }
+  else
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file,
+		   "Rewriting plus/mult tree at ");
+	  print_generic_expr (dump_file, lhs);
+	  fprintf (dump_file, "\n");
+	}
+
+      for (auto it : state.visited)
+	gimple_set_visited (it, true);
+
+      /* Perform the actual expansion.  The resulting gimple
+	 is supposed to be linearized conventionally afterwards.  */
+      return expand_plus_mult_tree (stmt, &state);
+    }
+
+  return false;
+}
+
 /* Pair to hold the information of one specific VECTOR_TYPE SSA_NAME:
    first: element index for each relevant BIT_FIELD_REF.
    second: the index of vec ops* for each relevant BIT_FIELD_REF.  */
@@ -7047,10 +7410,31 @@ reassociate_bb (basic_block bb)
 		continue;
 
 	      gimple_set_visited (stmt, true);
+
+	      /* If we can rewrite to a sum of constant-factor elements like
+		 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))
+		  && has_single_use (lhs))
+		{
+		  if (rewrite_plus_mult_tree (stmt))
+		    {
+		      /* If there's only one factor left or everything was
+			 zeroed out, nothing left to do here.  */
+		      if (gimple_assign_rhs_class (stmt) == GIMPLE_SINGLE_RHS)
+			continue;
+
+		      /* We linearized to a PLUS sequence, adjust the code.  */
+		      rhs_code = PLUS_EXPR;
+		    }
+		}
+
 	      linearize_expr_tree (&ops, stmt, true, true);
-	      ops.qsort (sort_by_operand_rank);
 	      int orig_len = ops.length ();
+	      ops.qsort (sort_by_operand_rank);
 	      optimize_ops_list (rhs_code, &ops);
+
 	      if (undistribute_ops_list (rhs_code, &ops,
 					 loop_containing_stmt (stmt)))
 		{
-- 
2.54.0