This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH][1/n] Vectorizer TLC: re-organize data dependence checking


This splits data reference group analysis away from data dependence
checking and splits the latter into loop and a BB vectorization
functions.  This allows us to perform the now no longer quadratic
but O(n * log (n)) data reference group analysis right after
data reference gathering, pushing the quadratic data dependence
testing down the vectorization analysis pipeline.

Bootstrap and regtest running on x86_64-unknown-linux-gnu, queued for 4.9.

Richard.

2013-02-27  Richard Biener  <rguenther@suse.de>

	* tree-vect-data-refs.c (vect_update_interleaving_chain): Remove.
	(vect_insert_into_interleaving_chain): Likewise.
	(vect_drs_dependent_in_basic_block): Inline ...
	(vect_slp_analyze_data_ref_dependence): ... here.  New function,
	split out from ...
	(vect_analyze_data_ref_dependence): ... here.  Simplify.
	(vect_check_interleaving): Simplify.
	(vect_analyze_data_ref_dependences): Likewise.  Split out ...
	(vect_slp_analyze_data_ref_dependences): ... this new function.
	(dr_group_sort_cmp): New function.
	(vect_analyze_data_ref_accesses): Compute data-reference groups
	here instead of in vect_analyze_data_ref_dependence.  Use
	a more efficient algorithm.
	* tree-vect-slp.c (vect_slp_analyze_bb_1): Use
	vect_slp_analyze_data_ref_dependences.  Call
	vect_analyze_data_ref_accesses earlier.
	* tree-vect-loop.c (vect_analyze_loop_2): Likewise.
	* tree-vectorizer.h (vect_analyze_data_ref_dependences): Adjust.
	(vect_slp_analyze_data_ref_dependences): New prototype.

Index: trunk/gcc/tree-vect-data-refs.c
===================================================================
*** trunk.orig/gcc/tree-vect-data-refs.c	2013-02-27 14:53:36.000000000 +0100
--- trunk/gcc/tree-vect-data-refs.c	2013-02-27 16:45:58.969861004 +0100
*************** vect_get_place_in_interleaving_chain (gi
*** 154,394 ****
  }
  
  
