public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [PATCH] AV - Use distance vector
@ 2004-09-16 17:01 Devang Patel
  2004-09-21 22:07 ` Richard Henderson
  0 siblings, 1 reply; 10+ messages in thread
From: Devang Patel @ 2004-09-16 17:01 UTC (permalink / raw)
  To: GCC Patches

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

This patch updates auto vectorizer to use distance
vector info while analyzing data dependence. It uses
existing API to compute distance vector.

With this patch included test cases are auto vectorized.
This patch is also required to vectorize if-converted
loops.

Bootstrapped and tested on powerpc-darwin.

OK?
Thanks,
-
Devang

2004-09-15  Devang Patel  <dpatel@apple.com>

         * tree-data-ref.c (compute_distance_vector): Export.
         * tree-data-ref.h (compute_distance_vector): Same.
         * 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.

         testsuite

         * gcc.dg/vect/vect-20040915-1.c: New test.

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

Index: gcc/tree-data-ref.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-data-ref.c,v
retrieving revision 2.7
diff -Idpatel.pbxuser -c -3 -p -r2.7 tree-data-ref.c
*** gcc/tree-data-ref.c	10 Sep 2004 15:09:38 -0000	2.7
--- gcc/tree-data-ref.c	15 Sep 2004 20:57:33 -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)
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	15 Sep 2004 20:57:33 -0000
*************** struct data_dependence_relation
*** 147,152 ****
--- 147,153 ----
  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 *ddr);
  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.8
diff -Idpatel.pbxuser -c -3 -p -r2.8 tree-vectorizer.c
*** gcc/tree-vectorizer.c	10 Sep 2004 10:44:47 -0000	2.8
--- gcc/tree-vectorizer.c	15 Sep 2004 20:57:34 -0000
*************** vect_analyze_scalar_cycles (loop_vec_inf
*** 1973,1982 ****
  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))
      {
--- 2116,2130 ----
  static bool
  vect_analyze_data_ref_dependence (struct data_reference *dra,
  				  struct data_reference *drb, 
! 				  struct loop *loop,
! 				  loop_vec_info loop_info)
  {
    bool differ_p;
    struct data_dependence_relation *ddr;
+   unsigned int i;
+   bool dep_exists = true;
+   int vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_info);
+   tree vf = NULL_TREE;
  
    if (!array_base_name_differ_p (dra, drb, &differ_p))
      {
*************** vect_analyze_data_ref_dependence (struct
*** 2000,2005 ****
--- 2148,2178 ----
    if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
      return false;
    
+   /* Check distance vector.  */
+   compute_distance_vector (ddr);
+   vf = build_int_cst (unsigned_type_node, vectorization_factor);
+ 
+   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+     {
+       struct subscript *subscript;
+  	  
+       subscript = DDR_SUBSCRIPT (ddr, i);
+ 
+       if (SUB_DISTANCE (subscript) == integer_zero_node)
+ 	dep_exists = false;
+       else if (INT_CST_LT (vf, SUB_DISTANCE (subscript)))
+ 	{
+ 	  dep_exists = false;
+ 
+ 	  if (TREE_INT_CST_LOW (vf) == TREE_INT_CST_LOW (SUB_DISTANCE (subscript))
+ 	      && TREE_INT_CST_HIGH (vf) == TREE_INT_CST_HIGH (SUB_DISTANCE (subscript)))
+ 	    dep_exists = true;
+ 	  }
+     }
+ 
+   if (!dep_exists)
+     return false;
+ 
    if (vect_debug_stats (loop) || vect_debug_details (loop))
      {
        fprintf (dump_file,
*************** vect_analyze_data_ref_dependences (loop_
*** 2045,2051 ****
  	    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;
  	}
      }
--- 2218,2224 ----
  	    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, loop_vinfo))
  	    return false;
  	}
      }
*************** vect_analyze_data_ref_dependences (loop_
*** 2062,2068 ****
  	  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;
  	}
      }
--- 2235,2241 ----
  	  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, loop_vinfo))
  	    return false;
  	}
      }
*************** vect_analyze_loop (struct loop *loop)
*** 3275,3327 ****
      }
  
  
!   /* 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;
      }
--- 3450,3500 ----
      }
  
  
!   /* 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;
      }
/* { dg-do run } */
/* { dg-options "-O2 -ftree-vectorize -fdump-tree-vect-stats -maltivec" { target powerpc*-*-* } } */
/* { dg-options "-O2 -ftree-vectorize -fdump-tree-vect-stats -msse2" { target i?86-*-* x86_64-*-* } } */

#include <stdarg.h>
#include <signal.h>

#define N 64
#define MAX 42

extern void abort(void); 

int main ()
{  
  int A[N];
  int B[N];
  int C[N];

  int i, j;

  for (i = 0; i < N; i++)
    {
      A[i] = i;
      B[i] = i;
      C[i] = i;
    }
  /* Vectorizable */
  for (i = 0; i < 16; i++)
    {
      A[i] = A[i+20];
    }

  /* check results:  */
  for (i = 0; i < 16; i++)
    {
      if (A[i] != A[i+20])
	abort ();
    }

  /* Vectorizable */
  for (i = 0; i < 16; i++)
    {
      B[i] = B[i] + 5;
    }

  /* check results:  */
  for (i = 0; i < 16; i++)
    {
      if (B[i] != C[i] + 5)
	abort ();
    }

  /* Not vectorizable */
  for (i = 0; i < 4; i++)
    {
      C[i] = C[i+4];
    }

  /* check results:  */
  for (i = 0; i < 4; i++)
    {
      if (C[i] != C[i+4])
	abort ();
    }


  return 0;
}



/* { dg-final { scan-tree-dump-times "vectorized 2 loops" 1 "vect" } } */

^ permalink raw reply	[flat|nested] 10+ messages in thread
* Re: [PATCH] AV - Use distance vector
@ 2004-09-23  0:29 Richard Kenner
  0 siblings, 0 replies; 10+ messages in thread
From: Richard Kenner @ 2004-09-23  0:29 UTC (permalink / raw)
  To: rth; +Cc: gcc-patches

    > It returns -1, 0 or 1.

    Do those satisfy <0, ==0, >0?  Why yes, I think they do.

    I really do mean not necessarily 1, no matter what the current
    implementation of the function does.  Please do as I ask.

I was originally going to send a message agreeing with you and making the
distinction between the specification and the implementation, but then I
checked and saw that the *specification* also says -1, 0, and 1, meaning it's
indeed legitimate to rely on it being 1, unlike if that was just what the
implementation did.  (I originally wrote that function and was now surprised
I'd done it that way.)

I agree with your comment above, but also think we ought to change the
specification of it to say < 0, 0, and >0 instead of -1, 0 and 1.

^ permalink raw reply	[flat|nested] 10+ messages in thread
end of thread, other threads:[~2004-10-12 21:27 UTC | newest]

Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2004-09-16 17:01 [PATCH] AV - Use distance vector Devang Patel
2004-09-21 22:07 ` Richard Henderson
2004-09-21 22:17   ` Devang Patel
2004-09-22 19:54   ` Devang Patel
2004-09-22 20:37     ` Richard Henderson
2004-09-22 22:19       ` Devang Patel
2004-09-22 23:45         ` Richard Henderson
2004-09-28 20:04           ` Devang Patel
2004-10-12 21:36             ` Ping : " Devang Patel
2004-09-23  0:29 Richard Kenner

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).