Ping : [PATCH] AV - Use distance vector

[Devang Patel <dpatel@apple.com>]

[-- Attachment #1: Type: text/plain, Size: 657 bytes --]


This time ping! with updated patch based on Dorit and Ira's feedback.

Thanks,
-
Devang

2004-10-12  Devang Patel  <dpatel@apple.com>

         * tree-data-ref.c (compute_distance_vector, 
build_classic_dist_vector):
         Make externally visible.
         * tree-data-ref.h (compute_distance_vector, 
build_classic_dist_vector):
         Export.
         * tree-vectorizer.c (vect_analyze_data_ref_dependence): new 
parameter,
         loop_vinfo. Use distance vector.
         (vect_analyze_data_ref_dependences): Supply new parameter.
         (vect_analyze_loop): Analyze operations before data dependences.
         (vect_build_dist_vector): New.


[-- Attachment #2: ifc2_fsf_mainline.2.4.diff --]
[-- Type: application/octet-stream, Size: 11013 bytes --]

Index: gcc/tree-data-ref.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-data-ref.c,v
retrieving revision 2.8
diff -Idpatel.pbxuser -c -3 -p -r2.8 tree-data-ref.c
*** gcc/tree-data-ref.c	19 Sep 2004 18:01:47 -0000	2.8
--- gcc/tree-data-ref.c	12 Oct 2004 21:14:28 -0000
*************** init_data_ref (tree stmt, 
*** 598,604 ****
  /* When there exists a dependence relation, determine its distance
     vector.  */
  
! static void
  compute_distance_vector (struct data_dependence_relation *ddr)
  {
    if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
--- 598,604 ----
  /* When there exists a dependence relation, determine its distance
     vector.  */
  
! void
  compute_distance_vector (struct data_dependence_relation *ddr)
  {
    if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
*************** subscript_dependence_tester (struct data
*** 1433,1439 ****
     NB_LOOPS is the total number of loops we are considering.
     FIRST_LOOP is the loop->num of the first loop.  */
  
! static void
  build_classic_dist_vector (struct data_dependence_relation *ddr, 
  			   int nb_loops, unsigned int first_loop)
  {
--- 1433,1439 ----
     NB_LOOPS is the total number of loops we are considering.
     FIRST_LOOP is the loop->num of the first loop.  */
  
! void
  build_classic_dist_vector (struct data_dependence_relation *ddr, 
  			   int nb_loops, unsigned int first_loop)
  {
Index: gcc/tree-data-ref.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-data-ref.h,v
retrieving revision 2.4
diff -Idpatel.pbxuser -c -3 -p -r2.4 tree-data-ref.h
*** gcc/tree-data-ref.h	10 Sep 2004 15:09:38 -0000	2.4
--- gcc/tree-data-ref.h	12 Oct 2004 21:14:28 -0000
*************** struct data_dependence_relation
*** 147,152 ****
--- 147,155 ----
  struct data_dependence_relation *initialize_data_dependence_relation 
  (struct data_reference *, struct data_reference *);
  void compute_affine_dependence (struct data_dependence_relation *);
+ void compute_distance_vector (struct data_dependence_relation *);
+ void build_classic_dist_vector (struct data_dependence_relation *, int, 
+ 				unsigned int);
  extern void analyze_all_data_dependences (struct loops *);
  extern void compute_data_dependences_for_loop (unsigned, struct loop *, 
  					       varray_type *, varray_type *);
Index: gcc/tree-vectorizer.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-vectorizer.c,v
retrieving revision 2.13
diff -Idpatel.pbxuser -c -3 -p -r2.13 tree-vectorizer.c
*** gcc/tree-vectorizer.c	28 Sep 2004 07:59:52 -0000	2.13
--- gcc/tree-vectorizer.c	12 Oct 2004 21:14:29 -0000
*************** stmt_vec_info new_stmt_vec_info (tree st
*** 214,219 ****
--- 218,226 ----
  static bool vect_debug_stats (struct loop *loop);
  static bool vect_debug_details (struct loop *loop);
  
+ /* Utilities for dependence analysis.  */
+ static unsigned int vect_build_dist_vector (struct loop *,
+ 					    struct data_dependence_relation *);
  
  /* Function new_stmt_vec_info.
  
*************** vect_analyze_scalar_cycles (loop_vec_inf
*** 2394,2399 ****
--- 2586,2621 ----
    return true;
  }
  
+ /* Function vect_build_dist_vector.
+ 
+    Build classic dist vector for dependence relation DDR using LOOP's loop
+    nest. Return LOOP's depth in its loop nest.  */
+ 
+ static unsigned int
+ vect_build_dist_vector (struct loop *loop,
+ 			struct data_dependence_relation *ddr)
+ {
+   struct loop *loop_nest = loop;
+   unsigned int loop_depth = 1;
+ 
+   /* Find loop nest and loop depth.  */
+   while (loop_nest)
+     {
+       if (loop_nest->outer && loop_nest->outer->outer)
+ 	{
+ 	  loop_nest = loop_nest->outer;
+ 	  loop_depth++;
+ 	}
+       else
+ 	break;
+     }
+ 
+   /* Compute distance vector.  */
+   compute_distance_vector (ddr);
+   build_classic_dist_vector (ddr, loop_depth, loop_nest->num);
+ 
+   return loop_depth - 1;
+ }
  
  /* Function vect_analyze_data_ref_dependence.
  
*************** vect_analyze_scalar_cycles (loop_vec_inf
*** 2403,2413 ****
  static bool
  vect_analyze_data_ref_dependence (struct data_reference *dra,
  				  struct data_reference *drb, 
! 				  struct loop *loop)
  {
    bool differ_p; 
    struct data_dependence_relation *ddr;
!   
    if (!array_base_name_differ_p (dra, drb, &differ_p))
      {
        if (vect_debug_stats (loop) || vect_debug_details (loop))   
--- 2625,2639 ----
  static bool
  vect_analyze_data_ref_dependence (struct data_reference *dra,
  				  struct data_reference *drb, 
! 				  loop_vec_info loop_info)
  {
    bool differ_p; 
    struct data_dependence_relation *ddr;
!   int vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_info);
!   struct loop *loop = LOOP_VINFO_LOOP (loop_info);
!   unsigned int loop_depth = 0;
!   int dist;
! 
    if (!array_base_name_differ_p (dra, drb, &differ_p))
      {
        if (vect_debug_stats (loop) || vect_debug_details (loop))   
*************** vect_analyze_data_ref_dependence (struct
*** 2429,2434 ****
--- 2655,2676 ----
  
    if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
      return false;
+ 
+   if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
+     return true;
+ 
+   loop_depth = vect_build_dist_vector (loop, ddr);
+ 
+   dist = DDR_DIST_VECT (ddr)[loop_depth];
+ 
+   /* Same loop iteration.  */
+   if (dist == 0)
+      return false;
+ 
+   if (dist >= vectorization_factor)
+     /* Dependence distance does not create dependence, as far as vectorization
+        is concerned, in this case.  */
+     return false;
    
    if (vect_debug_stats (loop) || vect_debug_details (loop))
      {
*************** vect_analyze_data_ref_dependence (struct
*** 2446,2455 ****
  /* Function vect_analyze_data_ref_dependences.
  
     Examine all the data references in the loop, and make sure there do not
!    exist any data dependences between them.
! 
!    TODO: dependences which distance is greater than the vectorization factor
!          can be ignored.   */
  
  static bool
  vect_analyze_data_ref_dependences (loop_vec_info loop_vinfo)
--- 2688,2694 ----
  /* Function vect_analyze_data_ref_dependences.
  
     Examine all the data references in the loop, and make sure there do not
!    exist any data dependences between them.  */
  
  static bool
  vect_analyze_data_ref_dependences (loop_vec_info loop_vinfo)
*************** vect_analyze_data_ref_dependences (loop_
*** 2457,2463 ****
    unsigned int i, j;
    varray_type loop_write_refs = LOOP_VINFO_DATAREF_WRITES (loop_vinfo);
    varray_type loop_read_refs = LOOP_VINFO_DATAREF_READS (loop_vinfo);
-   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
  
    /* Examine store-store (output) dependences.  */
  
--- 2696,2701 ----
*************** vect_analyze_data_ref_dependences (loop_
*** 2475,2481 ****
  	    VARRAY_GENERIC_PTR (loop_write_refs, i);
  	  struct data_reference *drb =
  	    VARRAY_GENERIC_PTR (loop_write_refs, j);
! 	  if (vect_analyze_data_ref_dependence (dra, drb, loop))
  	    return false;
  	}
      }
--- 2713,2719 ----
  	    VARRAY_GENERIC_PTR (loop_write_refs, i);
  	  struct data_reference *drb =
  	    VARRAY_GENERIC_PTR (loop_write_refs, j);
! 	  if (vect_analyze_data_ref_dependence (dra, drb, loop_vinfo))
  	    return false;
  	}
      }
*************** vect_analyze_data_ref_dependences (loop_
*** 2492,2498 ****
  	  struct data_reference *dra = VARRAY_GENERIC_PTR (loop_read_refs, i);
  	  struct data_reference *drb =
  	    VARRAY_GENERIC_PTR (loop_write_refs, j);
! 	  if (vect_analyze_data_ref_dependence (dra, drb, loop))
  	    return false;
  	}
      }
--- 2730,2736 ----
  	  struct data_reference *dra = VARRAY_GENERIC_PTR (loop_read_refs, i);
  	  struct data_reference *drb =
  	    VARRAY_GENERIC_PTR (loop_write_refs, j);
! 	  if (vect_analyze_data_ref_dependence (dra, drb, loop_vinfo))
  	    return false;
  	}
      }
*************** vect_analyze_loop (struct loop *loop)
*** 4009,4058 ****
        return NULL;
      }
  
!   /* Analyze data dependences between the data-refs in the loop. 
!      FORNOW: fail at the first data dependence that we encounter.  */
  
!   ok = vect_analyze_data_ref_dependences (loop_vinfo);
    if (!ok)
      {
        if (vect_debug_details (loop))
! 	fprintf (dump_file, "bad data dependence.");
        destroy_loop_vec_info (loop_vinfo);
        return NULL;
      }
  
!   /* 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);
    if (!ok)
      {
        if (vect_debug_details (loop))
! 	fprintf (dump_file, "bad data access.");
        destroy_loop_vec_info (loop_vinfo);
        return NULL;
      }
  
!   /* Analyze the alignment of the data-refs in the loop.
!      FORNOW: Only aligned accesses are handled.  */
  
!   ok = vect_analyze_data_refs_alignment (loop_vinfo);
    if (!ok)
      {
        if (vect_debug_details (loop))
! 	fprintf (dump_file, "bad data alignment.");
        destroy_loop_vec_info (loop_vinfo);
        return NULL;
      }
  
!   /* Scan all the operations in the loop and make sure they are
!      vectorizable.  */
  
!   ok = vect_analyze_operations (loop_vinfo);
    if (!ok)
      {
        if (vect_debug_details (loop))
! 	fprintf (dump_file, "bad operation or unsupported loop bound.");
        destroy_loop_vec_info (loop_vinfo);
        return NULL;
      }
--- 4246,4295 ----
        return NULL;
      }
  
!   /* Analyze the alignment of the data-refs in the loop.
!      FORNOW: Only aligned accesses are handled.  */
  
!   ok = vect_analyze_data_refs_alignment (loop_vinfo);
    if (!ok)
      {
        if (vect_debug_details (loop))
! 	fprintf (dump_file, "bad data alignment.");
        destroy_loop_vec_info (loop_vinfo);
        return NULL;
      }
  
!   /* Scan all the operations in the loop and make sure they are
!      vectorizable.  */
  
!   ok = vect_analyze_operations (loop_vinfo);
    if (!ok)
      {
        if (vect_debug_details (loop))
! 	fprintf (dump_file, "bad operation or unsupported loop bound.");
        destroy_loop_vec_info (loop_vinfo);
        return NULL;
      }
  
!   /* Analyze data dependences between the data-refs in the loop. 
!      FORNOW: fail at the first data dependence that we encounter.  */
  
!   ok = vect_analyze_data_ref_dependences (loop_vinfo);
    if (!ok)
      {
        if (vect_debug_details (loop))
! 	fprintf (dump_file, "bad data dependence.");
        destroy_loop_vec_info (loop_vinfo);
        return NULL;
      }
  
!   /* 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);
    if (!ok)
      {
        if (vect_debug_details (loop))
! 	fprintf (dump_file, "bad data access.");
        destroy_loop_vec_info (loop_vinfo);
        return NULL;
      }