The example
float
f (const float *x, int n)
{
float acc = 0;
for (int i = 0; i < n; ++i)
{
float d = x[i];
if (d < 0)
acc += d;
acc += d * 3.0f;
}
return acc;
}
compiled at -Ofast fails to vectorize with
note: vect_is_simple_use: operand acc_17 = PHI <acc_13(8), 0.0(18)>,
type of def: unknown
missed: Unsupported pattern.
missed: not vectorized: unsupported use in stmt.
due to
note: Analyze phi: acc_17 = PHI <acc_13(8), 0.0(18)>
missed: reduction used in loop.
missed: Unknown def-use cycle pattern.
This is happening because before if-convert we have the following reduction:
acc_1 = PHI <acc_0, acc_2>
if (cond)
acc_2 = acc_1 + value;
and so the reduction value is updated only on some paths.
if-cvt changes this into
acc_3 = cond ? acc_2 : acc_1;
but since acc_2 itself is acc_1 + value this is actually
acc_3 = cond ? acc_1 + value : acc_1;
This is semantically sound but hides the recurrence from the vectorizer.
In principle if-cvt creates
acc_1 = PHI <0, acc_3>
acc_2 = acc_1 + value
acc_3 = cond ? acc_2 : acc_1
so the loop carried value acc_3 is inside the COND_EXPR and acc_1 is used twice
inside the same reduction. The update chain is
PHI -> PLUS -> COND_EXPR -> PHI
\--------------^
which is a problem since reduction analysis needs a single statement that
updates the loop carried accumulator.
Note that if the user supplied this form manually, if-cvt rewrites it to one of
two forms that the vectorizer can handle. It either rewrites it to COND_ADD and
this removing the PLUS + COND_EXPR or it floats out the cond_expr.
This patch does the latter, as picking COND_ADD here is premature, it forces
selection of a masked target even though the vectorizer these days can convert
the cond expr to a masked operation on its own based on costing.
Essentially we change
cond ? base + addend : base or cond ? base : base + addend
into
base + (cond ? addend : 0) or base + (cond ? 0 : addend)
this turns the recurrence into a form the vectorizer can handle.
Special care is taken to only do this when the reduction is within the same
loop and where there is no other uses of the PHI reduction but the PHI node.
i.e. the rewrite is only applied when BASE is the loop-carried reduction PHI for
the current loop and the if-converted PHI feeds the latch update for that same
reduction. This avoids changing unrelated conditional expressions or cases
where the apparent recurrence is not the loop reduction being analyzed.
Bootstrapped Regtested on aarch64-none-linux-gnu,
arm-none-linux-gnueabihf, x86_64-pc-linux-gnu -m32, -m64 and no issues.
Any comments?
Thanks,
Tamar
gcc/ChangeLog:
PR tree-optimization/126551
* tree-if-conv.cc (ifc_temp_var): Support cases with no vUSE.
(ifc_plus_with_operand_p, ifc_phi_feeds_loop_reduction_p,
fold_build_cond_reduction_expr): New.
(predicate_scalar_phi): Use it.
gcc/testsuite/ChangeLog:
PR tree-optimization/126551
* gcc.dg/vect/vect-switch-ifcvt-2.c: Update testcases.
* gcc.dg/vect/cond-reduc-ifcvt-1.c: New test.
* gcc.dg/vect/cond-reduc-ifcvt-2.c: New test.
---
diff --git a/gcc/testsuite/gcc.dg/vect/cond-reduc-ifcvt-1.c
b/gcc/testsuite/gcc.dg/vect/cond-reduc-ifcvt-1.c
new file mode 100644
index
0000000000000000000000000000000000000000..e4a2e7634a8d6bf02d1d3a6f7f12515e83fb8423
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/cond-reduc-ifcvt-1.c
@@ -0,0 +1,21 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_float } */
+/* { dg-additional-options "-Ofast -fdump-tree-ifcvt-details" } */
+
+float
+f (const float *x, int n)
+{
+ float acc = 0;
+ for (int i = 0; i < n; ++i)
+ {
+ float d = x[i];
+ if (d < 0)
+ acc += d;
+ acc += d * 3.0f;
+ }
+ return acc;
+}
+
+/* { dg-final { scan-tree-dump "new phi replacement stmt" "ifcvt" } } */
+/* { dg-final { scan-tree-dump "_ifc_.* = MIN_EXPR" "ifcvt" } } */
+/* { dg-final { scan-tree-dump " = .* \\+ _ifc_" "ifcvt" } } */
diff --git a/gcc/testsuite/gcc.dg/vect/cond-reduc-ifcvt-2.c
b/gcc/testsuite/gcc.dg/vect/cond-reduc-ifcvt-2.c
new file mode 100644
index
0000000000000000000000000000000000000000..c6015303e5568dd51a7ced1edf33784fdf93f75d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/cond-reduc-ifcvt-2.c
@@ -0,0 +1,21 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_int } */
+/* { dg-additional-options "-O3 -fdump-tree-ifcvt-details" } */
+
+int
+f (const int *x, int n)
+{
+ int acc = 0;
+ for (int i = 0; i < n; ++i)
+ {
+ int d = x[i];
+ if (d < 0)
+ acc += d;
+ acc += d * 3;
+ }
+ return acc;
+}
+
+/* { dg-final { scan-tree-dump "new phi replacement stmt" "ifcvt" } } */
+/* { dg-final { scan-tree-dump "_ifc_.* = MIN_EXPR" "ifcvt" } } */
+/* { dg-final { scan-tree-dump " = .* \\+ _ifc_" "ifcvt" } } */
diff --git a/gcc/testsuite/gcc.dg/vect/vect-switch-ifcvt-2.c
b/gcc/testsuite/gcc.dg/vect/vect-switch-ifcvt-2.c
index
f0fcb43e17702492b4fb0e9bc89f0c90b3106fda..03f241aef3750be06e91b7c9c583d4bb091e87e7
100644
--- a/gcc/testsuite/gcc.dg/vect/vect-switch-ifcvt-2.c
+++ b/gcc/testsuite/gcc.dg/vect/vect-switch-ifcvt-2.c
@@ -46,4 +46,4 @@ f2 (char *s)
return c;
}
-/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 0 "vect" } } */
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" } } */
diff --git a/gcc/tree-if-conv.cc b/gcc/tree-if-conv.cc
index
cc3e1dfb4ef2bbd1edaa5ce188202650f5cb163d..1fbea5383fa1914031fceb6833ac7127055c8a81
100644
--- a/gcc/tree-if-conv.cc
+++ b/gcc/tree-if-conv.cc
@@ -392,7 +392,9 @@ ifc_temp_var (tree type, tree expr, gimple_stmt_iterator
*gsi)
{
tree new_name = make_temp_ssa_name (type, NULL, "_ifc_");
gimple *stmt = gimple_build_assign (new_name, expr);
- gimple_set_vuse (stmt, gimple_vuse (gsi_stmt (*gsi)));
+ gimple *curr_stmt = gsi_stmt (*gsi);
+ if (curr_stmt)
+ gimple_set_vuse (stmt, gimple_vuse (curr_stmt));
gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
return new_name;
}
@@ -526,6 +528,117 @@ fold_build_cond_expr (tree type, tree cond, tree rhs,
tree lhs)
return build3 (COND_EXPR, type, cond, rhs, lhs);
}
+/* If EXPR is BASE + ADDEND, return true and store ADDEND. */
+
+static bool
+ifc_plus_with_operand_p (tree expr, tree base, tree *addend)
+{
+ if (TREE_CODE (expr) != SSA_NAME)
+ return false;
+
+ gimple_match_op op;
+ if (!gimple_extract_op (SSA_NAME_DEF_STMT (expr), &op)
+ || op.code != PLUS_EXPR
+ || op.num_ops != 2)
+ return false;
+
+ if (op.ops[0] == base)
+ {
+ *addend = op.ops[1];
+ return true;
+ }
+ if (op.ops[1] == base)
+ {
+ *addend = op.ops[0];
+ return true;
+ }
+ return false;
+}
+
+/* Return true if BASE is a loop reduction PHI and PHI feeds the latch update
+ for that reduction. */
+
+static bool
+ifc_phi_feeds_loop_reduction_p (gphi *phi, tree base)
+{
+ use_operand_p use_p;
+ gimple *use_stmt;
+
+ if (TREE_CODE (base) != SSA_NAME
+ || gimple_code (SSA_NAME_DEF_STMT (base)) != GIMPLE_PHI
+ || !single_imm_use (gimple_phi_result (phi), &use_p, &use_stmt)
+ || !is_gimple_assign (use_stmt))
+ return false;
+
+ gphi *header_phi = as_a <gphi *> (SSA_NAME_DEF_STMT (base));
+ class loop *loop = gimple_bb (phi)->loop_father;
+ if (gimple_bb (header_phi) != loop->header)
+ return false;
+
+ tree use_lhs = gimple_assign_lhs (use_stmt);
+ edge latch_e = loop_latch_edge (loop);
+ return PHI_ARG_DEF_FROM_EDGE (header_phi, latch_e) == use_lhs;
+}
+
+/* Return a vectorizer-friendly form of COND ? RHS : LHS if it selects
+ between BASE + ADDEND and BASE. This keeps the reduction value in a
+ single add chain after if-conversion:
+
+ COND ? BASE + ADDEND : BASE -> BASE + (COND ? ADDEND : 0)
+ COND ? BASE : BASE + ADDEND -> BASE + (COND ? 0 : ADDEND)
+
+ PHI is the if-converted PHI whose result is being replaced. GSI is the
+ insertion point for the temporary conditional addend.
+
+ For floating-point types this reassociation is only done when
+ -fassociative-math allows it. For integer types it does not introduce new
+ overflow: the selected ADDEND is either the original addend or zero, so the
+ true arm keeps the original BASE + ADDEND and the false arm evaluates
+ BASE + 0. Return null if the expression cannot be rewritten safely. */
+
+static tree
+fold_build_cond_reduction_expr (gphi *phi, tree type, tree cond, tree rhs,
+ tree lhs, gimple_stmt_iterator *gsi)
+{
+ tree addend;
+ if (SCALAR_FLOAT_TYPE_P (type))
+ {
+ if (!flag_associative_math)
+ return NULL_TREE;
+ }
+ else if (ANY_INTEGRAL_TYPE_P (type))
+ {
+ if (TYPE_OVERFLOW_TRAPS (type))
+ return NULL_TREE;
+ }
+ else
+ return NULL_TREE;
+
+ if (ifc_plus_with_operand_p (rhs, lhs, &addend)
+ && ifc_phi_feeds_loop_reduction_p (phi, lhs)
+ && types_compatible_p (type, TREE_TYPE (lhs))
+ && types_compatible_p (type, TREE_TYPE (addend)))
+ {
+ tree zero = build_zero_cst (type);
+ tree expr = fold_build_cond_expr (type, cond, addend, zero);
+ tree tmp = ifc_temp_var (type, expr, gsi);
+ return build2 (PLUS_EXPR, type, lhs, tmp);
+ }
+
+ if (ifc_plus_with_operand_p (lhs, rhs, &addend)
+ && ifc_phi_feeds_loop_reduction_p (phi, rhs)
+ && types_compatible_p (type, TREE_TYPE (rhs))
+ && types_compatible_p (type, TREE_TYPE (addend)))
+ {
+ tree zero = build_zero_cst (type);
+ tree expr = fold_build_cond_expr (type, cond, zero, addend);
+ tree tmp = ifc_temp_var (type, expr, gsi);
+ return build2 (PLUS_EXPR, type, rhs, tmp);
+ }
+
+ return NULL_TREE;
+}
+
/* Add condition NC to the predicate list of basic block BB. LOOP is
the loop to be if-converted. Use predicate of cd-equivalent block
for join bb if it exists: we call basic blocks bb1 and bb2
@@ -2488,8 +2601,14 @@ predicate_scalar_phi (gphi *phi, gimple_stmt_iterator
*gsi)
}
else
/* Build new RHS using selected condition and arguments. */
- rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
- arg0, arg1);
+ {
+ tree type = TREE_TYPE (res);
+ rhs = fold_build_cond_reduction_expr (phi, type, cond, arg0,
+ arg1, gsi);
+ if (!rhs)
+ rhs = fold_build_cond_expr (type, unshare_expr (cond), arg0,
+ arg1);
+ }
new_stmt = gimple_build_assign (res, rhs);
gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
gimple_stmt_iterator new_gsi = gsi_for_stmt (new_stmt);
@@ -2574,9 +2693,16 @@ predicate_scalar_phi (gphi *phi, gimple_stmt_iterator
*gsi)
NULL_TREE, true, GSI_SAME_STMT);
if (!(is_cond_scalar_reduction (phi, &reduc, arg0 , arg1,
&op0, &op1, true, &has_nop, &nop_reduc)))
- rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
- swap ? arg1 : arg0,
- swap ? arg0 : arg1);
+ {
+ tree type = TREE_TYPE (res);
+ tree rhs_arg = swap ? arg1 : arg0;
+ tree lhs_arg = swap ? arg0 : arg1;
+ rhs = fold_build_cond_reduction_expr (phi, type, cond, rhs_arg,
+ lhs_arg, gsi);
+ if (!rhs)
+ rhs = fold_build_cond_expr (type, unshare_expr (cond), rhs_arg,
+ lhs_arg);
+ }
else
{
/* Convert reduction stmt into vectorizable form. */
--
diff --git a/gcc/testsuite/gcc.dg/vect/cond-reduc-ifcvt-1.c b/gcc/testsuite/gcc.dg/vect/cond-reduc-ifcvt-1.c
new file mode 100644
index 0000000000000000000000000000000000000000..e4a2e7634a8d6bf02d1d3a6f7f12515e83fb8423
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/cond-reduc-ifcvt-1.c
@@ -0,0 +1,21 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_float } */
+/* { dg-additional-options "-Ofast -fdump-tree-ifcvt-details" } */
+
+float
+f (const float *x, int n)
+{
+ float acc = 0;
+ for (int i = 0; i < n; ++i)
+ {
+ float d = x[i];
+ if (d < 0)
+ acc += d;
+ acc += d * 3.0f;
+ }
+ return acc;
+}
+
+/* { dg-final { scan-tree-dump "new phi replacement stmt" "ifcvt" } } */
+/* { dg-final { scan-tree-dump "_ifc_.* = MIN_EXPR" "ifcvt" } } */
+/* { dg-final { scan-tree-dump " = .* \\+ _ifc_" "ifcvt" } } */
diff --git a/gcc/testsuite/gcc.dg/vect/cond-reduc-ifcvt-2.c b/gcc/testsuite/gcc.dg/vect/cond-reduc-ifcvt-2.c
new file mode 100644
index 0000000000000000000000000000000000000000..c6015303e5568dd51a7ced1edf33784fdf93f75d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/cond-reduc-ifcvt-2.c
@@ -0,0 +1,21 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_int } */
+/* { dg-additional-options "-O3 -fdump-tree-ifcvt-details" } */
+
+int
+f (const int *x, int n)
+{
+ int acc = 0;
+ for (int i = 0; i < n; ++i)
+ {
+ int d = x[i];
+ if (d < 0)
+ acc += d;
+ acc += d * 3;
+ }
+ return acc;
+}
+
+/* { dg-final { scan-tree-dump "new phi replacement stmt" "ifcvt" } } */
+/* { dg-final { scan-tree-dump "_ifc_.* = MIN_EXPR" "ifcvt" } } */
+/* { dg-final { scan-tree-dump " = .* \\+ _ifc_" "ifcvt" } } */
diff --git a/gcc/testsuite/gcc.dg/vect/vect-switch-ifcvt-2.c b/gcc/testsuite/gcc.dg/vect/vect-switch-ifcvt-2.c
index f0fcb43e17702492b4fb0e9bc89f0c90b3106fda..03f241aef3750be06e91b7c9c583d4bb091e87e7 100644
--- a/gcc/testsuite/gcc.dg/vect/vect-switch-ifcvt-2.c
+++ b/gcc/testsuite/gcc.dg/vect/vect-switch-ifcvt-2.c
@@ -46,4 +46,4 @@ f2 (char *s)
return c;
}
-/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 0 "vect" } } */
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" } } */
diff --git a/gcc/tree-if-conv.cc b/gcc/tree-if-conv.cc
index cc3e1dfb4ef2bbd1edaa5ce188202650f5cb163d..1fbea5383fa1914031fceb6833ac7127055c8a81 100644
--- a/gcc/tree-if-conv.cc
+++ b/gcc/tree-if-conv.cc
@@ -392,7 +392,9 @@ ifc_temp_var (tree type, tree expr, gimple_stmt_iterator *gsi)
{
tree new_name = make_temp_ssa_name (type, NULL, "_ifc_");
gimple *stmt = gimple_build_assign (new_name, expr);
- gimple_set_vuse (stmt, gimple_vuse (gsi_stmt (*gsi)));
+ gimple *curr_stmt = gsi_stmt (*gsi);
+ if (curr_stmt)
+ gimple_set_vuse (stmt, gimple_vuse (curr_stmt));
gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
return new_name;
}
@@ -526,6 +528,117 @@ fold_build_cond_expr (tree type, tree cond, tree rhs, tree lhs)
return build3 (COND_EXPR, type, cond, rhs, lhs);
}
+/* If EXPR is BASE + ADDEND, return true and store ADDEND. */
+
+static bool
+ifc_plus_with_operand_p (tree expr, tree base, tree *addend)
+{
+ if (TREE_CODE (expr) != SSA_NAME)
+ return false;
+
+ gimple_match_op op;
+ if (!gimple_extract_op (SSA_NAME_DEF_STMT (expr), &op)
+ || op.code != PLUS_EXPR
+ || op.num_ops != 2)
+ return false;
+
+ if (op.ops[0] == base)
+ {
+ *addend = op.ops[1];
+ return true;
+ }
+ if (op.ops[1] == base)
+ {
+ *addend = op.ops[0];
+ return true;
+ }
+ return false;
+}
+
+/* Return true if BASE is a loop reduction PHI and PHI feeds the latch update
+ for that reduction. */
+
+static bool
+ifc_phi_feeds_loop_reduction_p (gphi *phi, tree base)
+{
+ use_operand_p use_p;
+ gimple *use_stmt;
+
+ if (TREE_CODE (base) != SSA_NAME
+ || gimple_code (SSA_NAME_DEF_STMT (base)) != GIMPLE_PHI
+ || !single_imm_use (gimple_phi_result (phi), &use_p, &use_stmt)
+ || !is_gimple_assign (use_stmt))
+ return false;
+
+ gphi *header_phi = as_a <gphi *> (SSA_NAME_DEF_STMT (base));
+ class loop *loop = gimple_bb (phi)->loop_father;
+ if (gimple_bb (header_phi) != loop->header)
+ return false;
+
+ tree use_lhs = gimple_assign_lhs (use_stmt);
+ edge latch_e = loop_latch_edge (loop);
+ return PHI_ARG_DEF_FROM_EDGE (header_phi, latch_e) == use_lhs;
+}
+
+/* Return a vectorizer-friendly form of COND ? RHS : LHS if it selects
+ between BASE + ADDEND and BASE. This keeps the reduction value in a
+ single add chain after if-conversion:
+
+ COND ? BASE + ADDEND : BASE -> BASE + (COND ? ADDEND : 0)
+ COND ? BASE : BASE + ADDEND -> BASE + (COND ? 0 : ADDEND)
+
+ PHI is the if-converted PHI whose result is being replaced. GSI is the
+ insertion point for the temporary conditional addend.
+
+ For floating-point types this reassociation is only done when
+ -fassociative-math allows it. For integer types it does not introduce new
+ overflow: the selected ADDEND is either the original addend or zero, so the
+ true arm keeps the original BASE + ADDEND and the false arm evaluates
+ BASE + 0. Return null if the expression cannot be rewritten safely. */
+
+static tree
+fold_build_cond_reduction_expr (gphi *phi, tree type, tree cond, tree rhs,
+ tree lhs, gimple_stmt_iterator *gsi)
+{
+ tree addend;
+ if (SCALAR_FLOAT_TYPE_P (type))
+ {
+ if (!flag_associative_math)
+ return NULL_TREE;
+ }
+ else if (ANY_INTEGRAL_TYPE_P (type))
+ {
+ if (TYPE_OVERFLOW_TRAPS (type))
+ return NULL_TREE;
+ }
+ else
+ return NULL_TREE;
+
+ if (ifc_plus_with_operand_p (rhs, lhs, &addend)
+ && ifc_phi_feeds_loop_reduction_p (phi, lhs)
+ && types_compatible_p (type, TREE_TYPE (lhs))
+ && types_compatible_p (type, TREE_TYPE (addend)))
+ {
+ tree zero = build_zero_cst (type);
+ tree expr = fold_build_cond_expr (type, cond, addend, zero);
+ tree tmp = ifc_temp_var (type, expr, gsi);
+ return build2 (PLUS_EXPR, type, lhs, tmp);
+ }
+
+ if (ifc_plus_with_operand_p (lhs, rhs, &addend)
+ && ifc_phi_feeds_loop_reduction_p (phi, rhs)
+ && types_compatible_p (type, TREE_TYPE (rhs))
+ && types_compatible_p (type, TREE_TYPE (addend)))
+ {
+ tree zero = build_zero_cst (type);
+ tree expr = fold_build_cond_expr (type, cond, zero, addend);
+ tree tmp = ifc_temp_var (type, expr, gsi);
+ return build2 (PLUS_EXPR, type, rhs, tmp);
+ }
+
+ return NULL_TREE;
+}
+
/* Add condition NC to the predicate list of basic block BB. LOOP is
the loop to be if-converted. Use predicate of cd-equivalent block
for join bb if it exists: we call basic blocks bb1 and bb2
@@ -2488,8 +2601,14 @@ predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi)
}
else
/* Build new RHS using selected condition and arguments. */
- rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
- arg0, arg1);
+ {
+ tree type = TREE_TYPE (res);
+ rhs = fold_build_cond_reduction_expr (phi, type, cond, arg0,
+ arg1, gsi);
+ if (!rhs)
+ rhs = fold_build_cond_expr (type, unshare_expr (cond), arg0,
+ arg1);
+ }
new_stmt = gimple_build_assign (res, rhs);
gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
gimple_stmt_iterator new_gsi = gsi_for_stmt (new_stmt);
@@ -2574,9 +2693,16 @@ predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi)
NULL_TREE, true, GSI_SAME_STMT);
if (!(is_cond_scalar_reduction (phi, &reduc, arg0 , arg1,
&op0, &op1, true, &has_nop, &nop_reduc)))
- rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
- swap ? arg1 : arg0,
- swap ? arg0 : arg1);
+ {
+ tree type = TREE_TYPE (res);
+ tree rhs_arg = swap ? arg1 : arg0;
+ tree lhs_arg = swap ? arg0 : arg1;
+ rhs = fold_build_cond_reduction_expr (phi, type, cond, rhs_arg,
+ lhs_arg, gsi);
+ if (!rhs)
+ rhs = fold_build_cond_expr (type, unshare_expr (cond), rhs_arg,
+ lhs_arg);
+ }
else
{
/* Convert reduction stmt into vectorizable form. */