- /* Function vect_insert_into_interleaving_chain.
- 
-    Insert DRA into the interleaving chain of DRB according to DRA's INIT.  */
- 
- static void
- vect_insert_into_interleaving_chain (struct data_reference *dra,
- 				     struct data_reference *drb)
- {
-   gimple prev, next;
-   tree next_init;
-   stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
-   stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
- 
-   prev = GROUP_FIRST_ELEMENT (stmtinfo_b);
-   next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev));
-   while (next)
-     {
-       next_init = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (next)));
-       if (tree_int_cst_compare (next_init, DR_INIT (dra)) > 0)
- 	{
- 	  /* Insert here.  */
- 	  GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev)) = DR_STMT (dra);
- 	  GROUP_NEXT_ELEMENT (stmtinfo_a) = next;
- 	  return;
- 	}
-       prev = next;
-       next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev));
-     }
- 
-   /* We got to the end of the list. Insert here.  */
-   GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev)) = DR_STMT (dra);
-   GROUP_NEXT_ELEMENT (stmtinfo_a) = NULL;
- }
- 
- 
- /* Function vect_update_interleaving_chain.
- 
-    For two data-refs DRA and DRB that are a part of a chain interleaved data
-    accesses, update the interleaving chain.  DRB's INIT is smaller than DRA's.
- 
-    There are four possible cases:
-    1. New stmts - both DRA and DRB are not a part of any chain:
-       FIRST_DR = DRB
-       NEXT_DR (DRB) = DRA
-    2. DRB is a part of a chain and DRA is not:
-       no need to update FIRST_DR
-       no need to insert DRB
-       insert DRA according to init
-    3. DRA is a part of a chain and DRB is not:
-       if (init of FIRST_DR > init of DRB)
-           FIRST_DR = DRB
- 	  NEXT(FIRST_DR) = previous FIRST_DR
-       else
-           insert DRB according to its init
-    4. both DRA and DRB are in some interleaving chains:
-       choose the chain with the smallest init of FIRST_DR
-       insert the nodes of the second chain into the first one.  */
- 
- static void
- vect_update_interleaving_chain (struct data_reference *drb,
- 				struct data_reference *dra)
- {
-   stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
-   stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
-   tree next_init, init_dra_chain, init_drb_chain;
-   gimple first_a, first_b;
-   tree node_init;
-   gimple node, prev, next, first_stmt;
- 
-   /* 1. New stmts - both DRA and DRB are not a part of any chain.   */
-   if (!GROUP_FIRST_ELEMENT (stmtinfo_a) && !GROUP_FIRST_ELEMENT (stmtinfo_b))
-     {
-       GROUP_FIRST_ELEMENT (stmtinfo_a) = DR_STMT (drb);
-       GROUP_FIRST_ELEMENT (stmtinfo_b) = DR_STMT (drb);
-       GROUP_NEXT_ELEMENT (stmtinfo_b) = DR_STMT (dra);
-       return;
-     }
- 
-   /* 2. DRB is a part of a chain and DRA is not.  */
-   if (!GROUP_FIRST_ELEMENT (stmtinfo_a) && GROUP_FIRST_ELEMENT (stmtinfo_b))
-     {
-       GROUP_FIRST_ELEMENT (stmtinfo_a) = GROUP_FIRST_ELEMENT (stmtinfo_b);
-       /* Insert DRA into the chain of DRB.  */
-       vect_insert_into_interleaving_chain (dra, drb);
-       return;
-     }
- 
-   /* 3. DRA is a part of a chain and DRB is not.  */
-   if (GROUP_FIRST_ELEMENT (stmtinfo_a) && !GROUP_FIRST_ELEMENT (stmtinfo_b))
-     {
-       gimple old_first_stmt = GROUP_FIRST_ELEMENT (stmtinfo_a);
-       tree init_old = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (
- 							      old_first_stmt)));
-       gimple tmp;
- 
-       if (tree_int_cst_compare (init_old, DR_INIT (drb)) > 0)
- 	{
- 	  /* DRB's init is smaller than the init of the stmt previously marked
- 	     as the first stmt of the interleaving chain of DRA.  Therefore, we
- 	     update FIRST_STMT and put DRB in the head of the list.  */
- 	  GROUP_FIRST_ELEMENT (stmtinfo_b) = DR_STMT (drb);
- 	  GROUP_NEXT_ELEMENT (stmtinfo_b) = old_first_stmt;
- 
- 	  /* Update all the stmts in the list to point to the new FIRST_STMT.  */
- 	  tmp = old_first_stmt;
- 	  while (tmp)
- 	    {
- 	      GROUP_FIRST_ELEMENT (vinfo_for_stmt (tmp)) = DR_STMT (drb);
- 	      tmp = GROUP_NEXT_ELEMENT (vinfo_for_stmt (tmp));
- 	    }
- 	}
-       else
- 	{
- 	  /* Insert DRB in the list of DRA.  */
- 	  vect_insert_into_interleaving_chain (drb, dra);
- 	  GROUP_FIRST_ELEMENT (stmtinfo_b) = GROUP_FIRST_ELEMENT (stmtinfo_a);
- 	}
-       return;
-     }
- 
-   /* 4. both DRA and DRB are in some interleaving chains.  */
-   first_a = GROUP_FIRST_ELEMENT (stmtinfo_a);
-   first_b = GROUP_FIRST_ELEMENT (stmtinfo_b);
-   if (first_a == first_b)
-     return;
-   init_dra_chain = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (first_a)));
-   init_drb_chain = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (first_b)));
- 
-   if (tree_int_cst_compare (init_dra_chain, init_drb_chain) > 0)
-     {
-       /* Insert the nodes of DRA chain into the DRB chain.
- 	 After inserting a node, continue from this node of the DRB chain (don't
-          start from the beginning.  */
-       node = GROUP_FIRST_ELEMENT (stmtinfo_a);
-       prev = GROUP_FIRST_ELEMENT (stmtinfo_b);
-       first_stmt = first_b;
-     }
-   else
-     {
-       /* Insert the nodes of DRB chain into the DRA chain.
- 	 After inserting a node, continue from this node of the DRA chain (don't
-          start from the beginning.  */
-       node = GROUP_FIRST_ELEMENT (stmtinfo_b);
-       prev = GROUP_FIRST_ELEMENT (stmtinfo_a);
-       first_stmt = first_a;
-     }
- 
-   while (node)
-     {
-       node_init = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (node)));
-       next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev));
-       while (next)
- 	{
- 	  next_init = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (next)));
- 	  if (tree_int_cst_compare (next_init, node_init) > 0)
- 	    {
- 	      /* Insert here.  */
- 	      GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev)) = node;
- 	      GROUP_NEXT_ELEMENT (vinfo_for_stmt (node)) = next;
- 	      prev = node;
- 	      break;
- 	    }
- 	  prev = next;
- 	  next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev));
- 	}
-       if (!next)
- 	{
- 	  /* We got to the end of the list. Insert here.  */
- 	  GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev)) = node;
- 	  GROUP_NEXT_ELEMENT (vinfo_for_stmt (node)) = NULL;
- 	  prev = node;
- 	}
-       GROUP_FIRST_ELEMENT (vinfo_for_stmt (node)) = first_stmt;
-       node = GROUP_NEXT_ELEMENT (vinfo_for_stmt (node));
-     }
- }
- 
- /* Check dependence between DRA and DRB for basic block vectorization.
-    If the accesses share same bases and offsets, we can compare their initial
-    constant offsets to decide whether they differ or not.  In case of a read-
-    write dependence we check that the load is before the store to ensure that
-    vectorization will not change the order of the accesses.  */
- 
- static bool
- vect_drs_dependent_in_basic_block (struct data_reference *dra,
-                                    struct data_reference *drb)
- {
-   HOST_WIDE_INT type_size_a, type_size_b, init_a, init_b;
-   gimple earlier_stmt;
- 
-   /* We only call this function for pairs of loads and stores, but we verify
-      it here.  */
-   if (DR_IS_READ (dra) == DR_IS_READ (drb))
-     {
-       if (DR_IS_READ (dra))
-         return false;
-       else
-         return true;
-     }
- 
-   /* Check that the data-refs have same bases and offsets.  If not, we can't
-      determine if they are dependent.  */
-   if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0)
-       || !dr_equal_offsets_p (dra, drb))
-     return true;
- 
-   /* Check the types.  */
-   type_size_a = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))));
-   type_size_b = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
- 
-   if (type_size_a != type_size_b
-       || !types_compatible_p (TREE_TYPE (DR_REF (dra)),
-                               TREE_TYPE (DR_REF (drb))))
-     return true;
- 
-   init_a = TREE_INT_CST_LOW (DR_INIT (dra));
-   init_b = TREE_INT_CST_LOW (DR_INIT (drb));
- 
-   /* Two different locations - no dependence.  */
-   if (init_a != init_b)
-     return false;
- 
-   /* 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.  */
-   earlier_stmt = get_earlier_stmt (DR_STMT (dra), DR_STMT (drb));   
-   if (DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (earlier_stmt))))
-     return false;
- 
-   return true;
- }
- 
- 
  /* Function vect_check_interleaving.
  
     Check if DRA and DRB are a part of interleaving.  In case they are, insert
--- 154,159 ----
*************** static bool
*** 398,479 ****
  vect_check_interleaving (struct data_reference *dra,
  			 struct data_reference *drb)
  {
!   HOST_WIDE_INT type_size_a, type_size_b, diff_mod_size, step, init_a, init_b;
  
!   /* Check that the data-refs have same first location (except init) and they
!      are both either store or load (not load and store).  */
    if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0)
        || !dr_equal_offsets_p (dra, drb)
