[patch] [autovect] don't allow changing order of computation

[patch] [autovect] don't allow changing order of computation

[Dorit Nuzman]

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


Don't allow changing the order of the computation in the inner-loop during
outer-loop vectorization.

Rational: The vectorized inner-loop executes sequentially (each vectorized
inner-loop iteration contributes to VF outer-loop iterations in parallel).
Reductions in the inner-loop are therefore also computed in order (which is
why we don't need to worry if reassociation/fast-math etc allowed). There
were a few remaining bits that did change the order of the computation in
the inner-loop - the WIDEN_MULT_EVEN/ODD idioms and the widening
reduction-patterns DOT_PROD and WIDEN_SUM. So this patch makes sure we
don't use these idioms in the inner-loop when vectorizing the outer-loop.

This also makes this fix -
http://gcc.gnu.org/ml/gcc-patches/2007-08/msg00013.html - redundant.

Bootstrapped with vectorization enabled on powerpc64-linux and tested on
the vectorizer testcases on powerpc64-linux and i386-linux.
Committed to autovect-branch.

dorit

        * tree-vect-analyze.c (vect_mark_relevant): Revert last change.
        * tree-vectorize.c (supportable_widening_operation): Don't allow
        unrodered vectorization in the inner-loop when doing outer-loop
        vectorization.
        * tree-vect-patterns.c (vect_recog_dot_prod_pattern): Don't allow
        in the inner-loop when doing outer-loop vectorization. Add
        documentation and printout.
        (vect_recog_widen_sum_pattern): Likewise.

        * gcc.dg/vect/vect-outer-4g.c: Add check for pattern not allowed.
Make
        check-loop in main unvectorizable.
        * gcc.dg/vect/vect-outer-4k.c: Likewise.
        * gcc.dg/vect/vect-outer-4l.c: Likewise.
        * gcc.dg/vect/vect-outer-4f.c: Likewise.

(See attached file: aug4.txt)

[-- Attachment #2: aug4.txt --]
[-- Type: text/plain, Size: 12701 bytes --]

Index: testsuite/gcc.dg/vect/vect-outer-4g.c
===================================================================
*** testsuite/gcc.dg/vect/vect-outer-4g.c	(revision 127202)
--- testsuite/gcc.dg/vect/vect-outer-4g.c	(working copy)
*************** foo (){
*** 26,31 ****
--- 26,41 ----
    return s;
  }
  
+ unsigned int
+ bar (int i, unsigned int diff, unsigned short *in)
+ {
+     int j;
+     for (j = 0; j < M; j+=8) {
+       diff += in[j+i];
+     }
+     return diff;
+ }
+ 
  int main (void)
  {
    int i, j;
*************** int main (void)
*** 42,50 ****
  
    for (i = 0; i < N; i++) {
      diff = 0;
!     for (j = 0; j < M; j+=8) {
!       diff += in[j+i];
!     }
      s += diff;
    }
  
--- 52,58 ----
  
    for (i = 0; i < N; i++) {
      diff = 0;
!     diff = bar (i, diff, in);
      s += diff;
    }
  
*************** int main (void)
*** 55,58 ****
--- 63,67 ----
  }
  
  /* { dg-final { scan-tree-dump-times "OUTER LOOP VECTORIZED" 1 "vect" { xfail *-*-* } } } */
+ /* { dg-final { scan-tree-dump-times "vect_recog_widen_sum_pattern: not allowed" 1 "vect" } } */
  /* { dg-final { cleanup-tree-dump "vect" } } */
Index: testsuite/gcc.dg/vect/vect-outer-4k.c
===================================================================
*** testsuite/gcc.dg/vect/vect-outer-4k.c	(revision 127202)
--- testsuite/gcc.dg/vect/vect-outer-4k.c	(working copy)
*************** foo (){
*** 26,31 ****
--- 26,41 ----
    return s;
  }
  
+ unsigned int
+ bar (int i, unsigned int diff, unsigned short *in)
+ {
+     int j;
+     for (j = 0; j < M; j+=8) {
+       diff += in[j+i];
+     }
+     return diff;
+ }
+ 
  int main (void)
  {
    int i, j;
*************** int main (void)
*** 42,50 ****
  
    for (i = 0; i < N; i++) {
      diff = 0;
!     for (j = 0; j < M; j+=8) {
!       diff += in[j+i];
!     }
      s += (diff>>3);
    }
  
--- 52,58 ----
  
    for (i = 0; i < N; i++) {
      diff = 0;
!     diff = bar (i, diff, in);
      s += (diff>>3);
    }
  
*************** int main (void)
*** 55,58 ****
--- 63,67 ----
  }
  
  /* { dg-final { scan-tree-dump-times "OUTER LOOP VECTORIZED" 1 "vect" { xfail *-*-* }  } } */
+ /* { dg-final { scan-tree-dump-times "vect_recog_widen_sum_pattern: not allowed" 1 "vect" } } */
  /* { dg-final { cleanup-tree-dump "vect" } } */
Index: testsuite/gcc.dg/vect/vect-outer-4l.c
===================================================================
*** testsuite/gcc.dg/vect/vect-outer-4l.c	(revision 127202)
--- testsuite/gcc.dg/vect/vect-outer-4l.c	(working copy)
*************** foo (){
*** 28,33 ****
--- 28,43 ----
    return s;
  }
  
+ unsigned int
+ bar (int i, unsigned int diff, unsigned short *in)
+ {
+     int j;
+     for (j = 0; j < M; j+=8) {
+       diff += in[j+i];
+     }
+     return diff;
+ }
+ 
  int main (void)
  {
    int i, j;
*************** int main (void)
*** 45,53 ****
    for (i = 0; i < N; i++) {
      arr[i] = 3;
      diff = 0;
!     for (j = 0; j < M; j+=8) {
!       diff += in[j+i];
!     }
      s += diff;
    }
  
--- 55,61 ----
    for (i = 0; i < N; i++) {
      arr[i] = 3;
      diff = 0;
!     diff = bar (i, diff, in);
      s += diff;
    }
  
*************** int main (void)
*** 58,61 ****
--- 66,70 ----
  }
  
  /* { dg-final { scan-tree-dump-times "OUTER LOOP VECTORIZED" 1 "vect" { xfail *-*-* } } } */
+ /* { dg-final { scan-tree-dump-times "vect_recog_widen_sum_pattern: not allowed" 1 "vect" } } */
  /* { dg-final { cleanup-tree-dump "vect" } } */
Index: testsuite/gcc.dg/vect/vect-outer-4f.c
===================================================================
*** testsuite/gcc.dg/vect/vect-outer-4f.c	(revision 127202)
--- testsuite/gcc.dg/vect/vect-outer-4f.c	(working copy)
*************** int main (void)
*** 50,53 ****
--- 50,54 ----
  }
  
  /* { dg-final { scan-tree-dump-times "OUTER LOOP VECTORIZED" 1 "vect" { xfail *-*-* } } } */
+ /* { dg-final { scan-tree-dump-times "vect_recog_widen_sum_pattern: not allowed" 1 "vect" } } */
  /* { dg-final { cleanup-tree-dump "vect" } } */
Index: tree-vectorizer.c
===================================================================
*** tree-vectorizer.c	(revision 127201)
--- tree-vectorizer.c	(working copy)
*************** supportable_widening_operation (enum tre
*** 1936,1941 ****
--- 1936,1943 ----
                                  enum tree_code *code1, enum tree_code *code2)
  {
    stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
+   loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (stmt_info);
+   struct loop *vect_loop = LOOP_VINFO_LOOP (loop_info);
    bool ordered_p;
    enum machine_mode vec_mode;
    enum insn_code icode1, icode2;
*************** supportable_widening_operation (enum tre
*** 1958,1967 ****
       Some targets can take advantage of this and generate more efficient code.
       For example, targets like Altivec, that support widen_mult using a sequence
       of {mult_even,mult_odd} generate the following vectors:
!         vect1: [res1,res3,res5,res7], vect2: [res2,res4,res6,res8].  */
  
     if (STMT_VINFO_RELEVANT (stmt_info) == vect_used_by_reduction
!        || STMT_VINFO_RELEVANT (stmt_info) == vect_used_in_outer_by_reduction)
       ordered_p = false;
     else
       ordered_p = true;
--- 1960,1974 ----
       Some targets can take advantage of this and generate more efficient code.
       For example, targets like Altivec, that support widen_mult using a sequence
       of {mult_even,mult_odd} generate the following vectors:
!         vect1: [res1,res3,res5,res7], vect2: [res2,res4,res6,res8].
! 
!      When vectorizaing outer-loops, we execute the inner-loop sequentially
!      (each vectorized inner-loop iteration contributes to VF outer-loop 
!      iterations in parallel). We therefore don't allow to change the order 
!      of the computation in the inner-loop during outer-loop vectorization.  */
  
     if (STMT_VINFO_RELEVANT (stmt_info) == vect_used_by_reduction
!        && !nested_in_vect_loop_p (vect_loop, stmt))
       ordered_p = false;
     else
       ordered_p = true;
Index: tree-vect-analyze.c
===================================================================
*** tree-vect-analyze.c	(revision 127201)
--- tree-vect-analyze.c	(working copy)
*************** vect_mark_relevant (VEC(tree,heap) **wor
*** 3108,3145 ****
  
        pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
  
!       /* One exception to the above is when the pattern-stmt is an
! 	 "unordered reduction" operation, whose results are used in the
! 	 outer-loop, in which case the order of the generated 
! 	 results is important, and therefore we can't vectorize the pattern. 
! 
! 	 An "unordered reduction" is a reduction that is vectorized without 
! 	 preserving all the intermediate results, like widen_sum and dot_prod, 
! 	 that produce only N/2 results (by summing up pairs of intermediate 
! 	 results). If these results are actually used (e.g., stored, in an 
! 	 outer-loop), we need to have all N results (and in the right order). 
! 	 Therefore, in such a case, we cannot vectorize the reduction pattern,
! 	 and need to resort to vectorizing the original stmts.  */
!       if ((TREE_CODE (GIMPLE_STMT_OPERAND (pattern_stmt, 1)) == WIDEN_SUM_EXPR
! 	   || TREE_CODE (GIMPLE_STMT_OPERAND (pattern_stmt,1)) == DOT_PROD_EXPR)
! 	  && (relevant == vect_used_in_outer 
! 	      || relevant == vect_used_in_outer_by_reduction))
!         {
! 	  if (vect_print_dump_info (REPORT_DETAILS))
! 	    fprintf (vect_dump, "skip unordered reduction pattern.");
! 	  STMT_VINFO_RELATED_STMT (stmt_info) = NULL_TREE;
! 	  STMT_VINFO_IN_PATTERN_P (stmt_info) = false;
! 	}
!       else
! 	{
! 	  if (vect_print_dump_info (REPORT_DETAILS))
! 	    fprintf (vect_dump, "last stmt in pattern. don't mark relevant/live.");
! 	  stmt_info = vinfo_for_stmt (pattern_stmt);
! 	  gcc_assert (STMT_VINFO_RELATED_STMT (stmt_info) == stmt);
! 	  save_relevant = STMT_VINFO_RELEVANT (stmt_info);
! 	  save_live_p = STMT_VINFO_LIVE_P (stmt_info);
! 	  stmt = pattern_stmt;
! 	}
      }
  
    STMT_VINFO_LIVE_P (stmt_info) |= live_p;
--- 3108,3120 ----
  
        pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
  
!       if (vect_print_dump_info (REPORT_DETAILS))
!         fprintf (vect_dump, "last stmt in pattern. don't mark relevant/live.");
!       stmt_info = vinfo_for_stmt (pattern_stmt);
!       gcc_assert (STMT_VINFO_RELATED_STMT (stmt_info) == stmt);
!       save_relevant = STMT_VINFO_RELEVANT (stmt_info);
!       save_live_p = STMT_VINFO_LIVE_P (stmt_info);
!       stmt = pattern_stmt;
      }
  
    STMT_VINFO_LIVE_P (stmt_info) |= live_p;
Index: tree-vect-patterns.c
===================================================================
*** tree-vect-patterns.c	(revision 127201)
--- tree-vect-patterns.c	(working copy)
*************** widened_name_p (tree name, tree use_stmt
*** 149,155 ****
     * Return value: A new stmt that will be used to replace the sequence of
     stmts that constitute the pattern. In this case it will be:
          WIDEN_DOT_PRODUCT <x_t, y_t, sum_0>
! */
  
  static tree
  vect_recog_dot_prod_pattern (tree last_stmt, tree *type_in, tree *type_out)
--- 149,162 ----
     * Return value: A new stmt that will be used to replace the sequence of
     stmts that constitute the pattern. In this case it will be:
          WIDEN_DOT_PRODUCT <x_t, y_t, sum_0>
! 
!    Note: The dot-prod idiom is a widening reduction pattern that is
!          vectorized without preserving all the intermediate results. It
!          produces only N/2 (widened) results (by summing up pairs of
!          intermediate results) rather than all N results.  Therefore, we
!          cannot allow this pattern when we want to get all the results and in
!          the correct order (as is the case when this computation is in an
!          inner-loop nested in an outer-loop that us being vectorized).  */
  
  static tree
  vect_recog_dot_prod_pattern (tree last_stmt, tree *type_in, tree *type_out)
*************** vect_recog_dot_prod_pattern (tree last_s
*** 322,327 ****
--- 329,344 ----
        fprintf (vect_dump, "vect_recog_dot_prod_pattern: detected: ");
        print_generic_expr (vect_dump, pattern_expr, TDF_SLIM);
      }
+ 
+   /* We don't allow changing the order of the computation in the inner-loop
+      when doing outer-loop vectorization.  */
+   if (nested_in_vect_loop_p (loop, last_stmt))
+     {
+       if (vect_print_dump_info (REPORT_DETAILS))
+         fprintf (vect_dump, "vect_recog_dot_prod_pattern: not allowed.");
+       return NULL;
+     }
+ 
    return pattern_expr;
  }
  
*************** vect_recog_pow_pattern (tree last_stmt, 
*** 548,554 ****
     * Return value: A new stmt that will be used to replace the sequence of
     stmts that constitute the pattern. In this case it will be:
          WIDEN_SUM <x_t, sum_0>
! */
  
  static tree
  vect_recog_widen_sum_pattern (tree last_stmt, tree *type_in, tree *type_out)
--- 565,578 ----
     * Return value: A new stmt that will be used to replace the sequence of
     stmts that constitute the pattern. In this case it will be:
          WIDEN_SUM <x_t, sum_0>
! 
!    Note: The widneing-sum idiom is a widening reduction pattern that is 
! 	 vectorized without preserving all the intermediate results. It
!          produces only N/2 (widened) results (by summing up pairs of 
! 	 intermediate results) rather than all N results.  Therefore, we 
! 	 cannot allow this pattern when we want to get all the results and in 
! 	 the correct order (as is the case when this computation is in an 
! 	 inner-loop nested in an outer-loop that us being vectorized).  */
  
  static tree
  vect_recog_widen_sum_pattern (tree last_stmt, tree *type_in, tree *type_out)
*************** vect_recog_widen_sum_pattern (tree last_
*** 558,563 ****
--- 582,589 ----
    stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
    tree type, half_type;
    tree pattern_expr;
+   loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
+   struct loop *loop = LOOP_VINFO_LOOP (loop_info);
  
    if (TREE_CODE (last_stmt) != GIMPLE_MODIFY_STMT)
      return NULL;
*************** vect_recog_widen_sum_pattern (tree last_
*** 607,612 ****
--- 633,648 ----
        fprintf (vect_dump, "vect_recog_widen_sum_pattern: detected: ");
        print_generic_expr (vect_dump, pattern_expr, TDF_SLIM);
      }
+ 
+   /* We don't allow changing the order of the computation in the inner-loop
+      when doing outer-loop vectorization.  */
+   if (nested_in_vect_loop_p (loop, last_stmt))
+     {
+       if (vect_print_dump_info (REPORT_DETAILS))
+         fprintf (vect_dump, "vect_recog_widen_sum_pattern: not allowed.");
+       return NULL;
+     }
+ 
    return pattern_expr;
  }