With the alias-improvements rewrite I unfortunately disabled
most of the invariant (and store) motions in LIM due to the
fact how the current code uses virtual operands to track
clobbers through stmts it cannot analyze. Given that we only
have a single virtual operand now this boils down to disabling
all invariant motion once a single unhandled stmt is in a loop.
The following patch cures this by simplifying the code. With
that the loop invariant motion pass after vectorization and
complete unrolling moves all invariant memory loads out of
the innermost loop again.
Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to trunk.
Richard.
2011-12-05 Richard Guenther <rguent...@suse.de>
PR tree-optimization/50904
* tree-ssa-loop-im.c (struct mem_ref): Remove vops member.
(MEM_ANALYZABLE): New.
(memory_references): Remove clobbered_vops and vop_ref_map
members, add all_refs_stored_in_loop member.
(memref_free): Adjust.
(mem_ref_alloc): Likewise.
(gather_mem_refs_stmt): Do not record clobbers, instead
record refs for unanalyzable stmts.
(gather_mem_refs_in_loops): Do not propagate clobbers.
(struct vop_to_refs_elt, vtoe_hash, vtoe_eq, vtoe_free,
record_vop_access, get_vop_accesses, get_vop_stores,
add_vop_ref_mapping): Remove.
(create_vop_ref_mapping_loop): Adjust to simply record all
stores.
(analyze_memory_references): Adjust.
(refs_independent_p): Check for not analyzable refs.
(can_sm_ref_p): Likewise.
(ref_indep_loop_p_1): Simplify.
(tree_ssa_lim_finalize): Adjust.
Index: gcc/tree-ssa-loop-im.c
===================================================================
*** gcc/tree-ssa-loop-im.c (revision 182001)
--- gcc/tree-ssa-loop-im.c (working copy)
*************** typedef struct mem_ref
*** 135,142 ****
VEC (mem_ref_locs_p, heap) *accesses_in_loop;
/* The locations of the accesses. Vector
indexed by the loop number. */
- bitmap vops; /* Vops corresponding to this memory
- location. */
/* The following sets are computed on demand. We keep both set and
its complement, so that we know whether the information was
--- 135,140 ----
*************** static struct
*** 181,192 ****
subloops. */
VEC (bitmap, heap) *all_refs_in_loop;
! /* The set of virtual operands clobbered in a given loop. */
! VEC (bitmap, heap) *clobbered_vops;
!
! /* Map from the pair (loop, virtual operand) to the set of refs that
! touch the virtual operand in the loop. */
! VEC (htab_t, heap) *vop_ref_map;
/* Cache for expanding memory addresses. */
struct pointer_map_t *ttae_cache;
--- 179,187 ----
subloops. */
VEC (bitmap, heap) *all_refs_in_loop;
! /* The set of memory references stored in each loop, including
! subloops. */
! VEC (bitmap, heap) *all_refs_stored_in_loop;
/* Cache for expanding memory addresses. */
struct pointer_map_t *ttae_cache;
*************** static bool ref_indep_loop_p (struct loo
*** 202,207 ****
--- 197,205 ----
#define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
#define SET_ALWAYS_EXECUTED_IN(BB, VAL) ((BB)->aux = (void *) (VAL))
+ /* Whether the reference was analyzable. */
+ #define MEM_ANALYZABLE(REF) ((REF)->mem != error_mark_node)
+
static struct lim_aux_data *
init_lim_data (gimple stmt)
{
*************** memref_free (void *obj)
*** 1472,1478 ****
free_mem_ref_locs (accs);
VEC_free (mem_ref_locs_p, heap, mem->accesses_in_loop);
- BITMAP_FREE (mem->vops);
free (mem);
}
--- 1476,1481 ----
*************** mem_ref_alloc (tree mem, unsigned hash,
*** 1492,1498 ****
ref->indep_ref = BITMAP_ALLOC (NULL);
ref->dep_ref = BITMAP_ALLOC (NULL);
ref->accesses_in_loop = NULL;
- ref->vops = BITMAP_ALLOC (NULL);
return ref;
}
--- 1495,1500 ----
*************** gather_mem_refs_stmt (struct loop *loop,
*** 1559,1567 ****
hashval_t hash;
PTR *slot;
mem_ref_p ref;
- tree vname;
bool is_stored;
- bitmap clvops;
unsigned id;
if (!gimple_vuse (stmt))
--- 1561,1567 ----
*************** gather_mem_refs_stmt (struct loop *loop,
*** 1569,1575 ****
mem = simple_mem_ref_in_stmt (stmt, &is_stored);
if (!mem)
! goto fail;
hash = iterative_hash_expr (*mem, 0);
slot = htab_find_slot_with_hash (memory_accesses.refs, *mem, hash, INSERT);
--- 1569,1588 ----
mem = simple_mem_ref_in_stmt (stmt, &is_stored);
if (!mem)
! {
! id = VEC_length (mem_ref_p, memory_accesses.refs_list);
! ref = mem_ref_alloc (error_mark_node, 0, id);
! VEC_safe_push (mem_ref_p, heap, memory_accesses.refs_list, 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);
! }
! if (gimple_vdef (stmt))
! mark_ref_stored (ref, loop);
! record_mem_ref_loc (ref, loop, stmt, mem);
! return;
! }
hash = iterative_hash_expr (*mem, 0);
slot = htab_find_slot_with_hash (memory_accesses.refs, *mem, hash, INSERT);
*************** gather_mem_refs_stmt (struct loop *loop,
*** 1596,1610 ****
if (is_stored)
mark_ref_stored (ref, loop);
- if ((vname = gimple_vuse (stmt)) != NULL_TREE)
- bitmap_set_bit (ref->vops, DECL_UID (SSA_NAME_VAR (vname)));
record_mem_ref_loc (ref, loop, stmt, mem);
return;
-
- fail:
- clvops = VEC_index (bitmap, memory_accesses.clobbered_vops, loop->num);
- if ((vname = gimple_vuse (stmt)) != NULL_TREE)
- bitmap_set_bit (clvops, DECL_UID (SSA_NAME_VAR (vname)));
}
/* Gathers memory references in loops. */
--- 1609,1616 ----
*************** gather_mem_refs_in_loops (void)
*** 1616,1622 ****
basic_block bb;
struct loop *loop;
loop_iterator li;
- bitmap clvo, clvi;
bitmap lrefs, alrefs, alrefso;
FOR_EACH_BB (bb)
--- 1622,1627 ----
*************** gather_mem_refs_in_loops (void)
*** 1629,1636 ****
gather_mem_refs_stmt (loop, gsi_stmt (bsi));
}
! /* Propagate the information about clobbered vops and accessed memory
! references up the loop hierarchy. */
FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
{
lrefs = VEC_index (bitmap, memory_accesses.refs_in_loop, loop->num);
--- 1634,1641 ----
gather_mem_refs_stmt (loop, gsi_stmt (bsi));
}
! /* Propagate the information about accessed memory references up
! the loop hierarchy. */
FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
{
lrefs = VEC_index (bitmap, memory_accesses.refs_in_loop, loop->num);
*************** gather_mem_refs_in_loops (void)
*** 1640,1772 ****
if (loop_outer (loop) == current_loops->tree_root)
continue;
- clvi = VEC_index (bitmap, memory_accesses.clobbered_vops, loop->num);
- clvo = VEC_index (bitmap, memory_accesses.clobbered_vops,
- loop_outer (loop)->num);
- bitmap_ior_into (clvo, clvi);
-
alrefso = VEC_index (bitmap, memory_accesses.all_refs_in_loop,
loop_outer (loop)->num);
bitmap_ior_into (alrefso, alrefs);
}
}
- /* Element of the hash table that maps vops to memory references. */
-
- struct vop_to_refs_elt
- {
- /* DECL_UID of the vop. */
- unsigned uid;
-
- /* List of the all references. */
- bitmap refs_all;
-
- /* List of stored references. */
- bitmap refs_stored;
- };
-
- /* A hash function for struct vop_to_refs_elt object OBJ. */
-
- static hashval_t
- vtoe_hash (const void *obj)
- {
- const struct vop_to_refs_elt *const vtoe =
- (const struct vop_to_refs_elt *) obj;
-
- return vtoe->uid;
- }
-
- /* An equality function for struct vop_to_refs_elt object OBJ1 with
- uid of a vop OBJ2. */
-
- static int
- vtoe_eq (const void *obj1, const void *obj2)
- {
- const struct vop_to_refs_elt *const vtoe =
- (const struct vop_to_refs_elt *) obj1;
- const unsigned *const uid = (const unsigned *) obj2;
-
- return vtoe->uid == *uid;
- }
-
- /* A function to free the struct vop_to_refs_elt object. */
-
- static void
- vtoe_free (void *obj)
- {
- struct vop_to_refs_elt *const vtoe =
- (struct vop_to_refs_elt *) obj;
-
- BITMAP_FREE (vtoe->refs_all);
- BITMAP_FREE (vtoe->refs_stored);
- free (vtoe);
- }
-
- /* Records REF to hashtable VOP_TO_REFS for the index VOP. STORED is true
- if the reference REF is stored. */
-
- static void
- record_vop_access (htab_t vop_to_refs, unsigned vop, unsigned ref, bool
stored)
- {
- void **slot = htab_find_slot_with_hash (vop_to_refs, &vop, vop, INSERT);
- struct vop_to_refs_elt *vtoe;
-
- if (!*slot)
- {
- vtoe = XNEW (struct vop_to_refs_elt);
- vtoe->uid = vop;
- vtoe->refs_all = BITMAP_ALLOC (NULL);
- vtoe->refs_stored = BITMAP_ALLOC (NULL);
- *slot = vtoe;
- }
- else
- vtoe = (struct vop_to_refs_elt *) *slot;
-
- bitmap_set_bit (vtoe->refs_all, ref);
- if (stored)
- bitmap_set_bit (vtoe->refs_stored, ref);
- }
-
- /* Returns the set of references that access VOP according to the table
- VOP_TO_REFS. */
-
- static bitmap
- get_vop_accesses (htab_t vop_to_refs, unsigned vop)
- {
- struct vop_to_refs_elt *const vtoe =
- (struct vop_to_refs_elt *) htab_find_with_hash (vop_to_refs, &vop, vop);
- return vtoe->refs_all;
- }
-
- /* Returns the set of stores that access VOP according to the table
- VOP_TO_REFS. */
-
- static bitmap
- get_vop_stores (htab_t vop_to_refs, unsigned vop)
- {
- struct vop_to_refs_elt *const vtoe =
- (struct vop_to_refs_elt *) htab_find_with_hash (vop_to_refs, &vop, vop);
- return vtoe->refs_stored;
- }
-
- /* Adds REF to mapping from virtual operands to references in LOOP. */
-
- static void
- add_vop_ref_mapping (struct loop *loop, mem_ref_p ref)
- {
- htab_t map = VEC_index (htab_t, memory_accesses.vop_ref_map, loop->num);
- bool stored = bitmap_bit_p (ref->stored, loop->num);
- bitmap clobbers = VEC_index (bitmap, memory_accesses.clobbered_vops,
- loop->num);
- bitmap_iterator bi;
- unsigned vop;
-
- EXECUTE_IF_AND_COMPL_IN_BITMAP (ref->vops, clobbers, 0, vop, bi)
- {
- record_vop_access (map, vop, ref->id, stored);
- }
- }
-
/* Create a mapping from virtual operands to references that touch them
in LOOP. */
--- 1645,1656 ----
*************** create_vop_ref_mapping_loop (struct loop
*** 1782,1789 ****
EXECUTE_IF_SET_IN_BITMAP (refs, 0, i, bi)
{
ref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
! for (sloop = loop; sloop != current_loops->tree_root; sloop =
loop_outer (sloop))
! add_vop_ref_mapping (sloop, ref);
}
}
--- 1666,1680 ----
EXECUTE_IF_SET_IN_BITMAP (refs, 0, i, bi)
{
ref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
! for (sloop = loop; sloop != current_loops->tree_root;
! sloop = loop_outer (sloop))
! if (bitmap_bit_p (ref->stored, loop->num))
! {
! bitmap refs_stored
! = VEC_index (bitmap, memory_accesses.all_refs_stored_in_loop,
! sloop->num);
! bitmap_set_bit (refs_stored, ref->id);
! }
}
}
*************** analyze_memory_references (void)
*** 1809,1815 ****
{
unsigned i;
bitmap empty;
- htab_t hempty;
memory_accesses.refs
= htab_create (100, memref_hash, memref_eq, memref_free);
--- 1700,1705 ----
*************** analyze_memory_references (void)
*** 1818,1827 ****
number_of_loops ());
memory_accesses.all_refs_in_loop = VEC_alloc (bitmap, heap,
number_of_loops ());
! memory_accesses.clobbered_vops = VEC_alloc (bitmap, heap,
! number_of_loops ());
! memory_accesses.vop_ref_map = VEC_alloc (htab_t, heap,
! number_of_loops ());
for (i = 0; i < number_of_loops (); i++)
{
--- 1708,1715 ----
number_of_loops ());
memory_accesses.all_refs_in_loop = VEC_alloc (bitmap, heap,
number_of_loops ());
! memory_accesses.all_refs_stored_in_loop = VEC_alloc (bitmap, heap,
! number_of_loops ());
for (i = 0; i < number_of_loops (); i++)
{
*************** analyze_memory_references (void)
*** 1830,1838 ****
empty = BITMAP_ALLOC (NULL);
VEC_quick_push (bitmap, memory_accesses.all_refs_in_loop, empty);
empty = BITMAP_ALLOC (NULL);
! VEC_quick_push (bitmap, memory_accesses.clobbered_vops, empty);
! hempty = htab_create (10, vtoe_hash, vtoe_eq, vtoe_free);
! VEC_quick_push (htab_t, memory_accesses.vop_ref_map, hempty);
}
memory_accesses.ttae_cache = NULL;
--- 1718,1724 ----
empty = BITMAP_ALLOC (NULL);
VEC_quick_push (bitmap, memory_accesses.all_refs_in_loop, empty);
empty = BITMAP_ALLOC (NULL);
! VEC_quick_push (bitmap, memory_accesses.all_refs_stored_in_loop, empty);
}
memory_accesses.ttae_cache = NULL;
*************** refs_independent_p (mem_ref_p ref1, mem_
*** 2183,2188 ****
--- 2069,2077 ----
return true;
if (bitmap_bit_p (ref1->dep_ref, ref2->id))
return false;
+ if (!MEM_ANALYZABLE (ref1)
+ || !MEM_ANALYZABLE (ref2))
+ return false;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Querying dependency of refs %u and %u: ",
*************** record_indep_loop (struct loop *loop, me
*** 2225,2259 ****
static bool
ref_indep_loop_p_1 (struct loop *loop, mem_ref_p ref)
{
! bitmap clobbers, refs_to_check, refs;
unsigned i;
bitmap_iterator bi;
bool ret = true, stored = bitmap_bit_p (ref->stored, loop->num);
- htab_t map;
mem_ref_p aref;
! /* If the reference is clobbered, it is not independent. */
! clobbers = VEC_index (bitmap, memory_accesses.clobbered_vops, loop->num);
! if (bitmap_intersect_p (ref->vops, clobbers))
! return false;
!
! refs_to_check = BITMAP_ALLOC (NULL);
!
! map = VEC_index (htab_t, memory_accesses.vop_ref_map, loop->num);
! EXECUTE_IF_AND_COMPL_IN_BITMAP (ref->vops, clobbers, 0, i, bi)
! {
! if (stored)
! refs = get_vop_accesses (map, i);
! else
! refs = get_vop_stores (map, i);
!
! bitmap_ior_into (refs_to_check, refs);
! }
EXECUTE_IF_SET_IN_BITMAP (refs_to_check, 0, i, bi)
{
aref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
! if (!refs_independent_p (ref, aref))
{
ret = false;
record_indep_loop (loop, aref, false);
--- 2114,2138 ----
static bool
ref_indep_loop_p_1 (struct loop *loop, mem_ref_p ref)
{
! 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 = VEC_index (bitmap,
! memory_accesses.all_refs_in_loop, loop->num);
! else
! refs_to_check = VEC_index (bitmap,
! memory_accesses.all_refs_stored_in_loop,
! loop->num);
EXECUTE_IF_SET_IN_BITMAP (refs_to_check, 0, i, bi)
{
aref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
! if (!MEM_ANALYZABLE (aref)
! || !refs_independent_p (ref, aref))
{
ret = false;
record_indep_loop (loop, aref, false);
*************** ref_indep_loop_p_1 (struct loop *loop, m
*** 2261,2267 ****
}
}
- BITMAP_FREE (refs_to_check);
return ret;
}
--- 2140,2145 ----
*************** can_sm_ref_p (struct loop *loop, mem_ref
*** 2296,2301 ****
--- 2174,2183 ----
{
tree base;
+ /* Can't hoist unanalyzable refs. */
+ if (!MEM_ANALYZABLE (ref))
+ return false;
+
/* Unless the reference is stored in the loop, there is nothing to do. */
if (!bitmap_bit_p (ref->stored, loop->num))
return false;
*************** tree_ssa_lim_finalize (void)
*** 2515,2521 ****
basic_block bb;
unsigned i;
bitmap b;
- htab_t h;
FOR_EACH_BB (bb)
SET_ALWAYS_EXECUTED_IN (bb, NULL);
--- 2397,2402 ----
*************** tree_ssa_lim_finalize (void)
*** 2533,2545 ****
BITMAP_FREE (b);
VEC_free (bitmap, heap, memory_accesses.all_refs_in_loop);
! FOR_EACH_VEC_ELT (bitmap, memory_accesses.clobbered_vops, i, b)
BITMAP_FREE (b);
! VEC_free (bitmap, heap, memory_accesses.clobbered_vops);
!
! FOR_EACH_VEC_ELT (htab_t, memory_accesses.vop_ref_map, i, h)
! htab_delete (h);
! VEC_free (htab_t, heap, memory_accesses.vop_ref_map);
if (memory_accesses.ttae_cache)
pointer_map_destroy (memory_accesses.ttae_cache);
--- 2414,2422 ----
BITMAP_FREE (b);
VEC_free (bitmap, heap, memory_accesses.all_refs_in_loop);
! FOR_EACH_VEC_ELT (bitmap, memory_accesses.all_refs_stored_in_loop, i, b)
BITMAP_FREE (b);
! VEC_free (bitmap, heap, memory_accesses.all_refs_stored_in_loop);
if (memory_accesses.ttae_cache)
pointer_map_destroy (memory_accesses.ttae_cache);