-       || !tree_int_cst_compare (DR_INIT (dra), DR_INIT (drb))
        || DR_IS_READ (dra) != DR_IS_READ (drb))
!     return false;
  
!   /* Check:
!      1. data-refs are of the same type
!      2. their steps are equal
!      3. the step (if greater than zero) is greater than the difference between
!         data-refs' inits.  */
    type_size_a = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))));
    type_size_b = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
- 
    if (type_size_a != type_size_b
!       || tree_int_cst_compare (DR_STEP (dra), DR_STEP (drb))
!       || !types_compatible_p (TREE_TYPE (DR_REF (dra)),
!                               TREE_TYPE (DR_REF (drb))))
      return false;
  
    init_a = TREE_INT_CST_LOW (DR_INIT (dra));
    init_b = TREE_INT_CST_LOW (DR_INIT (drb));
    step = TREE_INT_CST_LOW (DR_STEP (dra));
  
!   if (init_a > init_b)
!     {
!       /* If init_a == init_b + the size of the type * k, we have an interleaving,
! 	 and DRB is accessed before DRA.  */
!       diff_mod_size = (init_a - init_b) % type_size_a;
! 
!       if (step && (init_a - init_b) > step)
!          return false;
  
!       if (diff_mod_size == 0)
! 	{
! 	  vect_update_interleaving_chain (drb, dra);
! 	  if (dump_enabled_p ())
! 	    {
! 	      dump_printf_loc (MSG_NOTE, vect_location,
!                                "Detected interleaving ");
! 	      dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
! 	      dump_printf (MSG_NOTE,  " and ");
! 	      dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
! 	    }
! 	  return true;
! 	}
!     }
!   else
!     {
!       /* If init_b == init_a + the size of the type * k, we have an
! 	 interleaving, and DRA is accessed before DRB.  */
!       diff_mod_size = (init_b - init_a) % type_size_a;
  
!       if (step && (init_b - init_a) > step)
!          return false;
  
!       if (diff_mod_size == 0)
! 	{
! 	  vect_update_interleaving_chain (dra, drb);
! 	  if (dump_enabled_p ())
! 	    {
! 	      dump_printf_loc (MSG_NOTE, vect_location,
!                                "Detected interleaving ");
! 	      dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
! 	      dump_printf (MSG_NOTE,  " and ");
! 	      dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
! 	    }
! 	  return true;
! 	}
      }
  
!   return false;
  }
  
  /* Check if data references pointed by DR_I and DR_J are same or
--- 163,220 ----
  vect_check_interleaving (struct data_reference *dra,
  			 struct data_reference *drb)
  {
!   HOST_WIDE_INT type_size_a, type_size_b, step, init_a, init_b;
  
!   /* The caller has ensured that the data-refs have same first location
!      (except init) and they are both either store or load.  */
    if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0)
        || !dr_equal_offsets_p (dra, drb)
        || DR_IS_READ (dra) != DR_IS_READ (drb))
!     gcc_unreachable ();
  
