tree-data-ref.c (struct rdg_vertex_info): Remove.

2012-06-04  Richard Guenther  <rguenther@suse.de>

	* tree-data-ref.c (struct rdg_vertex_info): Remove.
	(rdg_vertex_for_stmt): Simplify using gimple_uid.
	(create_rdg_vertices): Pass loop argument, remove stmt to RDG index
	hashtable.   Record stmt data-references.
	(hash_stmt_vertex_info): Remove.
	(eq_stmt_vertex_info): Likewise.
	(hash_stmt_vertex_del): Likewise.
	(build_empty_rdg): Simplify.
	(build_rdg): Adjust.
	(free_rdg): Likewise.
	(ref_base_address): Remove.
	(have_similar_memory_accesses): Likewise.
	* tree-data-ref.h (create_rdg_vertices): Remove.
	(struct rdg_vertex): Add datarefs member.
	(RDGV_DATAREFS): New define.
	(RDG_DATAREFS): Likewise.
	(have_similar_memory_accesses): Remove.
	(rdg_has_similar_memory_accesses): Likewise.
	* tree-loop-distribution.c (ref_base_address): Re-implement here.
	(similar_memory_accesses): Re-implement using existing data-references.
	(tree_loop_distribution): Initialize stmt uids for the stmt to
	RDG index mapping.
	* tree-vect-loop.c (vect_create_epilog_for_reduction): Only
	access stmt vinfo for stmts in loop.

From-SVN: r188180

5 files changed, 110 insertions, 165 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 9ab51e8..7722dd5 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,30 @@
+2012-06-04  Richard Guenther  <rguenther@suse.de>
+
+	* tree-data-ref.c (struct rdg_vertex_info): Remove.
+	(rdg_vertex_for_stmt): Simplify using gimple_uid.
+	(create_rdg_vertices): Pass loop argument, remove stmt to RDG index
+	hashtable.   Record stmt data-references.
+	(hash_stmt_vertex_info): Remove.
+	(eq_stmt_vertex_info): Likewise.
+	(hash_stmt_vertex_del): Likewise.
+	(build_empty_rdg): Simplify.
+	(build_rdg): Adjust.
+	(free_rdg): Likewise.
+	(ref_base_address): Remove.
+	(have_similar_memory_accesses): Likewise.
+	* tree-data-ref.h (create_rdg_vertices): Remove.
+	(struct rdg_vertex): Add datarefs member.
+	(RDGV_DATAREFS): New define.
+	(RDG_DATAREFS): Likewise.
+	(have_similar_memory_accesses): Remove.
+	(rdg_has_similar_memory_accesses): Likewise.
+	* tree-loop-distribution.c (ref_base_address): Re-implement here.
+	(similar_memory_accesses): Re-implement using existing data-references.
+	(tree_loop_distribution): Initialize stmt uids for the stmt to
+	RDG index mapping.
+	* tree-vect-loop.c (vect_create_epilog_for_reduction): Only
+	access stmt vinfo for stmts in loop.
+
 2012-06-04  Andreas Schwab  <schwab@linux-m68k.org>
 
 	PR target/53461
diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index bbfc321..bf1d859 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -4924,29 +4924,14 @@ dot_rdg (struct graph *rdg)
 #endif
 }
 
-/* This structure is used for recording the mapping statement index in
-   the RDG.  */
-
-struct GTY(()) rdg_vertex_info
-{
-  gimple stmt;
-  int index;
-};
-
 /* Returns the index of STMT in RDG.  */
 
 int
-rdg_vertex_for_stmt (struct graph *rdg, gimple stmt)
+rdg_vertex_for_stmt (struct graph *rdg ATTRIBUTE_UNUSED, gimple stmt)
 {
-  struct rdg_vertex_info rvi, *slot;
-
-  rvi.stmt = stmt;
-  slot = (struct rdg_vertex_info *) htab_find (rdg->indices, &rvi);
-
-  if (!slot)
-    return -1;
-
-  return slot->index;
+  int index = gimple_uid (stmt);
+  gcc_checking_assert (index == -1 || RDG_STMT (rdg, index) == stmt);
+  return index;
 }
 
 /* Creates an edge in RDG for each distance vector from DDR.  The
@@ -5041,8 +5026,8 @@ create_rdg_edges (struct graph *rdg, VEC (ddr_p, heap) *ddrs)
 
 /* Build the vertices of the reduced dependence graph RDG.  */
 
