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 <rguent...@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;