tree-flow.h (stmt_ann_d): Move aux to ...

        * tree-flow.h (stmt_ann_d): Move aux to ...
        (tree_ann_common_d): ... here.
        * tree-ssa-loop-im.c (LIM_DATA, determine_invariantness_stmt,
        move_computations_stmt, schedule_sm): Update references to
        aux.
        * tree-vectorizer.h (set_stmt_info, vinfo_for_stmt): Likewise.
        * tree-vect-transform.c (vect_create_index_for_vector_ref): Update
        call to set_stmt_info.
        (vect_transform_loop): Likewise.
        * tree-vectorizer.c (new_loop_vec_info, destroy_loop_vec_info):
        Likewise.

        * tree-vect-analyze.c (vect_analyze_scalar_cycles): Made void instead of
        bool.
        (vect_mark_relevant): Takes two additional arguments - live_p and
        relevant_p. Set RELEVANT_P and LIVE_P according to these arguments.
        (vect_stmt_relevant_p): Differentiate between a live stmt and a
        relevant stmt. Return two values = live_p and relevant_p.
        (vect_mark_stmts_to_be_vectorized): Call vect_mark_relevant and
        vect_stmt_relevant_p with additional arguments. Phis are no longer
        put into the worklist (analyzed seperately in analyze_scalar_cycles).
        (vect_determine_vectorization_factor): Also check for LIVE_P, because a
        stmt that is marked as irrelevant and live, cause it's only used out
        side the loop, may need to be vectorized (e.g. reduction).
        (vect_analyze_operations): Examine phis. Call
        vectorizable_live_operation for for LIVE_P stmts. Check if
        need_to_vectorize.
        (vect_analyze_scalar_cycles): Update documentation. Don't fail
        vectorization - just classify the scalar cycles created by the loop
        phis. Call vect_is_simple_reduction.
        (vect_analyze_loop): Call to analyze_scalar_cycles moved earlier.
        * tree-vect-transform.c (vect_create_index_for_vector_ref): Update
        call to set_stmt_info.
        (vect_get_vec_def_for_operand): Code reorganized - the code that
        classifies the type of use was factored out to vect_is_simple_use.
        (vectorizable_store, vect_is_simple_cond): Call vect_is_simple_use with
        additional arguments.
        (vectorizable_assignment): Likewise. Also make sure the stmt is relevant
        and computes a loop_vec_def.
        (vectorizable_operation, vectorizable_load, vectorizable_condition):
        Likewise.
        (vectorizable_live_operation): New.
        (vect_transform_stmt): Handle LIVE_P stmts.
        * tree-vectorizer.c (new_stmt_vec_info): Initialize the new fields
        STMT_VINFO_LIVE_P and STMT_VINFO_DEF_TYPE.
        (new_loop_vec_info, destroy_loop_vec_info): Also handle phis.
        (vect_is_simple_use): Determine the type of the def and return it
        in a new function argument. Consider vect_reduction_def and
        vect_induction_def, but for now these are not supported.
        (vect_is_simple_reduction): New. Empty for now.
        * tree-vectorizer.h (vect_def_type): New enum type.
        (_stmt_vec_info): Added new fields - live and _stmt_vec_info.
        (STMT_VINFO_LIVE_P, STMT_VINFO_DEF_TYPE): New accessor macros.
        (vect_is_simple_use): New arguments added to function declaration.
        (vect_is_simple_reduction): New function declaration.
        (vectorizable_live_operation): New function declaration.

        * tree-vect-analyze.c (vect_can_advance_ivs_p): Add debug printout.
        (vect_can_advance_ivs_p): Likewise.
        * tree-vect-transform.c (vect_update_ivs_after_vectorizer): Likewise.

From-SVN: r100617

12 files changed, 882 insertions, 339 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index ae62274..47bcfa0 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,66 @@
+2005-06-05  Dorit Nuzman  <dorit@il.ibm.com>
+
+        * tree-flow.h (stmt_ann_d): Move aux to ...
+        (tree_ann_common_d): ... here.
+        * tree-ssa-loop-im.c (LIM_DATA, determine_invariantness_stmt,
+        move_computations_stmt, schedule_sm): Update references to
+        aux.
+        * tree-vectorizer.h (set_stmt_info, vinfo_for_stmt): Likewise.
+        * tree-vect-transform.c (vect_create_index_for_vector_ref): Update
+        call to set_stmt_info.
+        (vect_transform_loop): Likewise.
+        * tree-vectorizer.c (new_loop_vec_info, destroy_loop_vec_info):
+        Likewise.
+
+        * tree-vect-analyze.c (vect_analyze_scalar_cycles): Made void instead of
+        bool.
+        (vect_mark_relevant): Takes two additional arguments - live_p and
+        relevant_p. Set RELEVANT_P and LIVE_P according to these arguments.
+        (vect_stmt_relevant_p): Differentiate between a live stmt and a
+        relevant stmt. Return two values = live_p and relevant_p.
+        (vect_mark_stmts_to_be_vectorized): Call vect_mark_relevant and
+        vect_stmt_relevant_p with additional arguments. Phis are no longer
+        put into the worklist (analyzed seperately in analyze_scalar_cycles).
+        (vect_determine_vectorization_factor): Also check for LIVE_P, because a
+        stmt that is marked as irrelevant and live, cause it's only used out
+        side the loop, may need to be vectorized (e.g. reduction).
+        (vect_analyze_operations): Examine phis. Call
+        vectorizable_live_operation for for LIVE_P stmts. Check if
+        need_to_vectorize.
+        (vect_analyze_scalar_cycles): Update documentation. Don't fail
+        vectorization - just classify the scalar cycles created by the loop
+        phis. Call vect_is_simple_reduction.
+        (vect_analyze_loop): Call to analyze_scalar_cycles moved earlier.
+        * tree-vect-transform.c (vect_create_index_for_vector_ref): Update
+        call to set_stmt_info.
+        (vect_get_vec_def_for_operand): Code reorganized - the code that
+        classifies the type of use was factored out to vect_is_simple_use.
+        (vectorizable_store, vect_is_simple_cond): Call vect_is_simple_use with
+        additional arguments.
+        (vectorizable_assignment): Likewise. Also make sure the stmt is relevant
+        and computes a loop_vec_def.
+        (vectorizable_operation, vectorizable_load, vectorizable_condition):
+        Likewise.
+        (vectorizable_live_operation): New.
+        (vect_transform_stmt): Handle LIVE_P stmts.
+        * tree-vectorizer.c (new_stmt_vec_info): Initialize the new fields
+        STMT_VINFO_LIVE_P and STMT_VINFO_DEF_TYPE.
+        (new_loop_vec_info, destroy_loop_vec_info): Also handle phis.
+        (vect_is_simple_use): Determine the type of the def and return it
+        in a new function argument. Consider vect_reduction_def and
+        vect_induction_def, but for now these are not supported.
+        (vect_is_simple_reduction): New. Empty for now.
+        * tree-vectorizer.h (vect_def_type): New enum type.
+        (_stmt_vec_info): Added new fields - live and _stmt_vec_info.
+        (STMT_VINFO_LIVE_P, STMT_VINFO_DEF_TYPE): New accessor macros.
+        (vect_is_simple_use): New arguments added to function declaration.
+        (vect_is_simple_reduction): New function declaration.
+        (vectorizable_live_operation): New function declaration.
+
+        * tree-vect-analyze.c (vect_can_advance_ivs_p): Add debug printout.
+        (vect_can_advance_ivs_p): Likewise.
+        * tree-vect-transform.c (vect_update_ivs_after_vectorizer): Likewise.
+
 2005-06-05  Eric Christopher  <echristo@redhat.com>
 
 	* config/mips/mips.c (mips_rtx_costs): Remove unused variable.
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index e2c887a..5c440db 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,10 @@
+2005-06-05  Dorit Nuzman  <dorit@il.ibm.com>
+
+	* gcc.dg/vect/vect-62: Check that second loop is not vectorized.
+	* gcc.dg/vect/vect-reduc-1.c: New.
+	* gcc.dg/vect/vect-reduc-2.c: New.
+	* gcc.dg/vect/vect-reduc-3.c: New.
+
 2005-06-04  Dale Johannesen  <dalej@apple.com>
 
 	* gcc.c-torture/execute/20050603-1.c:  New.
diff --git a/gcc/testsuite/gcc.dg/vect/vect-62.c b/gcc/testsuite/gcc.dg/vect/vect-62.c
index f696aa3..433b8bf 100644
--- a/gcc/testsuite/gcc.dg/vect/vect-62.c
+++ b/gcc/testsuite/gcc.dg/vect/vect-62.c
@@ -32,7 +32,9 @@ int main1 ()
     }
 
   /* Multidimensional array. Aligned. The "inner" dimensions
-     are invariant in the inner loop. Store. */
+     are invariant in the inner loop. Vectorizable, but the
+     vectorizer detects that everything is invariant and that
+     the loop is better left untouched. (it should be optimized away). */
   for (i = 0; i < N; i++)
     {
       for (j = 0; j < N; j++)
@@ -62,6 +64,7 @@ int main (void)
   return main1 ();
 }
 