!   /* The caller has ensured type sizes and steps are equal.  */
    type_size_a = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))));
    type_size_b = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
    if (type_size_a != type_size_b
!       || tree_int_cst_compare (DR_STEP (dra), DR_STEP (drb)) != 0)
!     gcc_unreachable ();
! 
!   /* Do not place the same access in the interleaving chain twice.  */
!   if (tree_int_cst_compare (DR_INIT (dra), DR_INIT (drb)) == 0)
!     return false;
! 
!   /* Check the types are compatible.  */
!   if (!types_compatible_p (TREE_TYPE (DR_REF (dra)),
! 			   TREE_TYPE (DR_REF (drb))))
      return false;
  
    init_a = TREE_INT_CST_LOW (DR_INIT (dra));
    init_b = TREE_INT_CST_LOW (DR_INIT (drb));
    step = TREE_INT_CST_LOW (DR_STEP (dra));
  
!   /* The caller has ensured that DR_INIT (dra) <= DR_INIT (drb).  */
!   gcc_assert (init_a < init_b);
  
!   /* If init_b == init_a + the size of the type * k, we have an
!      interleaving, and DRA is accessed before DRB.  */
!   if ((init_b - init_a) % type_size_a != 0)
!     return false;
  
!   /* The step (if not zero) is greater than the difference between
!      data-refs' inits.  This splits groups into suitable sizes.  */
!   if (step != 0 && step <= (init_b - init_a))
!     return false;
  
!   if (dump_enabled_p ())
!     {
!       dump_printf_loc (MSG_NOTE, vect_location,
! 		       "Detected interleaving ");
!       dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
!       dump_printf (MSG_NOTE,  " and ");
!       dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
      }
  
!   return true;
  }
  
  /* Check if data references pointed by DR_I and DR_J are same or
*************** vect_analyze_data_ref_dependence (struct
*** 578,584 ****
                                    loop_vec_info loop_vinfo, int *max_vf)
  {
    unsigned int i;
!   struct loop *loop = NULL;
    struct data_reference *dra = DDR_A (ddr);
    struct data_reference *drb = DDR_B (ddr);
    stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
--- 319,325 ----
                                    loop_vec_info loop_vinfo, int *max_vf)
  {
    unsigned int i;
!   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
    struct data_reference *dra = DDR_A (ddr);
    struct data_reference *drb = DDR_B (ddr);
    stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
*************** vect_analyze_data_ref_dependence (struct
*** 586,688 ****
    lambda_vector dist_v;
    unsigned int loop_depth;
  
!   /* Don't bother to analyze statements marked as unvectorizable.  */
    if (!STMT_VINFO_VECTORIZABLE (stmtinfo_a)
        || !STMT_VINFO_VECTORIZABLE (stmtinfo_b))
!     return false;
  
    if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
!     {
!       /* Independent data accesses.  */
!       vect_check_interleaving (dra, drb);
!       return false;
!     }
! 
!   if (loop_vinfo)
!     loop = LOOP_VINFO_LOOP (loop_vinfo);
  
!   if ((DR_IS_READ (dra) && DR_IS_READ (drb) && loop_vinfo) || dra == drb)
      return false;
  
    if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
      {
-       gimple earlier_stmt;
- 
-       if (loop_vinfo)
-         {
-           if (dump_enabled_p ())
-             {
-               dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
-                                "versioning for alias required: "
-                                "can't determine dependence between ");
-               dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
-                                  DR_REF (dra));
-               dump_printf (MSG_MISSED_OPTIMIZATION, " and ");
-               dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
-                                  DR_REF (drb));
-             }
- 
-           /* Add to list of ddrs that need to be tested at run-time.  */
-           return !vect_mark_for_runtime_alias_test (ddr, loop_vinfo);
-         }
- 
-       /* When vectorizing a basic block unknown depnedence can still mean
- 	 grouped access.  */
-       if (vect_check_interleaving (dra, drb))
-          return false;
- 
-       /* Read-read is OK (we need this check here, after checking for
-          interleaving).  */
-       if (DR_IS_READ (dra) && DR_IS_READ (drb))
-         return false;
- 
-       if (dump_enabled_p ())
-         {
-           dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
-                            "can't determine dependence between ");
-           dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, DR_REF (dra));
-           dump_printf (MSG_MISSED_OPTIMIZATION,  " and ");
-           dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, DR_REF (drb));
-         }
- 
-       /* We do not vectorize basic blocks with write-write dependencies.  */
-       if (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))
-         return true;
- 
-       /* Check that it's not a load-after-store dependence.  */
-       earlier_stmt = get_earlier_stmt (DR_STMT (dra), DR_STMT (drb));
-       if (DR_IS_WRITE (STMT_VINFO_DATA_REF (vinfo_for_stmt (earlier_stmt))))
-         return true;
- 
-       return false;
-     }
- 
-   /* Versioning for alias is not yet supported for basic block SLP, and
-      dependence distance is unapplicable, hence, in case of known data
-      dependence, basic block vectorization is impossible for now.  */
-   if (!loop_vinfo)
-     {
-       if (dra != drb && vect_check_interleaving (dra, drb))
-         return false;
- 
        if (dump_enabled_p ())
!         {
!           dump_printf_loc (MSG_NOTE, vect_location,
!                            "determined dependence between ");
!           dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
!           dump_printf (MSG_NOTE, " and ");
!           dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
!         }
! 
!       /* Do not vectorize basic blcoks with write-write dependences.  */
!       if (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))
!         return true;
  
