[PATCH] Fix possible correctness issue in BB dependence analysis

Richard Biener rguenther@suse.de
Thu Nov 12 14:55:00 GMT 2015


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 ();



More information about the Gcc-patches mailing list