This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] Fix possible correctness issue in BB dependence analysis
- From: Richard Biener <rguenther at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Date: Thu, 12 Nov 2015 15:55:07 +0100 (CET)
- Subject: [PATCH] Fix possible correctness issue in BB dependence analysis
- Authentication-results: sourceware.org; auth=none
This fixes BB vectorization dependence analysis to not rely on
all instances being vectorized. The dependence check
- gimple *earlier_stmt = get_earlier_stmt (DR_STMT (dra), DR_STMT
(drb));
- if (DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (earlier_stmt))))
- {
- /* That only holds for load-store pairs taking part in
vectorization. */
- if (STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dra)))
- && STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (drb))))
- return false;
effectively does that and we remove instances later. I wasn't able
to build a testcase showing this defect as we always fail vectorization
for some other reason.
Still the following fixes this and implements this special case
instance-local only.
Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to trunk.
Richard.
2015-11-12 Richard Biener <rguenther@suse.de>
* tree-vectorizer.h (vect_slp_analyze_data_ref_dependences):
Rename to vect_slp_analyze_instance_dependence.
* tree-vect-data-refs.c (vect_slp_analyze_data_ref_dependence):
Remove WAR special-case.
(vect_slp_analyze_node_dependences): Instead add more specific
code here, not relying on other instances being vectorized.
(vect_slp_analyze_instance_dependence): Adjust accordingly.
* tree-vect-slp.c (vect_build_slp_tree_1): Remove excessive
vertical space in dump files.
(vect_print_slp_tree): Likewise.
(vect_analyze_slp_instance): Dump a header for the final SLP tree.
(vect_slp_analyze_bb_1): Delay computing relevant stmts and
not vectorized stmts until after dependence analysis removed
instances. Merge alignment and dependence checks.
* tree-vectorizer.c (pass_slp_vectorize::execute): Clear visited
flag on all stmts.
Index: gcc/tree-vectorizer.h
===================================================================
*** gcc/tree-vectorizer.h (revision 230216)
--- gcc/tree-vectorizer.h (working copy)
*************** extern enum dr_alignment_support vect_su
*** 1009,1015 ****
extern tree vect_get_smallest_scalar_type (gimple *, HOST_WIDE_INT *,
HOST_WIDE_INT *);
extern bool vect_analyze_data_ref_dependences (loop_vec_info, int *);
! extern bool vect_slp_analyze_data_ref_dependences (bb_vec_info);
extern bool vect_enhance_data_refs_alignment (loop_vec_info);
extern bool vect_analyze_data_refs_alignment (loop_vec_info);
extern bool vect_verify_datarefs_alignment (loop_vec_info);
--- 1009,1015 ----
extern tree vect_get_smallest_scalar_type (gimple *, HOST_WIDE_INT *,
HOST_WIDE_INT *);
extern bool vect_analyze_data_ref_dependences (loop_vec_info, int *);
! extern bool vect_slp_analyze_instance_dependence (slp_instance);
extern bool vect_enhance_data_refs_alignment (loop_vec_info);
extern bool vect_analyze_data_refs_alignment (loop_vec_info);
extern bool vect_verify_datarefs_alignment (loop_vec_info);
Index: gcc/tree-vect-data-refs.c
===================================================================
*** gcc/tree-vect-data-refs.c (revision 230216)
--- gcc/tree-vect-data-refs.c (working copy)
*************** vect_slp_analyze_data_ref_dependence (st
*** 537,568 ****
dump_printf (MSG_NOTE, "\n");
}
- /* We do not vectorize basic blocks with write-write dependencies. */
- if (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))
- return true;
-
- /* If we have a read-write dependence check that the load is before the store.
- When we vectorize basic blocks, vector load can be only before
- corresponding scalar load, and vector store can be only after its
- corresponding scalar store. So the order of the acceses is preserved in
- case the load is before the store. */
- gimple *earlier_stmt = get_earlier_stmt (DR_STMT (dra), DR_STMT (drb));
- if (DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (earlier_stmt))))
- {
- /* That only holds for load-store pairs taking part in vectorization. */
- if (STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dra)))
- && STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (drb))))
- return false;
- }
-
return true;
}
! /* Analyze dependences involved in the transform of SLP NODE. */
static bool
! vect_slp_analyze_node_dependences (slp_instance instance, slp_tree node)
{
/* This walks over all stmts involved in the SLP load/store done
in NODE verifying we can sink them up to the last stmt in the
--- 559,575 ----
dump_printf (MSG_NOTE, "\n");
}
return true;
}
! /* Analyze dependences involved in the transform of SLP NODE. STORES
! contain the vector of scalar stores of this instance if we are
! disambiguating the loads. */
static bool
! vect_slp_analyze_node_dependences (slp_instance instance, slp_tree node,
! vec<gimple *> stores, gimple *last_store)
{
/* This walks over all stmts involved in the SLP load/store done
in NODE verifying we can sink them up to the last stmt in the
*************** vect_slp_analyze_node_dependences (slp_i
*** 584,598 ****
/* If we couldn't record a (single) data reference for this
stmt we have to give up. */
data_reference *dr_b = STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt));
if (!dr_b)
return false;
ddr_p ddr = initialize_data_dependence_relation (dr_a, dr_b, vNULL);
if (vect_slp_analyze_data_ref_dependence (ddr))
{
- /* ??? If the dependence analysis failed we can resort to the
- alias oracle which can handle more kinds of stmts. */
free_dependence_relation (ddr);
return false;
}
--- 591,630 ----
/* If we couldn't record a (single) data reference for this
stmt we have to give up. */
+ /* ??? Here and below if dependence analysis fails we can resort
+ to the alias oracle which can handle more kinds of stmts. */
data_reference *dr_b = STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt));
if (!dr_b)
return false;
+ /* If we run into a store of this same instance (we've just
+ marked those) then delay dependence checking until we run
+ into the last store because this is where it will have
+ been sunk to (and we verify if we can do that as well). */
+ if (gimple_visited_p (stmt))
+ {
+ if (stmt != last_store)
+ continue;
+ unsigned i;
+ gimple *store;
+ FOR_EACH_VEC_ELT (stores, i, store)
+ {
+ data_reference *store_dr
+ = STMT_VINFO_DATA_REF (vinfo_for_stmt (store));
+ ddr_p ddr = initialize_data_dependence_relation
+ (dr_a, store_dr, vNULL);
+ if (vect_slp_analyze_data_ref_dependence (ddr))
+ {
+ free_dependence_relation (ddr);
+ return false;
+ }
+ free_dependence_relation (ddr);
+ }
+ }
+
ddr_p ddr = initialize_data_dependence_relation (dr_a, dr_b, vNULL);
if (vect_slp_analyze_data_ref_dependence (ddr))
{
free_dependence_relation (ddr);
return false;
}
*************** vect_slp_analyze_node_dependences (slp_i
*** 610,661 ****
the maximum vectorization factor the data dependences allow. */
bool
! vect_slp_analyze_data_ref_dependences (bb_vec_info bb_vinfo)
{
if (dump_enabled_p ())
dump_printf_loc (MSG_NOTE, vect_location,
! "=== vect_slp_analyze_data_ref_dependences ===\n");
! slp_instance instance;
! slp_tree load;
! unsigned int i, j;
! for (i = 0; BB_VINFO_SLP_INSTANCES (bb_vinfo).iterate (i, &instance); )
{
! bool remove = false;
! /* Verify we can sink loads to the vectorized stmt insert location. */
! FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (instance), j, load)
! if (! vect_slp_analyze_node_dependences (instance, load))
! {
! remove = true;
! break;
! }
! /* Verify we can sink stores to the vectorized stmt insert location. */
! slp_tree store = SLP_INSTANCE_TREE (instance);
! if (!remove
! && STMT_VINFO_DATA_REF
! (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (store)[0]))
! && ! vect_slp_analyze_node_dependences (instance, store))
! remove = true;
! if (remove)
! {
! dump_printf_loc (MSG_NOTE, vect_location,
! "removing SLP instance operations starting from: ");
! dump_gimple_stmt (MSG_NOTE, TDF_SLIM,
! SLP_TREE_SCALAR_STMTS
! (SLP_INSTANCE_TREE (instance))[0], 0);
! vect_free_slp_instance (instance);
! BB_VINFO_SLP_INSTANCES (bb_vinfo).ordered_remove (i);
! continue;
! }
! i++;
}
! if (!BB_VINFO_SLP_INSTANCES (bb_vinfo).length ())
! return false;
! return true;
! }
/* Function vect_compute_data_ref_alignment
--- 642,694 ----
the maximum vectorization factor the data dependences allow. */
bool
! vect_slp_analyze_instance_dependence (slp_instance instance)
{
if (dump_enabled_p ())
dump_printf_loc (MSG_NOTE, vect_location,
! "=== vect_slp_analyze_instance_dependence ===\n");
! /* The stores of this instance are at the root of the SLP tree. */
! slp_tree store = SLP_INSTANCE_TREE (instance);
! if (! STMT_VINFO_DATA_REF (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (store)[0])))
! store = NULL;
!
! /* Verify we can sink stores to the vectorized stmt insert location. */
! gimple *last_store = NULL;
! if (store)
{
! if (! vect_slp_analyze_node_dependences (instance, store, vNULL, NULL))
! return false;
!
! /* Mark stores in this instance and remember the last one. */
! last_store = vect_find_last_scalar_stmt_in_slp (store);
! for (unsigned k = 0; k < SLP_INSTANCE_GROUP_SIZE (instance); ++k)
! gimple_set_visited (SLP_TREE_SCALAR_STMTS (store)[k], true);
}
! bool res = true;
! /* Verify we can sink loads to the vectorized stmt insert location,
! special-casing stores of this instance. */
! slp_tree load;
! unsigned int i;
! FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (instance), i, load)
! if (! vect_slp_analyze_node_dependences (instance, load,
! store
! ? SLP_TREE_SCALAR_STMTS (store)
! : vNULL, last_store))
! {
! res = false;
! break;
! }
!
! /* Unset the visited flag. */
! if (store)
! for (unsigned k = 0; k < SLP_INSTANCE_GROUP_SIZE (instance); ++k)
! gimple_set_visited (SLP_TREE_SCALAR_STMTS (store)[k], false);
+ return res;
+ }
/* Function vect_compute_data_ref_alignment
Index: gcc/tree-vect-slp.c
===================================================================
*** gcc/tree-vect-slp.c (revision 230216)
--- gcc/tree-vect-slp.c (working copy)
*************** vect_build_slp_tree_1 (vec_info *vinfo,
*** 458,464 ****
{
dump_printf_loc (MSG_NOTE, vect_location, "Build SLP for ");
dump_gimple_stmt (MSG_NOTE, TDF_SLIM, stmt, 0);
- dump_printf (MSG_NOTE, "\n");
}
/* Fail to vectorize statements marked as unvectorizable. */
--- 458,463 ----
*************** vect_build_slp_tree (vec_info *vinfo,
*** 1114,1120 ****
/* Dump a slp tree NODE using flags specified in DUMP_KIND. */
static void
! vect_print_slp_tree (int dump_kind, slp_tree node)
{
int i;
gimple *stmt;
--- 1113,1119 ----
/* Dump a slp tree NODE using flags specified in DUMP_KIND. */
static void
! vect_print_slp_tree (int dump_kind, location_t loc, slp_tree node)
{
int i;
gimple *stmt;
*************** vect_print_slp_tree (int dump_kind, slp_
*** 1123,1138 ****
if (!node)
return;
! dump_printf (dump_kind, "node ");
FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt)
{
! dump_printf (dump_kind, "\n\tstmt %d ", i);
dump_gimple_stmt (dump_kind, TDF_SLIM, stmt, 0);
}
- dump_printf (dump_kind, "\n");
-
FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
! vect_print_slp_tree (dump_kind, child);
}
--- 1122,1135 ----
if (!node)
return;
! dump_printf_loc (dump_kind, loc, "node\n");
FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt)
{
! dump_printf_loc (dump_kind, loc, "\tstmt %d ", i);
dump_gimple_stmt (dump_kind, TDF_SLIM, stmt, 0);
}
FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
! vect_print_slp_tree (dump_kind, loc, child);
}
*************** vect_analyze_slp_instance (vec_info *vin
*** 1756,1762 ****
vinfo->slp_instances.safe_push (new_instance);
if (dump_enabled_p ())
! vect_print_slp_tree (MSG_NOTE, node);
return true;
}
--- 1753,1763 ----
vinfo->slp_instances.safe_push (new_instance);
if (dump_enabled_p ())
! {
! dump_printf_loc (MSG_NOTE, vect_location,
! "Final SLP tree for instance:\n");
! vect_print_slp_tree (MSG_NOTE, vect_location, node);
! }
return true;
}
*************** vect_slp_analyze_bb_1 (gimple_stmt_itera
*** 2294,2300 ****
bool &fatal)
{
bb_vec_info bb_vinfo;
- vec<slp_instance> slp_instances;
slp_instance instance;
int i;
int min_vf = 2;
--- 2295,2300 ----
*************** vect_slp_analyze_bb_1 (gimple_stmt_itera
*** 2389,2399 ****
return NULL;
}
! /* Analyze and verify the alignment of data references in the SLP
! instances. */
for (i = 0; BB_VINFO_SLP_INSTANCES (bb_vinfo).iterate (i, &instance); )
{
! if (! vect_slp_analyze_and_verify_instance_alignment (instance))
{
dump_printf_loc (MSG_NOTE, vect_location,
"removing SLP instance operations starting from: ");
--- 2389,2400 ----
return NULL;
}
! /* Analyze and verify the alignment of data references and the
! dependence in the SLP instances. */
for (i = 0; BB_VINFO_SLP_INSTANCES (bb_vinfo).iterate (i, &instance); )
{
! if (! vect_slp_analyze_and_verify_instance_alignment (instance)
! || ! vect_slp_analyze_instance_dependence (instance))
{
dump_printf_loc (MSG_NOTE, vect_location,
"removing SLP instance operations starting from: ");
*************** vect_slp_analyze_bb_1 (gimple_stmt_itera
*** 2404,2428 ****
BB_VINFO_SLP_INSTANCES (bb_vinfo).ordered_remove (i);
continue;
}
i++;
}
-
if (! BB_VINFO_SLP_INSTANCES (bb_vinfo).length ())
{
destroy_bb_vec_info (bb_vinfo);
return NULL;
}
- slp_instances = BB_VINFO_SLP_INSTANCES (bb_vinfo);
-
- /* Mark all the statements that we want to vectorize as pure SLP and
- relevant. */
- FOR_EACH_VEC_ELT (slp_instances, i, instance)
- {
- vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance), pure_slp, -1);
- vect_mark_slp_stmts_relevant (SLP_INSTANCE_TREE (instance));
- }
-
/* Mark all the statements that we do not want to vectorize. */
for (gimple_stmt_iterator gsi = bb_vinfo->region_begin;
gsi_stmt (gsi) != gsi_stmt (bb_vinfo->region_end); gsi_next (&gsi))
--- 2405,2424 ----
BB_VINFO_SLP_INSTANCES (bb_vinfo).ordered_remove (i);
continue;
}
+
+ /* Mark all the statements that we want to vectorize as pure SLP and
+ relevant. */
+ vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance), pure_slp, -1);
+ vect_mark_slp_stmts_relevant (SLP_INSTANCE_TREE (instance));
+
i++;
}
if (! BB_VINFO_SLP_INSTANCES (bb_vinfo).length ())
{
destroy_bb_vec_info (bb_vinfo);
return NULL;
}
/* Mark all the statements that we do not want to vectorize. */
for (gimple_stmt_iterator gsi = bb_vinfo->region_begin;
gsi_stmt (gsi) != gsi_stmt (bb_vinfo->region_end); gsi_next (&gsi))
*************** vect_slp_analyze_bb_1 (gimple_stmt_itera
*** 2432,2451 ****
STMT_VINFO_VECTORIZABLE (vinfo) = false;
}
- /* Analyze dependences. At this point all stmts not participating in
- vectorization have to be marked. Dependence analysis assumes
- that we either vectorize all SLP instances or none at all. */
- if (! vect_slp_analyze_data_ref_dependences (bb_vinfo))
- {
- if (dump_enabled_p ())
- dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
- "not vectorized: unhandled data dependence "
- "in basic block.\n");
-
- destroy_bb_vec_info (bb_vinfo);
- return NULL;
- }
-
if (!vect_slp_analyze_operations (BB_VINFO_SLP_INSTANCES (bb_vinfo),
BB_VINFO_TARGET_COST_DATA (bb_vinfo)))
{
--- 2428,2433 ----
Index: gcc/tree-vectorizer.c
===================================================================
--- gcc/tree-vectorizer.c (revision 230260)
+++ gcc/tree-vectorizer.c (working copy)
@@ -719,12 +719,16 @@ pass_slp_vectorize::execute (function *f
scev_initialize ();
}
- /* Mark all stmts as not belonging to the current region. */
+ /* Mark all stmts as not belonging to the current region and unvisited. */
FOR_EACH_BB_FN (bb, fun)
{
for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
gsi_next (&gsi))
- gimple_set_uid (gsi_stmt (gsi), -1);
+ {
+ gimple *stmt = gsi_stmt (gsi);
+ gimple_set_uid (stmt, -1);
+ gimple_set_visited (stmt, false);
+ }
}
init_stmt_vec_info_vec ();