-void
-create_rdg_vertices (struct graph *rdg, VEC (gimple, heap) *stmts)
+static void
+create_rdg_vertices (struct graph *rdg, VEC (gimple, heap) *stmts, loop_p loop)
 {
   int i, j;
   gimple stmt;
@@ -5052,33 +5037,31 @@ create_rdg_vertices (struct graph *rdg, VEC (gimple, heap) *stmts)
       VEC (data_ref_loc, heap) *references;
       data_ref_loc *ref;
       struct vertex *v = &(rdg->vertices[i]);
-      struct rdg_vertex_info *rvi = XNEW (struct rdg_vertex_info);
-      struct rdg_vertex_info **slot;
 
-      rvi->stmt = stmt;
-      rvi->index = i;
-      slot = (struct rdg_vertex_info **) htab_find_slot (rdg->indices, rvi, INSERT);
-
-      if (!*slot)
-	*slot = rvi;
-      else
-	free (rvi);
+      /* Record statement to vertex mapping.  */
+      gimple_set_uid (stmt, i);
 
       v->data = XNEW (struct rdg_vertex);
-      RDG_STMT (rdg, i) = stmt;
-
-      RDG_MEM_WRITE_STMT (rdg, i) = false;
-      RDG_MEM_READS_STMT (rdg, i) = false;
+      RDGV_STMT (v) = stmt;
+      RDGV_DATAREFS (v) = NULL;
+      RDGV_HAS_MEM_WRITE (v) = false;
+      RDGV_HAS_MEM_READS (v) = false;
       if (gimple_code (stmt) == GIMPLE_PHI)
 	continue;
 
       get_references_in_stmt (stmt, &references);
       FOR_EACH_VEC_ELT (data_ref_loc, references, j, ref)
-	if (!ref->is_read)
-	  RDG_MEM_WRITE_STMT (rdg, i) = true;
-	else
-	  RDG_MEM_READS_STMT (rdg, i) = true;
-
+	{
+	  data_reference_p dr;
+	  if (!ref->is_read)
+	    RDGV_HAS_MEM_WRITE (v) = true;
+	  else
+	    RDGV_HAS_MEM_READS (v) = true;
+	  dr = create_data_ref (loop, loop_containing_stmt (stmt),
+				*ref->pos, stmt, ref->is_read);
+	  if (dr)
+	    VEC_safe_push (data_reference_p, heap, RDGV_DATAREFS (v), dr);
+	}
       VEC_free (data_ref_loc, heap, references);
     }
 }
@@ -5130,37 +5113,6 @@ known_dependences_p (VEC (ddr_p, heap) *dependence_relations)
   return true;
 }
 
-/* Computes a hash function for element ELT.  */
-
-static hashval_t
-hash_stmt_vertex_info (const void *elt)
-{
-  const struct rdg_vertex_info *const rvi =
-    (const struct rdg_vertex_info *) elt;
-  gimple stmt = rvi->stmt;
-
-  return htab_hash_pointer (stmt);
-}
-
-/* Compares database elements E1 and E2.  */
-
-static int
-eq_stmt_vertex_info (const void *e1, const void *e2)
-{
-  const struct rdg_vertex_info *elt1 = (const struct rdg_vertex_info *) e1;
-  const struct rdg_vertex_info *elt2 = (const struct rdg_vertex_info *) e2;
-
-  return elt1->stmt == elt2->stmt;
-}
-
-/* Free the element E.  */
-
-static void
-hash_stmt_vertex_del (void *e)
-{
-  free (e);
-}
-
 /* Build the Reduced Dependence Graph (RDG) with one vertex per
    statement of the loop nest, and one edge per data dependence or
    scalar dependence.  */
