[patch] vectorizer cleanups (and prep for outer-loop vectorization)

[Dorit Nuzman <DORIT@il.ibm.com>]

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


Hi,

This is exactly the same patch as was committed to autovect last week:
http://gcc.gnu.org/ml/gcc-patches/2007-03/msg01904.html
(but relative to mainline, and after testig on mainline).

These are a few cleanups (really technical things, no new functionality),
some of which will be also useful for outer-loop vectorization:

o Remove the field exit_cond from loop_vec_info, which used to hold the
loop-exit stmt. Instead, a stmt that is identified as a loop-exit control
stmt is marked as a 'loop_exit_ctrl_vec_info_type' (new enum value for
stmt_vec_info_type).  This will be useful when looking at outer-loops
because we have more than one stmt like that in the loop (there's also one
in the inner-loop).

o Vectorization of induction is currently done upon encountering a use of
the induction variable. Instead, we now vectorize the induction earlier,
when we encounter the respective induction phi-node. This simplifies things
a bit cause it's more in-line with how we vectorize other things (when we
encounter a use of the induction we just get the vector def from the
STMT_VINFO_VEC_STMT field of the defining phi-node), and also we don't need
to worry about vectorizing the same induction multiple times.  When looking
at outer-loops this will be even more useful cause when we vectorize a
phi-node we know exactly relative to which loop-nest is the induction, and
don't need any extra logic to check for that.

o Reorganize the calls to the vectorizable_* functions: In the drivers that
call these functions (vect_analyze_operations and vect_transform_stmt), we
currently call most of these functions only for RELEVANT_P stmts, and then
call vectorizable_reduction only for LIVE_P stmts. Now, instead, each of
the vectorizable_* functions checks that STMT_VINFO_RELEVANT/LIVE_P are as
expected, and in the two driver functions we don't check for
STMT_VINFO_RELEVANT_P anymore, but apply the vectorizable_* functions to
all stmts.  When looking at outer-loops this is useful because a reduction
(in the inner-loop) may now be marked RELEVANT (if it is used in the
outer-loop), and not only LIVE as it is currently.

o A bunch of other cleanups (that are not necessarily inspired by
outer-loop vectorization): Factor out code from
vect_mark_stmts_to_be_vectorized to process_use; Remove the '#ifdef
ADJUST_IN_EPILOG' and the code path that was disabled by it (which removes
unused code and simplifies the function); Add a flag to allow disabling
tree-reassociation, to help test reductions that are otherwise transformed
by reassociation to something we currently don't recognize; Fix
indentation; A few ther small miscellaneous stuff.

Bootstrapped and tested (full regression testing) on powerpc64-linux and
i386-linux.
Also bootstrapped with vectorization enabled on powerpc64-linux.

ok for mainline?

:ADDPATCH vectorizer,non-algorithmic:

ChangeLog:

        * tree-vectorizer.h (_loop_vec_info): Remove unused field
exit_cond.
        (stmt_vec_info_type): Add enum value loop_exit_ctrl_vec_info_type.
        * tree-vectorizer.c (new_loop_vec_info): Remove setting of
        LOOP_VINFO_EXIT_COND.
        * tree-vect-analyze.c (vect_stmt_relevant_p): Replace use of
        LOOP_VINFO_EXIT_COND with use of loop_exit_ctrl_vec_info_type.
        (vect_analyze_loop_form): Likewise.

        * tree-vectorizer.h (stmt_vec_info_type): Add enum value
        induc_vec_info_type.
        (vectorizable_induction): New function declaration.
        * tree-vect-transform.c (get_initial_def_for_induction): No need to
        check if already vectorized.  Find first place in BB where nre
stmts
        can be inserted.
        (vectorizable_induction): New function.
        (vect_transform_stmt): Add case for induc_vec_info_type to call
        vectorizable_induction.
        (vect_transform_loop): Consider phis for vectorization.
        * tree-vect-analyze.c (analyze_operations): Call
        vectorizable_induction when analyzing phis and when analyzing
        stmts.

        * tree-vectorizer.c (vect_is_simple_use): Remove redundant check.
        (destroy_loop_vec_info): Set loop->aux to NULL.

        * tree-vect-analyze.c (vect_determine_vectorization_factor):
Simplify
        condition. Add dump print.
        (vect_analyze_operations): Fix indenetation.  Fix a comment.  Fix a
        print message.
        (vect_analyze_scalar_cycles): Fix indentation.
        (vect_enhance_data_refs_alignment): Fix check in case of peeling.
        (vect_mark_relevant): Include phis in relevance analysis.
        (process_use): New function.
        (vect_mark_stmts_to_be_vectorized): Factor out code to process_use.
        Check phis in all bbs.

        * tree-vect-patterns.c (widened_name_p): Remove redundant check.

        * tree-vect-analyze.c (vect_analyze_operations): Reorganize calls
to
        vectorizable_* functions.
        * tree-vect-transform.c (vectorizable_call): Add check for
        STMT_VINFO_RELEVANT_P, STMT_VINFO_DEF_TYPE and STMT_VINFO_LIVE_P.
        (vectorizable_store): likewise.
        (vectorizable_conversion): Add check for STMT_VINFO_DEF_TYPE.
        Add comments.
        (vectorizable_operation, vectorizable_type_demotion): Likewise.
        (vectorizable_type_promotion, vectorizable_load): Likewise.
        (vectorizable_live_operation, vectorizable_condition): Likewise.
        (vectorizable_assignment): Add check for STMT_VINFO_DEF_TYPE and
        STMT_VINFO_LIVE_P.
        (vect_transform_stmt): Reorganize calls to vectorizable_*
functions.
        (vect_analyze_loop_form): Use the new NITERS_KNOWN_P macro so that
        this check could be done without creating a loop_vinfo first.
Record
        loop_vinfo in loop->aux.

        * tree-vect-transform.c (get_initial_def_for_reduction): Clean away
        the unused code for reduction without adjust-in-epilog to simplify
the
        function.

        * tree-vect-transform.c (vect_transform_loop): Add an assert.

        * tree-ssa-reassoc.c (gate_reassoc): New function.
        * common.opt (tree-reassoc): New flag.
        (pass_reassoc): Add gate.


(See attached file: mainline-vect-cleanups.mar27.txt)

[-- Attachment #2: mainline-vect-cleanups.mar27.txt --]
[-- Type: text/plain, Size: 65441 bytes --]

Index: ChangeLog
===================================================================
*** ChangeLog	(revision 123103)
--- ChangeLog	(working copy)
***************
*** 1,3 ****
--- 1,70 ----
+ 2007-03-20  Dorit Nuzman  <dorit@il.ibm.com>
+ 	
+ 	* tree-vectorizer.h (_loop_vec_info): Remove unused field exit_cond.
+ 	(stmt_vec_info_type): Add enum value loop_exit_ctrl_vec_info_type.
+ 	* tree-vectorizer.c (new_loop_vec_info): Remove setting of
+ 	LOOP_VINFO_EXIT_COND.
+ 	* tree-vect-analyze.c (vect_stmt_relevant_p): Replace use of
+ 	LOOP_VINFO_EXIT_COND with use of loop_exit_ctrl_vec_info_type.
+ 	(vect_analyze_loop_form): Likewise.
+ 
+ 	* tree-vectorizer.h (stmt_vec_info_type): Add enum value 
+ 	induc_vec_info_type.
+ 	(vectorizable_induction): New function declaration.
+ 	* tree-vect-transform.c (get_initial_def_for_induction): No need to 
+ 	check if already vectorized.  Find first place in BB where nre stmts 
+ 	can be inserted.
+ 	(vectorizable_induction): New function.
+ 	(vect_transform_stmt): Add case for induc_vec_info_type to call 
+ 	vectorizable_induction.
+ 	(vect_transform_loop): Consider phis for vectorization.
+ 	* tree-vect-analyze.c (analyze_operations): Call 
+ 	vectorizable_induction when analyzing phis and when analyzing
+ 	stmts.
+ 
+         * tree-vectorizer.c (vect_is_simple_use): Remove redundant check.
+ 	(destroy_loop_vec_info): Set loop->aux to NULL.
+ 
+ 	* tree-vect-analyze.c (vect_determine_vectorization_factor): Simplify
+ 	condition. Add dump print.
+ 	(vect_analyze_operations): Fix indenetation.  Fix a comment.  Fix a
+ 	print message. 
+ 	(vect_analyze_scalar_cycles): Fix indentation.
+ 	(vect_enhance_data_refs_alignment): Fix check in case of peeling.
+ 	(vect_mark_relevant): Include phis in relevance analysis.
+ 	(process_use): New function.
+ 	(vect_mark_stmts_to_be_vectorized): Factor out code to process_use.
+ 	Check phis in all bbs.
+ 
+         * tree-vect-patterns.c (widened_name_p): Remove redundant check.
+ 
+ 	* tree-vect-analyze.c (vect_analyze_operations): Reorganize calls to
+ 	vectorizable_* functions.
+ 	* tree-vect-transform.c (vectorizable_call): Add check for
+ 	STMT_VINFO_RELEVANT_P, STMT_VINFO_DEF_TYPE and STMT_VINFO_LIVE_P.
+ 	(vectorizable_store): likewise.
+ 	(vectorizable_conversion): Add check for STMT_VINFO_DEF_TYPE.
+ 	Add comments.
+ 	(vectorizable_operation, vectorizable_type_demotion): Likewise.
+ 	(vectorizable_type_promotion, vectorizable_load): Likewise.
+ 	(vectorizable_live_operation, vectorizable_condition): Likewise.
+ 	(vectorizable_assignment): Add check for STMT_VINFO_DEF_TYPE and
+ 	STMT_VINFO_LIVE_P.
+ 	(vect_transform_stmt): Reorganize calls to vectorizable_* functions.
+ 	(vect_analyze_loop_form): Use the new NITERS_KNOWN_P macro so that
+ 	this check could be done without creating a loop_vinfo first.  Record
+ 	loop_vinfo in loop->aux.
+ 
+ 	* tree-vect-transform.c (get_initial_def_for_reduction): Clean away
+ 	the unused code for reduction without adjust-in-epilog to simplify the
+ 	function.
+ 
+ 	* tree-vect-transform.c (vect_transform_loop): Add an assert.
+ 
+ 	* tree-ssa-reassoc.c (gate_reassoc): New function.
+ 	* common.opt (tree-reassoc): New flag.
+ 	(pass_reassoc): Add gate.
+ 
  2007-03-20  Mark Mitchell  <mark@codesourcery.com>
  
  	* config/arm/elf.h (TARGET_ASM_DESTRUCTOR): Define.
Index: testsuite/gcc.dg/vect/vect-1.c
===================================================================
*** testsuite/gcc.dg/vect/vect-1.c	(revision 123103)
--- testsuite/gcc.dg/vect/vect-1.c	(working copy)
*************** foo (int n)
*** 38,44 ****
       inner-loop: cross iteration cycle; multi-dimensional arrays).  */
    diff = 0;
    for (i = 0; i < N; i++) {
!     for (i = 0; i < N; i++) {
        diff += (image[i][j] - block[i][j]);
      }
    }
