* [PATCH][1/n] tree LIM TLC
@ 2013-03-11 12:07 Richard Biener
2013-03-12 8:38 ` Richard Biener
0 siblings, 1 reply; 2+ messages in thread
From: Richard Biener @ 2013-03-11 12:07 UTC (permalink / raw)
To: gcc-patches
This is a series of patches applying some TLC to LIM. This first
patch gets rid of the remains of create_vop_ref_mapping and
alongside cleans up how we record references.
Bootstrap and regtest pending on x86_64-unknown-linux-gnu.
Richard.
2013-03-11 Richard Biener <rguenther@suse.de>
* tree-ssa-loop-im.c (record_mem_ref_loc): Record ref as
stored here.
(gather_mem_refs_stmt): Instead of here and in
create_vop_ref_mapping_loop.
(gather_mem_refs_in_loops): Fold into ...
(analyze_memory_references): ... this. Move data structure
init to tree_ssa_lim_initialize. Propagate stored refs info
as well.
(create_vop_ref_mapping_loop): Remove.
(create_vop_ref_mapping): Likewise.
(tree_ssa_lim_initialize): Initialize ref bitmaps here.
Index: trunk/gcc/tree-ssa-loop-im.c
===================================================================
*** trunk.orig/gcc/tree-ssa-loop-im.c 2013-03-11 12:38:43.000000000 +0100
--- trunk/gcc/tree-ssa-loop-im.c 2013-03-11 13:00:50.417737114 +0100
*************** mem_ref_locs_alloc (void)
*** 1518,1528 ****
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);
mem_ref_locs_p accs;
- bitmap ril = memory_accesses.refs_in_loop[loop->num];
if (ref->accesses_in_loop.length ()
<= (unsigned) loop->num)
--- 1518,1528 ----
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)
*************** record_mem_ref_loc (mem_ref_p ref, struc
*** 1536,1556 ****
aref->stmt = stmt;
aref->ref = loc;
-
accs->locs.safe_push (aref);
- bitmap_set_bit (ril, ref->id);
- }
-
- /* Marks reference REF as stored in LOOP. */
! static void
! mark_ref_stored (mem_ref_p ref, struct loop *loop)
! {
! for (;
! loop != current_loops->tree_root
! && !bitmap_bit_p (ref->stored, loop->num);
! loop = loop_outer (loop))
! bitmap_set_bit (ref->stored, loop->num);
}
/* Gathers memory references in statement STMT in LOOP, storing the
--- 1536,1552 ----
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
*************** gather_mem_refs_stmt (struct loop *loop,
*** 1582,1590 ****
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;
}
--- 1578,1584 ----
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;
}
*************** gather_mem_refs_stmt (struct loop *loop,
*** 1611,1627 ****
}
}
! if (is_stored)
! mark_ref_stored (ref, loop);
!
! record_mem_ref_loc (ref, loop, stmt, mem);
return;
}
/* Gathers memory references in loops. */
static void
! gather_mem_refs_in_loops (void)
{
gimple_stmt_iterator bsi;
basic_block bb;
--- 1605,1618 ----
}
}
! record_mem_ref_loc (ref, is_stored, loop, stmt, mem);
return;
}
/* Gathers memory references in loops. */
static void
! analyze_memory_references (void)
{
gimple_stmt_iterator bsi;
basic_block bb;
*************** gather_mem_refs_in_loops (void)
*** 1647,1731 ****
alrefs = memory_accesses.all_refs_in_loop[loop->num];
bitmap_ior_into (alrefs, lrefs);
! if (loop_outer (loop) == current_loops->tree_root)
continue;
! alrefso = memory_accesses.all_refs_in_loop[loop_outer (loop)->num];
bitmap_ior_into (alrefso, alrefs);
}
}
- /* Create a mapping from virtual operands to references that touch them
- in LOOP. */
-
- static void
- create_vop_ref_mapping_loop (struct loop *loop)
- {
- bitmap refs = memory_accesses.refs_in_loop[loop->num];
- struct loop *sloop;
- bitmap_iterator bi;
- unsigned i;
- mem_ref_p ref;
-
- EXECUTE_IF_SET_IN_BITMAP (refs, 0, i, bi)
- {
- ref = 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
- = memory_accesses.all_refs_stored_in_loop[sloop->num];
- bitmap_set_bit (refs_stored, ref->id);
- }
- }
- }
-
- /* For each non-clobbered virtual operand and each loop, record the memory
- references in this loop that touch the operand. */
-
- static void
- create_vop_ref_mapping (void)
- {
- loop_iterator li;
- struct loop *loop;
-
- FOR_EACH_LOOP (li, loop, 0)
- {
- create_vop_ref_mapping_loop (loop);
- }
- }
-
- /* Gathers information about memory accesses in the loops. */
-
- static void
- analyze_memory_references (void)
- {
- unsigned i;
- bitmap empty;
-
- memory_accesses.refs = htab_create (100, memref_hash, memref_eq, NULL);
- memory_accesses.refs_list.create (0);
- 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++)
- {
- 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;
-
- gather_mem_refs_in_loops ();
- create_vop_ref_mapping ();
- }
-
/* Returns true if MEM1 and MEM2 may alias. TTAE_CACHE is used as a cache in
tree_to_aff_combination_expand. */
--- 1638,1654 ----
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]);
}
}
/* Returns true if MEM1 and MEM2 may alias. TTAE_CACHE is used as a cache in
tree_to_aff_combination_expand. */
*************** tree_ssa_lim_initialize (void)
*** 2554,2559 ****
--- 2477,2484 ----
gimple_stmt_iterator bsi;
struct loop *loop;
basic_block bb;
+ unsigned i;
+ bitmap empty;
bitmap_obstack_initialize (&lim_bitmap_obstack);
*************** tree_ssa_lim_initialize (void)
*** 2581,2586 ****
--- 2506,2529 ----
compute_transaction_bits ();
alloc_aux_for_edges (0);
+
+ memory_accesses.refs = htab_create (100, memref_hash, memref_eq, NULL);
+ memory_accesses.refs_list.create (0);
+ 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++)
+ {
+ 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;
}
/* Cleans up after the invariant motion pass. */
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: [PATCH][1/n] tree LIM TLC
2013-03-11 12:07 [PATCH][1/n] tree LIM TLC Richard Biener
@ 2013-03-12 8:38 ` Richard Biener
0 siblings, 0 replies; 2+ messages in thread
From: Richard Biener @ 2013-03-12 8:38 UTC (permalink / raw)
To: gcc-patches
On Mon, 11 Mar 2013, Richard Biener wrote:
>
> This is a series of patches applying some TLC to LIM. This first
> patch gets rid of the remains of create_vop_ref_mapping and
> alongside cleans up how we record references.
Actually I rolled in some more changes into this patch,
bootstrapped and tested on x86_64-unknown-linux-gnu, queued for 4.9.
Richard.
2013-03-11 Richard Biener <rguenther@suse.de>
* tree-ssa-loop-im.c (record_mem_ref_loc): Record ref as
stored here.
(gather_mem_refs_stmt): Instead of here and in
create_vop_ref_mapping_loop.
(gather_mem_refs_in_loops): Fold into ...
(analyze_memory_references): ... this. Move data structure
init to tree_ssa_lim_initialize. Propagate stored refs info
as well.
(create_vop_ref_mapping_loop): Remove.
(create_vop_ref_mapping): Likewise.
(tree_ssa_lim_initialize): Initialize ref bitmaps here.
Split always-executed computation into ...
(fill_always_executed_in): ... this. Rename original to ...
(fill_always_executed_in_1): ... this.
(tree_ssa_lim): Call fill_always_executed_in here.
Index: trunk/gcc/tree-ssa-loop-im.c
===================================================================
*** trunk.orig/gcc/tree-ssa-loop-im.c 2013-03-11 12:38:43.000000000 +0100
--- trunk/gcc/tree-ssa-loop-im.c 2013-03-11 14:12:00.143773587 +0100
*************** mem_ref_locs_alloc (void)
*** 1518,1528 ****
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);
mem_ref_locs_p accs;
- bitmap ril = memory_accesses.refs_in_loop[loop->num];
if (ref->accesses_in_loop.length ()
<= (unsigned) loop->num)
--- 1518,1528 ----
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)
*************** record_mem_ref_loc (mem_ref_p ref, struc
*** 1536,1556 ****
aref->stmt = stmt;
aref->ref = loc;
-
accs->locs.safe_push (aref);
- bitmap_set_bit (ril, ref->id);
- }
-
- /* Marks reference REF as stored in LOOP. */
! static void
! mark_ref_stored (mem_ref_p ref, struct loop *loop)
! {
! for (;
! loop != current_loops->tree_root
! && !bitmap_bit_p (ref->stored, loop->num);
! loop = loop_outer (loop))
! bitmap_set_bit (ref->stored, loop->num);
}
/* Gathers memory references in statement STMT in LOOP, storing the
--- 1536,1552 ----
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
*************** gather_mem_refs_stmt (struct loop *loop,
*** 1582,1590 ****
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;
}
--- 1578,1584 ----
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;
}
*************** gather_mem_refs_stmt (struct loop *loop,
*** 1611,1627 ****
}
}
! if (is_stored)
! mark_ref_stored (ref, loop);
!
! record_mem_ref_loc (ref, loop, stmt, mem);
return;
}
/* Gathers memory references in loops. */
static void
! gather_mem_refs_in_loops (void)
{
gimple_stmt_iterator bsi;
basic_block bb;
--- 1605,1618 ----
}
}
! record_mem_ref_loc (ref, is_stored, loop, stmt, mem);
return;
}
/* Gathers memory references in loops. */
static void
! analyze_memory_references (void)
{
gimple_stmt_iterator bsi;
basic_block bb;
*************** gather_mem_refs_in_loops (void)
*** 1647,1731 ****
alrefs = memory_accesses.all_refs_in_loop[loop->num];
bitmap_ior_into (alrefs, lrefs);
! if (loop_outer (loop) == current_loops->tree_root)
continue;
! alrefso = memory_accesses.all_refs_in_loop[loop_outer (loop)->num];
bitmap_ior_into (alrefso, alrefs);
}
}
- /* Create a mapping from virtual operands to references that touch them
- in LOOP. */
-
- static void
- create_vop_ref_mapping_loop (struct loop *loop)
- {
- bitmap refs = memory_accesses.refs_in_loop[loop->num];
- struct loop *sloop;
- bitmap_iterator bi;
- unsigned i;
- mem_ref_p ref;
-
- EXECUTE_IF_SET_IN_BITMAP (refs, 0, i, bi)
- {
- ref = 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
- = memory_accesses.all_refs_stored_in_loop[sloop->num];
- bitmap_set_bit (refs_stored, ref->id);
- }
- }
- }
-
- /* For each non-clobbered virtual operand and each loop, record the memory
- references in this loop that touch the operand. */
-
- static void
- create_vop_ref_mapping (void)
- {
- loop_iterator li;
- struct loop *loop;
-
- FOR_EACH_LOOP (li, loop, 0)
- {
- create_vop_ref_mapping_loop (loop);
- }
- }
-
- /* Gathers information about memory accesses in the loops. */
-
- static void
- analyze_memory_references (void)
- {
- unsigned i;
- bitmap empty;
-
- memory_accesses.refs = htab_create (100, memref_hash, memref_eq, NULL);
- memory_accesses.refs_list.create (0);
- 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++)
- {
- 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;
-
- gather_mem_refs_in_loops ();
- create_vop_ref_mapping ();
- }
-
/* Returns true if MEM1 and MEM2 may alias. TTAE_CACHE is used as a cache in
tree_to_aff_combination_expand. */
--- 1638,1654 ----
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]);
}
}
/* Returns true if MEM1 and MEM2 may alias. TTAE_CACHE is used as a cache in
tree_to_aff_combination_expand. */
*************** store_motion (void)
*** 2483,2489 ****
blocks that contain a nonpure call. */
static void
! fill_always_executed_in (struct loop *loop, sbitmap contains_call)
{
basic_block bb = NULL, *bbs, last = NULL;
unsigned i;
--- 2406,2412 ----
blocks that contain a nonpure call. */
static void
! fill_always_executed_in_1 (struct loop *loop, sbitmap contains_call)
{
basic_block bb = NULL, *bbs, last = NULL;
unsigned i;
*************** fill_always_executed_in (struct loop *lo
*** 2542,2579 ****
}
for (loop = loop->inner; loop; loop = loop->next)
! fill_always_executed_in (loop, contains_call);
}
! /* Compute the global information needed by the loop invariant motion pass. */
static void
! tree_ssa_lim_initialize (void)
{
sbitmap contains_call = sbitmap_alloc (last_basic_block);
- gimple_stmt_iterator bsi;
- struct loop *loop;
basic_block bb;
!
! bitmap_obstack_initialize (&lim_bitmap_obstack);
bitmap_clear (contains_call);
FOR_EACH_BB (bb)
{
! for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
{
! if (nonpure_call_p (gsi_stmt (bsi)))
break;
}
! if (!gsi_end_p (bsi))
bitmap_set_bit (contains_call, bb->index);
}
for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
! fill_always_executed_in (loop, contains_call);
sbitmap_free (contains_call);
lim_aux_data_map = pointer_map_create ();
--- 2465,2513 ----
}
for (loop = loop->inner; loop; loop = loop->next)
! fill_always_executed_in_1 (loop, contains_call);
}
! /* Fills ALWAYS_EXECUTED_IN information for basic blocks, i.e.
! for each such basic block bb records the outermost loop for that execution
! of its header implies execution of bb. */
static void
! fill_always_executed_in (void)
{
sbitmap contains_call = sbitmap_alloc (last_basic_block);
basic_block bb;
! struct loop *loop;
bitmap_clear (contains_call);
FOR_EACH_BB (bb)
{
! gimple_stmt_iterator gsi;
! for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
! if (nonpure_call_p (gsi_stmt (gsi)))
break;
}
! if (!gsi_end_p (gsi))
bitmap_set_bit (contains_call, bb->index);
}
for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
! fill_always_executed_in_1 (loop, contains_call);
sbitmap_free (contains_call);
+ }
+
+
+ /* Compute the global information needed by the loop invariant motion pass. */
+
+ static void
+ tree_ssa_lim_initialize (void)
+ {
+ unsigned i;
+
+ bitmap_obstack_initialize (&lim_bitmap_obstack);
lim_aux_data_map = pointer_map_create ();
*************** tree_ssa_lim_initialize (void)
*** 2581,2586 ****
--- 2515,2538 ----
compute_transaction_bits ();
alloc_aux_for_edges (0);
+
+ 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;
}
/* Cleans up after the invariant motion pass. */
*************** tree_ssa_lim (void)
*** 2627,2632 ****
--- 2579,2587 ----
/* Gathers information about memory accesses in the loops. */
analyze_memory_references ();
+ /* Fills ALWAYS_EXECUTED_IN information for basic blocks. */
+ fill_always_executed_in ();
+
/* For each statement determine the outermost loop in that it is
invariant and cost for computing the invariant. */
determine_invariantness ();
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2013-03-12 8:38 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2013-03-11 12:07 [PATCH][1/n] tree LIM TLC Richard Biener
2013-03-12 8:38 ` Richard Biener
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).