-/* { dg-final { scan-tree-dump-times "vectorized 2 loops" 1 "vect" } } */
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" } } */
 /* { dg-final { scan-tree-dump-times "Vectorizing an unaligned access" 0 "vect" } } */
+/* { dg-final { scan-tree-dump-times "not vectorized: redundant loop. no profit to vectorize." 1 "vect" } } */
 /* { dg-final { cleanup-tree-dump "vect" } } */
diff --git a/gcc/testsuite/gcc.dg/vect/vect-reduc-1.c b/gcc/testsuite/gcc.dg/vect/vect-reduc-1.c
new file mode 100644
index 0000000..1c3d555
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-reduc-1.c
@@ -0,0 +1,56 @@
+/* { dg-require-effective-target vect_int } */
+
+#include <stdarg.h>
+#include "tree-vect.h"
+
+#define N 16
+#define DIFF 242
+
+/* Test vectorization of reduction of unsigned-int.  */
+/* Not supported yet.  */
+
+int main1 (unsigned int x, unsigned int max_result)
+{
+  int i;
+  unsigned int ub[N] = {0,3,6,9,12,15,18,21,24,27,30,33,36,39,42,45};
+  unsigned int uc[N] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
+  unsigned int udiff = 2;
+  unsigned int umax = x;
+  unsigned int umin = 10;
+
+  /* Summation.  */
+  for (i = 0; i < N; i++) {
+    udiff += (ub[i] - uc[i]);
+  }
+
+  /* Maximum.  */
+  for (i = 0; i < N; i++) {
+    umax = umax < uc[i] ? uc[i] : umax;
+  }
+
+  /* Minimum.  */
+  for (i = 0; i < N; i++) {
+    umin = umin > uc[i] ? uc[i] : umin;
+  }
+
+  /* check results:  */
+  if (udiff != DIFF)
+    abort ();
+  if (umax != max_result)
+    abort ();
+  if (umin != 0)
+    abort ();
+
+  return 0;
+}
+
+int main (void)
+{ 
+  check_vect ();
+  
+  return main1 (100, 100);
+  return main1 (0, 15);
+}
+
+/* { dg-final { scan-tree-dump-times "vectorized 3 loops" 1 "vect" { xfail *-*-* } } } */
+/* { dg-final { scan-tree-dump-times "not vectorized: unsupported use in stmt." 3 "vect" } } */
diff --git a/gcc/testsuite/gcc.dg/vect/vect-reduc-2.c b/gcc/testsuite/gcc.dg/vect/vect-reduc-2.c
new file mode 100644
index 0000000..fd5e94b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-reduc-2.c
@@ -0,0 +1,54 @@
+
+/* { dg-require-effective-target vect_int } */
+
+#include <stdarg.h>
+#include "tree-vect.h"
+
+#define N 16
+#define DIFF 242
+
+/* Test vectorization of reduction of signed-int.  */
+/* Not supported yet.  */
+
+int main1 (int x, int max_result)
+{
+  int i;
+  int b[N] = {0,3,6,9,12,15,18,21,24,27,30,33,36,39,42,45};
+  int c[N] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
+  int diff = 2;
+  int max = x;
+  int min = 10;
+
+  for (i = 0; i < N; i++) {
+    diff += (b[i] - c[i]);
+  }
+
+  for (i = 0; i < N; i++) {
+    max = max < c[i] ? c[i] : max;
+  }
+
+  for (i = 0; i < N; i++) {
+    min = min > c[i] ? c[i] : min;
+  }
+
+  /* check results:  */
+  if (diff != DIFF)
+    abort ();
+  if (max != max_result)
+    abort ();
+  if (min != 0)
+    abort ();
+
+  return 0;
+}
+
+int main (void)
+{ 
+  check_vect ();
+  
+  return main1 (100, 100);
+  return main1 (0, 15);
+}
+
+/* { dg-final { scan-tree-dump-times "vectorized 3 loops" 1 "vect" { xfail *-*-* } } } */
+/* { dg-final { scan-tree-dump-times "not vectorized: unsupported use in stmt." 3 "vect" } } */
diff --git a/gcc/testsuite/gcc.dg/vect/vect-reduc-3.c b/gcc/testsuite/gcc.dg/vect/vect-reduc-3.c
new file mode 100644
index 0000000..86fbc4b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-reduc-3.c
@@ -0,0 +1,41 @@
+/* { dg-require-effective-target vect_int } */
+
+#include <stdarg.h>
+#include "tree-vect.h"
+
+#define N 16
+#define DIFF 240
+
+/* Test vectorization of reduction of unsigned-int in the presence
+   of unknown-loop-bound.  */
+/* Not supported yet.  */
+
+int main1 (int n)
+{
+  int i;
+  unsigned int ub[N] = {0,3,6,9,12,15,18,21,24,27,30,33,36,39,42,45};
+  unsigned int uc[N] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
+  unsigned int udiff;
+
+  udiff = 0;
+  for (i = 0; i < n; i++) {
+    udiff += (ub[i] - uc[i]);
+  }
+
+  /* check results:  */
+  if (udiff != DIFF)
+    abort ();
+
+  return 0;
+}
+
+int main (void)
+{ 
+  check_vect ();
+  
+  return main1 (N);
+  return main1 (N-1);
+}
+
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" { xfail *-*-* } } } */
+/* { dg-final { scan-tree-dump-times "not vectorized: unsupported use in stmt." 1 "vect" } } */
diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h
index 2b044b8..584e42b 100644
--- a/gcc/tree-flow.h
+++ b/gcc/tree-flow.h
@@ -93,6 +93,10 @@ struct tree_ann_common_d GTY(())
   /* Annotation type.  */
   enum tree_ann_type type;
 
+ /* Auxiliary info specific to a pass.  At all times, this
+    should either point to valid data or be NULL.  */ 
+  PTR GTY ((skip (""))) aux; 
+
   /* The value handle for this expression.  Used by GVN-PRE.  */
   tree GTY((skip)) value_handle;
 };
@@ -293,10 +297,6 @@ struct stmt_ann_d GTY(())
      pass which needs statement UIDs.  */
   unsigned int uid;
 
- /* Auxiliary info specific to a pass.  At all times, this
-    should either point to valid data or be NULL.  */
-  PTR GTY ((skip (""))) aux;
-
   /* Linked list of histograms for value-based profiling.  This is really a
      struct histogram_value*.  We use void* to avoid having to export that
      everywhere, and to avoid having to put it in GC memory.  */
diff --git a/gcc/tree-ssa-loop-im.c b/gcc/tree-ssa-loop-im.c
index dc9002f..e7acc5c 100644
--- a/gcc/tree-ssa-loop-im.c
+++ b/gcc/tree-ssa-loop-im.c
@@ -102,7 +102,7 @@ struct lim_aux_data
 
 #define LIM_DATA(STMT) (TREE_CODE (STMT) == PHI_NODE \
 			? NULL \
-			: (struct lim_aux_data *) (stmt_ann (STMT)->aux))
+			: (struct lim_aux_data *) (stmt_ann (STMT)->common.aux))
 
 /* Description of a memory reference location for store motion.  */
 
@@ -632,7 +632,7 @@ determine_invariantness_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
 	  stmt = stmt1;
 	}
 
-      stmt_ann (stmt)->aux = xcalloc (1, sizeof (struct lim_aux_data));
+      stmt_ann (stmt)->common.aux = xcalloc (1, sizeof (struct lim_aux_data));
       LIM_DATA (stmt)->always_executed_in = outermost;
 
       if (maybe_never && pos == MOVE_PRESERVE_EXECUTION)
@@ -723,7 +723,7 @@ move_computations_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
       cost = LIM_DATA (stmt)->cost;
       level = LIM_DATA (stmt)->tgt_loop;
       free_lim_aux_data (LIM_DATA (stmt));