!       /* Check if this dependence is allowed in basic block vectorization.  */
!       return vect_drs_dependent_in_basic_block (dra, drb);
      }
  
!   /* Loop-based vectorization and known data dependence.  */
    if (DDR_NUM_DIST_VECTS (ddr) == 0)
      {
        if (dump_enabled_p ())
--- 327,365 ----
    lambda_vector dist_v;
    unsigned int loop_depth;
  
!   /* In loop analysis all data references should be vectorizable.  */
    if (!STMT_VINFO_VECTORIZABLE (stmtinfo_a)
        || !STMT_VINFO_VECTORIZABLE (stmtinfo_b))
!     gcc_unreachable ();
  
+   /* Independent data accesses.  */
    if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
!     return false;
  
!   if (dra == drb
!       || (DR_IS_READ (dra) && DR_IS_READ (drb)))
      return false;
  
+   /* Unknown data dependence.  */
    if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
      {
        if (dump_enabled_p ())
! 	{
! 	  dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
! 			   "versioning for alias required: "
! 			   "can't determine dependence between ");
! 	  dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
! 			     DR_REF (dra));
! 	  dump_printf (MSG_MISSED_OPTIMIZATION, " and ");
! 	  dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
! 			     DR_REF (drb));
! 	}
  
!       /* Add to list of ddrs that need to be tested at run-time.  */
!       return !vect_mark_for_runtime_alias_test (ddr, loop_vinfo);
      }
  
!   /* Known data dependence.  */
    if (DDR_NUM_DIST_VECTS (ddr) == 0)
      {
        if (dump_enabled_p ())
*************** vect_analyze_data_ref_dependence (struct
*** 719,725 ****
  	    }
  
            /* For interleaving, mark that there is a read-write dependency if
!              necessary. We check before that one of the data-refs is store.  */
            if (DR_IS_READ (dra))
              GROUP_READ_WRITE_DEPENDENCE (stmtinfo_a) = true;
  	  else
--- 396,402 ----
  	    }
  
            /* For interleaving, mark that there is a read-write dependency if
!              necessary.  We check before that one of the data-refs is store.  */
            if (DR_IS_READ (dra))
              GROUP_READ_WRITE_DEPENDENCE (stmtinfo_a) = true;
  	  else
*************** vect_analyze_data_ref_dependence (struct
*** 787,821 ****
     the maximum vectorization factor the data dependences allow.  */
  
  bool
! vect_analyze_data_ref_dependences (loop_vec_info loop_vinfo,
!                                    bb_vec_info bb_vinfo, int *max_vf)
  {
    unsigned int i;
-   vec<ddr_p> ddrs = vNULL;
    struct data_dependence_relation *ddr;
  
    if (dump_enabled_p ())
      dump_printf_loc (MSG_NOTE, vect_location,
!                      "=== vect_analyze_dependences ===");
!   if (loop_vinfo)
      {
!       if (!compute_all_dependences (LOOP_VINFO_DATAREFS (loop_vinfo),
! 				    &LOOP_VINFO_DDRS (loop_vinfo),
! 				    LOOP_VINFO_LOOP_NEST (loop_vinfo), true))
! 	return false;
!       ddrs = LOOP_VINFO_DDRS (loop_vinfo);
      }
!   else
      {
!       if (!compute_all_dependences (BB_VINFO_DATAREFS (bb_vinfo),
! 				    &BB_VINFO_DDRS (bb_vinfo),
! 				    vNULL, true))
! 	return false;
!       ddrs = BB_VINFO_DDRS (bb_vinfo);
      }
  
!   FOR_EACH_VEC_ELT (ddrs, i, ddr)
!     if (vect_analyze_data_ref_dependence (ddr, loop_vinfo, max_vf))
        return false;
  
    return true;
--- 464,624 ----
     the maximum vectorization factor the data dependences allow.  */
  
  bool
! vect_analyze_data_ref_dependences (loop_vec_info loop_vinfo, int *max_vf)
  {
    unsigned int i;
    struct data_dependence_relation *ddr;
  
    if (dump_enabled_p ())
      dump_printf_loc (MSG_NOTE, vect_location,
!                      "=== vect_analyze_data_ref_dependences ===");
! 
!   if (!compute_all_dependences (LOOP_VINFO_DATAREFS (loop_vinfo),
! 				&LOOP_VINFO_DDRS (loop_vinfo),
! 				LOOP_VINFO_LOOP_NEST (loop_vinfo), true))
!     return false;
! 
!   FOR_EACH_VEC_ELT (LOOP_VINFO_DDRS (loop_vinfo), i, ddr)
!     if (vect_analyze_data_ref_dependence (ddr, loop_vinfo, max_vf))
!       return false;
! 
!   return true;
! }
! 
! 
! /* Function vect_slp_analyze_data_ref_dependence.
! 
!    Return TRUE if there (might) exist a dependence between a memory-reference
!    DRA and a memory-reference DRB.  When versioning for alias may check a
!    dependence at run-time, return FALSE.  Adjust *MAX_VF according to
!    the data dependence.  */
! 
! static bool
! vect_slp_analyze_data_ref_dependence (struct data_dependence_relation *ddr)
! {
!   struct data_reference *dra = DDR_A (ddr);
!   struct data_reference *drb = DDR_B (ddr);
! 
!   /* We need to check dependences of statements marked as unvectorizable
!      as well, they still can prohibit vectorization.  */
! 
!   /* Independent data accesses.  */
!   if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
!     return false;
! 
!   if (dra == drb)
!     return false;
! 
!   /* Read-read is OK.  */
!   if (DR_IS_READ (dra) && DR_IS_READ (drb))
!     return false;
! 
!   /* Unknown data dependence.  */
!   if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
      {
!       gimple earlier_stmt;
! 
!       if (dump_enabled_p ())
!         {
!           dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
!                            "can't determine dependence between ");
!           dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, DR_REF (dra));
!           dump_printf (MSG_MISSED_OPTIMIZATION,  " and ");
!           dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, DR_REF (drb));
!         }
! 
!       /* We do not vectorize basic blocks with write-write dependencies.  */
!       if (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))
!         return true;
! 
!       /* Check that it's not a load-after-store dependence.  */
!       earlier_stmt = get_earlier_stmt (DR_STMT (dra), DR_STMT (drb));
!       if (DR_IS_WRITE (STMT_VINFO_DATA_REF (vinfo_for_stmt (earlier_stmt))))
!         return true;
! 
!       return false;
      }