--- 38,44 ----
       inner-loop: cross iteration cycle; multi-dimensional arrays).  */
    diff = 0;
    for (i = 0; i < N; i++) {
!     for (j = 0; j < N; j++) {
        diff += (image[i][j] - block[i][j]);
      }
    }
Index: testsuite/gcc.dg/vect/vect.exp
===================================================================
*** testsuite/gcc.dg/vect/vect.exp	(revision 123103)
--- testsuite/gcc.dg/vect/vect.exp	(working copy)
*************** dg-runtest [lsort [glob -nocomplain $src
*** 169,174 ****
--- 169,175 ----
  	"" $DEFAULT_VECTCFLAGS
  
  # With -Os
+ set DEFAULT_VECTCFLAGS $SAVED_DEFAULT_VECTCFLAGS
  lappend DEFAULT_VECTCFLAGS "-Os"
  dg-runtest [lsort [glob -nocomplain $srcdir/$subdir/Os-vect-*.\[cS\]]]  \
          "" $DEFAULT_VECTCFLAGS
Index: tree-vectorizer.c
===================================================================
*** tree-vectorizer.c	(revision 123103)
--- tree-vectorizer.c	(working copy)
*************** new_loop_vec_info (struct loop *loop)
*** 1420,1426 ****
  
    LOOP_VINFO_LOOP (res) = loop;
    LOOP_VINFO_BBS (res) = bbs;
-   LOOP_VINFO_EXIT_COND (res) = NULL;
    LOOP_VINFO_NITERS (res) = NULL;
    LOOP_VINFO_VECTORIZABLE_P (res) = 0;
    LOOP_PEELING_FOR_ALIGNMENT (res) = 0;
--- 1420,1425 ----
*************** destroy_loop_vec_info (loop_vec_info loo
*** 1511,1516 ****
--- 1510,1516 ----
    VEC_free (tree, heap, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo));
  
    free (loop_vinfo);
+   loop->aux = NULL;
  }
  
  
*************** vect_is_simple_use (tree operand, loop_v
*** 1714,1728 ****
        return false;
      }
  
-   /* stmts inside the loop that have been identified as performing
-      a reduction operation cannot have uses in the loop.  */
-   if (*dt == vect_reduction_def && TREE_CODE (*def_stmt) != PHI_NODE)
-     {
-       if (vect_print_dump_info (REPORT_DETAILS))
-         fprintf (vect_dump, "reduction used in loop.");
-       return false;
-     }
- 
    if (vect_print_dump_info (REPORT_DETAILS))
      fprintf (vect_dump, "type of def: %d.",*dt);
  
--- 1714,1719 ----
*************** vect_is_simple_use (tree operand, loop_v
*** 1730,1742 ****
      {
      case PHI_NODE:
        *def = PHI_RESULT (*def_stmt);
-       gcc_assert (*dt == vect_induction_def || *dt == vect_reduction_def
-                   || *dt == vect_invariant_def);
        break;
  
      case GIMPLE_MODIFY_STMT:
        *def = GIMPLE_STMT_OPERAND (*def_stmt, 0);
-       gcc_assert (*dt == vect_loop_def || *dt == vect_invariant_def);
        break;
  
      default:
--- 1721,1730 ----
Index: tree-vectorizer.h
===================================================================
*** tree-vectorizer.h	(revision 123103)
--- tree-vectorizer.h	(working copy)
*************** typedef struct _loop_vec_info {
*** 93,101 ****
    /* The loop basic blocks.  */
    basic_block *bbs;
  
-   /* The loop exit_condition.  */
-   tree exit_cond;
- 
    /* Number of iterations.  */
    tree num_iters;
  
--- 93,98 ----
*************** typedef struct _loop_vec_info {
*** 138,144 ****
  /* Access Functions.  */
  #define LOOP_VINFO_LOOP(L)            (L)->loop
  #define LOOP_VINFO_BBS(L)             (L)->bbs
- #define LOOP_VINFO_EXIT_COND(L)       (L)->exit_cond
  #define LOOP_VINFO_NITERS(L)          (L)->num_iters
  #define LOOP_VINFO_VECTORIZABLE_P(L)  (L)->vectorizable
  #define LOOP_VINFO_VECT_FACTOR(L)     (L)->vectorization_factor
--- 135,140 ----
*************** typedef struct _loop_vec_info {
*** 151,159 ****
  #define LOOP_VINFO_MAY_MISALIGN_STMTS(L) (L)->may_misalign_stmts
  #define LOOP_VINFO_LOC(L)             (L)->loop_line_number
  
  #define LOOP_VINFO_NITERS_KNOWN_P(L)                     \
! (host_integerp ((L)->num_iters,0)                        \
! && TREE_INT_CST_LOW ((L)->num_iters) > 0)
  
  /*-----------------------------------------------------------------*/
  /* Info on vectorized defs.                                        */
--- 147,158 ----
  #define LOOP_VINFO_MAY_MISALIGN_STMTS(L) (L)->may_misalign_stmts
  #define LOOP_VINFO_LOC(L)             (L)->loop_line_number
  
+ #define NITERS_KNOWN_P(n)                     \
+ (host_integerp ((n),0)                        \
+ && TREE_INT_CST_LOW ((n)) > 0)
+ 
  #define LOOP_VINFO_NITERS_KNOWN_P(L)                     \
! NITERS_KNOWN_P((L)->num_iters)
  
  /*-----------------------------------------------------------------*/
  /* Info on vectorized defs.                                        */
*************** enum stmt_vec_info_type {
*** 167,175 ****
    assignment_vec_info_type,
    condition_vec_info_type,
    reduc_vec_info_type,
    type_promotion_vec_info_type,
    type_demotion_vec_info_type,
!   type_conversion_vec_info_type
  };
  
  /* Indicates whether/how a variable is used in the loop.  */
--- 166,176 ----
    assignment_vec_info_type,
    condition_vec_info_type,
    reduc_vec_info_type,
+   induc_vec_info_type,
    type_promotion_vec_info_type,
    type_demotion_vec_info_type,
!   type_conversion_vec_info_type,
!   loop_exit_ctrl_vec_info_type
  };
  
  /* Indicates whether/how a variable is used in the loop.  */
*************** extern bool vectorizable_call (tree, blo
*** 428,433 ****
--- 429,435 ----
  extern bool vectorizable_condition (tree, block_stmt_iterator *, tree *);
  extern bool vectorizable_live_operation (tree, block_stmt_iterator *, tree *);
  extern bool vectorizable_reduction (tree, block_stmt_iterator *, tree *);
+ extern bool vectorizable_induction (tree, block_stmt_iterator *, tree *);
  /* Driver for transformation stage.  */
  extern void vect_transform_loop (loop_vec_info);
  
Index: tree-vect-analyze.c
===================================================================
*** tree-vect-analyze.c	(revision 123103)
--- tree-vect-analyze.c	(working copy)
*************** vect_determine_vectorization_factor (loo
*** 122,134 ****
  
  	  gcc_assert (stmt_info);
  
! 	  /* Two cases of "relevant" phis: those that define an 
! 	     induction that is used in the loop, and those that
! 	     define a reduction.  */
! 	  if ((STMT_VINFO_RELEVANT (stmt_info) == vect_used_in_loop
! 	       && STMT_VINFO_DEF_TYPE (stmt_info) == vect_induction_def)
! 	      || (STMT_VINFO_RELEVANT (stmt_info) == vect_used_by_reduction
! 		  && STMT_VINFO_DEF_TYPE (stmt_info) == vect_reduction_def))
              {
  	      gcc_assert (!STMT_VINFO_VECTYPE (stmt_info));
                scalar_type = TREE_TYPE (PHI_RESULT (phi));
--- 122,128 ----
  
  	  gcc_assert (stmt_info);
  
! 	  if (STMT_VINFO_RELEVANT_P (stmt_info))
              {
  	      gcc_assert (!STMT_VINFO_VECTYPE (stmt_info));
                scalar_type = TREE_TYPE (PHI_RESULT (phi));
*************** vect_determine_vectorization_factor (loo
*** 268,274 ****
      }
  
    /* TODO: Analyze cost. Decide if worth while to vectorize.  */
! 
    if (vectorization_factor <= 1)
      {
        if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
--- 262,269 ----
      }
  
    /* TODO: Analyze cost. Decide if worth while to vectorize.  */
!   if (vect_print_dump_info (REPORT_DETAILS))
!     fprintf (vect_dump, "vectorization factor = %d", vectorization_factor);
    if (vectorization_factor <= 1)
      {
        if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
*************** vect_analyze_operations (loop_vec_info l
*** 311,316 ****
--- 306,313 ----
  
        for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
          {
+ 	  ok = true;
+ 
  	  stmt_info = vinfo_for_stmt (phi);
  	  if (vect_print_dump_info (REPORT_DETAILS))
  	    {
*************** vect_analyze_operations (loop_vec_info l
*** 319,341 ****
  	    }
  
  	  gcc_assert (stmt_info);
- 
  	  if (STMT_VINFO_LIVE_P (stmt_info))
  	    {
  	      /* FORNOW: not yet supported.  */
  	      if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
  		fprintf (vect_dump, "not vectorized: value used after loop.");
! 	    return false;
  	  }
  
  	  if (STMT_VINFO_RELEVANT (stmt_info) == vect_used_in_loop
  	      && STMT_VINFO_DEF_TYPE (stmt_info) != vect_induction_def)
  	    {
! 	      /* Most likely a reduction-like computation that is used
! 		 in the loop.  */
  	      if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
! 	        fprintf (vect_dump, "not vectorized: unsupported pattern.");
!  	     return false;
  	    }
  	}
  
--- 316,351 ----
  	    }
  
  	  gcc_assert (stmt_info);
  	  if (STMT_VINFO_LIVE_P (stmt_info))
  	    {
  	      /* FORNOW: not yet supported.  */
  	      if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
  		fprintf (vect_dump, "not vectorized: value used after loop.");
! 	      return false;
  	  }
  
  	  if (STMT_VINFO_RELEVANT (stmt_info) == vect_used_in_loop
  	      && STMT_VINFO_DEF_TYPE (stmt_info) != vect_induction_def)
  	    {
! 	      /* A scalar-dependence cycle that we don't support.  */
! 	      if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
! 	        fprintf (vect_dump, "not vectorized: scalar dependence cycle.");
! 	      return false;
! 	    }
! 
! 	  if (STMT_VINFO_RELEVANT_P (stmt_info)
! 	      && STMT_VINFO_DEF_TYPE (stmt_info) == vect_induction_def)
! 	    ok = vectorizable_induction (phi, NULL, NULL);
! 
! 	  if (!ok)
! 	    {
  	      if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
! 		{
! 		  fprintf (vect_dump,
! 			   "not vectorized: relevant phi not supported: ");
! 		  print_generic_expr (vect_dump, phi, TDF_SLIM);
! 		}
! 	      return false;
  	    }
  	}
  
*************** vect_analyze_operations (loop_vec_info l
*** 343,348 ****
--- 353,359 ----
  	{
  	  tree stmt = bsi_stmt (si);
  	  stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
+ 	  enum vect_def_type relevance = STMT_VINFO_RELEVANT (stmt_info);
  
  	  if (vect_print_dump_info (REPORT_DETAILS))
  	    {
*************** vect_analyze_operations (loop_vec_info l
*** 367,421 ****
  	      continue;
  	    }
  
            if (STMT_VINFO_RELEVANT_P (stmt_info))
              {
                gcc_assert (GIMPLE_STMT_P (stmt)
  		  	  || !VECTOR_MODE_P (TYPE_MODE (TREE_TYPE (stmt))));
                gcc_assert (STMT_VINFO_VECTYPE (stmt_info));
- 
- 	      ok = (vectorizable_type_promotion (stmt, NULL, NULL)
- 		    || vectorizable_type_demotion (stmt, NULL, NULL)
- 		    || vectorizable_conversion (stmt, NULL, NULL)
- 		    || vectorizable_operation (stmt, NULL, NULL)
- 		    || vectorizable_assignment (stmt, NULL, NULL)
- 		    || vectorizable_load (stmt, NULL, NULL)
- 		    || vectorizable_call (stmt, NULL, NULL)
- 		    || vectorizable_store (stmt, NULL, NULL)
- 		    || vectorizable_condition (stmt, NULL, NULL));
- 
- 	      if (!ok)
- 		{
- 		  if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
- 		    {
- 		      fprintf (vect_dump, 
- 			       "not vectorized: relevant stmt not supported: ");
- 		      print_generic_expr (vect_dump, stmt, TDF_SLIM);
- 		    }
- 		  return false;
- 		}	
  	      need_to_vectorize = true;
!             }
! 
! 	  if (STMT_VINFO_LIVE_P (stmt_info))
! 	    {
! 	      ok = vectorizable_reduction (stmt, NULL, NULL);
  
! 	      if (ok)
!                 need_to_vectorize = true;
!               else
! 	        ok = vectorizable_live_operation (stmt, NULL, NULL);
  
! 	      if (!ok)
  		{
! 		  if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
! 		    {
! 		      fprintf (vect_dump, 
! 			       "not vectorized: live stmt not supported: ");
! 		      print_generic_expr (vect_dump, stmt, TDF_SLIM);
! 		    }
! 		  return false;
  		}
! 	    }
  	} /* stmts in bb */
      } /* bbs */
  
--- 378,434 ----
  	      continue;
  	    }
  
+ 	  switch (STMT_VINFO_DEF_TYPE (stmt_info))
+ 	    {
+  	    case vect_loop_def:
+ 	      break;
+ 	
+ 	    case vect_reduction_def:
+ 	      gcc_assert (relevance == vect_unused_in_loop);
+ 	      break;	
+ 
+ 	    case vect_induction_def:
+ 	    case vect_constant_def:
+ 	    case vect_invariant_def:
+ 	    case vect_unknown_def_type:
+ 	    default:
+ 	      gcc_unreachable ();	
+ 	    }
+ 
            if (STMT_VINFO_RELEVANT_P (stmt_info))
              {
                gcc_assert (GIMPLE_STMT_P (stmt)
  		  	  || !VECTOR_MODE_P (TYPE_MODE (TREE_TYPE (stmt))));
                gcc_assert (STMT_VINFO_VECTYPE (stmt_info));
  	      need_to_vectorize = true;
! 	    }
  
! 	  ok = (vectorizable_type_promotion (stmt, NULL, NULL)
! 		|| vectorizable_type_demotion (stmt, NULL, NULL)
! 		|| vectorizable_conversion (stmt, NULL, NULL)
! 		|| vectorizable_operation (stmt, NULL, NULL)
! 		|| vectorizable_assignment (stmt, NULL, NULL)
! 		|| vectorizable_load (stmt, NULL, NULL)
! 		|| vectorizable_call (stmt, NULL, NULL)
! 		|| vectorizable_store (stmt, NULL, NULL)
! 		|| vectorizable_condition (stmt, NULL, NULL)
! 		|| vectorizable_reduction (stmt, NULL, NULL));
! 
! 	  /* Stmts that are (also) "live" (i.e. - that are used out of the loop)
! 	     need extra handling, except for vectorizable reductions.  */
!           if (STMT_VINFO_LIVE_P (stmt_info)
! 	      && STMT_VINFO_TYPE (stmt_info) != reduc_vec_info_type) 
! 	    ok |= vectorizable_live_operation (stmt, NULL, NULL);
  
! 	  if (!ok)
! 	    {
! 	      if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
  		{
! 		  fprintf (vect_dump, "not vectorized: stmt not supported: ");
! 		  print_generic_expr (vect_dump, stmt, TDF_SLIM);
  		}
! 	      return false;
! 	    }	
  	} /* stmts in bb */
      } /* bbs */
  
*************** vect_analyze_scalar_cycles (loop_vec_inf
*** 605,618 ****
  	}
  
        if (!access_fn
! 	  || !vect_is_simple_iv_evolution (loop->num, access_fn, &dumy, &dumy)) 
  	{
! 	  VEC_safe_push (tree, heap, worklist, phi);	  
  	  continue;
  	}
  
        if (vect_print_dump_info (REPORT_DETAILS))
! 	fprintf (vect_dump, "Detected induction.");
        STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_induction_def;
      }
  
--- 618,631 ----
  	}
  
        if (!access_fn
! 	  || !vect_is_simple_iv_evolution (loop->num, access_fn, &dumy, &dumy))
  	{
! 	  VEC_safe_push (tree, heap, worklist, phi);
  	  continue;
  	}
  
        if (vect_print_dump_info (REPORT_DETAILS))
!         fprintf (vect_dump, "Detected induction.");
        STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_induction_def;
      }
  
*************** static bool
*** 1418,1423 ****
--- 1431,1437 ----
  vect_enhance_data_refs_alignment (loop_vec_info loop_vinfo)
  {
    VEC (data_reference_p, heap) *datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
+   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
    enum dr_alignment_support supportable_dr_alignment;
    struct data_reference *dr0 = NULL;
    struct data_reference *dr;
*************** vect_enhance_data_refs_alignment (loop_v
*** 1515,1521 ****
  
    /* Often peeling for alignment will require peeling for loop-bound, which in 
       turn requires that we know how to adjust the loop ivs after the loop.  */
!   if (!vect_can_advance_ivs_p (loop_vinfo))
      do_peeling = false;
  
    if (do_peeling)
--- 1529,1536 ----
  
    /* Often peeling for alignment will require peeling for loop-bound, which in 
       turn requires that we know how to adjust the loop ivs after the loop.  */
!   if (!vect_can_advance_ivs_p (loop_vinfo)
!       || !slpeel_can_duplicate_loop_p (loop, single_exit (loop)))
      do_peeling = false;
  
    if (do_peeling)
*************** vect_mark_relevant (VEC(tree,heap) **wor
*** 2100,2110 ****
    if (relevant > STMT_VINFO_RELEVANT (stmt_info))
      STMT_VINFO_RELEVANT (stmt_info) = relevant;
  
-   if (TREE_CODE (stmt) == PHI_NODE)
-     /* Don't put phi-nodes in the worklist. Phis that are marked relevant
-        or live will fail vectorization later on.  */
-     return;
- 
    if (STMT_VINFO_RELEVANT (stmt_info) == save_relevant
        && STMT_VINFO_LIVE_P (stmt_info) == save_live_p)
      {
--- 2115,2120 ----
*************** vect_stmt_relevant_p (tree stmt, loop_ve
*** 2143,2149 ****
    *live_p = false;
  
    /* cond stmt other than loop exit cond.  */
!   if (is_ctrl_stmt (stmt) && (stmt != LOOP_VINFO_EXIT_COND (loop_vinfo)))
      *relevant = vect_used_in_loop;
  
    /* changing memory.  */
--- 2153,2160 ----
    *live_p = false;
  
    /* cond stmt other than loop exit cond.  */
!   if (is_ctrl_stmt (stmt) 
!       && STMT_VINFO_TYPE (vinfo_for_stmt (stmt)) != loop_exit_ctrl_vec_info_type)
      *relevant = vect_used_in_loop;
  
    /* changing memory.  */
*************** vect_stmt_relevant_p (tree stmt, loop_ve
*** 2180,2185 ****
--- 2191,2271 ----
  }
  
  
+ /* 
+    Function process_use.
+ 
+    Inputs:
+    - a USE in STMT in a loop represented by LOOP_VINFO
+    - LIVE_P, RELEVANT - enum values to be set in the STMT_VINFO of the stmt 
+      that defined USE. This is dont by calling mark_relevant and passing it
+      the WORKLIST (to add DEF_STMT to the WORKlist in case itis relevant). 
+ 
+    Outputs:
+    Generally, LIVE_P and RELEVANT are used to define the liveness and
+    relevance info of the DEF_STMT of this USE:
+        STMT_VINFO_LIVE_P (DEF_STMT_info) <-- live_p
+        STMT_VINFO_RELEVANT (DEF_STMT_info) <-- relevant
+    Exceptions:
+    - case 1: If USE is used only for address computations (e.g. array indexing),
+    which does not need to be directly vectorized, then the liveness/relevance 
+    of the respective DEF_STMT is left unchanged.
+    - case 2: If STMT is a reduction phi and DEF_STMT is a reduction stmt, we 
+    skip DEF_STMT cause it had already been processed.  
+ 
+    Return true if everyting is as expected. Return false otherwise.  */
+ 
+ static bool
+ process_use (tree stmt, tree use, loop_vec_info loop_vinfo, bool live_p, 
+ 	     enum vect_relevant relevant, VEC(tree,heap) **worklist)
+ {
+   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
+   stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
+   stmt_vec_info dstmt_vinfo;
+   basic_block def_bb;
+   tree def, def_stmt;
+   enum vect_def_type dt;
+ 
+   /* case 1: we are only interested in uses that need to be vectorized.  Uses 
+      that are used for address computation are not considered relevant.  */
+   if (!exist_non_indexing_operands_for_use_p (use, stmt))
+      return true;
+ 
+   if (!vect_is_simple_use (use, loop_vinfo, &def_stmt, &def, &dt))
+     { 
+       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
+         fprintf (vect_dump, "not vectorized: unsupported use in stmt.");
+       return false;
+     }
+ 
+   if (!def_stmt || IS_EMPTY_STMT (def_stmt))
+     return true;
+ 
+   def_bb = bb_for_stmt (def_stmt);
+   if (!flow_bb_inside_loop_p (loop, def_bb))
+     return true;
+ 
+   /* case 2: A reduction phi defining a reduction stmt (DEF_STMT). DEF_STMT 
+      must have already been processed, so we just check that everything is as 
+      expected, and we are done.  */
+   dstmt_vinfo = vinfo_for_stmt (def_stmt);
+   if (TREE_CODE (stmt) == PHI_NODE
+       && STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def
+       && TREE_CODE (def_stmt) != PHI_NODE
+       && STMT_VINFO_DEF_TYPE (dstmt_vinfo) == vect_reduction_def)
+     {
+       if (STMT_VINFO_IN_PATTERN_P (dstmt_vinfo))
+ 	dstmt_vinfo = vinfo_for_stmt (STMT_VINFO_RELATED_STMT (dstmt_vinfo));
+       gcc_assert (STMT_VINFO_RELEVANT (dstmt_vinfo) < vect_used_by_reduction);
+       gcc_assert (STMT_VINFO_LIVE_P (dstmt_vinfo) 
+ 		  || STMT_VINFO_RELEVANT (dstmt_vinfo) > vect_unused_in_loop);
+       return true;
+     }
+ 
+   vect_mark_relevant (worklist, def_stmt, relevant, live_p);
+   return true;
+ }
+ 
+ 
  /* Function vect_mark_stmts_to_be_vectorized.
  
     Not all stmts in the loop need to be vectorized. For example:
*************** vect_mark_stmts_to_be_vectorized (loop_v
*** 2204,2220 ****
    basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
    unsigned int nbbs = loop->num_nodes;
    block_stmt_iterator si;
!   tree stmt, use;
    stmt_ann_t ann;
-   ssa_op_iter iter;
    unsigned int i;
    stmt_vec_info stmt_vinfo;
    basic_block bb;
    tree phi;
    bool live_p;
    enum vect_relevant relevant;
-   tree def, def_stmt;
-   enum vect_def_type dt;
  
    if (vect_print_dump_info (REPORT_DETAILS))
      fprintf (vect_dump, "=== vect_mark_stmts_to_be_vectorized ===");
--- 2290,2303 ----
    basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
    unsigned int nbbs = loop->num_nodes;
    block_stmt_iterator si;
!   tree stmt;
    stmt_ann_t ann;
    unsigned int i;
    stmt_vec_info stmt_vinfo;
    basic_block bb;
    tree phi;
    bool live_p;
    enum vect_relevant relevant;
  
    if (vect_print_dump_info (REPORT_DETAILS))
      fprintf (vect_dump, "=== vect_mark_stmts_to_be_vectorized ===");
*************** vect_mark_stmts_to_be_vectorized (loop_v
*** 2222,2248 ****
    worklist = VEC_alloc (tree, heap, 64);
  
    /* 1. Init worklist.  */
- 
-   bb = loop->header;
-   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
-     {
-       if (vect_print_dump_info (REPORT_DETAILS))
-         {
-           fprintf (vect_dump, "init: phi relevant? ");
-           print_generic_expr (vect_dump, phi, TDF_SLIM);
-         }
- 
-       if (vect_stmt_relevant_p (phi, loop_vinfo, &relevant, &live_p))
- 	vect_mark_relevant (&worklist, phi, relevant, live_p);
-     }
- 
    for (i = 0; i < nbbs; i++)
      {
        bb = bbs[i];
        for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
  	{
  	  stmt = bsi_stmt (si);
- 
  	  if (vect_print_dump_info (REPORT_DETAILS))
  	    {
  	      fprintf (vect_dump, "init: stmt relevant? ");
--- 2305,2327 ----
    worklist = VEC_alloc (tree, heap, 64);
  
    /* 1. Init worklist.  */
    for (i = 0; i < nbbs; i++)
      {
        bb = bbs[i];
+       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+ 	{ 
+ 	  if (vect_print_dump_info (REPORT_DETAILS))
+ 	    {
+ 	      fprintf (vect_dump, "init: phi relevant? ");
+ 	      print_generic_expr (vect_dump, phi, TDF_SLIM);
+ 	    }
+ 
+ 	  if (vect_stmt_relevant_p (phi, loop_vinfo, &relevant, &live_p))
+ 	    vect_mark_relevant (&worklist, phi, relevant, live_p);
+ 	}
        for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
  	{
  	  stmt = bsi_stmt (si);
  	  if (vect_print_dump_info (REPORT_DETAILS))
  	    {
  	      fprintf (vect_dump, "init: stmt relevant? ");
*************** vect_mark_stmts_to_be_vectorized (loop_v
*** 2254,2355 ****
  	}
      }
  
- 
    /* 2. Process_worklist */
- 
    while (VEC_length (tree, worklist) > 0)
      {
!       stmt = VEC_pop (tree, worklist);
  
        if (vect_print_dump_info (REPORT_DETAILS))
  	{
            fprintf (vect_dump, "worklist: examine stmt: ");
            print_generic_expr (vect_dump, stmt, TDF_SLIM);
  	}
  
!       /* Examine the USEs of STMT. For each ssa-name USE that is defined
!          in the loop, mark the stmt that defines it (DEF_STMT) as
!          relevant/irrelevant and live/dead according to the liveness and
!          relevance properties of STMT.
!        */
! 
!       gcc_assert (TREE_CODE (stmt) != PHI_NODE);
! 
        ann = stmt_ann (stmt);
        stmt_vinfo = vinfo_for_stmt (stmt);
- 
        relevant = STMT_VINFO_RELEVANT (stmt_vinfo);
        live_p = STMT_VINFO_LIVE_P (stmt_vinfo);
  
        /* Generally, the liveness and relevance properties of STMT are
!          propagated to the DEF_STMTs of its USEs:
!              STMT_VINFO_LIVE_P (DEF_STMT_info) <-- live_p
!              STMT_VINFO_RELEVANT (DEF_STMT_info) <-- relevant
! 
!          Exceptions:
! 
! 	 (case 1)
!            If USE is used only for address computations (e.g. array indexing),
!            which does not need to be directly vectorized, then the
!            liveness/relevance of the respective DEF_STMT is left unchanged.
! 
! 	 (case 2)
!            If STMT has been identified as defining a reduction variable, then
!            we want to set liveness/relevance as follows:
!                STMT_VINFO_LIVE_P (DEF_STMT_info) <-- false
!                STMT_VINFO_RELEVANT (DEF_STMT_info) <-- vect_used_by_reduction
!              because even though STMT is classified as live (since it defines a
!              value that is used across loop iterations) and irrelevant (since it
!              is not used inside the loop), it will be vectorized, and therefore
!              the corresponding DEF_STMTs need to marked as relevant.
! 	     We distinguish between two kinds of relevant stmts - those that are
! 	     used by a reduction computation, and those that are (also) used by
!  	     a regular computation. This allows us later on to identify stmts
! 	     that are used solely by a reduction, and therefore the order of 
! 	     the results that they produce does not have to be kept.
!        */
  
-       /* case 2.2:  */
        if (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def)
! 	{
! 	  gcc_assert (relevant == vect_unused_in_loop && live_p);
  	  relevant = vect_used_by_reduction;
! 	  live_p = false;
  	}
  
!       i = 0;
!       FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
  	{
! 	  if (vect_print_dump_info (REPORT_DETAILS))
  	    {
- 	      fprintf (vect_dump, "worklist: examine use %d: ", i++);
- 	      print_generic_expr (vect_dump, use, TDF_SLIM);
- 	    }
- 
- 	  /* case 1: we are only interested in uses that need to be vectorized. 
- 	     Uses that are used for address computation are not considered 
- 	     relevant.
- 	   */
- 	  if (!exist_non_indexing_operands_for_use_p (use, stmt))
- 	    continue;
- 
- 	  if (!vect_is_simple_use (use, loop_vinfo, &def_stmt, &def, &dt))
- 	    {
- 	      if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
- 		fprintf (vect_dump, "not vectorized: unsupported use in stmt.");
  	      VEC_free (tree, heap, worklist);
  	      return false;
!             }
! 
! 	  if (!def_stmt || IS_EMPTY_STMT (def_stmt))
! 	    continue;
! 
! 	  bb = bb_for_stmt (def_stmt);
! 	  if (!flow_bb_inside_loop_p (loop, bb))
! 	    continue;
! 	  vect_mark_relevant (&worklist, def_stmt, relevant, live_p);
  	}
!     }				/* while worklist */
  
    VEC_free (tree, heap, worklist);
    return true;
--- 2333,2414 ----
  	}
      }
  
    /* 2. Process_worklist */
    while (VEC_length (tree, worklist) > 0)
      {
!       use_operand_p use_p;
!       ssa_op_iter iter;
  
+       stmt = VEC_pop (tree, worklist);
        if (vect_print_dump_info (REPORT_DETAILS))
  	{
            fprintf (vect_dump, "worklist: examine stmt: ");
            print_generic_expr (vect_dump, stmt, TDF_SLIM);
  	}
  
!       /* Examine the USEs of STMT. For each USE, mark the stmt that defines it 
! 	 (DEF_STMT) as relevant/irrelevant and live/dead according to the 
! 	 liveness and relevance properties of STMT.  */
        ann = stmt_ann (stmt);
        stmt_vinfo = vinfo_for_stmt (stmt);
        relevant = STMT_VINFO_RELEVANT (stmt_vinfo);
        live_p = STMT_VINFO_LIVE_P (stmt_vinfo);
  
        /* Generally, the liveness and relevance properties of STMT are
! 	 propagated as is to the DEF_STMTs of its USEs:
! 	  live_p <-- STMT_VINFO_LIVE_P (STMT_VINFO)
! 	  relevant <-- STMT_VINFO_RELEVANT (STMT_VINFO)
! 
! 	 One exception is when STMT has been identified as defining a reduction
! 	 variable; in this case we set the liveness/relevance as follows:
! 	   live_p = false
! 	   relevant = vect_used_by_reduction
! 	 This is because we distinguish between two kinds of relevant stmts -
! 	 those that are used by a reduction computation, and those that are 
! 	 (also) used by a regular computation. This allows us later on to 
! 	 identify stmts that are used solely by a reduction, and therefore the 
! 	 order of the results that they produce does not have to be kept.
! 
!          Reduction phis are expected to be used by a reduction stmt;  Other 
! 	 reduction stmts are expected to be unused in the loop.  These are the 
! 	 expected values of "relevant" for reduction phis/stmts in the loop:
! 
! 	 relevance:				phi	stmt
! 	 vect_unused_in_loop				ok
! 	 vect_used_by_reduction			ok
! 	 vect_used_in_loop 						  */
  
        if (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def)
!         {
! 	  switch (relevant)
! 	    {
! 	    case vect_unused_in_loop:
! 	      gcc_assert (TREE_CODE (stmt) != PHI_NODE);
! 	      break;
! 	    case vect_used_by_reduction:
! 	      if (TREE_CODE (stmt) == PHI_NODE)
! 		break;
! 	    case vect_used_in_loop:
! 	    default:
! 	      if (vect_print_dump_info (REPORT_DETAILS))
! 	        fprintf (vect_dump, "unsupported use of reduction.");
! 	      VEC_free (tree, heap, worklist);
! 	      return false;
! 	    }
  	  relevant = vect_used_by_reduction;
! 	  live_p = false;	
  	}
  
!       FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
  	{
! 	  tree op = USE_FROM_PTR (use_p);
! 	  if (!process_use (stmt, op, loop_vinfo, live_p, relevant, &worklist))
  	    {
  	      VEC_free (tree, heap, worklist);
  	      return false;
! 	    }
  	}
!     } /* while worklist */
  
    VEC_free (tree, heap, worklist);
    return true;
*************** vect_analyze_loop_form (struct loop *loo
*** 2582,2591 ****
        return false;
      }
  
!   loop_vinfo = new_loop_vec_info (loop);
!   LOOP_VINFO_NITERS (loop_vinfo) = number_of_iterations;
! 
!   if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
      {
        if (vect_print_dump_info (REPORT_DETAILS))
          {
--- 2641,2647 ----
        return false;
      }
  
!   if (!NITERS_KNOWN_P (number_of_iterations))
      {
        if (vect_print_dump_info (REPORT_DETAILS))
          {
*************** vect_analyze_loop_form (struct loop *loo
*** 2594,2608 ****
          }
      }
    else
!   if (LOOP_VINFO_INT_NITERS (loop_vinfo) == 0)
      {
        if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
          fprintf (vect_dump, "not vectorized: number of iterations = 0.");
        return NULL;
      }
  
!   LOOP_VINFO_EXIT_COND (loop_vinfo) = loop_cond;
  
    return loop_vinfo;
  }
  
--- 2650,2669 ----
          }
      }
    else
!   if (TREE_INT_CST_LOW (number_of_iterations) == 0)
      {
        if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
          fprintf (vect_dump, "not vectorized: number of iterations = 0.");
        return NULL;
      }
  
!   loop_vinfo = new_loop_vec_info (loop);
!   LOOP_VINFO_NITERS (loop_vinfo) = number_of_iterations;
! 
!   STMT_VINFO_TYPE (vinfo_for_stmt (loop_cond)) = loop_exit_ctrl_vec_info_type;
  
+   gcc_assert (!loop->aux);
+   loop->aux = loop_vinfo;
    return loop_vinfo;
  }
  
Index: common.opt
===================================================================
*** common.opt	(revision 123103)
--- common.opt	(working copy)
*************** funroll-all-loops
*** 1070,1075 ****
--- 1070,1079 ----
  Common Report Var(flag_unroll_all_loops) Optimization
  Perform loop unrolling for all loops
  
+ ftree-reassoc
+ Common Report Var(flag_tree_reassoc) Init(1) Optimization
+ Perform reassociation on trees
+ 
  ; Nonzero means that loop optimizer may assume that the induction variables
  ; that control loops do not overflow and that the loops with nontrivial
  ; exit condition are not infinite
Index: tree-vect-patterns.c
===================================================================
*** tree-vect-patterns.c	(revision 123103)
--- tree-vect-patterns.c	(working copy)
*************** widened_name_p (tree name, tree use_stmt
*** 109,118 ****
    if (!vect_is_simple_use (oprnd0, loop_vinfo, &dummy, &dummy, &dt))
      return false;
  
-   if (dt != vect_invariant_def && dt != vect_constant_def
-       && dt != vect_loop_def)
-     return false;
- 
    return true;
  }
  
--- 109,114 ----
Index: tree-vect-transform.c
===================================================================
*** tree-vect-transform.c	(revision 123103)
--- tree-vect-transform.c	(working copy)
*************** vect_init_vector (tree stmt, tree vector
*** 514,520 ****
  /* Function get_initial_def_for_induction
  
     Input:
-    STMT - a stmt that performs an induction operation in the loop.
     IV_PHI - the initial value of the induction variable
  
     Output:
--- 514,519 ----
*************** vect_init_vector (tree stmt, tree vector
*** 524,532 ****
     [X, X + S, X + 2*S, X + 3*S].  */
  
  static tree
! get_initial_def_for_induction (tree stmt, tree iv_phi)
  {
!   stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
    loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
    struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
    tree scalar_type = TREE_TYPE (iv_phi);
--- 523,531 ----
     [X, X + S, X + 2*S, X + 3*S].  */
  
  static tree
! get_initial_def_for_induction (tree iv_phi)
  {
!   stmt_vec_info stmt_vinfo = vinfo_for_stmt (iv_phi);
    loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
    struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
    tree scalar_type = TREE_TYPE (iv_phi);
*************** get_initial_def_for_induction (tree stmt
*** 549,575 ****
    tree expr;
    stmt_vec_info phi_info = vinfo_for_stmt (iv_phi);
    tree stmts;
  
    gcc_assert (phi_info);
  
!   if (STMT_VINFO_VEC_STMT (phi_info))
      {
!       induction_phi = STMT_VINFO_VEC_STMT (phi_info);
!       gcc_assert (TREE_CODE (induction_phi) == PHI_NODE);
! 
!       if (vect_print_dump_info (REPORT_DETAILS))
! 	{
! 	  fprintf (vect_dump, "induction already vectorized:");
! 	  print_generic_expr (vect_dump, iv_phi, TDF_SLIM);
! 	  fprintf (vect_dump, "\n");
! 	  print_generic_expr (vect_dump, induction_phi, TDF_SLIM);
! 	}
! 
!       return PHI_RESULT (induction_phi);
      }
  
-   gcc_assert (ncopies >= 1);
-  
    access_fn = analyze_scalar_evolution (loop, PHI_RESULT (iv_phi));
    gcc_assert (access_fn);
    ok = vect_is_simple_iv_evolution (loop->num, access_fn, &init_expr, &step_expr);
--- 548,568 ----
    tree expr;
    stmt_vec_info phi_info = vinfo_for_stmt (iv_phi);
    tree stmts;
+   tree stmt = NULL_TREE;
+   block_stmt_iterator si;
+   basic_block bb = bb_for_stmt (iv_phi);
  
    gcc_assert (phi_info);
+   gcc_assert (ncopies >= 1);
  
!   /* Find the first insertion point in the BB.  */
!   for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
      {
!       stmt = bsi_stmt (si);
!       if (TREE_CODE (stmt) != LABEL_EXPR)
!         break;
      }
  
    access_fn = analyze_scalar_evolution (loop, PHI_RESULT (iv_phi));
    gcc_assert (access_fn);
    ok = vect_is_simple_iv_evolution (loop->num, access_fn, &init_expr, &step_expr);
*************** vect_get_vec_def_for_operand (tree op, t
*** 833,839 ****
  	gcc_assert (TREE_CODE (def_stmt) == PHI_NODE);
  
  	/* Get the def before the loop  */
! 	return get_initial_def_for_induction (stmt, def_stmt);
        }
  
      default:
--- 826,832 ----
  	gcc_assert (TREE_CODE (def_stmt) == PHI_NODE);
  
  	/* Get the def before the loop  */
! 	return get_initial_def_for_induction (def_stmt);
        }
  
      default:
*************** vect_finish_stmt_generation (tree stmt, 
*** 951,958 ****
  }
  
  
- #define ADJUST_IN_EPILOG 1
- 
  /* Function get_initial_def_for_reduction
  
     Input:
--- 944,949 ----
*************** vect_finish_stmt_generation (tree stmt, 
*** 960,977 ****
     INIT_VAL - the initial value of the reduction variable
  
     Output:
!    SCALAR_DEF - a tree that holds a value to be added to the final result
! 	of the reduction (used for "ADJUST_IN_EPILOG" - see below).
     Return a vector variable, initialized according to the operation that STMT
! 	performs. This vector will be used as the initial value of the
! 	vector of partial results.
  
!    Option1 ("ADJUST_IN_EPILOG"): Initialize the vector as follows:
       add:         [0,0,...,0,0]
       mult:        [1,1,...,1,1]
       min/max:     [init_val,init_val,..,init_val,init_val]
       bit and/or:  [init_val,init_val,..,init_val,init_val]
!    and when necessary (e.g. add/mult case) let the caller know 
     that it needs to adjust the result by init_val.
  
     Option2: Initialize the vector as follows:
--- 951,968 ----
     INIT_VAL - the initial value of the reduction variable
  
     Output:
!    ADJUSTMENT_DEF - a tree that holds a value to be added to the final result
!         of the reduction (used for adjusting the epilog - see below).
     Return a vector variable, initialized according to the operation that STMT
!         performs. This vector will be used as the initial value of the
!         vector of partial results.
  
!    Option1 (adjust in epilog): Initialize the vector as follows:
       add:         [0,0,...,0,0]
       mult:        [1,1,...,1,1]
       min/max:     [init_val,init_val,..,init_val,init_val]
       bit and/or:  [init_val,init_val,..,init_val,init_val]
!    and when necessary (e.g. add/mult case) let the caller know
     that it needs to adjust the result by init_val.
  
     Option2: Initialize the vector as follows:
*************** vect_finish_stmt_generation (tree stmt, 
*** 992,1075 ****
     or [0,0,0,0] and let the caller know that it needs to adjust
     the result at the end by 'init_val'.
  
!    FORNOW: We use the "ADJUST_IN_EPILOG" scheme.
!    TODO: Use some cost-model to estimate which scheme is more profitable.
! */
  
  static tree
! get_initial_def_for_reduction (tree stmt, tree init_val, tree *scalar_def)
  {
    stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
    tree vectype = STMT_VINFO_VECTYPE (stmt_vinfo);
    int nunits =  TYPE_VECTOR_SUBPARTS (vectype);
-   int nelements;
    enum tree_code code = TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1));
    tree type = TREE_TYPE (init_val);
!   tree def;
!   tree vec, t = NULL_TREE;
!   bool need_epilog_adjust;
    int i;
    tree vector_type;
  
    gcc_assert (INTEGRAL_TYPE_P (type) || SCALAR_FLOAT_TYPE_P (type));
  
    switch (code)
    {
    case WIDEN_SUM_EXPR:
    case DOT_PROD_EXPR:
    case PLUS_EXPR:
      if (INTEGRAL_TYPE_P (type))
!       def = build_int_cst (type, 0);
      else
!       def = build_real (type, dconst0);
! 
! #ifdef ADJUST_IN_EPILOG
!     /* All the 'nunits' elements are set to 0. The final result will be
!        adjusted by 'init_val' at the loop epilog.  */
!     nelements = nunits;
!     need_epilog_adjust = true;
! #else
!     /* 'nunits - 1' elements are set to 0; The last element is set to 
!         'init_val'.  No further adjustments at the epilog are needed.  */
!     nelements = nunits - 1;
!     need_epilog_adjust = false;
! #endif
      break;
  
    case MIN_EXPR:
    case MAX_EXPR:
!     def = init_val;
!     nelements = nunits;
!     need_epilog_adjust = false;
      break;
  
    default:
      gcc_unreachable ();
    }
  
!   for (i = nelements - 1; i >= 0; --i)
!     t = tree_cons (NULL_TREE, def, t);
! 
!   if (nelements == nunits - 1)
!     {
!       /* Set the last element of the vector.  */
!       t = tree_cons (NULL_TREE, init_val, t);
!       nelements += 1;
!     }
!   gcc_assert (nelements == nunits);
! 
!   vector_type = get_vectype_for_scalar_type (TREE_TYPE (def));
!   if (TREE_CODE (init_val) == INTEGER_CST || TREE_CODE (init_val) == REAL_CST)
!     vec = build_vector (vector_type, t);
!   else
!     vec = build_constructor_from_list (vector_type, t);
!     
!   if (!need_epilog_adjust)
!     *scalar_def = NULL_TREE;
!   else
!     *scalar_def = init_val;
! 
!   return vect_init_vector (stmt, vec, vector_type);
  }
  
  
--- 983,1038 ----
     or [0,0,0,0] and let the caller know that it needs to adjust
     the result at the end by 'init_val'.
  
!    FORNOW, we are using the 'adjust in epilog' scheme, because this way the
!    initialization vector is simpler (same element in all entries).
!    A cost model should help decide between these two schemes.  */
  
  static tree
! get_initial_def_for_reduction (tree stmt, tree init_val, tree *adjustment_def)
  {
    stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
    tree vectype = STMT_VINFO_VECTYPE (stmt_vinfo);
    int nunits =  TYPE_VECTOR_SUBPARTS (vectype);
    enum tree_code code = TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1));
    tree type = TREE_TYPE (init_val);
!   tree vecdef;
!   tree def_for_init;
!   tree init_def;
!   tree t = NULL_TREE;
    int i;
    tree vector_type;
  
    gcc_assert (INTEGRAL_TYPE_P (type) || SCALAR_FLOAT_TYPE_P (type));
+   vecdef = vect_get_vec_def_for_operand (init_val, stmt, NULL);
  
    switch (code)
    {
    case WIDEN_SUM_EXPR:
    case DOT_PROD_EXPR:
    case PLUS_EXPR:
+     *adjustment_def = init_val;
+     /* Create a vector of zeros for init_def.  */
      if (INTEGRAL_TYPE_P (type))
!       def_for_init = build_int_cst (type, 0);
      else
!       def_for_init = build_real (type, dconst0);
!       for (i = nunits - 1; i >= 0; --i)
!     t = tree_cons (NULL_TREE, def_for_init, t);
!     vector_type = get_vectype_for_scalar_type (TREE_TYPE (def_for_init));
!     init_def = build_vector (vector_type, t);
      break;
  
    case MIN_EXPR:
    case MAX_EXPR:
!     *adjustment_def = NULL_TREE;
!     init_def = vecdef;
      break;
  
    default:
      gcc_unreachable ();
    }
  
!   return init_def;
  }
  
  
*************** vectorizable_call (tree stmt, block_stmt
*** 1816,1821 ****
--- 1779,1798 ----
    int ncopies, j, nargs;
    call_expr_arg_iterator iter;
  
+   if (!STMT_VINFO_RELEVANT_P (stmt_info))
+     return false;
+ 
+   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_loop_def)
+     return false;
+ 
+   /* FORNOW: not yet supported.  */
+   if (STMT_VINFO_LIVE_P (stmt_info))
+     {
+       if (vect_print_dump_info (REPORT_DETAILS))
+         fprintf (vect_dump, "value used after loop.");
+       return false;
+     }
+ 
    /* Is STMT a vectorizable call?   */
    if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
      return false;
*************** vectorizable_conversion (tree stmt, bloc
*** 1994,2000 ****
    if (!STMT_VINFO_RELEVANT_P (stmt_info))
      return false;
  
!   gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info) == vect_loop_def);
  
    if (STMT_VINFO_LIVE_P (stmt_info))
      {
--- 1971,1978 ----
    if (!STMT_VINFO_RELEVANT_P (stmt_info))
      return false;
  
!   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_loop_def)
!     return false;
  
    if (STMT_VINFO_LIVE_P (stmt_info))
      {
*************** vectorizable_assignment (tree stmt, bloc
*** 2134,2145 ****
    if (ncopies > 1)
      return false; /* FORNOW */
  
-   /* Is vectorizable assignment?  */
    if (!STMT_VINFO_RELEVANT_P (stmt_info))
      return false;
  
!   gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info) == vect_loop_def);
  
    if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
      return false;
  
--- 2112,2132 ----
    if (ncopies > 1)
      return false; /* FORNOW */
  
    if (!STMT_VINFO_RELEVANT_P (stmt_info))
      return false;
  
!   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_loop_def)
!     return false;
! 
!   /* FORNOW: not yet supported.  */
!   if (STMT_VINFO_LIVE_P (stmt_info))
!     {
!       if (vect_print_dump_info (REPORT_DETAILS))
!         fprintf (vect_dump, "value used after loop.");
!       return false;
!     }
  
+   /* Is vectorizable assignment?  */
    if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
      return false;
  
*************** vect_min_worthwhile_factor (enum tree_co
*** 2209,2214 ****
--- 2196,2254 ----
  }
  
  
+ /* Function vectorizable_induction
+ 
+    Check if PHI performs an induction computation that can be vectorized.
+    If VEC_STMT is also passed, vectorize the induction PHI: create a vectorized
+    phi to replace it, put it in VEC_STMT, and add it to the same basic block.
+    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
+ 
+ bool
+ vectorizable_induction (tree phi, block_stmt_iterator *bsi ATTRIBUTE_UNUSED,
+                         tree *vec_stmt)
+ {
+   stmt_vec_info stmt_info = vinfo_for_stmt (phi);
+   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
+   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
+   int nunits = TYPE_VECTOR_SUBPARTS (vectype);
+   int ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits;
+   tree vec_def;
+ 
+   gcc_assert (ncopies >= 1);
+ 
+   if (!STMT_VINFO_RELEVANT_P (stmt_info))
+     return false;
+ 
+   gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info) == vect_induction_def);
+ 
+   if (STMT_VINFO_LIVE_P (stmt_info))
+     {
+       /* FORNOW: not yet supported.  */
+       if (vect_print_dump_info (REPORT_DETAILS))
+         fprintf (vect_dump, "value used after loop.");
+       return false;
+     }
+ 
+   if (TREE_CODE (phi) != PHI_NODE)
+     return false;
+ 
+   if (!vec_stmt) /* transformation not required.  */
+     {
+       STMT_VINFO_TYPE (stmt_info) = induc_vec_info_type;
+       return true;
+     }
+ 
+   /** Transform.  **/
+ 
+   if (vect_print_dump_info (REPORT_DETAILS))
+     fprintf (vect_dump, "transform induction phi.");
+ 
+   vec_def = get_initial_def_for_induction (phi);
+   *vec_stmt = SSA_NAME_DEF_STMT (vec_def);
+   return true;
+ }
+ 
+ 
  /* Function vectorizable_operation.
  
     Check if STMT performs a binary or unary operation that can be vectorized. 
*************** vectorizable_operation (tree stmt, block
*** 2246,2265 ****
  
    gcc_assert (ncopies >= 1);
  
-   /* Is STMT a vectorizable binary/unary operation?   */
    if (!STMT_VINFO_RELEVANT_P (stmt_info))
      return false;
  
!   gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info) == vect_loop_def);
  
    if (STMT_VINFO_LIVE_P (stmt_info))
      {
-       /* FORNOW: not yet supported.  */
        if (vect_print_dump_info (REPORT_DETAILS))
          fprintf (vect_dump, "value used after loop.");
        return false;
      }
  
    if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
      return false;
  
--- 2286,2306 ----
  
    gcc_assert (ncopies >= 1);
  
    if (!STMT_VINFO_RELEVANT_P (stmt_info))
      return false;
  
!   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_loop_def)
!     return false;
  
+   /* FORNOW: not yet supported.  */
    if (STMT_VINFO_LIVE_P (stmt_info))
      {
        if (vect_print_dump_info (REPORT_DETAILS))
          fprintf (vect_dump, "value used after loop.");
        return false;
      }
  
+   /* Is STMT a vectorizable binary/unary operation?   */
    if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
      return false;
  
*************** vectorizable_type_demotion (tree stmt, b
*** 2514,2534 ****
    optab optab;
    enum machine_mode vec_mode;
                                                                                  
-   /* Is STMT a vectorizable type-demotion operation?  */
-                                                                                 
    if (!STMT_VINFO_RELEVANT_P (stmt_info))
      return false;
!                                                                                 
!   gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info) == vect_loop_def);
!                                                                                 
    if (STMT_VINFO_LIVE_P (stmt_info))
      {
-       /* FORNOW: not yet supported.  */
        if (vect_print_dump_info (REPORT_DETAILS))
          fprintf (vect_dump, "value used after loop.");
        return false;
      }
                                                                                  
    if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
      return false;
                                                                                  
--- 2555,2575 ----
    optab optab;
    enum machine_mode vec_mode;
                                                                                  
    if (!STMT_VINFO_RELEVANT_P (stmt_info))
      return false;
! 
!   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_loop_def)
!     return false;
! 
!   /* FORNOW: not yet supported.  */
    if (STMT_VINFO_LIVE_P (stmt_info))
      {
        if (vect_print_dump_info (REPORT_DETAILS))
          fprintf (vect_dump, "value used after loop.");
        return false;
      }
                                                                                  
+   /* Is STMT a vectorizable type-demotion operation?  */
    if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
      return false;
                                                                                  
*************** vectorizable_type_promotion (tree stmt, 
*** 2723,2743 ****
    int j;
    tree vectype_in;
    
-   /* Is STMT a vectorizable type-promotion operation?  */
- 
    if (!STMT_VINFO_RELEVANT_P (stmt_info))
      return false;
  
!   gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info) == vect_loop_def);
  
    if (STMT_VINFO_LIVE_P (stmt_info))
      {
-       /* FORNOW: not yet supported.  */
        if (vect_print_dump_info (REPORT_DETAILS))
! 	fprintf (vect_dump, "value used after loop.");
        return false;
      }
  
    if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
      return false;
  