-      stmt_ann (stmt)->aux = NULL;
+      stmt_ann (stmt)->common.aux = NULL;
 
       if (!level)
 	{
@@ -952,7 +952,7 @@ schedule_sm (struct loop *loop, edge *exits, unsigned n_exits, tree ref,
 
   /* Emit the load & stores.  */
   load = build (MODIFY_EXPR, void_type_node, tmp_var, ref);
-  get_stmt_ann (load)->aux = xcalloc (1, sizeof (struct lim_aux_data));
+  get_stmt_ann (load)->common.aux = xcalloc (1, sizeof (struct lim_aux_data));
   LIM_DATA (load)->max_loop = loop;
   LIM_DATA (load)->tgt_loop = loop;
 
diff --git a/gcc/tree-vect-analyze.c b/gcc/tree-vect-analyze.c
index 4d2058f..0b8e26c 100644
--- a/gcc/tree-vect-analyze.c
+++ b/gcc/tree-vect-analyze.c
@@ -42,7 +42,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 static loop_vec_info vect_analyze_loop_form (struct loop *);
 static bool vect_analyze_data_refs (loop_vec_info);
 static bool vect_mark_stmts_to_be_vectorized (loop_vec_info);
-static bool vect_analyze_scalar_cycles (loop_vec_info);
+static void vect_analyze_scalar_cycles (loop_vec_info);
 static bool vect_analyze_data_ref_accesses (loop_vec_info);
 static bool vect_analyze_data_ref_dependences (loop_vec_info);
 static bool vect_analyze_data_refs_alignment (loop_vec_info);
@@ -53,8 +53,8 @@ static bool vect_determine_vectorization_factor (loop_vec_info);
 
 /* Utility functions for the analyses.  */
 static bool exist_non_indexing_operands_for_use_p (tree, tree);
-static void vect_mark_relevant (VEC(tree,heap) **, tree);
-static bool vect_stmt_relevant_p (tree, loop_vec_info);
+static void vect_mark_relevant (VEC(tree,heap) **, tree, bool, bool);
+static bool vect_stmt_relevant_p (tree, loop_vec_info, bool *, bool *);
 static tree vect_get_loop_niters (struct loop *, tree *);
 static bool vect_analyze_data_ref_dependence
   (struct data_reference *, struct data_reference *, loop_vec_info);
@@ -344,8 +344,13 @@ vect_determine_vectorization_factor (loop_vec_info loop_vinfo)
 
           gcc_assert (stmt_info);
           /* skip stmts which do not need to be vectorized.  */
-          if (!STMT_VINFO_RELEVANT_P (stmt_info))
-            continue;
+          if (!STMT_VINFO_RELEVANT_P (stmt_info)
+	      && !STMT_VINFO_LIVE_P (stmt_info))
+            {
+              if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+                fprintf (vect_dump, "skip.");
+              continue;
+            }
 
           if (VECTOR_MODE_P (TYPE_MODE (TREE_TYPE (stmt))))
             {
@@ -444,6 +449,9 @@ vect_analyze_operations (loop_vec_info loop_vinfo)
   unsigned int vectorization_factor = 0;
   int i;
   bool ok;
+  tree phi;
+  stmt_vec_info stmt_info;
+  bool need_to_vectorize = false;
 
   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
     fprintf (vect_dump, "=== vect_analyze_operations ===");
@@ -455,6 +463,29 @@ vect_analyze_operations (loop_vec_info loop_vinfo)
     {
       basic_block bb = bbs[i];
 
+      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+        {
+	  stmt_info = vinfo_for_stmt (phi);
+	  if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+	    {
+	      fprintf (vect_dump, "examining phi: ");
+	      print_generic_expr (vect_dump, phi, TDF_SLIM);
+	    }
+
+	  gcc_assert (stmt_info);
+
+	  if (STMT_VINFO_LIVE_P (stmt_info))
+	    {
+	      /* FORNOW: not yet supported.  */
+	      if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
+					LOOP_LOC (loop_vinfo)))
+		fprintf (vect_dump, "not vectorized: value used after loop.");
+	    return false;
+	  }
+
+          gcc_assert (!STMT_VINFO_RELEVANT_P (stmt_info));
+        }
+
       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
 	{
 	  tree stmt = bsi_stmt (si);
@@ -475,42 +506,77 @@ vect_analyze_operations (loop_vec_info loop_vinfo)
 	     - computations that are used only for array indexing or loop
 	     control  */
 
-	  if (!STMT_VINFO_RELEVANT_P (stmt_info))
+	  if (!STMT_VINFO_RELEVANT_P (stmt_info)
+	      && !STMT_VINFO_LIVE_P (stmt_info))
 	    {
 	      if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 	        fprintf (vect_dump, "irrelevant.");
 	      continue;
 	    }
 
-#ifdef ENABLE_CHECKING
           if (STMT_VINFO_RELEVANT_P (stmt_info))
             {
               gcc_assert (!VECTOR_MODE_P (TYPE_MODE (TREE_TYPE (stmt))));
               gcc_assert (STMT_VINFO_VECTYPE (stmt_info));
-            }
-#endif
 
-	  ok = (vectorizable_operation (stmt, NULL, NULL)
-		|| vectorizable_assignment (stmt, NULL, NULL)
-		|| vectorizable_load (stmt, NULL, NULL)
-		|| vectorizable_store (stmt, NULL, NULL)
-		|| vectorizable_condition (stmt, NULL, NULL));
+	      ok = (vectorizable_operation (stmt, NULL, NULL)
+		    || vectorizable_assignment (stmt, NULL, NULL)
+		    || vectorizable_load (stmt, NULL, NULL)
+		    || vectorizable_store (stmt, NULL, NULL)
+		    || vectorizable_condition (stmt, NULL, NULL));
+
+	      if (!ok)
+		{
+		  if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
+					    LOOP_LOC (loop_vinfo)))
+		    {
+		      fprintf (vect_dump, 
+			       "not vectorized: relevant stmt not supported: ");
+		      print_generic_expr (vect_dump, stmt, TDF_SLIM);
+		    }
+		  return false;
+		}	
+	      need_to_vectorize = true;
+            }
 
-	  if (!ok)
+	  if (STMT_VINFO_LIVE_P (stmt_info))
 	    {
-	      if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
-                                         LOOP_LOC (loop_vinfo)))
+	      ok = vectorizable_live_operation (stmt, NULL, NULL);
+
+	      if (!ok)
 		{
-                  fprintf (vect_dump, "not vectorized: stmt not supported: ");
-		  print_generic_expr (vect_dump, stmt, TDF_SLIM);
+		  if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
+					    LOOP_LOC (loop_vinfo)))
+		    {
+		      fprintf (vect_dump, 
+			       "not vectorized: live stmt not supported: ");
+		      print_generic_expr (vect_dump, stmt, TDF_SLIM);
+		    }
+		  return false;
 		}
-	      return false;
 	    }
-	}
-    }
+	} /* stmts in bb */
+    } /* bbs */
 
   /* TODO: Analyze cost. Decide if worth while to vectorize.  */
 
+  /* All operations in the loop are either irrelevant (deal with loop
+     control, or dead), or only used outside the loop and can be moved
+     out of the loop (e.g. invariants, inductions).  The loop can be 
+     optimized away by scalar optimizations.  We're better off not 
+     touching this loop.  */
+  if (!need_to_vectorize)
+    {
+      if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
+	fprintf (vect_dump, 
+		 "All the computation can be taken out of the loop.");
+      if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
+                                LOOP_LOC (loop_vinfo)))
+        fprintf (vect_dump, 
+		 "not vectorized: redundant loop. no profit to vectorize.");
+      return false;
+    }
+
   if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
       && vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
     fprintf (vect_dump,
@@ -601,40 +667,43 @@ exist_non_indexing_operands_for_use_p (tree use, tree stmt)
 /* Function vect_analyze_scalar_cycles.
 
    Examine the cross iteration def-use cycles of scalar variables, by
-   analyzing the loop (scalar) PHIs; verify that the cross iteration def-use
-   cycles that they represent do not impede vectorization.
+   analyzing the loop (scalar) PHIs; Classify each cycle as one of the
+   following: invariant, induction, reduction, unknown.
+   
+   Some forms of scalar cycles are not yet supported.
+
+   Example1: reduction: (unsupported yet)
 
-   FORNOW: Reduction as in the following loop, is not supported yet:
               loop1:
               for (i=0; i<N; i++)
                  sum += a[i];
-	   The cross-iteration cycle corresponding to variable 'sum' will be
-	   considered too complicated and will impede vectorization.
 
-   FORNOW: Induction as in the following loop, is not supported yet:
+   Example2: induction: (unsupported yet)
+
               loop2:
               for (i=0; i<N; i++)
                  a[i] = i;
 
-           However, the following loop *is* vectorizable:
+   Note: the following loop *is* vectorizable:
+
               loop3:
               for (i=0; i<N; i++)
                  a[i] = b[i];
 
-           In both loops there exists a def-use cycle for the variable i:
+         even though it has a def-use cycle caused by the induction variable i:
+
               loop: i_2 = PHI (i_0, i_1)
                     a[i_2] = ...;
                     i_1 = i_2 + 1;
                     GOTO loop;
 
-           The evolution of the above cycle is considered simple enough,
-	   however, we also check that the cycle does not need to be
-	   vectorized, i.e - we check that the variable that this cycle
-	   defines is only used for array indexing or in stmts that do not
-	   need to be vectorized. This is not the case in loop2, but it
-	   *is* the case in loop3.  */
+         because the def-use cycle in loop3 is considered "not relevant" - i.e.,
+         it does not need to be vectorized because it is only used for array
+         indexing (see 'mark_stmts_to_be_vectorized'). The def-use cycle in
+         loop2 on the other hand is relevant (it is being written to memory).
+*/
 
-static bool
+static void
 vect_analyze_scalar_cycles (loop_vec_info loop_vinfo)
 {
   tree phi;
@@ -648,6 +717,9 @@ vect_analyze_scalar_cycles (loop_vec_info loop_vinfo)
   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
     {
       tree access_fn = NULL;
+      tree def = PHI_RESULT (phi);
+      stmt_vec_info stmt_vinfo = vinfo_for_stmt (phi);
+      tree reduc_stmt;
 
       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 	{
@@ -658,35 +730,21 @@ vect_analyze_scalar_cycles (loop_vec_info loop_vinfo)
       /* Skip virtual phi's. The data dependences that are associated with
          virtual defs/uses (i.e., memory accesses) are analyzed elsewhere.  */
 
-      if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
+      if (!is_gimple_reg (SSA_NAME_VAR (def)))
 	{
 	  if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 	    fprintf (vect_dump, "virtual phi. skip.");
 	  continue;
 	}
 
-      /* Analyze the evolution function.  */
-
-      /* FORNOW: The only scalar cross-iteration cycles that we allow are
-         those of loop induction variables; This property is verified here.
+      STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_unknown_def_type;
 
-         Furthermore, if that induction variable is used in an operation
-         that needs to be vectorized (i.e, is not solely used to index
-         arrays and check the exit condition) - we do not support its
-         vectorization yet. This property is verified in vect_is_simple_use,
-         during vect_analyze_operations.  */
+      /* Analyze the evolution function.  */
 
-      access_fn = /* instantiate_parameters
-		     (loop,*/
-	 analyze_scalar_evolution (loop, PHI_RESULT (phi));
+      access_fn = analyze_scalar_evolution (loop, def);
 
       if (!access_fn)
-	{
-	  if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
-				    LOOP_LOC (loop_vinfo)))
-	    fprintf (vect_dump, "not vectorized: unsupported scalar cycle.");
-	  return false;
-	}
+	continue;
 
       if (vect_print_dump_info (REPORT_DETAILS,
 				LOOP_LOC (loop_vinfo)))
@@ -695,16 +753,32 @@ vect_analyze_scalar_cycles (loop_vec_info loop_vinfo)
            print_generic_expr (vect_dump, access_fn, TDF_SLIM);
         }
 
-      if (!vect_is_simple_iv_evolution (loop->num, access_fn, &dummy, &dummy))
+      if (vect_is_simple_iv_evolution (loop->num, access_fn, &dummy, &dummy))
 	{
-	  if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
-				    LOOP_LOC (loop_vinfo)))
-	    fprintf (vect_dump, "not vectorized: unsupported scalar cycle.");
-	  return false;
+	  if (vect_print_dump_info (REPORT_DETAILS,LOOP_LOC (loop_vinfo)))
+	    fprintf (vect_dump, "Detected induction.");
+	  STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_induction_def;
+          continue;
 	}