! 
!   if (dump_enabled_p ())
      {
!       dump_printf_loc (MSG_NOTE, vect_location,
! 		       "determined dependence between ");
!       dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
!       dump_printf (MSG_NOTE, " and ");
!       dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
      }
  
!   /* Do not vectorize basic blocks with write-write dependences.  */
!   if (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))
!     return true;
! 
!   /* Check dependence between DRA and DRB for basic block vectorization.
!      If the accesses share same bases and offsets, we can compare their initial
!      constant offsets to decide whether they differ or not.  In case of a read-
!      write dependence we check that the load is before the store to ensure that
!      vectorization will not change the order of the accesses.  */
! 
!   HOST_WIDE_INT type_size_a, type_size_b, init_a, init_b;
!   gimple earlier_stmt;
! 
!   /* Check that the data-refs have same bases and offsets.  If not, we can't
!      determine if they are dependent.  */
!   if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0)
!       || !dr_equal_offsets_p (dra, drb))
!     return true;
! 
!   /* Check the types.  */
!   type_size_a = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))));
!   type_size_b = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
! 
!   if (type_size_a != type_size_b
!       || !types_compatible_p (TREE_TYPE (DR_REF (dra)),
!                               TREE_TYPE (DR_REF (drb))))
!     return true;
! 
!   init_a = TREE_INT_CST_LOW (DR_INIT (dra));
!   init_b = TREE_INT_CST_LOW (DR_INIT (drb));
! 
!   /* Two different locations - no dependence.  */
!   if (init_a != init_b)
!     return false;
! 
!   /* 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.  */
!   earlier_stmt = get_earlier_stmt (DR_STMT (dra), DR_STMT (drb));
!   if (DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (earlier_stmt))))
!     return false;
! 
!   return true;
! }
! 
! 
! /* Function vect_analyze_data_ref_dependences.
! 
!    Examine all the data references in the basic-block, and make sure there
!    do not exist any data dependences between them.  Set *MAX_VF according to
!    the maximum vectorization factor the data dependences allow.  */
! 
! bool
! vect_slp_analyze_data_ref_dependences (bb_vec_info bb_vinfo)
! {
!   struct data_dependence_relation *ddr;
!   unsigned int i;
! 
!   if (dump_enabled_p ())
!     dump_printf_loc (MSG_NOTE, vect_location,
!                      "=== vect_slp_analyze_data_ref_dependences ===");
! 
!   if (!compute_all_dependences (BB_VINFO_DATAREFS (bb_vinfo),
! 				&BB_VINFO_DDRS (bb_vinfo),
! 				vNULL, true))
!     return false;
! 
!   FOR_EACH_VEC_ELT (BB_VINFO_DDRS (bb_vinfo), i, ddr)
!     if (vect_slp_analyze_data_ref_dependence (ddr))
        return false;
  
    return true;
*************** vect_analyze_data_ref_access (struct dat
*** 2567,2572 ****
--- 2370,2425 ----
    return vect_analyze_group_access (dr);
  }
  
+ /* Compare two data-references DRA and DRB to group them into chunks
+    suitable for grouping.  */
+ 
+ static int
+ dr_group_sort_cmp (const void *dra_, const void *drb_)
+ {
+   data_reference_p dra = *(data_reference_p *)const_cast<void *>(dra_);
+   data_reference_p drb = *(data_reference_p *)const_cast<void *>(drb_);
+   int cmp;
+ 
+   /* Stabilize sort.  */
+   if (dra == drb)
+     return 0;
+ 
+   /* Ordering of DRs with unequal base or offset according to a hash.  */
+   if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0)
+       || !dr_equal_offsets_p (dra, drb))
+     {
+       hashval_t h1
+ 	= iterative_hash_expr (DR_BASE_ADDRESS (dra),
+ 			       iterative_hash_expr (DR_OFFSET (dra), 0));
+       hashval_t h2
+ 	= iterative_hash_expr (DR_BASE_ADDRESS (drb),
+ 			       iterative_hash_expr (DR_OFFSET (drb), 0));
+       if (h1 == h2)
+ 	gcc_unreachable ();
+       return h1 < h2 ? -1 : 1;
+     }
+ 
+   /* Else put reads first.  */
+   if (DR_IS_READ (dra) != DR_IS_READ (drb))
+     return DR_IS_READ (dra) ? -1 : 1;
+ 
+   /* Then sort after access size.  */
+   cmp = tree_int_cst_compare (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))),
+ 			      TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
+   if (cmp != 0)
+     return cmp;
+ 
+   /* And after step.  */
+   cmp = tree_int_cst_compare (DR_STEP (dra), DR_STEP (drb));
+   if (cmp != 0)
+     return cmp;
+ 
+   /* Then sort after DR_INIT.  In case of identical DRs sort after stmt UID.  */
+   cmp = tree_int_cst_compare (DR_INIT (dra), DR_INIT (drb));
+   if (cmp == 0)
+     return gimple_uid (DR_STMT (dra)) < gimple_uid (DR_STMT (drb)) ? -1 : 1;
+   return cmp;
+ }
  
  /* Function vect_analyze_data_ref_accesses.
  
*************** vect_analyze_data_ref_accesses (loop_vec
*** 2593,2598 ****
--- 2446,2497 ----
    else
      datarefs = BB_VINFO_DATAREFS (bb_vinfo);
  
+   if (datarefs.is_empty ())
+     return true;
+ 
+   /* Sort the array of datarefs to make building the interleaving chains
+      linear.  */
+   qsort (datarefs.address(), datarefs.length (),
+ 	 sizeof (data_reference_p), dr_group_sort_cmp);
+ 
+   /* Build the interleaving chains.  */
+   for (i = 0; i < datarefs.length () - 1;)
+     {
+       data_reference_p dra = datarefs[i];
+       stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
+       stmt_vec_info lastinfo = NULL;
+       for (i = i + 1; i < datarefs.length (); ++i)
+ 	{
+ 	  data_reference_p drb = datarefs[i];
+ 	  stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
+ 	  /* Check that the data-refs have same first location (except init)
+ 	     and they are both either store or load (not load and store).
+ 	     Check that the data-refs have the same size and step.  */
+ 	  if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0)
+ 	      || !dr_equal_offsets_p (dra, drb)
+ 	      || DR_IS_READ (dra) != DR_IS_READ (drb)
+ 	      || tree_int_cst_compare (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))),
+ 				       TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))))
+ 	      || tree_int_cst_compare (DR_STEP (dra), DR_STEP (drb)))
+ 	    break;
+ 	  /* ???  Imperfect sorting (non-compatible types, non-modulo
+ 	     accesses, same accesses) can lead to a group to be artificially
+ 	     split here as we don't just skip over those.  If it really
+ 	     matters we can push those to a worklist and re-iterate
+ 	     over them.  The we can just skip ahead to the next DR here.  */
+ 	  if (!vect_check_interleaving (dra, drb))
+ 	    break;
+ 	  if (!GROUP_FIRST_ELEMENT (stmtinfo_a))
+ 	    {
+ 	      GROUP_FIRST_ELEMENT (stmtinfo_a) = DR_STMT (dra);
+ 	      lastinfo = stmtinfo_a;
+ 	    }
+ 	  GROUP_FIRST_ELEMENT (stmtinfo_b) = DR_STMT (dra);
+ 	  GROUP_NEXT_ELEMENT (lastinfo) = DR_STMT (drb);
+ 	  lastinfo = stmtinfo_b;
+ 	}
+     }
+ 
    FOR_EACH_VEC_ELT (datarefs, i, dr)
      if (STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr))) 
          && !vect_analyze_data_ref_access (dr))