@@ -5168,11 +5120,7 @@ hash_stmt_vertex_del (void *e)
 struct graph *
 build_empty_rdg (int n_stmts)
 {
-  int nb_data_refs = 10;
   struct graph *rdg = new_graph (n_stmts);
-
-  rdg->indices = htab_create (nb_data_refs, hash_stmt_vertex_info,
-			      eq_stmt_vertex_info, hash_stmt_vertex_del);
   return rdg;
 }
 
@@ -5195,7 +5143,7 @@ build_rdg (struct loop *loop,
       VEC (gimple, heap) *stmts = VEC_alloc (gimple, heap, 10);
       stmts_from_loop (loop, &stmts);
       rdg = build_empty_rdg (VEC_length (gimple, stmts));
-      create_rdg_vertices (rdg, stmts);
+      create_rdg_vertices (rdg, stmts, loop);
       create_rdg_edges (rdg, *dependence_relations);
       VEC_free (gimple, heap, stmts);
     }
@@ -5218,10 +5166,11 @@ free_rdg (struct graph *rdg)
       for (e = v->succ; e; e = e->succ_next)
 	free (e->data);
 
+      gimple_set_uid (RDGV_STMT (v), -1);
+      free_data_refs (RDGV_DATAREFS (v));
       free (v->data);
     }
 
-  htab_delete (rdg->indices);
   free_graph (rdg);
 }
 
@@ -5307,40 +5256,6 @@ stores_zero_from_loop (struct loop *loop, VEC (gimple, heap) **stmts)
   free (bbs);
 }
 
-/* For a data reference REF, return the declaration of its base
-   address or NULL_TREE if the base is not determined.  */
-
-static inline tree
-ref_base_address (gimple stmt, data_ref_loc *ref)
-{
-  tree base = NULL_TREE;
-  tree base_address;
-  struct data_reference *dr = XCNEW (struct data_reference);
-
-  DR_STMT (dr) = stmt;
-  DR_REF (dr) = *ref->pos;
-  dr_analyze_innermost (dr, loop_containing_stmt (stmt));
-  base_address = DR_BASE_ADDRESS (dr);
-
-  if (!base_address)
-    goto end;
-
-  switch (TREE_CODE (base_address))
-    {
-    case ADDR_EXPR:
-      base = TREE_OPERAND (base_address, 0);
-      break;
-
-    default:
-      base = base_address;
-      break;
-    }
-
- end:
-  free_data_ref (dr);
-  return base;
-}
-
 /* Determines whether the statement from vertex V of the RDG has a
    definition used outside the loop that contains this statement.  */
 
@@ -5368,38 +5283,3 @@ rdg_defs_used_in_other_loops_p (struct graph *rdg, int v)
 
   return false;
 }