+
+      /* TODO: handle invariant phis  */
+
+      reduc_stmt = vect_is_simple_reduction (loop, phi);
+      if (reduc_stmt)
+        {
+          if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
+            fprintf (vect_dump, "Detected reduction.");
+          STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_reduction_def;
+          STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) =
+                                                        vect_reduction_def;
+        }
+      else
+        if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
+          fprintf (vect_dump, "Unknown def-use cycle pattern.");
+
     }
 
-  return true;
+  return;
 }
 
 
@@ -2049,39 +2123,32 @@ vect_analyze_data_refs (loop_vec_info loop_vinfo)
    Mark STMT as "relevant for vectorization" and add it to WORKLIST.  */
 
 static void
-vect_mark_relevant (VEC(tree,heap) **worklist, tree stmt)
+vect_mark_relevant (VEC(tree,heap) **worklist, tree stmt,
+		    bool relevant_p, bool live_p)
 {
-  stmt_vec_info stmt_info;
+  stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
+  bool save_relevant_p = STMT_VINFO_RELEVANT_P (stmt_info);
+  bool save_live_p = STMT_VINFO_LIVE_P (stmt_info);
 
   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
-    fprintf (vect_dump, "mark relevant.");
+    fprintf (vect_dump, "mark relevant %d, live %d.",relevant_p, live_p);
 
-  if (TREE_CODE (stmt) == PHI_NODE)
-    {
-      VEC_safe_push (tree, heap, *worklist, stmt);
-      return;
-    }
+  STMT_VINFO_LIVE_P (stmt_info) |= live_p;
 
-  stmt_info = vinfo_for_stmt (stmt);
+  if (TREE_CODE (stmt) == PHI_NODE)
+    /* Don't mark as relevant because it's not going to vectorized.  */
+    return;
 
-  if (!stmt_info)
-    {
-      if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
-	{
-	  fprintf (vect_dump, "mark relevant: no stmt info!!.");
-	  print_generic_expr (vect_dump, stmt, TDF_SLIM);
-	}
-      return;
-    }
+  STMT_VINFO_RELEVANT_P (stmt_info) |= relevant_p;
 
-  if (STMT_VINFO_RELEVANT_P (stmt_info))
+  if (STMT_VINFO_RELEVANT_P (stmt_info) == save_relevant_p
+      && STMT_VINFO_LIVE_P (stmt_info) == save_live_p)
     {
       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
-        fprintf (vect_dump, "already marked relevant.");
+        fprintf (vect_dump, "already marked relevant/live.");
       return;
     }
 
-  STMT_VINFO_RELEVANT_P (stmt_info) = 1;
   VEC_safe_push (tree, heap, *worklist, stmt);
 }
 
@@ -2099,7 +2166,8 @@ vect_mark_relevant (VEC(tree,heap) **worklist, tree stmt)
    CHECKME: what other side effects would the vectorizer allow?  */
 
 static bool
-vect_stmt_relevant_p (tree stmt, loop_vec_info loop_vinfo)
+vect_stmt_relevant_p (tree stmt, loop_vec_info loop_vinfo,
+		      bool *relevant_p, bool *live_p)
 {
   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
   ssa_op_iter op_iter;
@@ -2107,9 +2175,12 @@ vect_stmt_relevant_p (tree stmt, loop_vec_info loop_vinfo)
   use_operand_p use_p;
   def_operand_p def_p;
 
+  *relevant_p = false;
+  *live_p = false;
+
   /* cond stmt other than loop exit cond.  */
   if (is_ctrl_stmt (stmt) && (stmt != LOOP_VINFO_EXIT_COND (loop_vinfo)))
-    return true;
+    *relevant_p = true;
 
   /* changing memory.  */
   if (TREE_CODE (stmt) != PHI_NODE)
@@ -2117,7 +2188,7 @@ vect_stmt_relevant_p (tree stmt, loop_vec_info loop_vinfo)
       {
 	if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 	  fprintf (vect_dump, "vec_stmt_relevant_p: stmt has vdefs.");
-	return true;
+	*relevant_p = true;
       }
 
   /* uses outside the loop.  */
@@ -2130,12 +2201,18 @@ vect_stmt_relevant_p (tree stmt, loop_vec_info loop_vinfo)
 	    {
 	      if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 		fprintf (vect_dump, "vec_stmt_relevant_p: used out of loop.");
-	      return true;
+
+	      /* We expect all such uses to be in the loop exit phis
+		 (because of loop closed form)   */
+	      gcc_assert (TREE_CODE (USE_STMT (use_p)) == PHI_NODE);
+	      gcc_assert (bb == loop->single_exit->dest);
+
+              *live_p = true;
 	    }
 	}
     }
 
-  return false;
+  return (*live_p || *relevant_p);
 }
 
 
@@ -2164,16 +2241,23 @@ vect_mark_stmts_to_be_vectorized (loop_vec_info 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;
-  int j;
-  stmt_vec_info stmt_info;
+  stmt_vec_info stmt_vinfo;
   basic_block bb;
   tree phi;
+  bool relevant_p, live_p;
+  tree def, def_stmt;
+  enum vect_def_type dt;
 
   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
     fprintf (vect_dump, "=== vect_mark_stmts_to_be_vectorized ===");
 
+  worklist = VEC_alloc (tree, heap, 64);
+
+  /* 1. Init worklist.  */
+
   bb = loop->header;
   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
     {
@@ -2183,19 +2267,10 @@ vect_mark_stmts_to_be_vectorized (loop_vec_info loop_vinfo)
           print_generic_expr (vect_dump, phi, TDF_SLIM);
         }
 
-      if (vect_stmt_relevant_p (phi, loop_vinfo))
-	{
-	  if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
-				    LOOP_LOC (loop_vinfo)))
-	    fprintf (vect_dump, "unsupported reduction/induction.");
-          return false;
-	}
+      if (vect_stmt_relevant_p (phi, loop_vinfo, &relevant_p, &live_p))
+	vect_mark_relevant (&worklist, phi, relevant_p, live_p);
     }
 
-  worklist = VEC_alloc (tree, heap, 64);
-
-  /* 1. Init worklist.  */
-
   for (i = 0; i < nbbs; i++)
     {
       bb = bbs[i];
@@ -2209,11 +2284,8 @@ vect_mark_stmts_to_be_vectorized (loop_vec_info loop_vinfo)
 	      print_generic_expr (vect_dump, stmt, TDF_SLIM);
 	    } 
 