Index: trunk/gcc/tree-vect-slp.c
===================================================================
*** trunk.orig/gcc/tree-vect-slp.c	2013-02-27 14:53:36.000000000 +0100
--- trunk/gcc/tree-vect-slp.c	2013-02-27 14:57:30.977783197 +0100
*************** vect_slp_analyze_bb_1 (basic_block bb)
*** 2089,2095 ****
    slp_instance instance;
    int i;
    int min_vf = 2;
-   int max_vf = MAX_VECTORIZATION_FACTOR;
  
    bb_vinfo = new_bb_vec_info (bb);
    if (!bb_vinfo)
--- 2089,2094 ----
*************** vect_slp_analyze_bb_1 (basic_block bb)
*** 2117,2126 ****
        return NULL;
      }
  
    vect_pattern_recog (NULL, bb_vinfo);
  
!   if (!vect_analyze_data_ref_dependences (NULL, bb_vinfo, &max_vf)
!        || min_vf > max_vf)
       {
         if (dump_enabled_p ())
  	 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
--- 2116,2135 ----
        return NULL;
      }
  
+   if (!vect_analyze_data_ref_accesses (NULL, bb_vinfo))
+     {
+      if (dump_enabled_p ())
+        dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ 			"not vectorized: unhandled data access in "
+ 			"basic block.\n");
+ 
+       destroy_bb_vec_info (bb_vinfo);
+       return NULL;
+     }
+ 
    vect_pattern_recog (NULL, bb_vinfo);
  