--- 2764,2784 ----
    int j;
    tree vectype_in;
    
    if (!STMT_VINFO_RELEVANT_P (stmt_info))
      return false;
  
!   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_loop_def)
!     return false;
  
+   /* FORNOW: not yet supported.  */
    if (STMT_VINFO_LIVE_P (stmt_info))
      {
        if (vect_print_dump_info (REPORT_DETAILS))
!         fprintf (vect_dump, "value used after loop.");
        return false;
      }
  
+   /* Is STMT a vectorizable type-promotion operation?  */
    if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
      return false;
  
*************** vectorizable_store (tree stmt, block_stm
*** 3064,3069 ****
--- 3105,3123 ----
    VEC(tree,heap) *dr_chain = NULL, *oprnds = NULL, *result_chain = NULL;
    gcc_assert (ncopies >= 1);
  
+   if (!STMT_VINFO_RELEVANT_P (stmt_info))
+     return false;
+ 
+   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_loop_def)
+     return false;
+ 
+   if (STMT_VINFO_LIVE_P (stmt_info))
+     {
+       if (vect_print_dump_info (REPORT_DETAILS))
+         fprintf (vect_dump, "value used after loop.");
+       return false;
+     }
+ 
    /* Is vectorizable store? */
  
    if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
*************** vectorizable_load (tree stmt, block_stmt
*** 3710,3729 ****
    bool strided_load = false;
    tree first_stmt;
  
-   /* Is vectorizable load? */
    if (!STMT_VINFO_RELEVANT_P (stmt_info))
      return false;
  
!   gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info) == vect_loop_def);
  
    if (STMT_VINFO_LIVE_P (stmt_info))
      {
-       /* FORNOW: not yet supported.  */
        if (vect_print_dump_info (REPORT_DETAILS))
          fprintf (vect_dump, "value used after loop.");
        return false;
      }
  
    if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
      return false;
  
