I've noticed we perform FP reduction association without the required
checks for associative math. I've added
gcc.dg/tree-ssa/loop-interchange-1b.c to cover this.
I also noticed we happily interchange a loop with a reduction like
sum = a[i] - sum;
where a change in order of elements isn't ok. Unfortunately bwaves
is exactly a case where single_use != next_def (tried to simply remove
that case for now), because reassoc didn't have a chance to fix the
operand order. Thus this patch exports the relevant handling from
the vectorizer (for stage1 having a separate infrastructure gathering /
analyzing of reduction/induction infrastructure would be nice...)
and uses it from interchange. We then don't handle
gcc.dg/tree-ssa/loop-interchange-4.c anymore (similar vectorizer
missed-opt is PR65930). I didn't bother to split up the vectorizer
code further to implement relaxed validity checking but simply XFAILed
this testcase.
Earlier I simplified allocation stuff in the main loop which is why
this part is included in this patch.
Bootstrap running on x86_64-unknown-linux-gnu.
I'll see to craft a testcase with the sum = a[i] - sum; mis-handling.
Ok?
Thanks,
Richard.
2017-12-04 Richard Biener <rguent...@suse.de>
* tree-vectorizer.h (check_reduction_path): Declare.
* tree-vect-loop.c (check_reduction_path): New function, split out
from ...
(vect_is_simple_reduction): ... here.
* gimple-loop-interchange.cc: Include tree-vectorizer.h.
(loop_cand::analyze_iloop_reduction_var): Use single_imm_use.
Properly check for a supported reduction operation and a
valid expression if the reduction covers multiple stmts.
(prepare_perfect_loop_nest): Simpify allocation.
(pass_linterchange::execute): Likewise.
* gcc.dg/tree-ssa/loop-interchange-1.c: Add fast-math flags.
* gcc.dg/tree-ssa/loop-interchange-1b.c: New test variant.
* gcc.dg/tree-ssa/loop-interchange-4.c: XFAIL.
Index: gcc/gimple-loop-interchange.cc
===================================================================
--- gcc/gimple-loop-interchange.cc (revision 255375)
+++ gcc/gimple-loop-interchange.cc (working copy)
@@ -41,6 +41,7 @@ along with GCC; see the file COPYING3.
#include "tree-ssa-loop-ivopts.h"
#include "tree-ssa-dce.h"
#include "tree-data-ref.h"
+#include "tree-vectorizer.h"
/* This pass performs loop interchange: for example, the loop nest
@@ -551,23 +552,29 @@ loop_cand::analyze_iloop_reduction_var (
in a way that reduction operation is seen as black box. In general,
we can ignore reassociation of reduction operator; we can handle fake
reductions in which VAR is not even used to compute NEXT. */
- FOR_EACH_IMM_USE_FAST (use_p, iterator, var)
- {
- stmt = USE_STMT (use_p);
- if (is_gimple_debug (stmt))
- continue;
-
- if (!flow_bb_inside_loop_p (m_loop, gimple_bb (stmt)))
- return false;
-
- if (single_use != NULL)
- return false;
+ if (! single_imm_use (var, &use_p, &single_use)
+ || ! flow_bb_inside_loop_p (m_loop, gimple_bb (single_use)))
+ return false;
- single_use = stmt;
- }
+ /* Check the reduction operation. We require a commutative or
+ left-associative operation. For FP math we also need to be allowed
+ to associate operations. */
+ if (! is_gimple_assign (single_use)
+ || ! (commutative_tree_code (gimple_assign_rhs_code (single_use))
+ || (commutative_ternary_tree_code
+ (gimple_assign_rhs_code (single_use))
+ && (use_p->use == gimple_assign_rhs1_ptr (single_use)
+ || use_p->use == gimple_assign_rhs2_ptr (single_use)))
+ || (gimple_assign_rhs_code (single_use) == MINUS_EXPR
+ && use_p->use == gimple_assign_rhs1_ptr (single_use)))
+ || (FLOAT_TYPE_P (TREE_TYPE (var))
+ && ! flag_associative_math))
+ return false;
+ /* Handle and verify a series of stmts feeding the reduction op. */
if (single_use != next_def
- && !stmt_dominates_stmt_p (single_use, next_def))
+ && !check_reduction_path (UNKNOWN_LOCATION, m_loop, phi, next,
+ gimple_assign_rhs_code (single_use)))
return false;
/* Only support cases in which INIT is used in inner loop. */
@@ -1964,7 +1971,7 @@ prepare_perfect_loop_nest (struct loop *
vec<data_reference_p> *datarefs, vec<ddr_p> *ddrs)
{
struct loop *start_loop = NULL, *innermost = loop;
- struct loop *outermost = superloop_at_depth (loop, 0);
+ struct loop *outermost = loops_for_fn (cfun)->tree_root;
/* Find loop nest from the innermost loop. The outermost is the innermost
outer*/
@@ -1985,21 +1992,26 @@ prepare_perfect_loop_nest (struct loop *
if (!start_loop || !start_loop->inner)
return false;
+ /* Prepare the data reference vector for the loop nest, pruning outer
+ loops we cannot handle. */
datarefs->create (20);
- if ((start_loop = prepare_data_references (start_loop, datarefs)) == NULL
+ start_loop = prepare_data_references (start_loop, datarefs);
+ if (!start_loop
/* Check if there is no data reference. */
|| datarefs->is_empty ()
/* Check if there are too many of data references. */
- || (int) datarefs->length () > MAX_DATAREFS
- /* Compute access strides for all data references. */
- || ((start_loop = compute_access_strides (start_loop, innermost,
- *datarefs)) == NULL)
- /* Check if loop nest should be interchanged. */
- || !should_interchange_loop_nest (start_loop, innermost, *datarefs))
- {
- free_data_refs_with_aux (*datarefs);
- return false;
- }
+ || (int) datarefs->length () > MAX_DATAREFS)
+ return false;
+
+ /* Compute access strides for all data references, pruning outer
+ loops we cannot analyze refs in. */
+ start_loop = compute_access_strides (start_loop, innermost, *datarefs);
+ if (!start_loop)
+ return false;
+
+ /* Check if any interchange is profitable in the loop nest. */
+ if (!should_interchange_loop_nest (start_loop, innermost, *datarefs))
+ return false;
/* Check if data dependences can be computed for loop nest starting from
start_loop. */
@@ -2029,14 +2041,15 @@ prepare_perfect_loop_nest (struct loop *
return true;
}
+ /* ??? We should be able to adjust DDRs we already computed by
+ truncating distance vectors. */
free_dependence_relations (*ddrs);
+ *ddrs = vNULL;
/* Try to compute data dependences with the outermost loop stripped. */
loop = start_loop;
start_loop = start_loop->inner;
} while (start_loop && start_loop->inner);
- loop_nest->release ();
- free_data_refs_with_aux (*datarefs);
return false;
}
@@ -2050,19 +2063,20 @@ pass_linterchange::execute (function *fu
bool changed_p = false;
struct loop *loop;
- vec<loop_p> loop_nest;
- vec<data_reference_p> datarefs;
- vec<ddr_p> ddrs;
-
FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST)
- if (prepare_perfect_loop_nest (loop, &loop_nest, &datarefs, &ddrs))
- {
- tree_loop_interchange loop_interchange (loop_nest);
- changed_p |= loop_interchange.interchange (datarefs, ddrs);
- free_dependence_relations (ddrs);
- free_data_refs_with_aux (datarefs);
- loop_nest.release ();
- }
+ {
+ vec<loop_p> loop_nest = vNULL;
+ vec<data_reference_p> datarefs = vNULL;
+ vec<ddr_p> ddrs = vNULL;
+ if (prepare_perfect_loop_nest (loop, &loop_nest, &datarefs, &ddrs))
+ {
+ tree_loop_interchange loop_interchange (loop_nest);
+ changed_p |= loop_interchange.interchange (datarefs, ddrs);
+ }
+ free_dependence_relations (ddrs);
+ free_data_refs_with_aux (datarefs);
+ loop_nest.release ();
+ }
if (changed_p)
scev_reset_htab ();
Index: gcc/testsuite/gcc.dg/tree-ssa/loop-interchange-1.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/loop-interchange-1.c (revision 255375)
+++ gcc/testsuite/gcc.dg/tree-ssa/loop-interchange-1.c (working copy)
@@ -1,5 +1,5 @@
/* { dg-do run } */
-/* { dg-options "-O2 -floop-interchange -fdump-tree-linterchange-details" } */
+/* { dg-options "-O2 -floop-interchange -fassociative-math -fno-signed-zeros
-fno-trapping-math -fdump-tree-linterchange-details" } */
/* Copied from graphite/interchange-4.c */
Index: gcc/testsuite/gcc.dg/tree-ssa/loop-interchange-1b.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/loop-interchange-1b.c (nonexistent)
+++ gcc/testsuite/gcc.dg/tree-ssa/loop-interchange-1b.c (working copy)
@@ -0,0 +1,52 @@
+/* { dg-do run } */
+/* { dg-options "-O2 -floop-interchange -fdump-tree-linterchange-details" } */
+
+/* Copied from graphite/interchange-4.c */
+
+#define DEBUG 0
+#if DEBUG
+#include <stdio.h>
+#endif
+
+double u[1782225];
+
+static void __attribute__((noinline))
+foo (int N, double *res)
+{
+ int i, j;
+ double sum = 0;
+ for (i = 0; i < N; i++)
+ for (j = 0; j < N; j++)
+ sum = sum + u[i + 1335 * j];
+
+ *res = sum;
+}
+
+extern void abort ();
+
+int
+main (void)
+{
+ int i, j;
+ double res;
+
+ for (i = 0; i < 1782225; i++)
+ u[i] = 0;
+ u[0] = __DBL_MAX__;
+ u[1335] = -__DBL_MAX__;
+ u[1] = __DBL_MAX__;
+ u[1336] = -__DBL_MAX__;
+
+ foo (1335, &res);
+
+#if DEBUG
+ fprintf (stderr, "res = %d \n", res);
+#endif
+
+ if (res != 0.0)
+ abort ();
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-not "is interchanged" "linterchange"} } */
Index: gcc/testsuite/gcc.dg/tree-ssa/loop-interchange-4.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/loop-interchange-4.c (revision 255375)
+++ gcc/testsuite/gcc.dg/tree-ssa/loop-interchange-4.c (working copy)
@@ -47,4 +47,4 @@ main (void)
return 0;
}
-/* { dg-final { scan-tree-dump-times "Loop_pair<outer:., inner:.> is
interchanged" 1 "linterchange"} } */
+/* { dg-final { scan-tree-dump-times "Loop_pair<outer:., inner:.> is
interchanged" 1 "linterchange" { xfail *-*-* } } } */
Index: gcc/tree-vectorizer.h
===================================================================
--- gcc/tree-vectorizer.h (revision 255375)
+++ gcc/tree-vectorizer.h (working copy)
@@ -1255,6 +1255,9 @@ extern tree vect_create_addr_base_for_ve
/* FORNOW: Used in tree-parloops.c. */
extern gimple *vect_force_simple_reduction (loop_vec_info, gimple *,
bool *, bool);
+/* Used in gimple-loop-interchange.c. */
+extern bool check_reduction_path (location_t, loop_p, gphi *, tree,
+ enum tree_code);
/* Drive for loop analysis stage. */
extern loop_vec_info vect_analyze_loop (struct loop *, loop_vec_info);
extern tree vect_build_loop_niters (loop_vec_info, bool * = NULL);
Index: gcc/tree-vect-loop.c
===================================================================
--- gcc/tree-vect-loop.c (revision 255375)
+++ gcc/tree-vect-loop.c (working copy)
@@ -2626,6 +2626,114 @@ vect_is_slp_reduction (loop_vec_info loo
}
+/* Return true if the reduction PHI in LOOP with latch arg LOOP_ARG and
+ reduction operation CODE has a handled computation expression. */
+
+bool
+check_reduction_path (location_t loc, loop_p loop, gphi *phi, tree loop_arg,
+ enum tree_code code)
+{
+ auto_vec<std::pair<ssa_op_iter, use_operand_p> > path;
+ auto_bitmap visited;
+ tree lookfor = PHI_RESULT (phi);
+ ssa_op_iter curri;
+ use_operand_p curr = op_iter_init_phiuse (&curri, phi, SSA_OP_USE);
+ while (USE_FROM_PTR (curr) != loop_arg)
+ curr = op_iter_next_use (&curri);
+ curri.i = curri.numops;
+ do
+ {
+ path.safe_push (std::make_pair (curri, curr));
+ tree use = USE_FROM_PTR (curr);
+ if (use == lookfor)
+ break;
+ gimple *def = SSA_NAME_DEF_STMT (use);
+ if (gimple_nop_p (def)
+ || ! flow_bb_inside_loop_p (loop, gimple_bb (def)))
+ {
+pop:
+ do
+ {
+ std::pair<ssa_op_iter, use_operand_p> x = path.pop ();
+ curri = x.first;
+ curr = x.second;
+ do
+ curr = op_iter_next_use (&curri);
+ /* Skip already visited or non-SSA operands (from iterating
+ over PHI args). */
+ while (curr != NULL_USE_OPERAND_P
+ && (TREE_CODE (USE_FROM_PTR (curr)) != SSA_NAME
+ || ! bitmap_set_bit (visited,
+ SSA_NAME_VERSION
+ (USE_FROM_PTR (curr)))));
+ }
+ while (curr == NULL_USE_OPERAND_P && ! path.is_empty ());
+ if (curr == NULL_USE_OPERAND_P)
+ break;
+ }
+ else
+ {
+ if (gimple_code (def) == GIMPLE_PHI)
+ curr = op_iter_init_phiuse (&curri, as_a <gphi *>(def), SSA_OP_USE);
+ else
+ curr = op_iter_init_use (&curri, def, SSA_OP_USE);
+ while (curr != NULL_USE_OPERAND_P
+ && (TREE_CODE (USE_FROM_PTR (curr)) != SSA_NAME
+ || ! bitmap_set_bit (visited,
+ SSA_NAME_VERSION
+ (USE_FROM_PTR (curr)))))
+ curr = op_iter_next_use (&curri);
+ if (curr == NULL_USE_OPERAND_P)
+ goto pop;
+ }
+ }
+ while (1);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ dump_printf_loc (MSG_NOTE, loc, "reduction path: ");
+ unsigned i;
+ std::pair<ssa_op_iter, use_operand_p> *x;
+ FOR_EACH_VEC_ELT (path, i, x)
+ {
+ dump_generic_expr (MSG_NOTE, TDF_SLIM, USE_FROM_PTR (x->second));
+ dump_printf (MSG_NOTE, " ");
+ }
+ dump_printf (MSG_NOTE, "\n");
+ }
+
+ /* Check whether the reduction path detected is valid. */
+ bool fail = path.length () == 0;
+ bool neg = false;
+ for (unsigned i = 1; i < path.length (); ++i)
+ {
+ gimple *use_stmt = USE_STMT (path[i].second);
+ tree op = USE_FROM_PTR (path[i].second);
+ if (! has_single_use (op)
+ || ! is_gimple_assign (use_stmt))
+ {
+ fail = true;
+ break;
+ }
+ if (gimple_assign_rhs_code (use_stmt) != code)
+ {
+ if (code == PLUS_EXPR
+ && gimple_assign_rhs_code (use_stmt) == MINUS_EXPR)
+ {
+ /* Track whether we negate the reduction value each iteration. */
+ if (gimple_assign_rhs2 (use_stmt) == op)
+ neg = ! neg;
+ }
+ else
+ {
+ fail = true;
+ break;
+ }
+ }
+ }
+ return ! fail && ! neg;
+}
+
+
/* Function vect_is_simple_reduction
(1) Detect a cross-iteration def-use cycle that represents a simple
@@ -3128,106 +3236,8 @@ vect_is_simple_reduction (loop_vec_info
}
/* Look for the expression computing loop_arg from loop PHI result. */
- auto_vec<std::pair<ssa_op_iter, use_operand_p> > path;
- auto_bitmap visited;
- tree lookfor = PHI_RESULT (phi);
- ssa_op_iter curri;
- use_operand_p curr = op_iter_init_phiuse (&curri, as_a <gphi *>(phi),
- SSA_OP_USE);
- while (USE_FROM_PTR (curr) != loop_arg)
- curr = op_iter_next_use (&curri);
- curri.i = curri.numops;
- do
- {
- path.safe_push (std::make_pair (curri, curr));
- tree use = USE_FROM_PTR (curr);
- if (use == lookfor)
- break;
- gimple *def = SSA_NAME_DEF_STMT (use);
- if (gimple_nop_p (def)
- || ! flow_bb_inside_loop_p (loop, gimple_bb (def)))
- {
-pop:
- do
- {
- std::pair<ssa_op_iter, use_operand_p> x = path.pop ();
- curri = x.first;
- curr = x.second;
- do
- curr = op_iter_next_use (&curri);
- /* Skip already visited or non-SSA operands (from iterating
- over PHI args). */
- while (curr != NULL_USE_OPERAND_P
- && (TREE_CODE (USE_FROM_PTR (curr)) != SSA_NAME
- || ! bitmap_set_bit (visited,
- SSA_NAME_VERSION
- (USE_FROM_PTR (curr)))));
- }
- while (curr == NULL_USE_OPERAND_P && ! path.is_empty ());
- if (curr == NULL_USE_OPERAND_P)
- break;
- }
- else
- {
- if (gimple_code (def) == GIMPLE_PHI)
- curr = op_iter_init_phiuse (&curri, as_a <gphi *>(def), SSA_OP_USE);
- else
- curr = op_iter_init_use (&curri, def, SSA_OP_USE);
- while (curr != NULL_USE_OPERAND_P
- && (TREE_CODE (USE_FROM_PTR (curr)) != SSA_NAME
- || ! bitmap_set_bit (visited,
- SSA_NAME_VERSION
- (USE_FROM_PTR (curr)))))
- curr = op_iter_next_use (&curri);
- if (curr == NULL_USE_OPERAND_P)
- goto pop;
- }
- }
- while (1);
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- dump_printf_loc (MSG_NOTE, vect_location,
- "reduction path: ");
- unsigned i;
- std::pair<ssa_op_iter, use_operand_p> *x;
- FOR_EACH_VEC_ELT (path, i, x)
- {
- dump_generic_expr (MSG_NOTE, TDF_SLIM, USE_FROM_PTR (x->second));
- dump_printf (MSG_NOTE, " ");
- }
- dump_printf (MSG_NOTE, "\n");
- }
-
- /* Check whether the reduction path detected is valid. */
- bool fail = path.length () == 0;
- bool neg = false;
- for (unsigned i = 1; i < path.length (); ++i)
- {
- gimple *use_stmt = USE_STMT (path[i].second);
- tree op = USE_FROM_PTR (path[i].second);
- if (! has_single_use (op)
- || ! is_gimple_assign (use_stmt))
- {
- fail = true;
- break;
- }
- if (gimple_assign_rhs_code (use_stmt) != code)
- {
- if (code == PLUS_EXPR
- && gimple_assign_rhs_code (use_stmt) == MINUS_EXPR)
- {
- /* Track whether we negate the reduction value each iteration. */
- if (gimple_assign_rhs2 (use_stmt) == op)
- neg = ! neg;
- }
- else
- {
- fail = true;
- break;
- }
- }
- }
- if (! fail && ! neg)
+ if (check_reduction_path (vect_location, loop, as_a <gphi *> (phi), loop_arg,
+ code))
return def_stmt;
if (dump_enabled_p ())