!   if (!vect_slp_analyze_data_ref_dependences (bb_vinfo))
       {
         if (dump_enabled_p ())
  	 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
*************** vect_slp_analyze_bb_1 (basic_block bb)
*** 2140,2156 ****
  
        destroy_bb_vec_info (bb_vinfo);
        return NULL;
-     }
- 
-   if (!vect_analyze_data_ref_accesses (NULL, bb_vinfo))
-     {
-      if (dump_enabled_p ())
-        dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
- 			"not vectorized: unhandled data access in "
- 			"basic block.\n");
- 
-       destroy_bb_vec_info (bb_vinfo);
-       return NULL;
      }
  
    /* Check the SLP opportunities in the basic block, analyze and build SLP
--- 2149,2154 ----
Index: trunk/gcc/tree-vect-loop.c
===================================================================
*** trunk.orig/gcc/tree-vect-loop.c	2013-02-27 14:53:36.000000000 +0100
--- trunk/gcc/tree-vect-loop.c	2013-02-27 14:57:30.978783208 +0100
*************** vect_analyze_loop_2 (loop_vec_info loop_
*** 1603,1608 ****
--- 1603,1620 ----
        return false;
      }
  
+   /* Analyze the access patterns of the data-refs in the loop (consecutive,
+      complex, etc.). FORNOW: Only handle consecutive access pattern.  */
+ 
+   ok = vect_analyze_data_ref_accesses (loop_vinfo, NULL);
+   if (!ok)
+     {
+       if (dump_enabled_p ())
+ 	dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ 			 "bad data access.");
+       return false;
+     }
+ 
    /* Classify all cross-iteration scalar data-flow cycles.
       Cross-iteration cycles caused by virtual phis are analyzed separately.  */
  
*************** vect_analyze_loop_2 (loop_vec_info loop_
*** 1626,1632 ****
       the dependences.
       FORNOW: fail at the first data dependence that we encounter.  */
  
!   ok = vect_analyze_data_ref_dependences (loop_vinfo, NULL, &max_vf);
    if (!ok
        || max_vf < min_vf)
      {
--- 1638,1644 ----
       the dependences.
       FORNOW: fail at the first data dependence that we encounter.  */
  
!   ok = vect_analyze_data_ref_dependences (loop_vinfo, &max_vf);
    if (!ok
        || max_vf < min_vf)
      {
*************** vect_analyze_loop_2 (loop_vec_info loop_
*** 1664,1681 ****
        return false;
      }
  
-   /* Analyze the access patterns of the data-refs in the loop (consecutive,
-      complex, etc.). FORNOW: Only handle consecutive access pattern.  */
- 
-   ok = vect_analyze_data_ref_accesses (loop_vinfo, NULL);
-   if (!ok)
-     {
-       if (dump_enabled_p ())
- 	dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
- 			 "bad data access.");
-       return false;
-     }
- 
    /* Prune the list of ddrs to be tested at run-time by versioning for alias.
       It is important to call pruning after vect_analyze_data_ref_accesses,
       since we use grouping information gathered by interleaving analysis.  */
--- 1676,1681 ----
Index: trunk/gcc/tree-vectorizer.h
===================================================================
*** trunk.orig/gcc/tree-vectorizer.h	2013-02-27 14:53:36.000000000 +0100
--- trunk/gcc/tree-vectorizer.h	2013-02-27 14:57:30.978783208 +0100
*************** extern enum dr_alignment_support vect_su
*** 914,921 ****
                                             (struct data_reference *, bool);
  extern tree vect_get_smallest_scalar_type (gimple, HOST_WIDE_INT *,
                                             HOST_WIDE_INT *);
! extern bool vect_analyze_data_ref_dependences (loop_vec_info, bb_vec_info,
! 					       int *);
  extern bool vect_enhance_data_refs_alignment (loop_vec_info);
  extern bool vect_analyze_data_refs_alignment (loop_vec_info, bb_vec_info);
  extern bool vect_verify_datarefs_alignment (loop_vec_info, bb_vec_info);
--- 914,921 ----
                                             (struct data_reference *, bool);
  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, bb_vec_info);
  extern bool vect_verify_datarefs_alignment (loop_vec_info, bb_vec_info);


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]