From: Lili Cui <lili.cui@intel.com>
Add a param for the chain with FMA in reassoc pass to make it more friendly to
the fma pass later. First to detect if this chain has ability to
generate more than 2 FMAs,if yes and param_reassoc_max_chain_length_with_fma
is enabled, We will rearrange the ops so that they can be combined into more
FMAs. When the chain length exceeds param_reassoc_max_chain_length_with_fma,
build parallel chains according to given association width and try to keep FMA
opportunity as much as possible.
TEST1:
float
foo (float a, float b, float c, float d, float *e)
{
return *e + a * b + c * d ;
}
For -Ofast -march=icelake-server GCC generates:
vmulss %xmm3, %xmm2, %xmm2
vfmadd132ss %xmm1, %xmm2, %xmm0
vaddss (%rdi), %xmm0, %xmm0
ret
with "--param=reassoc-max-chain-length-with-fma=3" GCC generates:
vfmadd213ss (%rdi), %xmm1, %xmm0
vfmadd231ss %xmm2, %xmm3, %xmm0
ret
gcc/ChangeLog:
PR gcc/98350
* params.opt (reassoc-max-fma-chain-length): New param.
* tree-ssa-reassoc.cc
(rewrite_expr_tree_parallel_for_fma): New.
(rank_ops_for_fma): Ditto.
(reassociate_bb): Handle new function.
gcc/testsuite/ChangeLog:
PR gcc/98350
* gcc.dg/pr98350-1.c: New test.
* gcc.dg/pr98350-2.c: Ditto.
---
gcc/params.opt | 4 +
gcc/testsuite/gcc.dg/pr98350-1.c | 31 +++++
gcc/testsuite/gcc.dg/pr98350-2.c | 17 +++
gcc/tree-ssa-reassoc.cc | 226 ++++++++++++++++++++++++++++---
4 files changed, 262 insertions(+), 16 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/pr98350-1.c
create mode 100644 gcc/testsuite/gcc.dg/pr98350-2.c
@@ -1182,4 +1182,8 @@ The maximum factor which the loop vectorizer applies to the cost of statements i
Common Joined UInteger Var(param_vect_induction_float) Init(1) IntegerRange(0, 1) Param Optimization
Enable loop vectorization of floating point inductions.
+-param=reassoc-max-chain-length-with-fma=
+Common Joined UInteger Var(param_reassoc_max_chain_length_with_fma) Init(1) IntegerRange(1, 65536) Param Optimization
+The maximum chain length with fma considered in reassociation pass.
+
; This comment is to ensure we retain the blank line above.
new file mode 100644
@@ -0,0 +1,31 @@
+/* { dg-do compile } */
+/* { dg-options "-Ofast -mfpmath=sse -mfma --param=reassoc-max-chain-length-with-fma=8 -Wno-attributes " } */
+
+/* Test that the compiler properly optimizes multiply and add
+ to generate more FMA instructions. */
+#define N 1024
+double a[N];
+double b[N];
+double c[N];
+double d[N];
+double e[N];
+double f[N];
+double g[N];
+double h[N];
+double j[N];
+double k[N];
+double l[N];
+double m[N];
+double o[N];
+double p[N];
+
+
+void
+foo (void)
+{
+ for (int i = 0; i < N; i++)
+ {
+ a[i] += b[i] * c[i] + d[i] * e[i] + f[i] * g[i] + h[i] * j[i] + k[i] * l[i] + m[i]* o[i] + p[i];
+ }
+}
+/* { dg-final { scan-assembler-times "vfm" 6 } } */
new file mode 100644
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-Ofast -mfpmath=sse -mfma --param=reassoc-max-chain-length-with-fma=6 -Wno-attributes " } */
+
+/* Test that the compiler properly build parallel chains according to given
+ association width and try to keep FMA opportunity as much as possible. */
+#define N 33
+double a[N];
+
+void
+foo (void)
+{
+ a[32] = a[0] *a[1] + a[2] * a[3] + a[4] * a[5] + a[6] * a[7] + a[8] * a[9]
+ + a[10] * a[11] + a[12] * a[13] + a[14] * a[15] + a[16] * a[17]
+ + a[18] * a[19] + a[20] * a[21] + a[22] * a[23] + a[24] + a[25]
+ + a[26] + a[27] + a[28] + a[29] + a[30] + a[31];
+}
+/* { dg-final { scan-assembler-times "vfm" 12 } } */
@@ -54,6 +54,7 @@ along with GCC; see the file COPYING3. If not see
#include "tree-ssa-reassoc.h"
#include "tree-ssa-math-opts.h"
#include "gimple-range.h"
+#include "internal-fn.h"
/* This is a simple global reassociation pass. It is, in part, based
on the LLVM pass of the same name (They do some things more/less
@@ -5468,6 +5469,114 @@ get_reassociation_width (int ops_num, enum tree_code opc,
return width;
}
+/* Rewrite statements with dependency chain with regard to the chance to
+ generate FMA. When the dependency chain length exceeds
+ param_max_reassoc_chain_length_with_fma, build parallel chains according to
+ given association width and try to keep fma opportunity as much as possible.
+ E.g.
+ e + f + g + a * b + c * d;
+
+ ssa1 = e + f;
+ ssa2 = g + a * b;
+ ssa3 = ssa1 + c * d;
+ ssa4 = ssa2 + ssa3;
+
+ This reassociation approach preserves the chance of fma generation as much
+ as possible. */
+static void
+rewrite_expr_tree_parallel_for_fma (gassign *stmt, int width,
+ const vec<operand_entry *> &ops)
+{
+ enum tree_code opcode = gimple_assign_rhs_code (stmt);
+ int op_num = ops.length ();
+ gcc_assert (op_num > 0);
+ int stmt_num = op_num - 1;
+ gimple **stmts = XALLOCAVEC (gimple *, stmt_num);
+ int op_index = op_num - 1;
+ int width_count = width;
+ int i = 0, j = 0;
+ tree tmp_op[2], op1;
+ operand_entry *oe;
+ gimple *stmt1 = NULL;
+ tree last_rhs1 = gimple_assign_rhs1 (stmt);
+
+ /* We start expression rewriting from the top statements.
+ So, in this loop we create a full list of statements
+ we will work with. */
+ stmts[stmt_num - 1] = stmt;
+ for (i = stmt_num - 2; i >= 0; i--)
+ stmts[i] = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmts[i+1]));
+
+ /* Build parallel FMA dependency chain according to width. */
+ for (i = 0; i < width; i++)
+ {
+ for (j = 0; j < 2; j++)
+ {
+ oe = ops[op_index--];
+ tmp_op[j] = oe->op;
+ stmt1 = oe->stmt_to_insert;
+ if (stmt1)
+ insert_stmt_before_use (stmts[i], stmt1);
+ stmt1 = NULL;
+ }
+ stmts[i] = build_and_add_sum (TREE_TYPE (last_rhs1), tmp_op[1], tmp_op[0], opcode);
+ gimple_set_visited (stmts[i], true);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " into ");
+ print_gimple_stmt (dump_file, stmts[i], 0);
+ }
+ }
+
+ for (i = width; i < stmt_num; i++)
+ {
+ /* We keep original statement only for the last one. All others are
+ recreated. */
+ if ( op_index < 0)
+ {
+ if (width_count == 2)
+ {
+
+ gimple_assign_set_rhs1 (stmts[i], gimple_assign_lhs (stmts[i-1]));
+ gimple_assign_set_rhs2 (stmts[i], gimple_assign_lhs (stmts[i-2]));
+ }
+ else
+ {
+
+ stmts[i] =
+ build_and_add_sum (TREE_TYPE (last_rhs1),
+ gimple_assign_lhs (stmts[i-width_count]),
+ gimple_assign_lhs (stmts[i-width_count+1]),
+ opcode);
+ width_count--;
+ }
+ update_stmt (stmts[i]);
+ }
+ else
+ {
+ oe = ops[op_index--];
+ op1 = oe->op;
+ stmt1 = oe->stmt_to_insert;
+ if (stmt1)
+ insert_stmt_before_use (stmts[i], stmt1);
+ stmt1 = NULL;
+ stmts[i] = build_and_add_sum (TREE_TYPE (last_rhs1),
+ gimple_assign_lhs (stmts[i-width]),
+ op1,
+ opcode);
+ gimple_set_visited (stmts[i], true);
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " into ");
+ print_gimple_stmt (dump_file, stmts[i], 0);
+ }
+ }
+ remove_visited_stmt_chain (last_rhs1);
+}
+
/* Recursively rewrite our linearized statements so that the operators
match those in OPS[OPINDEX], putting the computation in rank
order and trying to allow operations to be executed in
@@ -6649,6 +6758,62 @@ transform_stmt_to_multiply (gimple_stmt_iterator *gsi, gimple *stmt,
}
}
+/* Rearrange ops to generate more FMA when the chain may has more than 2 fmas.
+ Putting ops that not def from mult in front can generate more fma.
+ E.g.
+ a * b + c * d + e generates:
+
+ _4 = c_9(D) * d_10(D);
+ _12 = .FMA (a_7(D), b_8(D), _4);
+ _11 = e_6(D) + _12;
+
+ Rtearrange ops to -> e + a * b + c * d generates:
+
+ _4 = .FMA (c_7(D), d_8(D), _3);
+ _11 = .FMA (a_5(D), b_6(D), _4);
+ */
+static bool
+rank_ops_for_fma (vec<operand_entry *> *ops)
+{
+ operand_entry *oe;
+ unsigned int i;
+ auto_vec<operand_entry *> ops_mult;
+ auto_vec<operand_entry *> ops_others;
+
+ FOR_EACH_VEC_ELT (*ops, i, oe)
+ {
+ if (TREE_CODE (oe->op) == SSA_NAME)
+ {
+ gimple *def_stmt = SSA_NAME_DEF_STMT (oe->op);
+ if (is_gimple_assign (def_stmt)
+ && gimple_assign_rhs_code (def_stmt) == MULT_EXPR)
+ ops_mult.safe_push (oe);
+ else
+ ops_others.safe_push (oe);
+ }
+ else
+ ops_others.safe_push (oe);
+ }
+ /* When ops_mult.length == 2, like the following case,
+
+ a * b + c * d + e.
+
+ we need to rearrange the ops.
+
+ Putting ops that not def from mult in front can generate more fmas. */
+ if (ops_mult.length () >= 2)
+ {
+ /* If all ops are defined with mult, we don't need to rearrange them. */
+ if (ops_mult.length () != ops->length ())
+ {
+ ops->truncate (0);
+ ops->splice (ops_mult);
+ ops->splice (ops_others);
+ }
+ return true;
+ }
+ return false;
+}
/* Reassociate expressions in basic block BB and its post-dominator as
children.
@@ -6813,6 +6978,7 @@ reassociate_bb (basic_block bb)
machine_mode mode = TYPE_MODE (TREE_TYPE (lhs));
int ops_num = ops.length ();
int width;
+ bool keep_fma_chain = false;
/* For binary bit operations, if there are at least 3
operands and the last operand in OPS is a constant,
@@ -6826,36 +6992,64 @@ reassociate_bb (basic_block bb)
&& TREE_CODE (ops.last ()->op) == INTEGER_CST)
std::swap (*ops[0], *ops[ops_num - 1]);
+ optimization_type opt_type = bb_optimization_type (bb);
+
+ /* When enabling param_reassoc_max_chain_length_with_fma to
+ keep the chain with fma, rank_ops_for_fma will detect if
+ the chain has fmas and if so it will rearrange the ops. */
+ if (param_reassoc_max_chain_length_with_fma > 1
+ && direct_internal_fn_supported_p (IFN_FMA,
+ TREE_TYPE (lhs),
+ opt_type)
+ && (rhs_code == PLUS_EXPR || rhs_code == MINUS_EXPR))
+ {
+ keep_fma_chain = rank_ops_for_fma(&ops);
+ }
+
+ int len = ops.length ();
/* Only rewrite the expression tree to parallel in the
last reassoc pass to avoid useless work back-and-forth
with initial linearization. */
if (!reassoc_insert_powi_p
- && ops.length () > 3
+ && len > 3
+ && (!keep_fma_chain
+ || (keep_fma_chain
+ && len > param_reassoc_max_chain_length_with_fma))
&& (width = get_reassociation_width (ops_num, rhs_code,
- mode)) > 1)
+ mode)) > 1)
{
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file,
- "Width = %d was chosen for reassociation\n",
- width);
- rewrite_expr_tree_parallel (as_a <gassign *> (stmt),
- width, ops);
+ if (keep_fma_chain)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file,
+ "Break chain len = %d into width for FMA\n",
+ len);
+ rewrite_expr_tree_parallel_for_fma
+ (as_a <gassign *> (stmt), width, ops);
+ }
+ else
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file,
+ "Width = %d was chosen for reassociation\n",
+ width);
+ rewrite_expr_tree_parallel (as_a <gassign *> (stmt),
+ width, ops);
+ }
}
else
- {
- /* When there are three operands left, we want
- to make sure the ones that get the double
- binary op are chosen wisely. */
- int len = ops.length ();
- if (len >= 3)
+ {
+ /* When there are three operands left, we want
+ to make sure the ones that get the double
+ binary op are chosen wisely. */
+ if (len >= 3 && !keep_fma_chain)
swap_ops_for_binary_stmt (ops, len - 3);
new_lhs = rewrite_expr_tree (stmt, rhs_code, 0, ops,
powi_result != NULL
|| negate_result,
len != orig_len);
- }
-
+ }
/* If we combined some repeated factors into a
__builtin_powi call, multiply that result by the
reassociated operands. */