This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH][7/n] tree LIM TLC
- From: Richard Biener <rguenther at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Date: Wed, 13 Mar 2013 14:29:03 +0100 (CET)
- Subject: [PATCH][7/n] tree LIM TLC
This uses bitmap_heads for more bitmaps (one indirection less
and slightly smaller memory footprint) and it avoids the
extra indirection to avoid having a vec of a vec which is now
possible.
Bootstrap and regtest running on x86_64-unknown-linux-gnu.
Richard.
2013-03-13 Richard Biener <rguenther@suse.de>
* tree-ssa-loop-im.c (struct mem_ref_locs): Remove.
(struct mem_ref): Make accesses_in_loop a vec of a vec of
pointers to aggregate mem_ref_loc. Use a bitmap_head for
the vector of loops the ref is stored in.
(memory_accesses): Use vectors of bitmap_heads instead of
vectors of bitmaps
(outermost_indep_loop): Adjust.
(free_mem_ref_locs): Inline into ...
(memref_free): ... this and adjust.
(mem_ref_alloc): Adjust.
(mem_ref_locs_alloc): Remove.
(record_mem_ref_loc): Adjust. Inline ref bitmap manipulation
into its caller.
(gather_mem_refs_stmt): Use a shared mem_ref for unanalyzable mems
and do not record locations for it.
(analyze_memory_references): Adjust.
(get_all_locs_in_loop): Likewise.
(ref_indep_loop_p_1): Likewise.
(find_refs_for_sm): Likewise.
(tree_ssa_lim_initialize): Likewise.
Index: trunk/gcc/tree-ssa-loop-im.c
===================================================================
*** trunk.orig/gcc/tree-ssa-loop-im.c 2013-03-13 12:53:47.000000000 +0100
--- trunk/gcc/tree-ssa-loop-im.c 2013-03-13 13:40:17.437154471 +0100
*************** typedef struct mem_ref_loc
*** 105,118 ****
} *mem_ref_loc_p;
- /* The list of memory reference locations in a loop. */
-
- typedef struct mem_ref_locs
- {
- vec<mem_ref_loc_p> locs;
- } *mem_ref_locs_p;
-
-
/* Description of a memory reference. */
typedef struct mem_ref
--- 105,110 ----
*************** typedef struct mem_ref
*** 121,129 ****
unsigned id; /* ID assigned to the memory reference
(its index in memory_accesses.refs_list) */
hashval_t hash; /* Its hash value. */
! bitmap stored; /* The set of loops in that this memory location
is stored to. */
! vec<mem_ref_locs_p> accesses_in_loop;
/* The locations of the accesses. Vector
indexed by the loop number. */
--- 113,121 ----
unsigned id; /* ID assigned to the memory reference
(its index in memory_accesses.refs_list) */
hashval_t hash; /* Its hash value. */
! bitmap_head stored; /* The set of loops in that this memory location
is stored to. */
! vec<vec<mem_ref_loc_p> > accesses_in_loop;
/* The locations of the accesses. Vector
indexed by the loop number. */
*************** static struct
*** 158,172 ****
vec<mem_ref_p> refs_list;
/* The set of memory references accessed in each loop. */
! vec<bitmap> refs_in_loop;
/* The set of memory references accessed in each loop, including
subloops. */
! vec<bitmap> all_refs_in_loop;
/* The set of memory references stored in each loop, including
subloops. */
! vec<bitmap> all_refs_stored_in_loop;
/* Cache for expanding memory addresses. */
struct pointer_map_t *ttae_cache;
--- 150,164 ----
vec<mem_ref_p> refs_list;
/* The set of memory references accessed in each loop. */
! vec<bitmap_head> refs_in_loop;
/* The set of memory references accessed in each loop, including
subloops. */
! vec<bitmap_head> all_refs_in_loop;
/* The set of memory references stored in each loop, including
subloops. */
! vec<bitmap_head> all_refs_stored_in_loop;
/* Cache for expanding memory addresses. */
struct pointer_map_t *ttae_cache;
*************** outermost_indep_loop (struct loop *outer
*** 605,617 ****
{
struct loop *aloop;
! if (bitmap_bit_p (ref->stored, loop->num))
return NULL;
for (aloop = outer;
aloop != loop;
aloop = superloop_at_depth (loop, loop_depth (aloop) + 1))
! if (!bitmap_bit_p (ref->stored, aloop->num)
&& ref_indep_loop_p (aloop, ref))
return aloop;
--- 597,609 ----
{
struct loop *aloop;
! if (bitmap_bit_p (&ref->stored, loop->num))
return NULL;
for (aloop = outer;
aloop != loop;
aloop = superloop_at_depth (loop, loop_depth (aloop) + 1))
! if (!bitmap_bit_p (&ref->stored, aloop->num)
&& ref_indep_loop_p (aloop, ref))
return aloop;
*************** memref_eq (const void *obj1, const void
*** 1438,1470 ****
return operand_equal_p (mem1->mem, (const_tree) obj2, 0);
}
- /* Releases list of memory reference locations ACCS. */
-
- static void
- free_mem_ref_locs (mem_ref_locs_p accs)
- {
- unsigned i;
- mem_ref_loc_p loc;
-
- if (!accs)
- return;
-
- FOR_EACH_VEC_ELT (accs->locs, i, loc)
- free (loc);
- accs->locs.release ();
- free (accs);
- }
-
/* A function to free the mem_ref object OBJ. */
static void
memref_free (struct mem_ref *mem)
{
! unsigned i;
! mem_ref_locs_p accs;
FOR_EACH_VEC_ELT (mem->accesses_in_loop, i, accs)
! free_mem_ref_locs (accs);
mem->accesses_in_loop.release ();
free (mem);
--- 1430,1450 ----
return operand_equal_p (mem1->mem, (const_tree) obj2, 0);
}
/* A function to free the mem_ref object OBJ. */
static void
memref_free (struct mem_ref *mem)
{
! unsigned i, j;
! vec<mem_ref_loc_p> *accs;
! mem_ref_loc_p loc;
FOR_EACH_VEC_ELT (mem->accesses_in_loop, i, accs)
! {
! FOR_EACH_VEC_ELT (*accs, j, loc)
! free (loc);
! accs->release ();
! }
mem->accesses_in_loop.release ();
free (mem);
*************** mem_ref_alloc (tree mem, unsigned hash,
*** 1480,1486 ****
ref->mem = mem;
ref->id = id;
ref->hash = hash;
! ref->stored = BITMAP_ALLOC (&lim_bitmap_obstack);
bitmap_initialize (&ref->loop_dependence, &lim_bitmap_obstack);
bitmap_initialize (&ref->ref_dependence, &lim_bitmap_obstack);
ref->accesses_in_loop.create (0);
--- 1460,1466 ----
ref->mem = mem;
ref->id = id;
ref->hash = hash;
! bitmap_initialize (&ref->stored, &lim_bitmap_obstack);
bitmap_initialize (&ref->loop_dependence, &lim_bitmap_obstack);
bitmap_initialize (&ref->ref_dependence, &lim_bitmap_obstack);
ref->accesses_in_loop.create (0);
*************** mem_ref_alloc (tree mem, unsigned hash,
*** 1488,1536 ****
return ref;
}
- /* Allocates and returns the new list of locations. */
-
- static mem_ref_locs_p
- mem_ref_locs_alloc (void)
- {
- mem_ref_locs_p accs = XNEW (struct mem_ref_locs);
- accs->locs.create (0);
- return accs;
- }
-
/* Records memory reference location *LOC in LOOP to the memory reference
description REF. The reference occurs in statement STMT. */
static void
! record_mem_ref_loc (mem_ref_p ref, bool is_stored,
! struct loop *loop, gimple stmt, tree *loc)
{
mem_ref_loc_p aref = XNEW (struct mem_ref_loc);
- mem_ref_locs_p accs;
if (ref->accesses_in_loop.length ()
<= (unsigned) loop->num)
ref->accesses_in_loop.safe_grow_cleared (loop->num + 1);
- accs = ref->accesses_in_loop[loop->num];
- if (!accs)
- {
- accs = mem_ref_locs_alloc ();
- ref->accesses_in_loop[loop->num] = accs;
- }
aref->stmt = stmt;
aref->ref = loc;
! accs->locs.safe_push (aref);
!
! bitmap_set_bit (memory_accesses.refs_in_loop[loop->num], ref->id);
! if (is_stored)
! {
! bitmap_set_bit (memory_accesses.all_refs_stored_in_loop[loop->num],
! ref->id);
! while (loop != current_loops->tree_root
! && bitmap_set_bit (ref->stored, loop->num))
! loop = loop_outer (loop);
! }
}
/* Gathers memory references in statement STMT in LOOP, storing the
--- 1468,1488 ----
return ref;
}
/* Records memory reference location *LOC in LOOP to the memory reference
description REF. The reference occurs in statement STMT. */
static void
! record_mem_ref_loc (mem_ref_p ref, struct loop *loop, gimple stmt, tree *loc)
{
mem_ref_loc_p aref = XNEW (struct mem_ref_loc);
if (ref->accesses_in_loop.length ()
<= (unsigned) loop->num)
ref->accesses_in_loop.safe_grow_cleared (loop->num + 1);
aref->stmt = stmt;
aref->ref = loc;
! ref->accesses_in_loop[loop->num].safe_push (aref);
}
/* Gathers memory references in statement STMT in LOOP, storing the
*************** gather_mem_refs_stmt (struct loop *loop,
*** 1554,1596 ****
mem = simple_mem_ref_in_stmt (stmt, &is_stored);
if (!mem)
{
! id = memory_accesses.refs_list.length ();
! ref = mem_ref_alloc (error_mark_node, 0, id);
! memory_accesses.refs_list.safe_push (ref);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Unanalyzed memory reference %u: ", id);
print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
}
! record_mem_ref_loc (ref, gimple_vdef (stmt), loop, stmt, mem);
! return;
! }
!
! hash = iterative_hash_expr (*mem, 0);
! slot = htab_find_slot_with_hash (memory_accesses.refs, *mem, hash, INSERT);
!
! if (*slot)
! {
! ref = (mem_ref_p) *slot;
! id = ref->id;
}
else
{
! id = memory_accesses.refs_list.length ();
! ref = mem_ref_alloc (*mem, hash, id);
! memory_accesses.refs_list.safe_push (ref);
! *slot = ref;
!
! if (dump_file && (dump_flags & TDF_DETAILS))
{
! fprintf (dump_file, "Memory reference %u: ", id);
! print_generic_expr (dump_file, ref->mem, TDF_SLIM);
! fprintf (dump_file, "\n");
}
}
! record_mem_ref_loc (ref, is_stored, loop, stmt, mem);
! return;
}
/* Gathers memory references in loops. */
--- 1506,1558 ----
mem = simple_mem_ref_in_stmt (stmt, &is_stored);
if (!mem)
{
! /* We use the shared mem_ref for all unanalyzable refs. */
! id = 0;
! ref = memory_accesses.refs_list[0];
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Unanalyzed memory reference %u: ", id);
print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
}
! is_stored = gimple_vdef (stmt);
}
else
{
! hash = iterative_hash_expr (*mem, 0);
! slot = htab_find_slot_with_hash (memory_accesses.refs,
! *mem, hash, INSERT);
! if (*slot)
{
! ref = (mem_ref_p) *slot;
! id = ref->id;
}
+ else
+ {
+ id = memory_accesses.refs_list.length ();
+ ref = mem_ref_alloc (*mem, hash, id);
+ memory_accesses.refs_list.safe_push (ref);
+ *slot = ref;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Memory reference %u: ", id);
+ print_generic_expr (dump_file, ref->mem, TDF_SLIM);
+ fprintf (dump_file, "\n");
+ }
+ }
+
+ record_mem_ref_loc (ref, loop, stmt, mem);
}
! bitmap_set_bit (&memory_accesses.refs_in_loop[loop->num], ref->id);
! if (is_stored)
! {
! bitmap_set_bit (&memory_accesses.all_refs_stored_in_loop[loop->num],
! ref->id);
! while (loop != current_loops->tree_root
! && bitmap_set_bit (&ref->stored, loop->num))
! loop = loop_outer (loop);
! }
}
/* Gathers memory references in loops. */
*************** analyze_memory_references (struct loop *
*** 1617,1634 ****
the loop hierarchy. */
FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
{
! lrefs = memory_accesses.refs_in_loop[loop->num];
! alrefs = memory_accesses.all_refs_in_loop[loop->num];
bitmap_ior_into (alrefs, lrefs);
struct loop *outer = loop_outer (loop);
if (outer == current_loops->tree_root)
continue;
! alrefso = memory_accesses.all_refs_in_loop[outer->num];
bitmap_ior_into (alrefso, alrefs);
! bitmap_ior_into (memory_accesses.all_refs_stored_in_loop[outer->num],
! memory_accesses.all_refs_stored_in_loop[loop->num]);
}
}
--- 1579,1596 ----
the loop hierarchy. */
FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
{
! lrefs = &memory_accesses.refs_in_loop[loop->num];
! alrefs = &memory_accesses.all_refs_in_loop[loop->num];
bitmap_ior_into (alrefs, lrefs);
struct loop *outer = loop_outer (loop);
if (outer == current_loops->tree_root)
continue;
! alrefso = &memory_accesses.all_refs_in_loop[outer->num];
bitmap_ior_into (alrefso, alrefs);
! bitmap_ior_into (&memory_accesses.all_refs_stored_in_loop[outer->num],
! &memory_accesses.all_refs_stored_in_loop[loop->num]);
}
}
*************** static void
*** 1681,1690 ****
get_all_locs_in_loop (struct loop *loop, mem_ref_p ref,
vec<mem_ref_loc_p> *locs)
{
- mem_ref_locs_p accs;
unsigned i;
mem_ref_loc_p loc;
! bitmap refs = memory_accesses.all_refs_in_loop[loop->num];
struct loop *subloop;
if (!bitmap_bit_p (refs, ref->id))
--- 1643,1651 ----
get_all_locs_in_loop (struct loop *loop, mem_ref_p ref,
vec<mem_ref_loc_p> *locs)
{
unsigned i;
mem_ref_loc_p loc;
! bitmap refs = &memory_accesses.all_refs_in_loop[loop->num];
struct loop *subloop;
if (!bitmap_bit_p (refs, ref->id))
*************** get_all_locs_in_loop (struct loop *loop,
*** 1693,1704 ****
if (ref->accesses_in_loop.length ()
> (unsigned) loop->num)
{
! accs = ref->accesses_in_loop[loop->num];
! if (accs)
! {
! FOR_EACH_VEC_ELT (accs->locs, i, loc)
! locs->safe_push (loc);
! }
}
for (subloop = loop->inner; subloop != NULL; subloop = subloop->next)
--- 1654,1661 ----
if (ref->accesses_in_loop.length ()
> (unsigned) loop->num)
{
! FOR_EACH_VEC_ELT (ref->accesses_in_loop[loop->num], i, loc)
! locs->safe_push (loc);
}
for (subloop = loop->inner; subloop != NULL; subloop = subloop->next)
*************** ref_indep_loop_p_1 (struct loop *loop, m
*** 2223,2235 ****
bitmap refs_to_check;
unsigned i;
bitmap_iterator bi;
! bool ret = true, stored = bitmap_bit_p (ref->stored, loop->num);
mem_ref_p aref;
if (stored)
! refs_to_check = memory_accesses.all_refs_in_loop[loop->num];
else
! refs_to_check = memory_accesses.all_refs_stored_in_loop[loop->num];
EXECUTE_IF_SET_IN_BITMAP (refs_to_check, 0, i, bi)
{
--- 2180,2192 ----
bitmap refs_to_check;
unsigned i;
bitmap_iterator bi;
! bool ret = true, stored = bitmap_bit_p (&ref->stored, loop->num);
mem_ref_p aref;
if (stored)
! refs_to_check = &memory_accesses.all_refs_in_loop[loop->num];
else
! refs_to_check = &memory_accesses.all_refs_stored_in_loop[loop->num];
EXECUTE_IF_SET_IN_BITMAP (refs_to_check, 0, i, bi)
{
*************** can_sm_ref_p (struct loop *loop, mem_ref
*** 2316,2322 ****
static void
find_refs_for_sm (struct loop *loop, bitmap sm_executed, bitmap refs_to_sm)
{
! bitmap refs = memory_accesses.all_refs_stored_in_loop[loop->num];
unsigned i;
bitmap_iterator bi;
mem_ref_p ref;
--- 2273,2279 ----
static void
find_refs_for_sm (struct loop *loop, bitmap sm_executed, bitmap refs_to_sm)
{
! bitmap refs = &memory_accesses.all_refs_stored_in_loop[loop->num];
unsigned i;
bitmap_iterator bi;
mem_ref_p ref;
*************** tree_ssa_lim_initialize (void)
*** 2499,2516 ****
memory_accesses.refs = htab_create (100, memref_hash, memref_eq, NULL);
memory_accesses.refs_list.create (100);
memory_accesses.refs_in_loop.create (number_of_loops ());
memory_accesses.all_refs_in_loop.create (number_of_loops ());
memory_accesses.all_refs_stored_in_loop.create (number_of_loops ());
!
for (i = 0; i < number_of_loops (); i++)
{
! bitmap empty = BITMAP_ALLOC (&lim_bitmap_obstack);
! memory_accesses.refs_in_loop.quick_push (empty);
! empty = BITMAP_ALLOC (&lim_bitmap_obstack);
! memory_accesses.all_refs_in_loop.quick_push (empty);
! empty = BITMAP_ALLOC (&lim_bitmap_obstack);
! memory_accesses.all_refs_stored_in_loop.quick_push (empty);
}
memory_accesses.ttae_cache = NULL;
--- 2456,2478 ----
memory_accesses.refs = htab_create (100, memref_hash, memref_eq, NULL);
memory_accesses.refs_list.create (100);
+ /* Allocate special, unanalyzable mem-ref with ID zero. */
+ memory_accesses.refs_list.quick_push (mem_ref_alloc (error_mark_node, 0, 0));
+
memory_accesses.refs_in_loop.create (number_of_loops ());
+ memory_accesses.refs_in_loop.quick_grow (number_of_loops ());
memory_accesses.all_refs_in_loop.create (number_of_loops ());
+ memory_accesses.all_refs_in_loop.quick_grow (number_of_loops ());
memory_accesses.all_refs_stored_in_loop.create (number_of_loops ());
! memory_accesses.all_refs_stored_in_loop.quick_grow (number_of_loops ());
for (i = 0; i < number_of_loops (); i++)
{
! bitmap_initialize (&memory_accesses.refs_in_loop[i],
! &lim_bitmap_obstack);
! bitmap_initialize (&memory_accesses.all_refs_in_loop[i],
! &lim_bitmap_obstack);
! bitmap_initialize (&memory_accesses.all_refs_stored_in_loop[i],
! &lim_bitmap_obstack);
}
memory_accesses.ttae_cache = NULL;