--- 3764,3784 ----
    bool strided_load = false;
    tree first_stmt;
  
    if (!STMT_VINFO_RELEVANT_P (stmt_info))
      return false;
  
!   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_loop_def)
!     return false;
  
+   /* FORNOW: not yet supported.  */
    if (STMT_VINFO_LIVE_P (stmt_info))
      {
        if (vect_print_dump_info (REPORT_DETAILS))
          fprintf (vect_dump, "value used after loop.");
        return false;
      }
  
+   /* Is vectorizable load? */
    if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
      return false;
  
*************** vectorizable_live_operation (tree stmt,
*** 4010,4016 ****
    tree def, def_stmt;
    enum vect_def_type dt; 
  
!   if (!STMT_VINFO_LIVE_P (stmt_info))
      return false;
  
    if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
--- 4065,4073 ----
    tree def, def_stmt;
    enum vect_def_type dt; 
  
!   gcc_assert (STMT_VINFO_LIVE_P (stmt_info));
! 
!   if (STMT_VINFO_DEF_TYPE (stmt_info) == vect_reduction_def)
      return false;
  
    if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
*************** vectorizable_condition (tree stmt, block
*** 4123,4138 ****
    if (!STMT_VINFO_RELEVANT_P (stmt_info))
      return false;
  
!   gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info) == vect_loop_def);
  
    if (STMT_VINFO_LIVE_P (stmt_info))
      {
-       /* FORNOW: not yet supported.  */
        if (vect_print_dump_info (REPORT_DETAILS))
          fprintf (vect_dump, "value used after loop.");
        return false;
      }
  
    if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
      return false;
  