-	  stmt_info = vinfo_for_stmt (stmt);
-	  STMT_VINFO_RELEVANT_P (stmt_info) = 0;
-
-	  if (vect_stmt_relevant_p (stmt, loop_vinfo))
-	    vect_mark_relevant (&worklist, stmt);
+	  if (vect_stmt_relevant_p (stmt, loop_vinfo, &relevant_p, &live_p))
+            vect_mark_relevant (&worklist, stmt, relevant_p, live_p);
 	}
     }
 
@@ -2230,61 +2302,65 @@ vect_mark_stmts_to_be_vectorized (loop_vec_info loop_vinfo)
           print_generic_expr (vect_dump, stmt, TDF_SLIM);
 	}
 
-      /* Examine the USES in this statement. Mark all the statements which
-         feed this statement's uses as "relevant", unless the USE is used as
-         an array index.  */
+      /* Examine the USEs of STMT. For each ssa-name USE thta 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.
+       */
 
-      if (TREE_CODE (stmt) == PHI_NODE)
-	{
-	  /* follow the def-use chain inside the loop.  */
-	  for (j = 0; j < PHI_NUM_ARGS (stmt); j++)
-	    {
-	      tree arg = PHI_ARG_DEF (stmt, j);
-	      tree def_stmt = NULL_TREE;
-	      basic_block bb;
-	      if (!vect_is_simple_use (arg, loop_vinfo, &def_stmt))
-		{
-		  if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
-					    LOOP_LOC (loop_vinfo)))
-		    fprintf (vect_dump, "not vectorized: unsupported use in stmt.");
-		  VEC_free (tree, heap, worklist);
-		  return false;
-		}
-	      if (!def_stmt)
-		continue;
+      gcc_assert (TREE_CODE (stmt) != PHI_NODE);
 
-	      if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
-	        {
-	          fprintf (vect_dump, "worklist: def_stmt: ");
-		  print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
-		}
+      ann = stmt_ann (stmt);
+      stmt_vinfo = vinfo_for_stmt (stmt);
 
-	      bb = bb_for_stmt (def_stmt);
-	      if (flow_bb_inside_loop_p (loop, bb))
-	        vect_mark_relevant (&worklist, def_stmt);
-	    }
-	} 
+      relevant_p = STMT_VINFO_RELEVANT_P (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_P (DEF_STMT_info) <-- relevant_p
+
+         Exceptions:
+
+         - 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.
+
+         - if STMT has been identified as defining a reduction variable, then:
+             STMT_VINFO_LIVE_P (DEF_STMT_info) <-- false
+             STMT_VINFO_RELEVANT_P (DEF_STMT_info) <-- true
+           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.
+       */
+
+      if (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def)
+        {
+          gcc_assert (!relevant_p && live_p);
+          relevant_p = true;
+          live_p = false;
+        }
 
       FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
 	{
-
 	  /* 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))
 	    {
-              tree def_stmt = NULL_TREE;
-              basic_block bb;
-              if (!vect_is_simple_use (use, loop_vinfo, &def_stmt))
+	      if (!vect_is_simple_use (use, loop_vinfo, &def_stmt, &def, &dt))
                 {
                   if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
 					    LOOP_LOC (loop_vinfo)))
-                    fprintf (vect_dump, "not vectorized: unsupported use in stmt.");
+                    fprintf (vect_dump, 
+			     "not vectorized: unsupported use in stmt.");
 		  VEC_free (tree, heap, worklist);
                   return false;
                 }
 
-	      if (!def_stmt)
+	      if (!def_stmt || IS_EMPTY_STMT (def_stmt))
 		continue;
 
               if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
@@ -2294,8 +2370,16 @@ vect_mark_stmts_to_be_vectorized (loop_vec_info loop_vinfo)
                 }
 
 	      bb = bb_for_stmt (def_stmt);
-	      if (flow_bb_inside_loop_p (loop, bb))
-		vect_mark_relevant (&worklist, def_stmt);
+              if (!flow_bb_inside_loop_p (loop, bb))
+                continue;
+
+              if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+                {
+                  fprintf (vect_dump, "def_stmt: ");
+                  print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
+                }
+
+              vect_mark_relevant (&worklist, def_stmt, relevant_p, live_p);
 	    }
 	}
     }				/* while worklist */
@@ -2323,6 +2407,9 @@ vect_can_advance_ivs_p (loop_vec_info loop_vinfo)
 
   /* Analyze phi functions of the loop header.  */
 
+  if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+    fprintf (vect_dump, "=== vect_can_advance_ivs_p ===");
+
   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
     {
       tree access_fn = NULL;
@@ -2365,7 +2452,11 @@ vect_can_advance_ivs_p (loop_vec_info loop_vinfo)
       evolution_part = evolution_part_in_loop_num (access_fn, loop->num);
       
       if (evolution_part == NULL_TREE)
-	return false;
+        {
+	  if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+	    fprintf (vect_dump, "No evolution.");
+	  return false;
+        }
   
       /* FORNOW: We do not transform initial conditions of IVs 
 	 which evolution functions are a polynomial of degree >= 2.  */
@@ -2582,6 +2673,11 @@ vect_analyze_loop (struct loop *loop)
       return NULL;
     }
 
+  /* Classify all cross-iteration scalar data-flow cycles.
+     Cross-iteration cycles caused by virtual phis are analyzed separately.  */
+
+  vect_analyze_scalar_cycles (loop_vinfo);
+
   /* Data-flow analysis to detect stmts that do not need to be vectorized.  */
 
   ok = vect_mark_stmts_to_be_vectorized (loop_vinfo);
@@ -2593,18 +2689,6 @@ vect_analyze_loop (struct loop *loop)
       return NULL;
     }
 
-  /* Check that all cross-iteration scalar data-flow cycles are OK.
-     Cross-iteration cycles caused by virtual phis are analyzed separately.  */
-
-  ok = vect_analyze_scalar_cycles (loop_vinfo);
-  if (!ok)
-    {
-      if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
-	fprintf (vect_dump, "bad scalar cycle.");
-      destroy_loop_vec_info (loop_vinfo);
-      return NULL;
-    }
-
   ok = vect_determine_vectorization_factor (loop_vinfo);
   if (!ok)
     {
diff --git a/gcc/tree-vect-transform.c b/gcc/tree-vect-transform.c
index 97d3384..f5724db 100644
--- a/gcc/tree-vect-transform.c
+++ b/gcc/tree-vect-transform.c
@@ -145,7 +145,7 @@ vect_create_index_for_vector_ref (loop_vec_info loop_vinfo)
   create_iv (init, step, NULL_TREE, loop, &incr_bsi, insert_after,
 	&indx_before_incr, &indx_after_incr);
   incr = bsi_stmt (incr_bsi);
-  set_stmt_info (stmt_ann (incr), new_stmt_vec_info (incr, loop_vinfo));
+  set_stmt_info ((tree_ann_t)stmt_ann (incr), new_stmt_vec_info (incr, loop_vinfo));
 
   return indx_before_incr;
 }
@@ -512,12 +512,13 @@ vect_get_vec_def_for_operand (tree op, tree stmt)
   tree vectype = STMT_VINFO_VECTYPE (stmt_vinfo);
   int nunits = TYPE_VECTOR_SUBPARTS (vectype);
   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
-  struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
-  basic_block bb;
   tree vec_inv;
+  tree vec_cst;
   tree t = NULL_TREE;
   tree def;
   int i;
+  enum vect_def_type dt;
+  bool is_simple_use;
 
   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
     {
@@ -525,103 +526,80 @@ vect_get_vec_def_for_operand (tree op, tree stmt)
       print_generic_expr (vect_dump, op, TDF_SLIM);
     }
 
-  /** ===> Case 1: operand is a constant.  **/
-
-  if (TREE_CODE (op) == INTEGER_CST || TREE_CODE (op) == REAL_CST)
+  is_simple_use = vect_is_simple_use (op, loop_vinfo, &def_stmt, &def, &dt);
+  gcc_assert (is_simple_use);
+  if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
     {
-      /* Create 'vect_cst_ = {cst,cst,...,cst}'  */
-
-      tree vec_cst;
-
-      /* Build a tree with vector elements.  */
-      if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
-        fprintf (vect_dump, "Create vector_cst. nunits = %d", nunits);
-
-      for (i = nunits - 1; i >= 0; --i)
+      if (def)
         {
-          t = tree_cons (NULL_TREE, op, t);
+          fprintf (vect_dump, "def =  ");
+          print_generic_expr (vect_dump, def, TDF_SLIM);
+        }
+      if (def_stmt)
+        {
+          fprintf (vect_dump, "  def_stmt =  ");
+          print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
         }
-      vec_cst = build_vector (vectype, t);
-      return vect_init_vector (stmt, vec_cst);
-    }
-
-  gcc_assert (TREE_CODE (op) == SSA_NAME);
- 
-  /** ===> Case 2: operand is an SSA_NAME - find the stmt that defines it.  **/
-
-  def_stmt = SSA_NAME_DEF_STMT (op);
-  def_stmt_info = vinfo_for_stmt (def_stmt);
-
-  if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
-    {
-      fprintf (vect_dump, "vect_get_vec_def_for_operand: def_stmt: ");
-      print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
-    }
-
-
-  /** ==> Case 2.1: operand is defined inside the loop.  **/
-
-  if (def_stmt_info)
-    {
-      /* Get the def from the vectorized stmt.  */
-
-      vec_stmt = STMT_VINFO_VEC_STMT (def_stmt_info);
-      gcc_assert (vec_stmt);
-      vec_oprnd = TREE_OPERAND (vec_stmt, 0);
-      return vec_oprnd;
     }
 
+  /* FORNOW */
+  gcc_assert (dt != vect_reduction_def);
 
-  /** ==> Case 2.2: operand is defined by the loop-header phi-node - 
-                    it is a reduction/induction.  **/
-
-  bb = bb_for_stmt (def_stmt);
-  if (TREE_CODE (def_stmt) == PHI_NODE && flow_bb_inside_loop_p (loop, bb))
+  switch (dt)
     {
-      if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
-	fprintf (vect_dump, "reduction/induction - unsupported.");
-      internal_error ("no support for reduction/induction"); /* FORNOW */
-    }
-
+    /* Case 1: operand is a constant.  */
+    case vect_constant_def:
+      {
+        /* Create 'vect_cst_ = {cst,cst,...,cst}'  */
+        if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+          fprintf (vect_dump, "Create vector_cst. nunits = %d", nunits);
+
+        for (i = nunits - 1; i >= 0; --i)
+          {
+            t = tree_cons (NULL_TREE, op, t);
+          }
+        vec_cst = build_vector (vectype, t);
+        return vect_init_vector (stmt, vec_cst);
+      }
+
+    /* Case 2: operand is defined outside the loop - loop invariant.  */
+    case vect_invariant_def:
+      {
+        /* Create 'vec_inv = {inv,inv,..,inv}'  */
+        if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+          fprintf (vect_dump, "Create vector_inv.");
+
+        for (i = nunits - 1; i >= 0; --i)
+          {
+            t = tree_cons (NULL_TREE, def, t);
+          }
+
+        vec_inv = build_constructor (vectype, t);
+        return vect_init_vector (stmt, vec_inv);
+      }
+
+    /* Case 3: operand is defined inside the loop.  */
+    case vect_loop_def:
+      {
+        /* Get the def from the vectorized stmt.  */
+        def_stmt_info = vinfo_for_stmt (def_stmt);
+        vec_stmt = STMT_VINFO_VEC_STMT (def_stmt_info);
+        gcc_assert (vec_stmt);
+        vec_oprnd = TREE_OPERAND (vec_stmt, 0);
+        return vec_oprnd;
+      }
+
+    /* Case 4: operand is defined by loop-header phi - induction.  */
+    case vect_induction_def:
+      {
+        if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+          fprintf (vect_dump, "induction - unsupported.");
+        internal_error ("no support for induction"); /* FORNOW */
+      }
 
-  /** ==> Case 2.3: operand is defined outside the loop - 
-                    it is a loop invariant.  */
-
-  switch (TREE_CODE (def_stmt))
-    {
-    case PHI_NODE:
-      def = PHI_RESULT (def_stmt);
-      break;
-    case MODIFY_EXPR:
-      def = TREE_OPERAND (def_stmt, 0);
-      break;
-    case NOP_EXPR:
-      def = TREE_OPERAND (def_stmt, 0);
-      gcc_assert (IS_EMPTY_STMT (def_stmt));
-      def = op;
-      break;
     default:
-      if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
-	{
-          fprintf (vect_dump, "unsupported defining stmt: ");
-	  print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
-	}
-      internal_error ("unsupported defining stmt");
-    }
-
-  /* Build a tree with vector elements.
-     Create 'vec_inv = {inv,inv,..,inv}'  */
-
-  if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
-    fprintf (vect_dump, "Create vector_inv.");
-
-  for (i = nunits - 1; i >= 0; --i)
-    {
-      t = tree_cons (NULL_TREE, def, t);
+      gcc_unreachable ();
     }
-
-  vec_inv = build_constructor (vectype, t);
-  return vect_init_vector (stmt, vec_inv);
 }
 
 