-
-/* Determines whether statements S1 and S2 access to similar memory
-   locations.  Two memory accesses are considered similar when they
-   have the same base address declaration, i.e. when their
-   ref_base_address is the same.  */
-
-bool
-have_similar_memory_accesses (gimple s1, gimple s2)
-{
-  bool res = false;
-  unsigned i, j;
-  VEC (data_ref_loc, heap) *refs1, *refs2;
-  data_ref_loc *ref1, *ref2;
-
-  get_references_in_stmt (s1, &refs1);
-  get_references_in_stmt (s2, &refs2);
-
-  FOR_EACH_VEC_ELT (data_ref_loc, refs1, i, ref1)
-    {
-      tree base1 = ref_base_address (s1, ref1);
-
-      if (base1)
-	FOR_EACH_VEC_ELT (data_ref_loc, refs2, j, ref2)
-	  if (base1 == ref_base_address (s2, ref2))
-	    {
-	      res = true;
-	      goto end;
-	    }
-    }
-
- end:
-  VEC_free (data_ref_loc, heap, refs1);
-  VEC_free (data_ref_loc, heap, refs2);
-  return res;
-}
diff --git a/gcc/tree-data-ref.h b/gcc/tree-data-ref.h
index da4802e..2edddc03 100644
--- a/gcc/tree-data-ref.h
+++ b/gcc/tree-data-ref.h
@@ -403,7 +403,6 @@ extern bool compute_all_dependences (VEC (data_reference_p, heap) *,
 extern tree find_data_references_in_bb (struct loop *, basic_block,
                                         VEC (data_reference_p, heap) **);
 
-extern void create_rdg_vertices (struct graph *, VEC (gimple, heap) *);
 extern bool dr_may_alias_p (const struct data_reference *,
 			    const struct data_reference *, bool);
 extern bool dr_equal_offsets_p (struct data_reference *,
@@ -525,6 +524,9 @@ typedef struct rdg_vertex
   /* The statement represented by this vertex.  */
   gimple stmt;
 
+  /* Vector of data-references in this statement.  */
+  VEC(data_reference_p, heap) *datarefs;
+
   /* True when the statement contains a write to memory.  */
   bool has_mem_write;
 
@@ -533,9 +535,11 @@ typedef struct rdg_vertex
 } *rdg_vertex_p;
 
 #define RDGV_STMT(V)     ((struct rdg_vertex *) ((V)->data))->stmt
+#define RDGV_DATAREFS(V) ((struct rdg_vertex *) ((V)->data))->datarefs
 #define RDGV_HAS_MEM_WRITE(V) ((struct rdg_vertex *) ((V)->data))->has_mem_write
 #define RDGV_HAS_MEM_READS(V) ((struct rdg_vertex *) ((V)->data))->has_mem_reads
 #define RDG_STMT(RDG, I) RDGV_STMT (&(RDG->vertices[I]))
+#define RDG_DATAREFS(RDG, I) RDGV_DATAREFS (&(RDG->vertices[I]))
 #define RDG_MEM_WRITE_STMT(RDG, I) RDGV_HAS_MEM_WRITE (&(RDG->vertices[I]))
 #define RDG_MEM_READS_STMT(RDG, I) RDGV_HAS_MEM_READS (&(RDG->vertices[I]))
 
@@ -608,7 +612,6 @@ index_in_loop_nest (int var, VEC (loop_p, heap) *loop_nest)
 void stores_from_loop (struct loop *, VEC (gimple, heap) **);
 void stores_zero_from_loop (struct loop *, VEC (gimple, heap) **);
 bool rdg_defs_used_in_other_loops_p (struct graph *, int);
-bool have_similar_memory_accesses (gimple, gimple);
 bool stmt_with_adjacent_zero_store_dr_p (gimple);
 
 /* Returns true when STRIDE is equal in absolute value to the size of
@@ -623,16 +626,6 @@ stride_of_unit_type_p (tree stride, tree type)
 				 TYPE_SIZE_UNIT (type)));
 }
 
-/* Determines whether RDG vertices V1 and V2 access to similar memory
-   locations, in which case they have to be in the same partition.  */
-
-static inline bool
-rdg_has_similar_memory_accesses (struct graph *rdg, int v1, int v2)
-{
-  return have_similar_memory_accesses (RDG_STMT (rdg, v1),
-				       RDG_STMT (rdg, v2));
-}
-
 /* In tree-data-ref.c  */
 void split_constant_offset (tree , tree *, tree *);
 
diff --git a/gcc/tree-loop-distribution.c b/gcc/tree-loop-distribution.c
index 1fc1d8d..f4476cb 100644
--- a/gcc/tree-loop-distribution.c
+++ b/gcc/tree-loop-distribution.c
@@ -878,6 +878,20 @@ classify_partition (loop_p loop, struct graph *rdg, partition_t partition)
     partition->kind = PKIND_MEMSET;
 }
 
+/* For a data reference REF, return the declaration of its base
+   address or NULL_TREE if the base is not determined.  */
+
+static tree
+ref_base_address (data_reference_p dr)
+{
+  tree base_address = DR_BASE_ADDRESS (dr);
+  if (base_address
+      && TREE_CODE (base_address) == ADDR_EXPR)
+    return TREE_OPERAND (base_address, 0);
+
+  return base_address;
+}
+
 /* Returns true when PARTITION1 and PARTITION2 have similar memory
    accesses in RDG.  */
 