--- 4180,4197 ----
    if (!STMT_VINFO_RELEVANT_P (stmt_info))
      return false;
  
!   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_loop_def)
!     return false;
  
+   /* FORNOW: not yet supported.  */
    if (STMT_VINFO_LIVE_P (stmt_info))
      {
        if (vect_print_dump_info (REPORT_DETAILS))
          fprintf (vect_dump, "value used after loop.");
        return false;
      }
  
+   /* Is vectorizable conditional operation?  */
    if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
      return false;
  
*************** vect_transform_stmt (tree stmt, block_st
*** 4225,4334 ****
    tree orig_stmt_in_pattern;
    bool done;
  
!   if (STMT_VINFO_RELEVANT_P (stmt_info))
      {
!       switch (STMT_VINFO_TYPE (stmt_info))
!       {
!       case type_demotion_vec_info_type:
!         done = vectorizable_type_demotion (stmt, bsi, &vec_stmt);
!         gcc_assert (done);
!         break;
                                                                                  
!       case type_promotion_vec_info_type:
! 	done = vectorizable_type_promotion (stmt, bsi, &vec_stmt);
! 	gcc_assert (done);
! 	break;
! 
!       case type_conversion_vec_info_type:
! 	done = vectorizable_conversion (stmt, bsi, &vec_stmt);
! 	gcc_assert (done);
! 	break;
! 
!       case op_vec_info_type:
! 	done = vectorizable_operation (stmt, bsi, &vec_stmt);
! 	gcc_assert (done);
! 	break;
! 
!       case assignment_vec_info_type:
! 	done = vectorizable_assignment (stmt, bsi, &vec_stmt);
! 	gcc_assert (done);
! 	break;
! 
!       case load_vec_info_type:
! 	done = vectorizable_load (stmt, bsi, &vec_stmt);
! 	gcc_assert (done);
! 	break;
! 
!       case store_vec_info_type:
! 	done = vectorizable_store (stmt, bsi, &vec_stmt);
! 	gcc_assert (done);
! 	if (DR_GROUP_FIRST_DR (stmt_info))
! 	  {
! 	    /* In case of interleaving, the whole chain is vectorized when the
! 	       last store in the chain is reached. Store stmts before the last
! 	       one are skipped, and there vec_stmt_info shouldn't be freed
! 	       meanwhile.  */
! 	    *strided_store = true;
! 	    if (STMT_VINFO_VEC_STMT (stmt_info))
! 	      is_store = true;
  	  }
! 	else
! 	  is_store = true;
! 	break;
! 
!       case condition_vec_info_type:
! 	done = vectorizable_condition (stmt, bsi, &vec_stmt);
! 	gcc_assert (done);
! 	break;
  
!       case call_vec_info_type:
! 	done = vectorizable_call (stmt, bsi, &vec_stmt);
! 	break;
  
!       default:
! 	if (vect_print_dump_info (REPORT_DETAILS))
! 	  fprintf (vect_dump, "stmt not supported.");
! 	gcc_unreachable ();
!       }
! 
!       gcc_assert (vec_stmt || *strided_store);
!       if (vec_stmt)
  	{
! 	  STMT_VINFO_VEC_STMT (stmt_info) = vec_stmt;
! 	  orig_stmt_in_pattern = STMT_VINFO_RELATED_STMT (stmt_info);
! 	  if (orig_stmt_in_pattern)
! 	    {
! 	      stmt_vec_info stmt_vinfo = vinfo_for_stmt (orig_stmt_in_pattern);
! 	      if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
! 		{
! 		  gcc_assert (STMT_VINFO_RELATED_STMT (stmt_vinfo) == stmt);
! 		  
! 		  /* STMT was inserted by the vectorizer to replace a 
! 		     computation idiom.  ORIG_STMT_IN_PATTERN is a stmt in the 
! 		     original sequence that computed this idiom.  We need to 
! 		     record a pointer to VEC_STMT in the stmt_info of 
! 		     ORIG_STMT_IN_PATTERN.  See more details in the 
! 		     documentation of vect_pattern_recog.  */
! 
! 		  STMT_VINFO_VEC_STMT (stmt_vinfo) = vec_stmt;
! 		}
! 	    }
  	}
      }
  
!   if (STMT_VINFO_LIVE_P (stmt_info))
      {
!       switch (STMT_VINFO_TYPE (stmt_info))
!       {
!       case reduc_vec_info_type:
!         done = vectorizable_reduction (stmt, bsi, &vec_stmt);
!         gcc_assert (done);
!         break;
  
!       default:
!         done = vectorizable_live_operation (stmt, bsi, &vec_stmt);
!         gcc_assert (done);
!       }
      }
  
    return is_store; 
--- 4284,4391 ----
    tree orig_stmt_in_pattern;
    bool done;
  
!   switch (STMT_VINFO_TYPE (stmt_info))
      {
!     case type_demotion_vec_info_type:
!       done = vectorizable_type_demotion (stmt, bsi, &vec_stmt);
!       gcc_assert (done);
!       break;
                                                                                  
!     case type_promotion_vec_info_type:
!       done = vectorizable_type_promotion (stmt, bsi, &vec_stmt);
!       gcc_assert (done);
!       break;
! 
!     case type_conversion_vec_info_type:
!       done = vectorizable_conversion (stmt, bsi, &vec_stmt);
!       gcc_assert (done);
!       break;
! 
!     case induc_vec_info_type:
!       done = vectorizable_induction (stmt, bsi, &vec_stmt);
!       gcc_assert (done);
!       break;
! 
!     case op_vec_info_type:
!       done = vectorizable_operation (stmt, bsi, &vec_stmt);
!       gcc_assert (done);
!       break;
! 
!     case assignment_vec_info_type:
!       done = vectorizable_assignment (stmt, bsi, &vec_stmt);
!       gcc_assert (done);
!       break;
! 
!     case load_vec_info_type:
!       done = vectorizable_load (stmt, bsi, &vec_stmt);
!       gcc_assert (done);
!       break;
! 
!     case store_vec_info_type:
!       done = vectorizable_store (stmt, bsi, &vec_stmt);
!       gcc_assert (done);
!       if (DR_GROUP_FIRST_DR (stmt_info))
! 	{
! 	  /* In case of interleaving, the whole chain is vectorized when the
! 	     last store in the chain is reached. Store stmts before the last
! 	     one are skipped, and there vec_stmt_info shouldn't be freed
! 	     meanwhile.  */
! 	  *strided_store = true;
! 	  if (STMT_VINFO_VEC_STMT (stmt_info))
! 	    is_store = true;
  	  }
!       else
! 	is_store = true;
!       break;
  
!     case condition_vec_info_type:
!       done = vectorizable_condition (stmt, bsi, &vec_stmt);
!       gcc_assert (done);
!       break;
! 
!     case call_vec_info_type:
!       done = vectorizable_call (stmt, bsi, &vec_stmt);
!       break;
! 
!     case reduc_vec_info_type:
!       done = vectorizable_reduction (stmt, bsi, &vec_stmt);
!       gcc_assert (done);
!       break;
  
!     default:
!       if (!STMT_VINFO_LIVE_P (stmt_info))
  	{
! 	  if (vect_print_dump_info (REPORT_DETAILS))
! 	    fprintf (vect_dump, "stmt not supported.");
! 	  gcc_unreachable ();
  	}
      }
  
!   if (STMT_VINFO_LIVE_P (stmt_info)
!       && STMT_VINFO_TYPE (stmt_info) != reduc_vec_info_type)
      {
!       done = vectorizable_live_operation (stmt, bsi, &vec_stmt);
!       gcc_assert (done);
!     }
  
!   if (vec_stmt)
!     {
!       STMT_VINFO_VEC_STMT (stmt_info) = vec_stmt;
!       orig_stmt_in_pattern = STMT_VINFO_RELATED_STMT (stmt_info);
!       if (orig_stmt_in_pattern)
! 	{
! 	  stmt_vec_info stmt_vinfo = vinfo_for_stmt (orig_stmt_in_pattern);
! 	  /* STMT was inserted by the vectorizer to replace a computation idiom.
! 	     ORIG_STMT_IN_PATTERN is a stmt in the original sequence that 
! 	     computed this idiom.  We need to record a pointer to VEC_STMT in 
! 	     the stmt_info of ORIG_STMT_IN_PATTERN.  See more details in the 
! 	     documentation of vect_pattern_recog.  */
! 	  if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
! 	    {
! 	      gcc_assert (STMT_VINFO_RELATED_STMT (stmt_vinfo) == stmt);
! 	      STMT_VINFO_VEC_STMT (stmt_vinfo) = vec_stmt;
! 	    }
! 	}
      }
  
    return is_store; 
*************** vect_transform_loop (loop_vec_info loop_
*** 5156,5166 ****
    for (i = 0; i < nbbs; i++)
      {
        basic_block bb = bbs[i];
  
        for (si = bsi_start (bb); !bsi_end_p (si);)
  	{
  	  tree stmt = bsi_stmt (si);
- 	  stmt_vec_info stmt_info;
  	  bool is_store;
  
  	  if (vect_print_dump_info (REPORT_DETAILS))
--- 5213,5251 ----
    for (i = 0; i < nbbs; i++)
      {
        basic_block bb = bbs[i];
+       stmt_vec_info stmt_info;
+       tree phi;
+ 
+       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+         {
+ 	  if (vect_print_dump_info (REPORT_DETAILS))
+ 	    {
+ 	      fprintf (vect_dump, "------>vectorizing phi: ");
+ 	      print_generic_expr (vect_dump, phi, TDF_SLIM);
+ 	    }
+ 	  stmt_info = vinfo_for_stmt (phi);
+ 	  if (!stmt_info)
+ 	    continue;
+ 	  if (!STMT_VINFO_RELEVANT_P (stmt_info)
+ 	      && !STMT_VINFO_LIVE_P (stmt_info))
+ 	    continue;
+ 
+ 	  if ((TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info))
+ 	        != (unsigned HOST_WIDE_INT) vectorization_factor)
+ 	      && vect_print_dump_info (REPORT_DETAILS))
+ 	    fprintf (vect_dump, "multiple-types.");
+ 
+ 	  if (STMT_VINFO_DEF_TYPE (stmt_info) == vect_induction_def)
+ 	    {
+ 	      if (vect_print_dump_info (REPORT_DETAILS))
+ 		fprintf (vect_dump, "transform phi.");
+ 	      vect_transform_stmt (phi, NULL, NULL);
+ 	    }
+ 	}
  
        for (si = bsi_start (bb); !bsi_end_p (si);)
  	{
  	  tree stmt = bsi_stmt (si);
  	  bool is_store;
  
  	  if (vect_print_dump_info (REPORT_DETAILS))
*************** vect_transform_loop (loop_vec_info loop_
*** 5177,5182 ****
--- 5262,5268 ----
  	      continue;
  	    }
  
+ 	  gcc_assert (STMT_VINFO_VECTYPE (stmt_info));
  	  if ((TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info))
  		 != (unsigned HOST_WIDE_INT) vectorization_factor)
  	      && vect_print_dump_info (REPORT_DETAILS))
Index: tree-ssa-reassoc.c
===================================================================
*** tree-ssa-reassoc.c	(revision 123103)
--- tree-ssa-reassoc.c	(working copy)
*************** execute_reassoc (void)
*** 1476,1485 ****
    return 0;
  }
  
  struct tree_opt_pass pass_reassoc =
  {
    "reassoc",				/* name */
!   NULL,				/* gate */
    execute_reassoc,				/* execute */
    NULL,					/* sub */
    NULL,					/* next */
--- 1476,1491 ----
    return 0;
  }
  
+ static bool
+ gate_reassoc (void)
+ {
+   return flag_tree_reassoc != 0;
+ }
+ 
  struct tree_opt_pass pass_reassoc =
  {
    "reassoc",				/* name */
!   gate_reassoc,				/* gate */
    execute_reassoc,				/* execute */
    NULL,					/* sub */
    NULL,					/* next */