* [PATCH][2/n] loop distribution TLC
@ 2012-05-31 14:01 Richard Guenther
0 siblings, 0 replies; only message in thread
From: Richard Guenther @ 2012-05-31 14:01 UTC (permalink / raw)
To: gcc-patches
This abstracts the notion of a partition properly so we can add
more information to it in followup patches (and not re-compute
everything all the time).
Bootstrap and regtest running on x86_64-unknown-linux-gnu.
Richard.
2012-05-31 Richard Guenther <rguenther@suse.de>
* tree-loop-distribution.c (struct partition_s): New struct,
typedef and vector type.
(partition_alloc, partition_free): New functions.
(generate_loops_for_partition, generate_builtin,
generate_code_for_partition, rdg_flag_uses, rdg_flag_vertex,
rdg_flag_vertex_and_dependent, rdg_flag_loop_exits,
build_rdg_partition_for_component, can_generate_builtin,
similar_memory_accesses, fuse_partitions_with_similar_memory_accesses,
rdg_build_partitions, dump_rdg_partitions, debug_rdg_partitions,
number_of_rw_in_partition, partition_contains_all_rw,
ldist_gen): Use partition_t instead of bitmap.
Index: gcc/tree-loop-distribution.c
===================================================================
*** gcc/tree-loop-distribution.c.orig 2012-05-31 15:51:46.000000000 +0200
--- gcc/tree-loop-distribution.c 2012-05-31 15:58:12.560517791 +0200
*************** along with GCC; see the file COPYING3.
*** 52,57 ****
--- 52,85 ----
#include "tree-scalar-evolution.h"
#include "tree-pass.h"
+ typedef struct partition_s
+ {
+ bitmap stmts;
+ } *partition_t;
+
+ DEF_VEC_P (partition_t);
+ DEF_VEC_ALLOC_P (partition_t, heap);
+
+ /* Allocate and initialize a partition from BITMAP. */
+
+ static partition_t
+ partition_alloc (bitmap stmts)
+ {
+ partition_t partition = XCNEW (struct partition_s);
+ partition->stmts = stmts ? stmts : BITMAP_ALLOC (NULL);
+ return partition;
+ }
+
+ /* Free PARTITION. */
+
+ static void
+ partition_free (partition_t partition)
+ {
+ BITMAP_FREE (partition->stmts);
+ free (partition);
+ }
+
+
/* If bit I is not set, it means that this node represents an
operation that has already been performed, and that should not be
performed again. This is the subgraph of remaining important
*************** create_bb_after_loop (struct loop *loop)
*** 192,198 ****
the code gen succeeded. */
static bool
! generate_loops_for_partition (struct loop *loop, bitmap partition, bool copy_p)
{
unsigned i, x;
gimple_stmt_iterator bsi;
--- 220,227 ----
the code gen succeeded. */
static bool
! generate_loops_for_partition (struct loop *loop, partition_t partition,
! bool copy_p)
{
unsigned i, x;
gimple_stmt_iterator bsi;
*************** generate_loops_for_partition (struct loo
*** 219,225 ****
basic_block bb = bbs[i];
for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
! if (!bitmap_bit_p (partition, x++))
reset_debug_uses (gsi_stmt (bsi));
for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
--- 248,254 ----
basic_block bb = bbs[i];
for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
! if (!bitmap_bit_p (partition->stmts, x++))
reset_debug_uses (gsi_stmt (bsi));
for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
*************** generate_loops_for_partition (struct loo
*** 227,233 ****
gimple stmt = gsi_stmt (bsi);
if (gimple_code (stmt) != GIMPLE_LABEL
&& !is_gimple_debug (stmt)
! && !bitmap_bit_p (partition, x++))
reset_debug_uses (stmt);
}
}
--- 256,262 ----
gimple stmt = gsi_stmt (bsi);
if (gimple_code (stmt) != GIMPLE_LABEL
&& !is_gimple_debug (stmt)
! && !bitmap_bit_p (partition->stmts, x++))
reset_debug_uses (stmt);
}
}
*************** generate_loops_for_partition (struct loo
*** 237,243 ****
basic_block bb = bbs[i];
for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi);)
! if (!bitmap_bit_p (partition, x++))
{
gimple phi = gsi_stmt (bsi);
if (!is_gimple_reg (gimple_phi_result (phi)))
--- 266,272 ----
basic_block bb = bbs[i];
for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi);)
! if (!bitmap_bit_p (partition->stmts, x++))
{
gimple phi = gsi_stmt (bsi);
if (!is_gimple_reg (gimple_phi_result (phi)))
*************** generate_loops_for_partition (struct loo
*** 252,258 ****
gimple stmt = gsi_stmt (bsi);
if (gimple_code (stmt) != GIMPLE_LABEL
&& !is_gimple_debug (stmt)
! && !bitmap_bit_p (partition, x++))
{
unlink_stmt_vdef (stmt);
gsi_remove (&bsi, true);
--- 281,287 ----
gimple stmt = gsi_stmt (bsi);
if (gimple_code (stmt) != GIMPLE_LABEL
&& !is_gimple_debug (stmt)
! && !bitmap_bit_p (partition->stmts, x++))
{
unlink_stmt_vdef (stmt);
gsi_remove (&bsi, true);
*************** generate_memset_zero (gimple stmt, tree
*** 337,343 ****
operation succeeded. */
static bool
! generate_builtin (struct loop *loop, bitmap partition, bool copy_p)
{
bool res = false;
unsigned i, x = 0;
--- 366,372 ----
operation succeeded. */
static bool
! generate_builtin (struct loop *loop, partition_t partition, bool copy_p)
{
bool res = false;
unsigned i, x = 0;
*************** generate_builtin (struct loop *loop, bit
*** 366,372 ****
|| is_gimple_debug (stmt))
continue;
! if (!bitmap_bit_p (partition, x++))
continue;
/* If the stmt has uses outside of the loop fail.
--- 395,401 ----
|| is_gimple_debug (stmt))
continue;
! if (!bitmap_bit_p (partition->stmts, x++))
continue;
/* If the stmt has uses outside of the loop fail.
*************** generate_builtin (struct loop *loop, bit
*** 432,438 ****
generate a built-in. */
static bool
! generate_code_for_partition (struct loop *loop, bitmap partition, bool copy_p)
{
if (generate_builtin (loop, partition, copy_p))
return true;
--- 461,468 ----
generate a built-in. */
static bool
! generate_code_for_partition (struct loop *loop, partition_t partition,
! bool copy_p)
{
if (generate_builtin (loop, partition, copy_p))
return true;
*************** has_upstream_mem_writes (int u)
*** 544,557 ****
return bitmap_bit_p (upstream_mem_writes, u);
}
! static void rdg_flag_vertex_and_dependent (struct graph *, int, bitmap, bitmap,
! bitmap, bool *);
/* Flag the uses of U stopping following the information from
upstream_mem_writes. */
static void
! rdg_flag_uses (struct graph *rdg, int u, bitmap partition, bitmap loops,
bitmap processed, bool *part_has_writes)
{
use_operand_p use_p;
--- 574,587 ----
return bitmap_bit_p (upstream_mem_writes, u);
}
! static void rdg_flag_vertex_and_dependent (struct graph *, int, partition_t,
! bitmap, bitmap, bool *);
/* Flag the uses of U stopping following the information from
upstream_mem_writes. */
static void
! rdg_flag_uses (struct graph *rdg, int u, partition_t partition, bitmap loops,
bitmap processed, bool *part_has_writes)
{
use_operand_p use_p;
*************** rdg_flag_uses (struct graph *rdg, int u,
*** 617,628 ****
in LOOPS. */
static void
! rdg_flag_vertex (struct graph *rdg, int v, bitmap partition, bitmap loops,
bool *part_has_writes)
{
struct loop *loop;
! if (!bitmap_set_bit (partition, v))
return;
loop = loop_containing_stmt (RDG_STMT (rdg, v));
--- 647,658 ----
in LOOPS. */
static void
! rdg_flag_vertex (struct graph *rdg, int v, partition_t partition, bitmap loops,
bool *part_has_writes)
{
struct loop *loop;
! if (!bitmap_set_bit (partition->stmts, v))
return;
loop = loop_containing_stmt (RDG_STMT (rdg, v));
*************** rdg_flag_vertex (struct graph *rdg, int
*** 639,645 ****
Also flag their loop number in LOOPS. */
static void
! rdg_flag_vertex_and_dependent (struct graph *rdg, int v, bitmap partition,
bitmap loops, bitmap processed,
bool *part_has_writes)
{
--- 669,675 ----
Also flag their loop number in LOOPS. */
static void
! rdg_flag_vertex_and_dependent (struct graph *rdg, int v, partition_t partition,
bitmap loops, bitmap processed,
bool *part_has_writes)
{
*************** collect_condition_stmts (struct loop *lo
*** 686,692 ****
RDG. */
static void
! rdg_flag_loop_exits (struct graph *rdg, bitmap loops, bitmap partition,
bitmap processed, bool *part_has_writes)
{
unsigned i;
--- 716,722 ----
RDG. */
static void
! rdg_flag_loop_exits (struct graph *rdg, bitmap loops, partition_t partition,
bitmap processed, bool *part_has_writes)
{
unsigned i;
*************** rdg_flag_loop_exits (struct graph *rdg,
*** 720,731 ****
the strongly connected component C of the RDG are flagged, also
including the loop exit conditions. */
! static bitmap
build_rdg_partition_for_component (struct graph *rdg, rdgc c,
bool *part_has_writes)
{
int i, v;
! bitmap partition = BITMAP_ALLOC (NULL);
bitmap loops = BITMAP_ALLOC (NULL);
bitmap processed = BITMAP_ALLOC (NULL);
--- 750,761 ----
the strongly connected component C of the RDG are flagged, also
including the loop exit conditions. */
! static partition_t
build_rdg_partition_for_component (struct graph *rdg, rdgc c,
bool *part_has_writes)
{
int i, v;
! partition_t partition = partition_alloc (NULL);
bitmap loops = BITMAP_ALLOC (NULL);
bitmap processed = BITMAP_ALLOC (NULL);
*************** rdg_build_components (struct graph *rdg,
*** 803,809 ****
zero pattern. */
static bool
! can_generate_builtin (struct graph *rdg, bitmap partition)
{
unsigned i;
bitmap_iterator bi;
--- 833,839 ----
zero pattern. */
static bool
! can_generate_builtin (struct graph *rdg, partition_t partition)
{
unsigned i;
bitmap_iterator bi;
*************** can_generate_builtin (struct graph *rdg,
*** 811,817 ****
int nb_writes = 0;
int stores_zero = 0;
! EXECUTE_IF_SET_IN_BITMAP (partition, 0, i, bi)
if (RDG_MEM_READS_STMT (rdg, i))
nb_reads++;
else if (RDG_MEM_WRITE_STMT (rdg, i))
--- 841,847 ----
int nb_writes = 0;
int stores_zero = 0;
! EXECUTE_IF_SET_IN_BITMAP (partition->stmts, 0, i, bi)
if (RDG_MEM_READS_STMT (rdg, i))
nb_reads++;
else if (RDG_MEM_WRITE_STMT (rdg, i))
*************** can_generate_builtin (struct graph *rdg,
*** 830,845 ****
accesses in RDG. */
static bool
! similar_memory_accesses (struct graph *rdg, bitmap partition1,
! bitmap partition2)
{
unsigned i, j;
bitmap_iterator bi, bj;
! EXECUTE_IF_SET_IN_BITMAP (partition1, 0, i, bi)
if (RDG_MEM_WRITE_STMT (rdg, i)
|| RDG_MEM_READS_STMT (rdg, i))
! EXECUTE_IF_SET_IN_BITMAP (partition2, 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))
--- 860,875 ----
accesses in RDG. */
static bool
! 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))
*************** similar_memory_accesses (struct graph *r
*** 855,874 ****
static void
fuse_partitions_with_similar_memory_accesses (struct graph *rdg,
! VEC (bitmap, heap) **partitions)
{
int p1, p2;
! bitmap partition1, partition2;
! FOR_EACH_VEC_ELT (bitmap, *partitions, p1, partition1)
if (!can_generate_builtin (rdg, partition1))
! FOR_EACH_VEC_ELT (bitmap, *partitions, p2, partition2)
if (p1 != p2
&& !can_generate_builtin (rdg, partition2)
&& similar_memory_accesses (rdg, partition1, partition2))
{
! bitmap_ior_into (partition1, partition2);
! VEC_ordered_remove (bitmap, *partitions, p2);
p2--;
}
}
--- 885,904 ----
static void
fuse_partitions_with_similar_memory_accesses (struct graph *rdg,
! VEC (partition_t, heap) **partitions)
{
int p1, p2;
! partition_t partition1, partition2;
! FOR_EACH_VEC_ELT (partition_t, *partitions, p1, partition1)
if (!can_generate_builtin (rdg, partition1))
! FOR_EACH_VEC_ELT (partition_t, *partitions, p2, partition2)
if (p1 != p2
&& !can_generate_builtin (rdg, partition2)
&& similar_memory_accesses (rdg, partition1, partition2))
{
! bitmap_ior_into (partition1->stmts, partition2->stmts);
! VEC_ordered_remove (partition_t, *partitions, p2);
p2--;
}
}
*************** fuse_partitions_with_similar_memory_acce
*** 880,894 ****
static void
rdg_build_partitions (struct graph *rdg, VEC (rdgc, heap) *components,
VEC (int, heap) **other_stores,
! VEC (bitmap, heap) **partitions, bitmap processed)
{
int i;
rdgc x;
! bitmap partition = BITMAP_ALLOC (NULL);
FOR_EACH_VEC_ELT (rdgc, components, i, x)
{
! bitmap np;
bool part_has_writes = false;
int v = VEC_index (int, x->vertices, 0);
--- 910,924 ----
static void
rdg_build_partitions (struct graph *rdg, VEC (rdgc, heap) *components,
VEC (int, heap) **other_stores,
! VEC (partition_t, heap) **partitions, bitmap processed)
{
int i;
rdgc x;
! partition_t partition = partition_alloc (NULL);
FOR_EACH_VEC_ELT (rdgc, components, i, x)
{
! partition_t np;
bool part_has_writes = false;
int v = VEC_index (int, x->vertices, 0);
*************** rdg_build_partitions (struct graph *rdg,
*** 896,915 ****
continue;
np = build_rdg_partition_for_component (rdg, x, &part_has_writes);
! bitmap_ior_into (partition, np);
! bitmap_ior_into (processed, np);
! BITMAP_FREE (np);
if (part_has_writes)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "ldist useful partition:\n");
! dump_bitmap (dump_file, partition);
}
! VEC_safe_push (bitmap, heap, *partitions, partition);
! partition = BITMAP_ALLOC (NULL);
}
}
--- 926,945 ----
continue;
np = build_rdg_partition_for_component (rdg, x, &part_has_writes);
! bitmap_ior_into (partition->stmts, np->stmts);
! bitmap_ior_into (processed, np->stmts);
! partition_free (np);
if (part_has_writes)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "ldist useful partition:\n");
! dump_bitmap (dump_file, partition->stmts);
}
! VEC_safe_push (partition_t, heap, *partitions, partition);
! partition = partition_alloc (NULL);
}
}
*************** rdg_build_partitions (struct graph *rdg,
*** 937,946 ****
}
/* If there is something left in the last partition, save it. */
! if (bitmap_count_bits (partition) > 0)
! VEC_safe_push (bitmap, heap, *partitions, partition);
else
! BITMAP_FREE (partition);
fuse_partitions_with_similar_memory_accesses (rdg, partitions);
}
--- 967,976 ----
}
/* If there is something left in the last partition, save it. */
! if (bitmap_count_bits (partition->stmts) > 0)
! VEC_safe_push (partition_t, heap, *partitions, partition);
else
! partition_free (partition);
fuse_partitions_with_similar_memory_accesses (rdg, partitions);
}
*************** rdg_build_partitions (struct graph *rdg,
*** 948,967 ****
/* Dump to FILE the PARTITIONS. */
static void
! dump_rdg_partitions (FILE *file, VEC (bitmap, heap) *partitions)
{
int i;
! bitmap partition;
! FOR_EACH_VEC_ELT (bitmap, partitions, i, partition)
! debug_bitmap_file (file, partition);
}
/* Debug PARTITIONS. */
! extern void debug_rdg_partitions (VEC (bitmap, heap) *);
DEBUG_FUNCTION void
! debug_rdg_partitions (VEC (bitmap, heap) *partitions)
{
dump_rdg_partitions (stderr, partitions);
}
--- 978,997 ----
/* Dump to FILE the PARTITIONS. */
static void
! dump_rdg_partitions (FILE *file, VEC (partition_t, heap) *partitions)
{
int i;
! partition_t partition;
! FOR_EACH_VEC_ELT (partition_t, partitions, i, partition)
! debug_bitmap_file (file, partition->stmts);
}
/* Debug PARTITIONS. */
! extern void debug_rdg_partitions (VEC (partition_t, heap) *);
DEBUG_FUNCTION void
! debug_rdg_partitions (VEC (partition_t, heap) *partitions)
{
dump_rdg_partitions (stderr, partitions);
}
*************** number_of_rw_in_rdg (struct graph *rdg)
*** 989,1001 ****
the RDG. */
static int
! number_of_rw_in_partition (struct graph *rdg, bitmap partition)
{
int res = 0;
unsigned i;
bitmap_iterator ii;
! EXECUTE_IF_SET_IN_BITMAP (partition, 0, i, ii)
{
if (RDG_MEM_WRITE_STMT (rdg, i))
++res;
--- 1019,1031 ----
the RDG. */
static int
! number_of_rw_in_partition (struct graph *rdg, partition_t partition)
{
int res = 0;
unsigned i;
bitmap_iterator ii;
! EXECUTE_IF_SET_IN_BITMAP (partition->stmts, 0, i, ii)
{
if (RDG_MEM_WRITE_STMT (rdg, i))
++res;
*************** number_of_rw_in_partition (struct graph
*** 1011,1023 ****
write operations of RDG. */
static bool
! partition_contains_all_rw (struct graph *rdg, VEC (bitmap, heap) *partitions)
{
int i;
! bitmap partition;
int nrw = number_of_rw_in_rdg (rdg);
! FOR_EACH_VEC_ELT (bitmap, partitions, i, partition)
if (nrw == number_of_rw_in_partition (rdg, partition))
return true;
--- 1041,1053 ----
write operations of RDG. */
static bool
! partition_contains_all_rw (struct graph *rdg, VEC (partition_t, heap) *partitions)
{
int i;
! partition_t partition;
int nrw = number_of_rw_in_rdg (rdg);
! FOR_EACH_VEC_ELT (partition_t, partitions, i, partition)
if (nrw == number_of_rw_in_partition (rdg, partition))
return true;
*************** ldist_gen (struct loop *loop, struct gra
*** 1033,1041 ****
{
int i, nbp;
VEC (rdgc, heap) *components = VEC_alloc (rdgc, heap, 3);
! VEC (bitmap, heap) *partitions = VEC_alloc (bitmap, heap, 3);
VEC (int, heap) *other_stores = VEC_alloc (int, heap, 3);
! bitmap partition, processed = BITMAP_ALLOC (NULL);
remaining_stmts = BITMAP_ALLOC (NULL);
upstream_mem_writes = BITMAP_ALLOC (NULL);
--- 1063,1072 ----
{
int i, nbp;
VEC (rdgc, heap) *components = VEC_alloc (rdgc, heap, 3);
! VEC (partition_t, heap) *partitions = VEC_alloc (partition_t, heap, 3);
VEC (int, heap) *other_stores = VEC_alloc (int, heap, 3);
! partition_t partition;
! bitmap processed = BITMAP_ALLOC (NULL);
remaining_stmts = BITMAP_ALLOC (NULL);
upstream_mem_writes = BITMAP_ALLOC (NULL);
*************** ldist_gen (struct loop *loop, struct gra
*** 1069,1079 ****
rdg_build_partitions (rdg, components, &other_stores, &partitions,
processed);
BITMAP_FREE (processed);
- nbp = VEC_length (bitmap, partitions);
if (nbp == 0
|| (nbp == 1
! && !can_generate_builtin (rdg, VEC_index (bitmap, partitions, 0)))
|| (nbp > 1
&& partition_contains_all_rw (rdg, partitions)))
goto ldist_done;
--- 1100,1111 ----
rdg_build_partitions (rdg, components, &other_stores, &partitions,
processed);
BITMAP_FREE (processed);
+ nbp = VEC_length (partition_t, partitions);
if (nbp == 0
|| (nbp == 1
! && !can_generate_builtin (rdg,
! VEC_index (partition_t, partitions, 0)))
|| (nbp > 1
&& partition_contains_all_rw (rdg, partitions)))
goto ldist_done;
*************** ldist_gen (struct loop *loop, struct gra
*** 1081,1087 ****
if (dump_file && (dump_flags & TDF_DETAILS))
dump_rdg_partitions (dump_file, partitions);
! FOR_EACH_VEC_ELT (bitmap, partitions, i, partition)
if (!generate_code_for_partition (loop, partition, i < nbp - 1))
goto ldist_done;
--- 1113,1119 ----
if (dump_file && (dump_flags & TDF_DETAILS))
dump_rdg_partitions (dump_file, partitions);
! FOR_EACH_VEC_ELT (partition_t, partitions, i, partition)
if (!generate_code_for_partition (loop, partition, i < nbp - 1))
goto ldist_done;
*************** ldist_gen (struct loop *loop, struct gra
*** 1094,1104 ****
BITMAP_FREE (remaining_stmts);
BITMAP_FREE (upstream_mem_writes);
! FOR_EACH_VEC_ELT (bitmap, partitions, i, partition)
! BITMAP_FREE (partition);
VEC_free (int, heap, other_stores);
! VEC_free (bitmap, heap, partitions);
free_rdg_components (components);
return nbp;
}
--- 1126,1136 ----
BITMAP_FREE (remaining_stmts);
BITMAP_FREE (upstream_mem_writes);
! FOR_EACH_VEC_ELT (partition_t, partitions, i, partition)
! partition_free (partition);
VEC_free (int, heap, other_stores);
! VEC_free (partition_t, heap, partitions);
free_rdg_components (components);
return nbp;
}
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2012-05-31 14:01 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-05-31 14:01 [PATCH][2/n] loop distribution TLC Richard Guenther
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).