@@ -671,8 +649,14 @@ vectorizable_assignment (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
   tree new_temp;
+  tree def, def_stmt;
+  enum vect_def_type dt;
 
   /* 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) != MODIFY_EXPR)
     return false;
@@ -682,7 +666,7 @@ vectorizable_assignment (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
     return false;
 
   op = TREE_OPERAND (stmt, 1);
-  if (!vect_is_simple_use (op, loop_vinfo, NULL))
+  if (!vect_is_simple_use (op, loop_vinfo, &def_stmt, &def, &dt))
     {
       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
         fprintf (vect_dump, "use not simple.");
@@ -742,6 +726,7 @@ vect_min_worthwhile_factor (enum tree_code code)
     }
 }
 
+
 /* Function vectorizable_operation.
 
    Check if STMT performs a binary or unary operation that can be vectorized. 
@@ -767,8 +752,23 @@ vectorizable_operation (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
   int op_type;
   tree op;
   optab optab;
+  tree def, def_stmt;
+  enum vect_def_type dt;
 
   /* 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, LOOP_LOC (loop_vinfo)))
+        fprintf (vect_dump, "value used after loop.");
+      return false;
+    }
+
   if (TREE_CODE (stmt) != MODIFY_EXPR)
     return false;
 
@@ -791,7 +791,7 @@ vectorizable_operation (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
   for (i = 0; i < op_type; i++)
     {
       op = TREE_OPERAND (operation, i);
-      if (!vect_is_simple_use (op, loop_vinfo, NULL))
+      if (!vect_is_simple_use (op, loop_vinfo, &def_stmt, &def, &dt))
 	{
 	  if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 	    fprintf (vect_dump, "use not simple.");
@@ -892,8 +892,9 @@ vectorizable_store (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
   enum machine_mode vec_mode;
   tree dummy;
   enum dr_alignment_support alignment_support_cheme;
-  tree def;
   ssa_op_iter iter;
+  tree def, def_stmt;
+  enum vect_def_type dt;
 
   /* Is vectorizable store? */
 
@@ -906,7 +907,7 @@ vectorizable_store (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
     return false;
 
   op = TREE_OPERAND (stmt, 1);
-  if (!vect_is_simple_use (op, loop_vinfo, NULL))
+  if (!vect_is_simple_use (op, loop_vinfo, &def_stmt, &def, &dt))
     {
       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
         fprintf (vect_dump, "use not simple.");
@@ -1001,6 +1002,18 @@ vectorizable_load (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
   enum dr_alignment_support alignment_support_cheme;
 
   /* 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, LOOP_LOC (loop_vinfo)))
+        fprintf (vect_dump, "value used after loop.");
+      return false;
+    }
 
   if (TREE_CODE (stmt) != MODIFY_EXPR)
     return false;
@@ -1180,6 +1193,64 @@ vectorizable_load (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
   return true;
 }
 
+
+/* Function vectorizable_live_operation.
+
+   STMT computes a value that is used outside the loop. Check if 
+   it can be supported.  */
+
+bool
+vectorizable_live_operation (tree stmt,
+                             block_stmt_iterator *bsi ATTRIBUTE_UNUSED,
+                             tree *vec_stmt ATTRIBUTE_UNUSED)
+{
+  tree operation;
+  stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
+  loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
+  int i;
+  enum tree_code code;
+  int op_type;
+  tree op;
+  tree def, def_stmt;
+  enum vect_def_type dt; 
+
+  if (!STMT_VINFO_LIVE_P (stmt_info))
+    return false;
+
+  if (TREE_CODE (stmt) != MODIFY_EXPR)
+    return false;
+
+  if (TREE_CODE (TREE_OPERAND (stmt, 0)) != SSA_NAME)
+    return false;
+
+  operation = TREE_OPERAND (stmt, 1);
+  code = TREE_CODE (operation);
+
+  op_type = TREE_CODE_LENGTH (code);
+
+  /* FORNOW: support only if all uses are invariant. This means
+     that the scalar operations can remain in place, unvectorized.
+     The original last scalar value that they compute will be used.  */
+
+  for (i = 0; i < op_type; i++)
+    {
+      op = TREE_OPERAND (operation, i);
+      if (!vect_is_simple_use (op, loop_vinfo, &def_stmt, &def, &dt))
+        {
+          if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+            fprintf (vect_dump, "use not simple.");
+          return false;
+        }
+
+      if (dt != vect_invariant_def && dt != vect_constant_def)
+        return false;
+    }
+
+  /* No transformation is required for the cases we currently support.  */
+  return true;
+}
+
+
 /* Function vect_is_simple_cond.
   
    Input:
@@ -1193,6 +1264,8 @@ static bool
 vect_is_simple_cond (tree cond, loop_vec_info loop_vinfo)
 {
   tree lhs, rhs;
+  tree def;
+  enum vect_def_type dt;
 
   if (!COMPARISON_CLASS_P (cond))
     return false;
@@ -1203,7 +1276,7 @@ vect_is_simple_cond (tree cond, loop_vec_info loop_vinfo)
   if (TREE_CODE (lhs) == SSA_NAME)
     {
       tree lhs_def_stmt = SSA_NAME_DEF_STMT (lhs);
-      if (!vect_is_simple_use (lhs, loop_vinfo, &lhs_def_stmt))
+      if (!vect_is_simple_use (lhs, loop_vinfo, &lhs_def_stmt, &def, &dt))
 	return false;
     }
   else if (TREE_CODE (lhs) != INTEGER_CST && TREE_CODE (lhs) != REAL_CST)
@@ -1212,7 +1285,7 @@ vect_is_simple_cond (tree cond, loop_vec_info loop_vinfo)
   if (TREE_CODE (rhs) == SSA_NAME)
     {
       tree rhs_def_stmt = SSA_NAME_DEF_STMT (rhs);
-      if (!vect_is_simple_use (rhs, loop_vinfo, &rhs_def_stmt))
+      if (!vect_is_simple_use (rhs, loop_vinfo, &rhs_def_stmt, &def, &dt))
 	return false;
     }
   else if (TREE_CODE (rhs) != INTEGER_CST  && TREE_CODE (rhs) != REAL_CST)
@@ -1244,10 +1317,22 @@ vectorizable_condition (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
   tree new_temp;
   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
   enum machine_mode vec_mode;
+  tree def;
+  enum vect_def_type dt;
 
   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, LOOP_LOC (loop_vinfo)))
+        fprintf (vect_dump, "value used after loop.");
+      return false;
+    }
+
   if (TREE_CODE (stmt) != MODIFY_EXPR)
     return false;
 
@@ -1266,7 +1351,8 @@ vectorizable_condition (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
   if (TREE_CODE (then_clause) == SSA_NAME)
     {
       tree then_def_stmt = SSA_NAME_DEF_STMT (then_clause);
-      if (!vect_is_simple_use (then_clause, loop_vinfo, &then_def_stmt))
+      if (!vect_is_simple_use (then_clause, loop_vinfo, 
+			       &then_def_stmt, &def, &dt))
 	return false;
     }
   else if (TREE_CODE (then_clause) != INTEGER_CST 
@@ -1276,7 +1362,8 @@ vectorizable_condition (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
   if (TREE_CODE (else_clause) == SSA_NAME)
     {
       tree else_def_stmt = SSA_NAME_DEF_STMT (else_clause);
-      if (!vect_is_simple_use (else_clause, loop_vinfo, &else_def_stmt))
+      if (!vect_is_simple_use (else_clause, loop_vinfo, 
+			       &else_def_stmt, &def, &dt))
 	return false;
     }
   else if (TREE_CODE (else_clause) != INTEGER_CST 
@@ -1332,43 +1419,52 @@ vect_transform_stmt (tree stmt, block_stmt_iterator *bsi)
   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
   bool done;
 
-  switch (STMT_VINFO_TYPE (stmt_info))
+  if (STMT_VINFO_RELEVANT_P (stmt_info))
     {
-    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);
-      is_store = true;
-      break;
+      switch (STMT_VINFO_TYPE (stmt_info))
+      {
+      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);
+	is_store = true;
+	break;
+
+      case condition_vec_info_type:
+	done = vectorizable_condition (stmt, bsi, &vec_stmt);
+	gcc_assert (done);
+	break;
+
+      default:
+	if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+	  fprintf (vect_dump, "stmt not supported.");
+	gcc_unreachable ();
+      }
+
+      STMT_VINFO_VEC_STMT (stmt_info) = vec_stmt;
+    }
 
-    case condition_vec_info_type:
-      done = vectorizable_condition (stmt, bsi, &vec_stmt);
+  if (STMT_VINFO_LIVE_P (stmt_info))
+    {
+      done = vectorizable_live_operation (stmt, bsi, &vec_stmt);
       gcc_assert (done);
-      break;
-
-    default:
-      if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
-        fprintf (vect_dump, "stmt not supported.");
-      gcc_unreachable ();
     }
 
-  STMT_VINFO_VEC_STMT (stmt_info) = vec_stmt;
-
-  return is_store;
+  return is_store; 
 }
 
 
@@ -1607,6 +1703,12 @@ vect_update_ivs_after_vectorizer (loop_vec_info loop_vinfo, tree niters,
       tree var, stmt, ni, ni_name;
       block_stmt_iterator last_bsi;
 
+      if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+        {
+          fprintf (vect_dump, "vect_update_ivs_after_vectorizer: phi: ");
+          print_generic_expr (vect_dump, phi, TDF_SLIM);
+        }
+
       /* Skip virtual phi's.  */
       if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
 	{
@@ -2021,7 +2123,7 @@ vect_transform_loop (loop_vec_info loop_vinfo,
 	      /* Free the attached stmt_vec_info and remove the stmt.  */
 	      stmt_ann_t ann = stmt_ann (stmt);
 	      free (stmt_info);
-	      set_stmt_info (ann, NULL);
+	      set_stmt_info ((tree_ann_t)ann, NULL);
 	      bsi_remove (&si);
 	      continue;
 	    }
diff --git a/gcc/tree-vectorizer.c b/gcc/tree-vectorizer.c
index 883f403..53f5358 100644
--- a/gcc/tree-vectorizer.c
+++ b/gcc/tree-vectorizer.c
@@ -1338,9 +1338,14 @@ new_stmt_vec_info (tree stmt, loop_vec_info loop_vinfo)
   STMT_VINFO_STMT (res) = stmt;
   STMT_VINFO_LOOP_VINFO (res) = loop_vinfo;
   STMT_VINFO_RELEVANT_P (res) = 0;
+  STMT_VINFO_LIVE_P (res) = 0;
   STMT_VINFO_VECTYPE (res) = NULL;
   STMT_VINFO_VEC_STMT (res) = NULL;
   STMT_VINFO_DATA_REF (res) = NULL;
+  if (TREE_CODE (stmt) == PHI_NODE)
+    STMT_VINFO_DEF_TYPE (res) = vect_unknown_def_type;
+  else
+    STMT_VINFO_DEF_TYPE (res) = vect_loop_def;
   STMT_VINFO_MEMTAG (res) = NULL;
   STMT_VINFO_PTR_INFO (res) = NULL;
   STMT_VINFO_SUBVARS (res) = NULL;
@@ -1375,13 +1380,21 @@ new_loop_vec_info (struct loop *loop)
   for (i = 0; i < loop->num_nodes; i++)
     {
       basic_block bb = bbs[i];
+      tree phi;
+
+      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+        {
+          tree_ann_t ann = get_tree_ann (phi);
+          set_stmt_info (ann, new_stmt_vec_info (phi, res));
+        }
+
       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
 	{
 	  tree stmt = bsi_stmt (si);
 	  stmt_ann_t ann;
 
 	  ann = stmt_ann (stmt);
-	  set_stmt_info (ann, new_stmt_vec_info (stmt, res));
+	  set_stmt_info ((tree_ann_t)ann, new_stmt_vec_info (stmt, res));
 	}
     }
 
@@ -1428,13 +1441,26 @@ destroy_loop_vec_info (loop_vec_info loop_vinfo)
   for (j = 0; j < nbbs; j++)
     {
       basic_block bb = bbs[j];
+      tree phi;
+      stmt_vec_info stmt_info;
+
+      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+        {
+          tree_ann_t ann = get_tree_ann (phi);
+
+          stmt_info = vinfo_for_stmt (phi);
+          free (stmt_info);
+          set_stmt_info (ann, NULL);
+        }
+
       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
 	{
 	  tree stmt = bsi_stmt (si);
 	  stmt_ann_t ann = stmt_ann (stmt);
+
 	  stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
 	  free (stmt_info);
-	  set_stmt_info (ann, NULL);
+	  set_stmt_info ((tree_ann_t)ann, NULL);
 	}
     }
 
@@ -1596,64 +1622,148 @@ vect_supportable_dr_alignment (struct data_reference *dr)
    in reduction/induction computations).  */
 
 bool
-vect_is_simple_use (tree operand, loop_vec_info loop_vinfo, tree *def)
+vect_is_simple_use (tree operand, loop_vec_info loop_vinfo, tree *def_stmt,
+		    tree *def, enum vect_def_type *dt)
 { 
-  tree def_stmt;
   basic_block bb;
+  stmt_vec_info stmt_vinfo;
   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
 
-  if (def)
-    *def = NULL_TREE;
-
+  *def_stmt = NULL_TREE;
+  *def = NULL_TREE;
+  
+  if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+    {
+      fprintf (vect_dump, "vect_is_simple_use: operand ");
+      print_generic_expr (vect_dump, operand, TDF_SLIM);
+    }
+    
   if (TREE_CODE (operand) == INTEGER_CST || TREE_CODE (operand) == REAL_CST)
-    return true;
-
+    {
+      *dt = vect_constant_def;
+      return true;
+    }
+    
   if (TREE_CODE (operand) != SSA_NAME)
-    return false;
-
-  def_stmt = SSA_NAME_DEF_STMT (operand);
-  if (def_stmt == NULL_TREE )
+    {
+      if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+        fprintf (vect_dump, "not ssa-name.");
+      return false;
+    }
+    
+  *def_stmt = SSA_NAME_DEF_STMT (operand);
+  if (*def_stmt == NULL_TREE )
     {
       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
         fprintf (vect_dump, "no def_stmt.");
       return false;
     }
 
+  if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+    {
+      fprintf (vect_dump, "def_stmt: ");
+      print_generic_expr (vect_dump, *def_stmt, TDF_SLIM);
+    }
+
   /* empty stmt is expected only in case of a function argument.
      (Otherwise - we expect a phi_node or a modify_expr).  */
-  if (IS_EMPTY_STMT (def_stmt))
+  if (IS_EMPTY_STMT (*def_stmt))
     {
-      tree arg = TREE_OPERAND (def_stmt, 0);
+      tree arg = TREE_OPERAND (*def_stmt, 0);
       if (TREE_CODE (arg) == INTEGER_CST || TREE_CODE (arg) == REAL_CST)
-	return true;
+        {
+          *def = operand;
+          *dt = vect_invariant_def;
+          return true;
+        }
+
       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
-	{
-	  fprintf (vect_dump, "Unexpected empty stmt: ");
-	  print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
-	}
-      return false;  
+        fprintf (vect_dump, "Unexpected empty stmt.");
+      return false;
     }
 
-  /* phi_node inside the loop indicates an induction/reduction pattern.
-     This is not supported yet.  */
-  bb = bb_for_stmt (def_stmt);
-  if (TREE_CODE (def_stmt) == PHI_NODE && flow_bb_inside_loop_p (loop, bb))
+  bb = bb_for_stmt (*def_stmt);
+  if (!flow_bb_inside_loop_p (loop, bb))
+    *dt = vect_invariant_def;
+  else
+    {
+      stmt_vinfo = vinfo_for_stmt (*def_stmt);
+      *dt = STMT_VINFO_DEF_TYPE (stmt_vinfo);
+    }
+
+  if (*dt == vect_unknown_def_type)
     {
       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
-	fprintf (vect_dump, "reduction/induction - unsupported.");
-      return false; /* FORNOW: not supported yet.  */
+        fprintf (vect_dump, "Unsupported pattern.");
+      return false;
     }
 
-  /* Expecting a modify_expr or a phi_node.  */
-  if (TREE_CODE (def_stmt) == MODIFY_EXPR
-      || TREE_CODE (def_stmt) == PHI_NODE)
+  /* 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 (def)
-        *def = def_stmt; 	
-      return true;
+      if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+        fprintf (vect_dump, "reduction used in loop.");
+      return false;
+    }
+
+  if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+    fprintf (vect_dump, "type of def: %d.",*dt);
+
+  switch (TREE_CODE (*def_stmt))
+    {
+    case PHI_NODE:
+      *def = PHI_RESULT (*def_stmt);
+      gcc_assert (*dt == vect_induction_def || *dt == vect_reduction_def
+                  || *dt == vect_invariant_def);
+      break;
+
+    case MODIFY_EXPR:
+      *def = TREE_OPERAND (*def_stmt, 0);
+      gcc_assert (*dt == vect_loop_def || *dt == vect_invariant_def);
+      break;
+
+    default:
+      if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+        fprintf (vect_dump, "unsupported defining stmt: ");
+      return false;
     }
 
-  return false;
+  if (*dt == vect_induction_def)
+    {
+      if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+        fprintf (vect_dump, "induction not supported.");
+      return false;
+    }
+
+  return true;
+}
+
+
+/* Function vect_is_simple_reduction
+
+   TODO:
+   Detect a cross-iteration def-use cucle that represents a simple
+   reduction computation. We look for the followng pattern:
+
+   loop_header:
+     a1 = phi < a0, a2 >
+     a3 = ...
+     a2 = operation (a3, a1)
+  
+   such that:
+   1. operation is...
+   2. no uses for a2 in the loop (elsewhere)  */
+
+tree
+vect_is_simple_reduction (struct loop *loop ATTRIBUTE_UNUSED, 
+			  tree phi ATTRIBUTE_UNUSED)
+{
+  /* FORNOW */
+  if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
+    fprintf (vect_dump, "reduction: unknown pattern.");
+
+  return NULL_TREE;
 }
 
 
diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h
index 30a7830..739da71 100644
--- a/gcc/tree-vectorizer.h
+++ b/gcc/tree-vectorizer.h
@@ -56,6 +56,16 @@ enum dr_alignment_support {
   dr_aligned
 };
 
+/* Define type of def-use cross-iteraiton cycle.  */
+enum vect_def_type {
+  vect_constant_def,
+  vect_invariant_def,
+  vect_loop_def,
+  vect_induction_def,
+  vect_reduction_def,
+  vect_unknown_def_type
+};
+
 /* Define verbosity levels.  */
 enum verbosity_levels {
   REPORT_NONE,
@@ -163,6 +173,10 @@ typedef struct _stmt_vec_info {
      indicates whether the stmt needs to be vectorized.  */
   bool relevant;
 
+  /* Indicates whether this stmts is part of a computation whose result is
+     used outside the loop.  */
+  bool live;
+
   /* The vector type to be used.  */
   tree vectype;
 
@@ -215,6 +229,10 @@ typedef struct _stmt_vec_info {
   /* Alignment information. The offset of the data-reference from its base 
      in bytes.  */
   tree misalignment;
+
+  /* Classify the def of this stmt.  */
+  enum vect_def_type def_type;
+
 } *stmt_vec_info;
 
 /* Access Functions.  */
@@ -222,6 +240,7 @@ typedef struct _stmt_vec_info {
 #define STMT_VINFO_STMT(S)                (S)->stmt
 #define STMT_VINFO_LOOP_VINFO(S)          (S)->loop_vinfo
 #define STMT_VINFO_RELEVANT_P(S)          (S)->relevant
+#define STMT_VINFO_LIVE_P(S)              (S)->live
 #define STMT_VINFO_VECTYPE(S)             (S)->vectype
 #define STMT_VINFO_VEC_STMT(S)            (S)->vectorized_stmt
 #define STMT_VINFO_DATA_REF(S)            (S)->data_ref_info
@@ -233,22 +252,23 @@ typedef struct _stmt_vec_info {
 #define STMT_VINFO_VECT_STEP(S)           (S)->step
 #define STMT_VINFO_VECT_BASE_ALIGNED_P(S) (S)->base_aligned_p
 #define STMT_VINFO_VECT_MISALIGNMENT(S)   (S)->misalignment
+#define STMT_VINFO_DEF_TYPE(S)            (S)->def_type
 
-static inline void set_stmt_info (stmt_ann_t ann, stmt_vec_info stmt_info);
+static inline void set_stmt_info (tree_ann_t ann, stmt_vec_info stmt_info);
 static inline stmt_vec_info vinfo_for_stmt (tree stmt);
 
 static inline void
-set_stmt_info (stmt_ann_t ann, stmt_vec_info stmt_info)
+set_stmt_info (tree_ann_t ann, stmt_vec_info stmt_info)
 {
   if (ann)
-    ann->aux = (char *) stmt_info;
+    ann->common.aux = (char *) stmt_info;
 }
 
 static inline stmt_vec_info
 vinfo_for_stmt (tree stmt)
 {
-  stmt_ann_t ann = stmt_ann (stmt);
-  return ann ? (stmt_vec_info) ann->aux : NULL;
+  tree_ann_t ann = tree_ann (stmt);
+  return ann ? (stmt_vec_info) ann->common.aux : NULL;
 }
 
 /*-----------------------------------------------------------------*/
@@ -309,8 +329,10 @@ extern void slpeel_verify_cfg_after_peeling (struct loop *, struct loop *);
 /** In tree-vectorizer.c **/
 extern tree vect_strip_conversion (tree);
 extern tree get_vectype_for_scalar_type (tree);
-extern bool vect_is_simple_use (tree , loop_vec_info, tree *);
+extern bool vect_is_simple_use (tree, loop_vec_info, tree *, tree *,
+				enum vect_def_type *);
 extern bool vect_is_simple_iv_evolution (unsigned, tree, tree *, tree *);
+extern tree vect_is_simple_reduction (struct loop *, tree);
 extern bool vect_can_force_dr_alignment_p (tree, unsigned int);
 extern enum dr_alignment_support vect_supportable_dr_alignment
   (struct data_reference *);
@@ -331,6 +353,7 @@ extern bool vectorizable_store (tree, block_stmt_iterator *, tree *);
 extern bool vectorizable_operation (tree, block_stmt_iterator *, tree *);
 extern bool vectorizable_assignment (tree, block_stmt_iterator *, tree *);
 extern bool vectorizable_condition (tree, block_stmt_iterator *, tree *);
+extern bool vectorizable_live_operation (tree, block_stmt_iterator *, tree *);
 /* Driver for transformation stage.  */
 extern void vect_transform_loop (loop_vec_info, struct loops *);