[prev in list] [next in list] [prev in thread] [next in thread]
List: gcc-patches
Subject: Re: [patch]: To remove the Reaching Uses dataflow problem.
From: Kenneth Zadeck <zadeck () naturalbridge ! com>
Date: 2007-07-31 16:26:21
Message-ID: 46AF62AD.4060402 () naturalbridge ! com
[Download RAW message or body]
Seongbae Park (???, ???) wrote:
> On 7/31/07, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:
>
>> Because of recent improvements to ddg.c, the reaching uses problem is no
>> longer used.
>> I am deleting it because it is not really a useful dataflow problem in
>> that it tends to be more expensive to compute than reaching defs but
>> provides little extra information.
>>
>> Removing the code will discourage any subsequent usage.
>>
>> I bootstrapped this change on x86-64.
>>
>> Ok for commit?
>>
>> Kenny
>>
>> 2007-07-31 Kenneth Zadeck <zadeck@naturalbridge.com>
>>
>> * df.h (DF_RU, DF_RU_BB_INFO, df_ru_bb_info, df_ru,
>> df_ru_add_problem, df_ru_get_bb_info): Removed.
>> (DF_RD, DF_UREC, DF_CHAIN, DF_NOTE): Renumbered.
>> * df-problems.c (df_ru_problem_data, df_ru_set_bb_info,
>> df_ru_free_bb_info, df_ru_alloc,
>> df_ru_bb_local_compute_process_def,
>> df_ru_bb_local_compute_process_use, df_ru_bb_local_compute,
>> df_ru_local_compute, df_ru_init_solution, df_ru_confluence_n,
>> df_ru_transfer_function, df_ru_free, df_ru_start_dump,
>> df_ru_top_dump, df_ru_bottom_dump, df_problem problem_RU,
>> df_ru_add_problem): Removed.
>>
>
> Looks great to me.
>
committed as revision 127099
["noRU1.diff" (text/x-patch)]
Index: df.h
===================================================================
--- df.h (revision 127089)
+++ df.h (working copy)
@@ -44,11 +44,10 @@ struct df_link;
#define DF_LR 1 /* Live Registers backward. */
#define DF_LIVE 2 /* Live Registers & Uninitialized Registers */
-#define DF_RU 3 /* Reaching Uses. */
-#define DF_RD 4 /* Reaching Defs. */
-#define DF_UREC 5 /* Uninitialized Registers with Early Clobber. */
-#define DF_CHAIN 6 /* Def-Use and/or Use-Def Chains. */
-#define DF_NOTE 7 /* REG_DEF and REG_UNUSED notes. */
+#define DF_RD 3 /* Reaching Defs. */
+#define DF_UREC 4 /* Uninitialized Registers with Early Clobber. */
+#define DF_CHAIN 5 /* Def-Use and/or Use-Def Chains. */
+#define DF_NOTE 6 /* REG_DEF and REG_UNUSED notes. */
#define DF_LAST_PROBLEM_PLUS1 (DF_NOTE + 1)
@@ -541,7 +540,6 @@ struct df
};
#define DF_SCAN_BB_INFO(BB) (df_scan_get_bb_info((BB)->index))
-#define DF_RU_BB_INFO(BB) (df_ru_get_bb_info((BB)->index))
#define DF_RD_BB_INFO(BB) (df_rd_get_bb_info((BB)->index))
#define DF_LR_BB_INFO(BB) (df_lr_get_bb_info((BB)->index))
#define DF_UREC_BB_INFO(BB) (df_urec_get_bb_info((BB)->index))
@@ -694,30 +692,6 @@ struct df_scan_bb_info
};
-/* Reaching uses. All bitmaps are indexed by the id field of the ref
- except sparse_kill (see below). */
-struct df_ru_bb_info
-{
- /* Local sets to describe the basic blocks. */
- /* The kill set is the set of uses that are killed in this block.
- However, if the number of uses for this register is greater than
- DF_SPARSE_THRESHOLD, the sparse_kill is used instead. In
- sparse_kill, each register gets a slot and a 1 in this bitvector
- means that all of the uses of that register are killed. This is
- a very useful efficiency hack in that it keeps from having push
- around big groups of 1s. This is implemented by the
- bitmap_clear_range call. */
-
- bitmap kill;
- bitmap sparse_kill;
- bitmap gen; /* The set of uses generated in this block. */
-
- /* The results of the dataflow problem. */
- bitmap in; /* At the top of the block. */
- bitmap out; /* At the bottom of the block. */
-};
-
-
/* Reaching definitions. All bitmaps are indexed by the id field of
the ref except sparse_kill (see above). */
struct df_rd_bb_info
@@ -807,7 +781,6 @@ struct df_urec_bb_info
should not be used by regular code. */
extern struct df *df;
#define df_scan (df->problems_by_index[DF_SCAN])
-#define df_ru (df->problems_by_index[DF_RU])
#define df_rd (df->problems_by_index[DF_RD])
#define df_lr (df->problems_by_index[DF_LR])
#define df_live (df->problems_by_index[DF_LIVE])
@@ -889,7 +862,6 @@ extern bitmap df_get_live_top (basic_blo
extern void df_grow_bb_info (struct dataflow *);
extern void df_chain_dump (struct df_link *, FILE *);
extern void df_print_bb_index (basic_block bb, FILE *file);
-extern void df_ru_add_problem (void);
extern void df_rd_add_problem (void);
extern void df_lr_add_problem (void);
extern void df_lr_verify_transfer_functions (void);
@@ -954,15 +926,6 @@ df_scan_get_bb_info (unsigned int index)
return NULL;
}
-static inline struct df_ru_bb_info *
-df_ru_get_bb_info (unsigned int index)
-{
- if (index < df_ru->block_info_size)
- return (struct df_ru_bb_info *) df_ru->block_info[index];
- else
- return NULL;
-}
-
static inline struct df_rd_bb_info *
df_rd_get_bb_info (unsigned int index)
{
Index: df-problems.c
===================================================================
--- df-problems.c (revision 127089)
+++ df-problems.c (working copy)
@@ -202,536 +202,6 @@ df_unset_seen (void)
/*----------------------------------------------------------------------------
- REACHING USES
-
- Find the locations in the function where each use site for a pseudo
- can reach backwards. In and out bitvectors are built for each basic
- block. The id field in the ref is used to index into these sets.
- See df.h for details.
-
-----------------------------------------------------------------------------*/
-
-/* This problem plays a large number of games for the sake of
- efficiency.
-
- 1) The order of the bits in the bitvectors. After the scanning
- phase, all of the uses are sorted. All of the uses for the reg 0
- are first, followed by all uses for reg 1 and so on.
-
- 2) There are two kill sets, one if the number of uses is less or
- equal to DF_SPARSE_THRESHOLD and another if it is greater.
-
- <= : Data is built directly in the kill set.
-
- > : One level of indirection is used to keep from generating long
- strings of 1 bits in the kill sets. Bitvectors that are indexed
- by the regnum are used to represent that there is a killing def
- for the register. The confluence and transfer functions use
- these along with the bitmap_clear_range call to remove ranges of
- bits without actually generating a knockout vector.
-
- The kill and sparse_kill and the dense_invalidated_by_call and
- sparse_invalidated_by_call both play this game. */
-
-/* Private data used to compute the solution for this problem. These
- data structures are not accessible outside of this module. */
-struct df_ru_problem_data
-{
- /* The set of defs to regs invalidated by call. */
- bitmap sparse_invalidated_by_call;
- /* The set of defs to regs invalidated by call for ru. */
- bitmap dense_invalidated_by_call;
- /* An obstack for the bitmaps we need for this problem. */
- bitmap_obstack ru_bitmaps;
-};
-
-/* Set basic block info. */
-
-static void
-df_ru_set_bb_info (unsigned int index, struct df_ru_bb_info *bb_info)
-{
- gcc_assert (df_ru);
- gcc_assert (index < df_ru->block_info_size);
- df_ru->block_info[index] = bb_info;
-}
-
-
-/* Free basic block info. */
-
-static void
-df_ru_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
- void *vbb_info)
-{
- struct df_ru_bb_info *bb_info = (struct df_ru_bb_info *) vbb_info;
- if (bb_info)
- {
- BITMAP_FREE (bb_info->kill);
- BITMAP_FREE (bb_info->sparse_kill);
- BITMAP_FREE (bb_info->gen);
- BITMAP_FREE (bb_info->in);
- BITMAP_FREE (bb_info->out);
- pool_free (df_ru->block_pool, bb_info);
- }
-}
-
-
-/* Allocate or reset bitmaps for DF_RU blocks. The solution bits are
- not touched unless the block is new. */
-
-static void
-df_ru_alloc (bitmap all_blocks)
-{
- unsigned int bb_index;
- bitmap_iterator bi;
- struct df_ru_problem_data *problem_data;
-
- if (!df_ru->block_pool)
- df_ru->block_pool = create_alloc_pool ("df_ru_block pool",
- sizeof (struct df_ru_bb_info), 50);
-
- if (df_ru->problem_data)
- {
- problem_data = (struct df_ru_problem_data *) df_ru->problem_data;
- bitmap_clear (problem_data->sparse_invalidated_by_call);
- bitmap_clear (problem_data->dense_invalidated_by_call);
- }
- else
- {
- problem_data = XNEW (struct df_ru_problem_data);
- df_ru->problem_data = problem_data;
-
- bitmap_obstack_initialize (&problem_data->ru_bitmaps);
- problem_data->sparse_invalidated_by_call
- = BITMAP_ALLOC (&problem_data->ru_bitmaps);
- problem_data->dense_invalidated_by_call
- = BITMAP_ALLOC (&problem_data->ru_bitmaps);
- }
-
- df_grow_bb_info (df_ru);
-
- /* Because of the clustering of all def sites for the same pseudo,
- we have to process all of the blocks before doing the
- analysis. */
-
- EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
- {
- struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb_index);
- if (bb_info)
- {
- bitmap_clear (bb_info->kill);
- bitmap_clear (bb_info->sparse_kill);
- bitmap_clear (bb_info->gen);
- }
- else
- {
- bb_info = (struct df_ru_bb_info *) pool_alloc (df_ru->block_pool);
- df_ru_set_bb_info (bb_index, bb_info);
- bb_info->kill = BITMAP_ALLOC (&problem_data->ru_bitmaps);
- bb_info->sparse_kill = BITMAP_ALLOC (&problem_data->ru_bitmaps);
- bb_info->gen = BITMAP_ALLOC (&problem_data->ru_bitmaps);
- bb_info->in = BITMAP_ALLOC (&problem_data->ru_bitmaps);
- bb_info->out = BITMAP_ALLOC (&problem_data->ru_bitmaps);
- }
- }
- df_ru->optional_p = true;
-}
-
-
-/* Process a list of DEFs for df_ru_bb_local_compute. */
-
-static void
-df_ru_bb_local_compute_process_def (struct df_ru_bb_info *bb_info,
- struct df_ref **def_rec,
- enum df_ref_flags top_flag)
-{
- while (*def_rec)
- {
- struct df_ref *def = *def_rec;
- if ((top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
- /* If the def is to only part of the reg, it is as if it did
- not happen, since some of the bits may get thru. */
- && (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))))
- {
- unsigned int regno = DF_REF_REGNO (def);
- unsigned int begin = DF_USES_BEGIN (regno);
- unsigned int n_uses = DF_USES_COUNT (regno);
-
- if (!bitmap_bit_p (seen_in_block, regno))
- {
- /* The first def for regno in the insn, causes the kill
- info to be generated. Do not modify the gen set
- because the only values in it are the uses from here
- to the top of the block and this def does not effect
- them. */
- if (!bitmap_bit_p (seen_in_insn, regno))
- {
- if (n_uses > DF_SPARSE_THRESHOLD)
- bitmap_set_bit (bb_info->sparse_kill, regno);
- else
- bitmap_set_range (bb_info->kill, begin, n_uses);
- }
- bitmap_set_bit (seen_in_insn, regno);
- }
- }
- def_rec++;
- }
-}
-
-
-/* Process a list of USEs for df_ru_bb_local_compute. */
-
-static void
-df_ru_bb_local_compute_process_use (struct df_ru_bb_info *bb_info,
- struct df_ref **use_rec,
- enum df_ref_flags top_flag)
-{
- while (*use_rec)
- {
- struct df_ref *use = *use_rec;
- if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
- {
- /* Add use to set of gens in this BB unless we have seen a
- def in a previous instruction. */
- unsigned int regno = DF_REF_REGNO (use);
- if (!bitmap_bit_p (seen_in_block, regno))
- bitmap_set_bit (bb_info->gen, DF_REF_ID (use));
- }
- use_rec++;
- }
-}
-
-/* Compute local reaching use (upward exposed use) info for basic
- block BB. USE_INFO->REGS[R] caches the set of uses for register R. */
-static void
-df_ru_bb_local_compute (unsigned int bb_index)
-{
- basic_block bb = BASIC_BLOCK (bb_index);
- struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb_index);
- rtx insn;
-
- /* Set when a def for regno is seen. */
- bitmap_clear (seen_in_block);
- bitmap_clear (seen_in_insn);
-
-#ifdef EH_USES
- /* Variables defined in the prolog that are used by the exception
- handler. */
- df_ru_bb_local_compute_process_use (bb_info,
- df_get_artificial_uses (bb_index),
- DF_REF_AT_TOP);
-#endif
- df_ru_bb_local_compute_process_def (bb_info,
- df_get_artificial_defs (bb_index),
- DF_REF_AT_TOP);
-
- FOR_BB_INSNS (bb, insn)
- {
- unsigned int uid = INSN_UID (insn);
- if (!INSN_P (insn))
- continue;
-
- df_ru_bb_local_compute_process_use (bb_info,
- DF_INSN_UID_USES (uid), 0);
-
- if (df->changeable_flags & DF_EQ_NOTES)
- df_ru_bb_local_compute_process_use (bb_info,
- DF_INSN_UID_EQ_USES (uid), 0);
-
- df_ru_bb_local_compute_process_def (bb_info,
- DF_INSN_UID_DEFS (uid), 0);
-
- bitmap_ior_into (seen_in_block, seen_in_insn);
- bitmap_clear (seen_in_insn);
- }
-
- /* Process the hardware registers that are always live. */
- df_ru_bb_local_compute_process_use (bb_info,
- df_get_artificial_uses (bb_index), 0);
-
- df_ru_bb_local_compute_process_def (bb_info,
- df_get_artificial_defs (bb_index), 0);
-}
-
-
-/* Compute local reaching use (upward exposed use) info for each basic
- block within BLOCKS. */
-static void
-df_ru_local_compute (bitmap all_blocks)
-{
- unsigned int bb_index;
- bitmap_iterator bi;
- unsigned int regno;
- struct df_ru_problem_data *problem_data
- = (struct df_ru_problem_data *) df_ru->problem_data;
- bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
- bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
-
- df_set_seen ();
-
- df_maybe_reorganize_use_refs (df->changeable_flags & DF_EQ_NOTES ?
- DF_REF_ORDER_BY_REG_WITH_NOTES : DF_REF_ORDER_BY_REG);
-
- EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
- {
- df_ru_bb_local_compute (bb_index);
- }
-
- /* Set up the knockout bit vectors to be applied across EH_EDGES. */
- EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, regno, bi)
- {
- if (DF_USES_COUNT (regno) > DF_SPARSE_THRESHOLD)
- bitmap_set_bit (sparse_invalidated, regno);
- else
- bitmap_set_range (dense_invalidated,
- DF_USES_BEGIN (regno),
- DF_USES_COUNT (regno));
- }
-
- df_unset_seen ();
-}
-
-
-/* Initialize the solution bit vectors for problem. */
-
-static void
-df_ru_init_solution (bitmap all_blocks)
-{
- unsigned int bb_index;
- bitmap_iterator bi;
-
- EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
- {
- struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb_index);
- bitmap_copy (bb_info->in, bb_info->gen);
- bitmap_clear (bb_info->out);
- }
-}
-
-
-/* Out of target gets or of in of source. */
-
-static void
-df_ru_confluence_n (edge e)
-{
- bitmap op1 = df_ru_get_bb_info (e->src->index)->out;
- bitmap op2 = df_ru_get_bb_info (e->dest->index)->in;
-
- if (e->flags & EDGE_EH)
- {
- struct df_ru_problem_data *problem_data
- = (struct df_ru_problem_data *) df_ru->problem_data;
- bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
- bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
- bitmap_iterator bi;
- unsigned int regno;
- bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
-
- bitmap_copy (tmp, op2);
- bitmap_and_compl_into (tmp, dense_invalidated);
-
- EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
- {
- bitmap_clear_range (tmp,
- DF_USES_BEGIN (regno),
- DF_USES_COUNT (regno));
- }
- bitmap_ior_into (op1, tmp);
- BITMAP_FREE (tmp);
- }
- else
- bitmap_ior_into (op1, op2);
-}
-
-
-/* Transfer function. */
-
-static bool
-df_ru_transfer_function (int bb_index)
-{
- struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb_index);
- unsigned int regno;
- bitmap_iterator bi;
- bitmap in = bb_info->in;
- bitmap out = bb_info->out;
- bitmap gen = bb_info->gen;
- bitmap kill = bb_info->kill;
- bitmap sparse_kill = bb_info->sparse_kill;
-
- if (bitmap_empty_p (sparse_kill))
- return bitmap_ior_and_compl (in, gen, out, kill);
- else
- {
- struct df_ru_problem_data *problem_data;
- bitmap tmp;
- bool changed = false;
-
- /* Note that TMP is _not_ a temporary bitmap if we end up replacing
- IN with TMP. Therefore, allocate TMP in the RU bitmaps obstack. */
- problem_data = (struct df_ru_problem_data *) df_ru->problem_data;
- tmp = BITMAP_ALLOC (&problem_data->ru_bitmaps);
-
- bitmap_copy (tmp, out);
- EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
- {
- bitmap_clear_range (tmp,
- DF_USES_BEGIN (regno),
- DF_USES_COUNT (regno));
- }
- bitmap_and_compl_into (tmp, kill);
- bitmap_ior_into (tmp, gen);
- changed = !bitmap_equal_p (tmp, in);
- if (changed)
- {
- BITMAP_FREE (in);
- bb_info->in = tmp;
- }
- else
- BITMAP_FREE (tmp);
- return changed;
- }
-}
-
-
-/* Free all storage associated with the problem. */
-
-static void
-df_ru_free (void)
-{
- unsigned int i;
- struct df_ru_problem_data *problem_data
- = (struct df_ru_problem_data *) df_ru->problem_data;
-
- if (problem_data)
- {
- for (i = 0; i < df_ru->block_info_size; i++)
- {
- struct df_ru_bb_info *bb_info = df_ru_get_bb_info (i);
- if (bb_info)
- {
- BITMAP_FREE (bb_info->kill);
- BITMAP_FREE (bb_info->sparse_kill);
- BITMAP_FREE (bb_info->gen);
- BITMAP_FREE (bb_info->in);
- BITMAP_FREE (bb_info->out);
- }
- }
-
- free_alloc_pool (df_ru->block_pool);
- BITMAP_FREE (problem_data->sparse_invalidated_by_call);
- BITMAP_FREE (problem_data->dense_invalidated_by_call);
- bitmap_obstack_release (&problem_data->ru_bitmaps);
-
- df_ru->block_info_size = 0;
- free (df_ru->block_info);
- free (df_ru->problem_data);
- }
- free (df_ru);
-}
-
-
-/* Debugging info. */
-
-static void
-df_ru_start_dump (FILE *file)
-{
- struct df_ru_problem_data *problem_data
- = (struct df_ru_problem_data *) df_ru->problem_data;
- unsigned int m = DF_REG_SIZE(df);
- unsigned int regno;
-
- if (!df_ru->block_info)
- return;
-
- fprintf (file, ";; Reaching uses:\n");
-
- fprintf (file, ";; sparse invalidated \t");
- dump_bitmap (file, problem_data->sparse_invalidated_by_call);
- fprintf (file, " dense invalidated \t");
- dump_bitmap (file, problem_data->dense_invalidated_by_call);
-
- for (regno = 0; regno < m; regno++)
- if (DF_USES_COUNT (regno))
- fprintf (file, "%d[%d,%d] ", regno,
- DF_USES_BEGIN (regno),
- DF_USES_COUNT (regno));
- fprintf (file, "\n");
-}
-
-
-/* Debugging info at top of bb. */
-
-static void
-df_ru_top_dump (basic_block bb, FILE *file)
-{
- struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb->index);
- if (!bb_info || !bb_info->in)
- return;
-
- fprintf (file, ";; ru in \t(%d)\n", (int) bitmap_count_bits (bb_info->in));
- dump_bitmap (file, bb_info->in);
- fprintf (file, ";; ru gen \t(%d)\n", (int) bitmap_count_bits (bb_info->gen));
- dump_bitmap (file, bb_info->gen);
- fprintf (file, ";; ru kill\t(%d)\n", (int) bitmap_count_bits (bb_info->kill));
- dump_bitmap (file, bb_info->kill);
-}
-
-
-/* Debugging info at bottom of bb. */
-
-static void
-df_ru_bottom_dump (basic_block bb, FILE *file)
-{
- struct df_ru_bb_info *bb_info = df_ru_get_bb_info (bb->index);
- if (!bb_info || !bb_info->out)
- return;
-
- fprintf (file, ";; ru out \t(%d)\n", (int) bitmap_count_bits (bb_info->out));
- dump_bitmap (file, bb_info->out);
-}
-
-
-/* All of the information associated with every instance of the problem. */
-
-static struct df_problem problem_RU =
-{
- DF_RU, /* Problem id. */
- DF_BACKWARD, /* Direction. */
- df_ru_alloc, /* Allocate the problem specific data. */
- NULL, /* Reset global information. */
- df_ru_free_bb_info, /* Free basic block info. */
- df_ru_local_compute, /* Local compute function. */
- df_ru_init_solution, /* Init the solution specific data. */
- df_worklist_dataflow, /* Worklist solver. */
- NULL, /* Confluence operator 0. */
- df_ru_confluence_n, /* Confluence operator n. */
- df_ru_transfer_function, /* Transfer function. */
- NULL, /* Finalize function. */
- df_ru_free, /* Free all of the problem information. */
- df_ru_free, /* Remove this problem from the stack of dataflow problems. */
- df_ru_start_dump, /* Debugging. */
- df_ru_top_dump, /* Debugging start block. */
- df_ru_bottom_dump, /* Debugging end block. */
- NULL, /* Incremental solution verify start. */
- NULL, /* Incremental solution verify end. */
- NULL, /* Dependent problem. */
- TV_DF_RU, /* Timing variable. */
- true /* Reset blocks on dropping out of blocks_to_analyze. */
-};
-
-
-
-/* Create a new DATAFLOW instance and add it to an existing instance
- of DF. The returned structure is what is used to get at the
- solution. */
-
-void
-df_ru_add_problem (void)
-{
- df_add_problem (&problem_RU);
-}
-
-
-/*----------------------------------------------------------------------------
REACHING DEFINITIONS
Find the locations in the function where each definition site for a
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic