This removes a pointless stmt -> RDG index hash (simply use gimple_uid)
and arranges to compute and analyze data-references once instead of
O(stmts^4) when looking for common data accesses (ugh!).
Bootstrapped and tested on x86_64-unknown-linux-gnu, applied.
Richard.
2012-06-04 Richard Guenther <rguent...@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.
Index: trunk/gcc/tree-data-ref.c
===================================================================
*** trunk.orig/gcc/tree-data-ref.c 2012-06-04 15:09:18.000000000 +0200
--- trunk/gcc/tree-data-ref.c 2012-06-04 15:09:40.605652827 +0200
*************** dot_rdg (struct graph *rdg)
*** 4924,4952 ****
#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)
{
! 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;
}
/* Creates an edge in RDG for each distance vector from DDR. The
--- 4924,4937 ----
#endif
}
/* Returns the index of STMT in RDG. */
int
! rdg_vertex_for_stmt (struct graph *rdg ATTRIBUTE_UNUSED, gimple stmt)
{
! 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
*************** create_rdg_edges (struct graph *rdg, VEC
*** 5041,5048 ****
/* Build the vertices of the reduced dependence graph RDG. */
! void
! create_rdg_vertices (struct graph *rdg, VEC (gimple, heap) *stmts)
{
int i, j;
gimple stmt;
--- 5026,5033 ----
/* Build the vertices of the reduced dependence graph RDG. */
! static void
! create_rdg_vertices (struct graph *rdg, VEC (gimple, heap) *stmts, loop_p
loop)
{
int i, j;
gimple stmt;
*************** create_rdg_vertices (struct graph *rdg,
*** 5052,5084 ****
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);
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;
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;
!
VEC_free (data_ref_loc, heap, references);
}
}
--- 5037,5067 ----
VEC (data_ref_loc, heap) *references;
data_ref_loc *ref;
struct vertex *v = &(rdg->vertices[i]);
! /* Record statement to vertex mapping. */
! gimple_set_uid (stmt, i);
v->data = XNEW (struct rdg_vertex);
! 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)
! {
! 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);
}
}
*************** known_dependences_p (VEC (ddr_p, heap) *
*** 5130,5166 ****
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. */
--- 5113,5118 ----
*************** hash_stmt_vertex_del (void *e)
*** 5168,5178 ****
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;
}
--- 5120,5126 ----
*************** build_rdg (struct loop *loop,
*** 5195,5201 ****
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_edges (rdg, *dependence_relations);
VEC_free (gimple, heap, stmts);
}
--- 5143,5149 ----
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, loop);
create_rdg_edges (rdg, *dependence_relations);
VEC_free (gimple, heap, stmts);
}
*************** free_rdg (struct graph *rdg)
*** 5218,5227 ****
for (e = v->succ; e; e = e->succ_next)
free (e->data);
free (v->data);
}
- htab_delete (rdg->indices);
free_graph (rdg);
}
--- 5166,5176 ----
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);
}
free_graph (rdg);
}
*************** stores_zero_from_loop (struct loop *loop
*** 5307,5346 ****
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. */
--- 5256,5261 ----
*************** rdg_defs_used_in_other_loops_p (struct g
*** 5368,5405 ****
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;
- }
--- 5283,5285 ----
Index: trunk/gcc/tree-data-ref.h
===================================================================
*** trunk.orig/gcc/tree-data-ref.h 2012-06-04 15:09:18.000000000 +0200
--- trunk/gcc/tree-data-ref.h 2012-06-04 15:09:40.606652827 +0200
*************** extern bool compute_all_dependences (VEC
*** 403,409 ****
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 *,
--- 403,408 ----
*************** typedef struct rdg_vertex
*** 525,530 ****
--- 524,532 ----
/* 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;
*************** typedef struct rdg_vertex
*** 533,541 ****
--- 535,545 ----
} *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]))
*************** index_in_loop_nest (int var, VEC (loop_p
*** 608,614 ****
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
--- 612,617 ----
*************** stride_of_unit_type_p (tree stride, tree
*** 623,638 ****
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 *);
--- 626,631 ----
Index: trunk/gcc/tree-loop-distribution.c
===================================================================
*** trunk.orig/gcc/tree-loop-distribution.c 2012-06-04 15:09:18.000000000
+0200
--- trunk/gcc/tree-loop-distribution.c 2012-06-04 15:09:40.607652827 +0200
*************** classify_partition (loop_p loop, struct
*** 878,883 ****
--- 878,897 ----
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. */
*************** static bool
*** 885,901 ****
similar_memory_accesses (struct graph *rdg, partition_t partition1,
partition_t partition2)
{
! unsigned i, j;
bitmap_iterator bi, bj;
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;
return false;
}
--- 899,934 ----
similar_memory_accesses (struct graph *rdg, partition_t partition1,
partition_t partition2)
{
! 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))
! {
! 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;
}
*************** tree_loop_distribution (void)
*** 1252,1257 ****
--- 1285,1300 ----
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. */
Index: trunk/gcc/tree-vect-loop.c
===================================================================
*** trunk.orig/gcc/tree-vect-loop.c 2012-06-04 15:09:38.000000000 +0200
--- trunk/gcc/tree-vect-loop.c 2012-06-04 15:09:50.690652479 +0200
*************** vect_finalize_reduction:
*** 4211,4217 ****
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 new_phi_vinfo;
tree vect_phi_init, preheader_arg, vect_phi_res, init_def;
basic_block bb = gimple_bb (use_stmt);
--- 4211,4217 ----
orig_name = PHI_RESULT (exit_phi);
FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, orig_name)
{
! 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);
*************** vect_finalize_reduction:
*** 4221,4231 ****
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;
/* Create vector phi node for double reduction:
vs1 = phi <vs0, vs2>
--- 4221,4233 ----
node. */
if (gimple_code (use_stmt) != GIMPLE_PHI
|| gimple_phi_num_args (use_stmt) != 2
|| 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>