@@ -885,17 +899,36 @@ static bool
 similar_memory_accesses (struct graph *rdg, partition_t partition1,
 			 partition_t partition2)
 {
-  unsigned i, j;
+  unsigned i, j, k, l;
   bitmap_iterator bi, bj;
+  data_reference_p ref1, ref2;
+
+  /* First check whether in the intersection of the two partitions are
+     any loads or stores.  Common loads are the situation that happens
+     most often.  */
+  EXECUTE_IF_AND_IN_BITMAP (partition1->stmts, partition2->stmts, 0, i, bi)
+    if (RDG_MEM_WRITE_STMT (rdg, i)
+	|| RDG_MEM_READS_STMT (rdg, i))
+      return true;
 
+  /* Then check all data-references against each other.  */
   EXECUTE_IF_SET_IN_BITMAP (partition1->stmts, 0, i, bi)
     if (RDG_MEM_WRITE_STMT (rdg, i)
 	|| RDG_MEM_READS_STMT (rdg, i))
       EXECUTE_IF_SET_IN_BITMAP (partition2->stmts, 0, j, bj)
 	if (RDG_MEM_WRITE_STMT (rdg, j)
 	    || RDG_MEM_READS_STMT (rdg, j))
-	  if (rdg_has_similar_memory_accesses (rdg, i, j))
-	    return true;
+	  {
+	    FOR_EACH_VEC_ELT (data_reference_p, RDG_DATAREFS (rdg, i), k, ref1)
+	      {
+		tree base1 = ref_base_address (ref1);
+		if (base1)
+		  FOR_EACH_VEC_ELT (data_reference_p,
+				    RDG_DATAREFS (rdg, j), l, ref2)
+		    if (base1 == ref_base_address (ref2))
+		      return true;
+	      }
+	  }
 
   return false;
 }
@@ -1252,6 +1285,16 @@ tree_loop_distribution (void)
   struct loop *loop;
   loop_iterator li;
   bool changed = false;
+  basic_block bb;
+
+  FOR_ALL_BB (bb)
+    {
+      gimple_stmt_iterator gsi;
+      for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+	gimple_set_uid (gsi_stmt (gsi), -1);
+      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+	gimple_set_uid (gsi_stmt (gsi), -1);
+    }
 
   /* We can at the moment only distribute non-nested loops, thus restrict
      walking to innermost loops.  */
diff --git a/gcc/tree-vect-loop.c b/gcc/tree-vect-loop.c
index ea48b4b..93a785a 100644
--- a/gcc/tree-vect-loop.c
+++ b/gcc/tree-vect-loop.c
@@ -4211,7 +4211,7 @@ vect_finalize_reduction:
               orig_name = PHI_RESULT (exit_phi);
               FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, orig_name)
                 {
-                  stmt_vec_info use_stmt_vinfo = vinfo_for_stmt (use_stmt);
+                  stmt_vec_info use_stmt_vinfo;
                   stmt_vec_info new_phi_vinfo;
                   tree vect_phi_init, preheader_arg, vect_phi_res, init_def;
                   basic_block bb = gimple_bb (use_stmt);
@@ -4221,11 +4221,13 @@ vect_finalize_reduction:
                      node.  */
                   if (gimple_code (use_stmt) != GIMPLE_PHI
                       || gimple_phi_num_args (use_stmt) != 2
-                      || !use_stmt_vinfo
-                      || STMT_VINFO_DEF_TYPE (use_stmt_vinfo)
-                          != vect_double_reduction_def
                       || bb->loop_father != outer_loop)
                     continue;
+                  use_stmt_vinfo = vinfo_for_stmt (use_stmt);
+                  if (!use_stmt_vinfo
+                      || STMT_VINFO_DEF_TYPE (use_stmt_vinfo)
+                          != vect_double_reduction_def)
+		    continue;
 
                   /* Create vector phi node for double reduction:
                      vs1 = phi <vs0, vs2>