This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[dataflow]: PATCH COMMITTED to improve compile time and space.
- From: Kenneth Zadeck <zadeck at naturalbridge dot com>
- To: gcc-patches <gcc-patches at gcc dot gnu dot org>, "Park, Seongbae" <seongbae dot park at gmail dot com>, Steven Bosscher <stevenb dot gcc at gmail dot com>, "Zadeck, Kenneth" <zadeck at naturalbridge dot com>, "Bonzini, Paolo" <bonzini at gnu dot org>, "Hubicha, Jan" <jh at suse dot cz>
- Date: Fri, 27 Apr 2007 16:44:04 -0400
- Subject: [dataflow]: PATCH COMMITTED to improve compile time and space.
This patch addresses two compile time issues and one compile space issue.
1) Alloc_pool has been modified so that it does not immediately kill the
cache whenever it needs a new block from the os. This was caused by
immediately
formatting the block onto the free list, a process that touched the
entire block.
Now, there are two free lists, the returned_free_list handles objects
that have been returned from the client. The virgin_free_list holds the
latest block obtained from the os, and formats it as needed.
This speeds up compilation on one of my machines by 1 to 2 percent.
Your mileage will vary. I also played around with increasing the
pool_sizes of various alloc pools. Before this change, this was a
definite loosing proposition. However, it has been hard for me to find
a stable enough platform to test this, and the gain will again vary a
lot by architecture.
2) The marked bitmap was changed to an sbitmap since this bitmap will
generally be mostly full.
3) The ur df problem and the live df problem have been merged. This
saves two bitmaps per basic block. It may save a little time, but
mostly this was a space move. As it turns out there was only one
remaining place that used the output of the ur problem directly and this
was easily changed to use live.
This has been bootstrapped and regression tested on x86-64, x86-32, ppc
and ia-64.
Honza, could you please run the memtester on this again?
Kenny
2007-04-27 Kenneth Zadeck <zadeck@naturalbridge.com>
* timevar.def (TV_DF_UR): Removed.
* df-scan.c (df_scan_alloc): Change pool size.
* df-core.c (df_finish_pass, rest_of_handle_df_initialize,
df_get_bb_dirty, df_verify): Merged df_ur and df_live problems
into df_live.
* global.c (compute_regsets, rest_of_handle_global_alloc): Ditto.
* df.h (DF_UR, DF_UR_BB_INFO, DF_UR_IN, DF_UR_OUT, df_ur,
df_ur_get_bb_info): Removed.
(df_ur_bb_info): Merged df_ur and df_live problems
into df_live.
* init-regs.c (initialize_uninitialized_regs): Changed DF_UR_IN to
DF_LIVE_IN.
* df_problems.c (df_ur_problem_data): Renamed to
df_live_problem_data.
(df_ur_set_bb_info): Renamed to df_live_set_bb_info.
(df_ur_free_bb_info): Renamed to df_live_free_bb_info.
(df_ur_alloc): Renamed to df_live_alloc.
(df_ur_reset): Renamed to df_live_reset.
(df_ur_bb_local_compute): Renamed to df_live_bb_local_compute.
(df_ur_local_compute): Renamed to df_live_local_compute.
(df_ur_init): Renamed to df_live_init.
(df_ur_confluence_n): Renamed to df_live_confluence_n.
(df_ur_transfer_function): Renamed to df_live_transfer_function.
(df_ur_local_finalize): Removed.
(df_ur_free): Renamed to df_live_free.
(df_ur_top_dump): Renamed to df_live_top_dump.
(df_ur_bottom_dump): Renamed to df_live_bottom_dump.
(df_ur_verify_solution_start): Renamed to
df_live_verify_solution_start.
(df_ur_verify_solution_end): Renamed to
df_live_verify_solution_end.
(problem_UR): Renamed to problem_LIVE.
(df_ur_add_problem): Renamed to df_live_add_problem.
(df_ur_verify_transfer_functions): Renamed to
df_live_verify_transfer_functions.
(df_live_set_bb_info, df_live_free_bb_info, df_live_alloc,
df_live_free, df_live_top_dump, df_live_bottom_dump,
df_live_add_problem): Deleted.
(df_chain_fully_remove_problem): Changed pool alloc block size.
* dce.c (dce_marked_bitmap_obstack): Removed.
(marked_insn_p, mark_insn, init_dce, end_ud_dce, fini_dce,
fast_dce): Changed marked to be sbitmap rather than bitmap.
* alloc_pool.c (create_alloc_pool, pool_alloc, pool_free): Split
free_list into virgin_free_list and returned_free_list.
* alloc_pool.h (free_list): Split into virgin_free_list and
returned_free_list.
(virgin_elts_remaining): New variable.
Index: timevar.def
===================================================================
--- timevar.def (revision 124202)
+++ timevar.def (working copy)
@@ -62,7 +62,6 @@ DEFTIMEVAR (TV_DF_SCAN , "df scan
DEFTIMEVAR (TV_DF_RU , "df reaching uses")
DEFTIMEVAR (TV_DF_RD , "df reaching defs")
DEFTIMEVAR (TV_DF_LR , "df live regs")
-DEFTIMEVAR (TV_DF_UR , "df uninitialized regs")
DEFTIMEVAR (TV_DF_LIVE , "df live&initialized regs")
DEFTIMEVAR (TV_DF_UREC , "df uninitialized regs 2")
DEFTIMEVAR (TV_DF_CHAIN , "df use-def / def-use chains")
Index: df-scan.c
===================================================================
--- df-scan.c (revision 124202)
+++ df-scan.c (working copy)
@@ -278,7 +278,7 @@ df_scan_alloc (bitmap all_blocks ATTRIBU
{
struct df_scan_problem_data *problem_data;
unsigned int insn_num = get_max_uid () + 1;
- unsigned int block_size = 50;
+ unsigned int block_size = 400;
basic_block bb;
/* Given the number of pools, this is really faster than tearing
Index: df-core.c
===================================================================
--- df-core.c (revision 124202)
+++ df-core.c (working copy)
@@ -689,8 +689,8 @@ df_finish_pass (void)
if (!(saved_flags & DF_NO_INSN_RESCAN))
{
df_lr_verify_transfer_functions ();
- if (df_ur)
- df_ur_verify_transfer_functions ();
+ if (df_live)
+ df_live_verify_transfer_functions ();
}
#ifdef DF_DEBUG_CFG
@@ -721,10 +721,7 @@ rest_of_handle_df_initialize (void)
/* These three problems are permanent. */
df_lr_add_problem ();
if (optimize)
- {
- df_ur_add_problem ();
- df_live_add_problem ();
- }
+ df_live_add_problem ();
df->postorder = XNEWVEC (int, last_basic_block);
df->postorder_inverted = XNEWVEC (int, last_basic_block);
@@ -1486,7 +1483,7 @@ bool
df_get_bb_dirty (basic_block bb)
{
if (df)
- return bitmap_bit_p (df_ur->out_of_date_transfer_functions, bb->index);
+ return bitmap_bit_p (df_live->out_of_date_transfer_functions, bb->index);
else
return false;
}
@@ -1715,8 +1712,8 @@ df_verify (void)
{
df_scan_verify ();
df_lr_verify_transfer_functions ();
- if (df_ur)
- df_ur_verify_transfer_functions ();
+ if (df_live)
+ df_live_verify_transfer_functions ();
}
#ifdef DF_DEBUG_CFG
Index: global.c
===================================================================
--- global.c (revision 124202)
+++ global.c (working copy)
@@ -405,7 +405,6 @@ compute_regsets (HARD_REG_SET *elim_set,
if (optimize)
{
df_remove_problem (df_live);
- df_remove_problem (df_ur);
df_urec_add_problem ();
}
df_analyze ();
@@ -2135,10 +2134,7 @@ rest_of_handle_global_alloc (void)
and defs. */
df_finish_pass ();
if (optimize)
- {
- df_ur_add_problem ();
- df_live_add_problem ();
- }
+ df_live_add_problem ();
df_scan_alloc (NULL);
df_scan_blocks ();
Index: df.h
===================================================================
--- df.h (revision 124202)
+++ df.h (working copy)
@@ -43,14 +43,13 @@ struct df_link;
last 5 are optional and can be added or deleted at any time. */
#define DF_SCAN 0
#define DF_LR 1 /* Live Registers backward. */
-#define DF_UR 2 /* Uninitialized Registers forwards. */
-#define DF_LIVE 3 /* Live Registers & Uninitialized Registers */
+#define DF_LIVE 2 /* Live Registers & Uninitialized Registers */
-#define DF_RU 4 /* Reaching Uses. */
-#define DF_RD 5 /* Reaching Defs. */
-#define DF_UREC 6 /* Uninitialized Registers with Early Clobber. */
-#define DF_CHAIN 7 /* Def-Use and/or Use-Def Chains. */
-#define DF_RI 8 /* Register Info. */
+#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_RI 7 /* Register Info. */
#define DF_LAST_PROBLEM_PLUS1 (DF_RI + 1)
#define DF_FIRST_OPTIONAL_PROBLEM DF_RU
@@ -268,7 +267,7 @@ struct dataflow
/* The pool to allocate the block_info from. */
alloc_pool block_pool;
- /* The lr and ur problems have their transfer functions recomputed
+ /* The lr and live problems have their transfer functions recomputed
only if necessary. This is possible for them because, the
problems are kept active for the entire backend and their
transfer functions are indexed by the REGNO. These are not
@@ -292,7 +291,7 @@ struct dataflow
/* True if the something has changed which invalidates the dataflow
solutions. Note that this bit is always true for all problems except
- lr, ur, and live. */
+ lr and live. */
bool solutions_dirty;
};
@@ -537,12 +536,11 @@ struct df
#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_UR_BB_INFO(BB) (df_ur_get_bb_info((BB)->index))
#define DF_UREC_BB_INFO(BB) (df_urec_get_bb_info((BB)->index))
#define DF_LIVE_BB_INFO(BB) (df_live_get_bb_info((BB)->index))
/* Most transformations that wish to use live register analysis will
- use these macros. This info is the and of the lr and ur sets. */
+ use these macros. This info is the and of the lr and live sets. */
#define DF_LIVE_IN(BB) (DF_LIVE_BB_INFO(BB)->in)
#define DF_LIVE_OUT(BB) (DF_LIVE_BB_INFO(BB)->out)
@@ -559,12 +557,6 @@ struct df
#define DF_LR_TOP(BB) (DF_LR_BB_INFO(BB)->top)
#define DF_LR_OUT(BB) (DF_LR_BB_INFO(BB)->out)
-/* These macros are currently used by only combine which needs to know
- what is really uninitialized. */
-#define DF_UR_IN(BB) (DF_UR_BB_INFO(BB)->in)
-#define DF_UR_OUT(BB) (DF_UR_BB_INFO(BB)->out)
-
-
/* Macros to access the elements within the ref structure. */
@@ -768,9 +760,11 @@ struct df_lr_bb_info
};
-
-/* Uninitialized registers. All bitmaps are referenced by the register number. */
-struct df_ur_bb_info
+/* Uninitialized registers. All bitmaps are referenced by the
+ register number. Anded results of the forwards and backward live
+ info. Note that the forwards live information is not available
+ separately. */
+struct df_live_bb_info
{
/* Local sets to describe the basic blocks. */
bitmap kill; /* The set of registers unset in this block. Calls,
@@ -782,14 +776,6 @@ struct df_ur_bb_info
bitmap out; /* At the bottom of the block. */
};
-/* Anded results of LR and UR. */
-struct df_live_bb_info
-{
- /* The results of the dataflow problem. */
- bitmap in; /* At the top of the block. */
- bitmap out; /* At the bottom of the block. */
-};
-
/* Uninitialized registers. All bitmaps are referenced by the register number. */
struct df_urec_bb_info
@@ -816,7 +802,6 @@ extern struct df *df;
#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_ur (df->problems_by_index[DF_UR])
#define df_live (df->problems_by_index[DF_LIVE])
#define df_urec (df->problems_by_index[DF_UREC])
#define df_chain (df->problems_by_index[DF_CHAIN])
@@ -904,8 +889,7 @@ extern void df_lr_simulate_artificial_re
extern void df_lr_simulate_one_insn (basic_block, rtx, bitmap);
extern void df_lr_add_problem (void);
extern void df_lr_verify_transfer_functions (void);
-extern void df_ur_add_problem (void);
-extern void df_ur_verify_transfer_functions (void);
+extern void df_live_verify_transfer_functions (void);
extern void df_live_add_problem (void);
extern void df_urec_add_problem (void);
extern void df_chain_add_problem (enum df_chain_flags);
@@ -986,15 +970,6 @@ df_lr_get_bb_info (unsigned int index)
return NULL;
}
-static inline struct df_ur_bb_info *
-df_ur_get_bb_info (unsigned int index)
-{
- if (index < df_ur->block_info_size)
- return (struct df_ur_bb_info *) df_ur->block_info[index];
- else
- return NULL;
-}
-
static inline struct df_live_bb_info *
df_live_get_bb_info (unsigned int index)
{
Index: init-regs.c
===================================================================
--- init-regs.c (revision 124202)
+++ init-regs.c (working copy)
@@ -60,7 +60,7 @@ initialize_uninitialized_regs (void)
{
rtx insn;
bitmap lr = DF_LR_IN (bb);
- bitmap ur = DF_UR_IN (bb);
+ bitmap ur = DF_LIVE_IN (bb);
bitmap_clear (already_genned);
FOR_BB_INSNS (bb, insn)
Index: df-problems.c
===================================================================
--- df-problems.c (revision 124202)
+++ df-problems.c (working copy)
@@ -2033,16 +2033,20 @@ df_lr_verify_transfer_functions (void)
/*----------------------------------------------------------------------------
- UNINITIALIZED REGISTERS
+ COMBINED LIVE REGISTERS AND UNINITIALIZED REGISTERS.
- Find the set of uses for registers that are reachable from the entry
- block without passing thru a definition. In and out bitvectors are built
- for each basic block. The regnum is used to index into these sets.
- See df.h for details.
+ First find the set of uses for registers that are reachable from
+ the entry block without passing thru a definition. In and out
+ bitvectors are built for each basic block. The regnum is used to
+ index into these sets. See df.h for details.
+
+ Then the in and out sets here are the anded results of the in and
+ out sets from the lr and ur
+ problems.
----------------------------------------------------------------------------*/
/* Private data used to verify the solution for this problem. */
-struct df_ur_problem_data
+struct df_live_problem_data
{
bitmap *in;
bitmap *out;
@@ -2052,51 +2056,51 @@ struct df_ur_problem_data
/* Set basic block info. */
static void
-df_ur_set_bb_info (unsigned int index,
- struct df_ur_bb_info *bb_info)
+df_live_set_bb_info (unsigned int index,
+ struct df_live_bb_info *bb_info)
{
- gcc_assert (df_ur);
- gcc_assert (index < df_ur->block_info_size);
- df_ur->block_info[index] = bb_info;
+ gcc_assert (df_live);
+ gcc_assert (index < df_live->block_info_size);
+ df_live->block_info[index] = bb_info;
}
/* Free basic block info. */
static void
-df_ur_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
+df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
void *vbb_info)
{
- struct df_ur_bb_info *bb_info = (struct df_ur_bb_info *) vbb_info;
+ struct df_live_bb_info *bb_info = (struct df_live_bb_info *) vbb_info;
if (bb_info)
{
BITMAP_FREE (bb_info->gen);
BITMAP_FREE (bb_info->kill);
BITMAP_FREE (bb_info->in);
BITMAP_FREE (bb_info->out);
- pool_free (df_ur->block_pool, bb_info);
+ pool_free (df_live->block_pool, bb_info);
}
}
-/* Allocate or reset bitmaps for DF_UR blocks. The solution bits are
+/* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
not touched unless the block is new. */
static void
-df_ur_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
+df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
{
unsigned int bb_index;
bitmap_iterator bi;
- if (!df_ur->block_pool)
- df_ur->block_pool = create_alloc_pool ("df_ur_block pool",
- sizeof (struct df_ur_bb_info), 100);
+ if (!df_live->block_pool)
+ df_live->block_pool = create_alloc_pool ("df_live_block pool",
+ sizeof (struct df_live_bb_info), 100);
- df_grow_bb_info (df_ur);
+ df_grow_bb_info (df_live);
- EXECUTE_IF_SET_IN_BITMAP (df_ur->out_of_date_transfer_functions, 0, bb_index, bi)
+ EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)
{
- struct df_ur_bb_info *bb_info = df_ur_get_bb_info (bb_index);
+ struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
if (bb_info)
{
bitmap_clear (bb_info->kill);
@@ -2104,8 +2108,8 @@ df_ur_alloc (bitmap all_blocks ATTRIBUTE
}
else
{
- bb_info = (struct df_ur_bb_info *) pool_alloc (df_ur->block_pool);
- df_ur_set_bb_info (bb_index, bb_info);
+ bb_info = (struct df_live_bb_info *) pool_alloc (df_live->block_pool);
+ df_live_set_bb_info (bb_index, bb_info);
bb_info->kill = BITMAP_ALLOC (NULL);
bb_info->gen = BITMAP_ALLOC (NULL);
bb_info->in = BITMAP_ALLOC (NULL);
@@ -2118,7 +2122,7 @@ df_ur_alloc (bitmap all_blocks ATTRIBUTE
/* Reset the global solution for recalculation. */
static void
-df_ur_reset (bitmap all_blocks)
+df_live_reset (bitmap all_blocks)
{
unsigned int bb_index;
bitmap_iterator bi;
@@ -2136,10 +2140,10 @@ df_ur_reset (bitmap all_blocks)
/* Compute local uninitialized register info for basic block BB. */
static void
-df_ur_bb_local_compute (unsigned int bb_index)
+df_live_bb_local_compute (unsigned int bb_index)
{
basic_block bb = BASIC_BLOCK (bb_index);
- struct df_ur_bb_info *bb_info = df_ur_get_bb_info (bb_index);
+ struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
rtx insn;
struct df_ref **def_rec;
int luid = 0;
@@ -2200,34 +2204,34 @@ df_ur_bb_local_compute (unsigned int bb_
/* Compute local uninitialized register info. */
static void
-df_ur_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
+df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
{
unsigned int bb_index;
bitmap_iterator bi;
df_grow_insn_info ();
- EXECUTE_IF_SET_IN_BITMAP (df_ur->out_of_date_transfer_functions,
+ EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions,
0, bb_index, bi)
{
- df_ur_bb_local_compute (bb_index);
+ df_live_bb_local_compute (bb_index);
}
- bitmap_clear (df_ur->out_of_date_transfer_functions);
+ bitmap_clear (df_live->out_of_date_transfer_functions);
}
/* Initialize the solution vectors. */
static void
-df_ur_init (bitmap all_blocks)
+df_live_init (bitmap all_blocks)
{
unsigned int bb_index;
bitmap_iterator bi;
EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
{
- struct df_ur_bb_info *bb_info = df_ur_get_bb_info (bb_index);
+ struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
bitmap_copy (bb_info->out, bb_info->gen);
bitmap_clear (bb_info->in);
@@ -2237,10 +2241,10 @@ df_ur_init (bitmap all_blocks)
/* Confluence function that ignores fake edges. */
static void
-df_ur_confluence_n (edge e)
+df_live_confluence_n (edge e)
{
- bitmap op1 = df_ur_get_bb_info (e->dest->index)->in;
- bitmap op2 = df_ur_get_bb_info (e->src->index)->out;
+ bitmap op1 = df_live_get_bb_info (e->dest->index)->in;
+ bitmap op2 = df_live_get_bb_info (e->src->index)->out;
if (e->flags & EDGE_FAKE)
return;
@@ -2252,9 +2256,9 @@ df_ur_confluence_n (edge e)
/* Transfer function. */
static bool
-df_ur_transfer_function (int bb_index)
+df_live_transfer_function (int bb_index)
{
- struct df_ur_bb_info *bb_info = df_ur_get_bb_info (bb_index);
+ struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
bitmap in = bb_info->in;
bitmap out = bb_info->out;
bitmap gen = bb_info->gen;
@@ -2264,27 +2268,45 @@ df_ur_transfer_function (int bb_index)
}
-/* Run the fast dce as a side effect of building LR. */
+/* And the LR and UR info to produce the LIVE info. */
static void
-df_ur_local_finalize (bitmap all_blocks ATTRIBUTE_UNUSED)
+df_live_local_finalize (bitmap all_blocks)
{
- df_ur->solutions_dirty = false;
+
+ if (df_live->solutions_dirty)
+ {
+ bitmap_iterator bi;
+ unsigned int bb_index;
+
+ EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
+ {
+ struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
+ struct df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
+
+ /* No register may reach a location where it is not used. Thus
+ we trim the rr result to the places where it is used. */
+ bitmap_and_into (bb_live_info->in, bb_lr_info->in);
+ bitmap_and_into (bb_live_info->out, bb_lr_info->out);
+ }
+
+ df_live->solutions_dirty = false;
+ }
}
/* Free all storage associated with the problem. */
static void
-df_ur_free (void)
+df_live_free (void)
{
- if (df_ur->block_info)
+ if (df_live->block_info)
{
unsigned int i;
- for (i = 0; i < df_ur->block_info_size; i++)
+ for (i = 0; i < df_live->block_info_size; i++)
{
- struct df_ur_bb_info *bb_info = df_ur_get_bb_info (i);
+ struct df_live_bb_info *bb_info = df_live_get_bb_info (i);
if (bb_info)
{
BITMAP_FREE (bb_info->gen);
@@ -2294,37 +2316,37 @@ df_ur_free (void)
}
}
- free_alloc_pool (df_ur->block_pool);
- df_ur->block_info_size = 0;
- free (df_ur->block_info);
+ free_alloc_pool (df_live->block_pool);
+ df_live->block_info_size = 0;
+ free (df_live->block_info);
}
- BITMAP_FREE (df_ur->out_of_date_transfer_functions);
- free (df_ur);
+ BITMAP_FREE (df_live->out_of_date_transfer_functions);
+ free (df_live);
}
/* Debugging info at top of bb. */
static void
-df_ur_top_dump (basic_block bb, FILE *file)
+df_live_top_dump (basic_block bb, FILE *file)
{
- struct df_ur_bb_info *bb_info = df_ur_get_bb_info (bb->index);
- struct df_ur_problem_data *problem_data;
+ struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
+ struct df_live_problem_data *problem_data;
if (!bb_info || !bb_info->in)
return;
- fprintf (file, ";; ur in \t");
+ fprintf (file, ";; live in \t");
df_print_regset (file, bb_info->in);
- if (df_ur->problem_data)
+ if (df_live->problem_data)
{
- problem_data = (struct df_ur_problem_data *)df_ur->problem_data;
+ problem_data = (struct df_live_problem_data *)df_live->problem_data;
fprintf (file, ";; old in \t");
df_print_regset (file, problem_data->in[bb->index]);
}
- fprintf (file, ";; ur gen \t");
+ fprintf (file, ";; live gen \t");
df_print_regset (file, bb_info->gen);
- fprintf (file, ";; ur kill\t");
+ fprintf (file, ";; live kill\t");
df_print_regset (file, bb_info->kill);
}
@@ -2332,19 +2354,19 @@ df_ur_top_dump (basic_block bb, FILE *fi
/* Debugging info at bottom of bb. */
static void
-df_ur_bottom_dump (basic_block bb, FILE *file)
+df_live_bottom_dump (basic_block bb, FILE *file)
{
- struct df_ur_bb_info *bb_info = df_ur_get_bb_info (bb->index);
- struct df_ur_problem_data *problem_data;
+ struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
+ struct df_live_problem_data *problem_data;
if (!bb_info || !bb_info->out)
return;
- fprintf (file, ";; ur out \t");
+ fprintf (file, ";; live out \t");
df_print_regset (file, bb_info->out);
- if (df_ur->problem_data)
+ if (df_live->problem_data)
{
- problem_data = (struct df_ur_problem_data *)df_ur->problem_data;
+ problem_data = (struct df_live_problem_data *)df_live->problem_data;
fprintf (file, ";; old out \t");
df_print_regset (file, problem_data->out[bb->index]);
}
@@ -2355,21 +2377,21 @@ df_ur_bottom_dump (basic_block bb, FILE
equations is not dirty. */
static void
-df_ur_verify_solution_start (void)
+df_live_verify_solution_start (void)
{
basic_block bb;
- struct df_ur_problem_data *problem_data;
- if (df_ur->solutions_dirty)
+ struct df_live_problem_data *problem_data;
+ if (df_live->solutions_dirty)
{
- df_ur->problem_data = NULL;
+ df_live->problem_data = NULL;
return;
}
/* Set it true so that the solution is recomputed. */
- df_ur->solutions_dirty = true;
+ df_live->solutions_dirty = true;
- problem_data = XNEW (struct df_ur_problem_data);
- df_ur->problem_data = problem_data;
+ problem_data = XNEW (struct df_live_problem_data);
+ df_live->problem_data = problem_data;
problem_data->in = XNEWVEC (bitmap, last_basic_block);
problem_data->out = XNEWVEC (bitmap, last_basic_block);
@@ -2377,8 +2399,8 @@ df_ur_verify_solution_start (void)
{
problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
- bitmap_copy (problem_data->in[bb->index], DF_UR_IN (bb));
- bitmap_copy (problem_data->out[bb->index], DF_UR_OUT (bb));
+ bitmap_copy (problem_data->in[bb->index], DF_LIVE_IN (bb));
+ bitmap_copy (problem_data->out[bb->index], DF_LIVE_OUT (bb));
}
}
@@ -2387,20 +2409,20 @@ df_ur_verify_solution_start (void)
equations. */
static void
-df_ur_verify_solution_end (void)
+df_live_verify_solution_end (void)
{
- struct df_ur_problem_data *problem_data;
+ struct df_live_problem_data *problem_data;
basic_block bb;
- if (df_ur->problem_data == NULL)
+ if (df_live->problem_data == NULL)
return;
- problem_data = (struct df_ur_problem_data *)df_ur->problem_data;
+ problem_data = (struct df_live_problem_data *)df_live->problem_data;
FOR_ALL_BB (bb)
{
- if ((!bitmap_equal_p (problem_data->in[bb->index], DF_UR_IN (bb)))
- || (!bitmap_equal_p (problem_data->out[bb->index], DF_UR_OUT (bb))))
+ if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LIVE_IN (bb)))
+ || (!bitmap_equal_p (problem_data->out[bb->index], DF_LIVE_OUT (bb))))
{
/*df_dump (stderr);*/
gcc_unreachable ();
@@ -2418,35 +2440,35 @@ df_ur_verify_solution_end (void)
free (problem_data->in);
free (problem_data->out);
free (problem_data);
- df_ur->problem_data = NULL;
+ df_live->problem_data = NULL;
}
/* All of the information associated with every instance of the problem. */
-static struct df_problem problem_UR =
+static struct df_problem problem_LIVE =
{
- DF_UR, /* Problem id. */
- DF_FORWARD, /* Direction. */
- df_ur_alloc, /* Allocate the problem specific data. */
- df_ur_reset, /* Reset global information. */
- df_ur_free_bb_info, /* Free basic block info. */
- df_ur_local_compute, /* Local compute function. */
- df_ur_init, /* Init the solution specific data. */
- df_worklist_dataflow, /* Worklist solver. */
- NULL, /* Confluence operator 0. */
- df_ur_confluence_n, /* Confluence operator n. */
- df_ur_transfer_function, /* Transfer function. */
- df_ur_local_finalize, /* Finalize function. */
- df_ur_free, /* Free all of the problem information. */
- df_ur_free, /* Remove this problem from the stack of dataflow problems. */
- NULL, /* Debugging. */
- df_ur_top_dump, /* Debugging start block. */
- df_ur_bottom_dump, /* Debugging end block. */
- df_ur_verify_solution_start,/* Incremental solution verify start. */
- df_ur_verify_solution_end, /* Incremental solution verify end. */
- &problem_LR, /* Dependent problem. */
- TV_DF_UR /* Timing variable. */
+ DF_LIVE, /* Problem id. */
+ DF_FORWARD, /* Direction. */
+ df_live_alloc, /* Allocate the problem specific data. */
+ df_live_reset, /* Reset global information. */
+ df_live_free_bb_info, /* Free basic block info. */
+ df_live_local_compute, /* Local compute function. */
+ df_live_init, /* Init the solution specific data. */
+ df_worklist_dataflow, /* Worklist solver. */
+ NULL, /* Confluence operator 0. */
+ df_live_confluence_n, /* Confluence operator n. */
+ df_live_transfer_function, /* Transfer function. */
+ df_live_local_finalize, /* Finalize function. */
+ df_live_free, /* Free all of the problem information. */
+ df_live_free, /* Remove this problem from the stack of dataflow problems. */
+ NULL, /* Debugging. */
+ df_live_top_dump, /* Debugging start block. */
+ df_live_bottom_dump, /* Debugging end block. */
+ df_live_verify_solution_start,/* Incremental solution verify start. */
+ df_live_verify_solution_end, /* Incremental solution verify end. */
+ &problem_LR, /* Dependent problem. */
+ TV_DF_LIVE /* Timing variable. */
};
@@ -2455,12 +2477,12 @@ static struct df_problem problem_UR =
solution. */
void
-df_ur_add_problem (void)
+df_live_add_problem (void)
{
- df_add_problem (&problem_UR);
+ df_add_problem (&problem_LIVE);
/* These will be initialized when df_scan_blocks processes each
block. */
- df_ur->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
+ df_live->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
}
@@ -2468,7 +2490,7 @@ df_ur_add_problem (void)
correct. */
void
-df_ur_verify_transfer_functions (void)
+df_live_verify_transfer_functions (void)
{
basic_block bb;
bitmap saved_gen;
@@ -2486,7 +2508,7 @@ df_ur_verify_transfer_functions (void)
FOR_ALL_BB (bb)
{
- struct df_ur_bb_info *bb_info = df_ur_get_bb_info (bb->index);
+ struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
bitmap_set_bit (all_blocks, bb->index);
if (bb_info)
@@ -2494,7 +2516,7 @@ df_ur_verify_transfer_functions (void)
/* Make a copy of the transfer functions and then compute
new ones to see if the transfer functions have
changed. */
- if (!bitmap_bit_p (df_ur->out_of_date_transfer_functions,
+ if (!bitmap_bit_p (df_live->out_of_date_transfer_functions,
bb->index))
{
bitmap_copy (saved_gen, bb_info->gen);
@@ -2502,7 +2524,7 @@ df_ur_verify_transfer_functions (void)
bitmap_clear (bb_info->gen);
bitmap_clear (bb_info->kill);
- df_ur_bb_local_compute (bb->index);
+ df_live_bb_local_compute (bb->index);
gcc_assert (bitmap_equal_p (saved_gen, bb_info->gen));
gcc_assert (bitmap_equal_p (saved_kill, bb_info->kill));
}
@@ -2512,7 +2534,7 @@ df_ur_verify_transfer_functions (void)
/* If we do not have basic block info, the block must be in
the list of dirty blocks or else some one has added a
block behind our backs. */
- gcc_assert (bitmap_bit_p (df_ur->out_of_date_transfer_functions,
+ gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions,
bb->index));
}
/* Make sure no one created a block without following
@@ -2521,7 +2543,7 @@ df_ur_verify_transfer_functions (void)
}
/* Make sure there are no dirty bits in blocks that have been deleted. */
- gcc_assert (!bitmap_intersect_compl_p (df_ur->out_of_date_transfer_functions,
+ gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions,
all_blocks));
BITMAP_FREE (saved_gen);
BITMAP_FREE (saved_kill);
@@ -2531,192 +2553,6 @@ df_ur_verify_transfer_functions (void)
/*----------------------------------------------------------------------------
- COMBINED LIVE REGISTERS AND UNINITIALIZED REGISTERS.
-
- The in and out sets here are the anded results of the in and out
- sets from the lr and ur problems.
- ----------------------------------------------------------------------------*/
-
-/* Set basic block info. */
-
-static void
-df_live_set_bb_info (unsigned int index,
- struct df_live_bb_info *bb_info)
-{
- gcc_assert (df_live);
- gcc_assert (index < df_live->block_info_size);
- df_live->block_info[index] = bb_info;
-}
-
-
-/* Free basic block info. */
-
-static void
-df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
- void *vbb_info)
-{
- struct df_live_bb_info *bb_info = (struct df_live_bb_info *) vbb_info;
- if (bb_info)
- {
- BITMAP_FREE (bb_info->in);
- BITMAP_FREE (bb_info->out);
- pool_free (df_live->block_pool, bb_info);
- }
-}
-
-
-/* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
- not touched unless the block is new. */
-
-static void
-df_live_alloc (bitmap all_blocks)
-{
- unsigned int bb_index;
- bitmap_iterator bi;
-
- if (!df_live->block_pool)
- df_live->block_pool = create_alloc_pool ("df_live_block pool",
- sizeof (struct df_live_bb_info), 100);
-
- df_grow_bb_info (df_live);
-
- EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
- {
- struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
- if (!bb_info)
- {
- bb_info = (struct df_live_bb_info *) pool_alloc (df_live->block_pool);
- df_live_set_bb_info (bb_index, bb_info);
- bb_info->in = BITMAP_ALLOC (NULL);
- bb_info->out = BITMAP_ALLOC (NULL);
- }
- }
-}
-
-
-/* And the LR and UR info to produce the LIVE info. */
-
-static void
-df_live_local_finalize (bitmap all_blocks)
-{
-
- if (df_live->solutions_dirty)
- {
- bitmap_iterator bi;
- unsigned int bb_index;
-
- EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
- {
- struct df_ur_bb_info *bb_ur_info = df_ur_get_bb_info (bb_index);
- struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
- struct df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
-
- /* No register may reach a location where it is not used. Thus
- we trim the rr result to the places where it is used. */
- bitmap_and (bb_live_info->in, bb_ur_info->in, bb_lr_info->in);
- bitmap_and (bb_live_info->out, bb_ur_info->out, bb_lr_info->out);
- }
-
- df_live->solutions_dirty = false;
- }
-}
-
-
-/* Free all storage associated with the problem. */
-
-static void
-df_live_free (void)
-{
- if (df_live->block_info)
- {
- unsigned int i;
-
- for (i = 0; i < df_live->block_info_size; i++)
- {
- struct df_live_bb_info *bb_info = df_live_get_bb_info (i);
- if (bb_info)
- {
- BITMAP_FREE (bb_info->in);
- BITMAP_FREE (bb_info->out);
- }
- }
-
- free_alloc_pool (df_live->block_pool);
- df_live->block_info_size = 0;
- free (df_live->block_info);
- }
- free (df_live);
-}
-
-
-/* Debugging info at top of bb. */
-
-static void
-df_live_top_dump (basic_block bb, FILE *file)
-{
- struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
- if (!bb_info || !bb_info->in)
- return;
-
- fprintf (file, ";; live in \t");
- df_print_regset (file, bb_info->in);
-}
-
-
-/* Debugging info at bottom of bb. */
-
-static void
-df_live_bottom_dump (basic_block bb, FILE *file)
-{
- struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
- if (!bb_info || !bb_info->out)
- return;
-
- fprintf (file, ";; live out \t");
- df_print_regset (file, bb_info->out);
-}
-
-
-/* All of the information associated with every instance of the problem. */
-
-static struct df_problem problem_LIVE =
-{
- DF_LIVE, /* Problem id. */
- DF_NONE, /* Direction. */
- df_live_alloc, /* Allocate the problem specific data. */
- NULL, /* Reset global information. */
- df_live_free_bb_info, /* Free basic block info. */
- NULL, /* Local compute function. */
- NULL, /* Init the solution specific data. */
- NULL, /* Iterative solver. */
- NULL, /* Confluence operator 0. */
- NULL, /* Confluence operator n. */
- NULL, /* Transfer function. */
- df_live_local_finalize, /* Finalize function. */
- df_live_free, /* Free all of the problem information. */
- df_live_free, /* Remove this problem from the stack of dataflow problems. */
- NULL, /* Debugging. */
- df_live_top_dump, /* Debugging start block. */
- df_live_bottom_dump, /* Debugging end block. */
- NULL, /* Incremental solution verify start. */
- NULL, /* Incremental solution verfiy end. */
- &problem_UR, /* Dependent problem. */
- TV_DF_LIVE /* Timing variable. */
-};
-
-
-/* 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_live_add_problem (void)
-{
- df_add_problem (&problem_LIVE);
-}
-
-
-/*----------------------------------------------------------------------------
UNINITIALIZED REGISTERS WITH EARLYCLOBBER
Find the set of uses for registers that are reachable from the entry
@@ -3129,7 +2965,7 @@ df_urec_init (bitmap all_blocks)
/* Or in the stack regs, hard regs and early clobber regs into the
- ur_in sets of all of the blocks. */
+ urec_in sets of all of the blocks. */
static void
@@ -3478,11 +3314,10 @@ df_chain_fully_remove_problem (void)
static void
df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
-
{
df_chain_remove_problem ();
df_chain->block_pool = create_alloc_pool ("df_chain_block pool",
- sizeof (struct df_link), 100);
+ sizeof (struct df_link), 50);
}
Index: dce.c
===================================================================
--- dce.c (revision 124202)
+++ dce.c (working copy)
@@ -53,11 +53,10 @@ static bool something_changed;
yet been processed. */
static VEC(rtx,heap) *worklist;
-static bitmap_obstack dce_marked_bitmap_obstack;
static bitmap_obstack dce_blocks_bitmap_obstack;
static bitmap_obstack dce_tmp_bitmap_obstack;
-static bitmap marked = NULL;
+static sbitmap marked = NULL;
/* Return true if INSN a normal instruction that can be deleted by the
DCE pass. */
@@ -113,11 +112,11 @@ deletable_insn_p (rtx insn, bool fast)
/* Return true if INSN has not been marked as needed. */
-static inline bool
+static inline int
marked_insn_p (rtx insn)
{
if (insn)
- return bitmap_bit_p (marked, INSN_UID (insn));
+ return TEST_BIT (marked, INSN_UID (insn));
else
/* Artificial defs are always needed and they do not have an
insn. */
@@ -135,7 +134,7 @@ mark_insn (rtx insn, bool fast)
{
if (!fast)
VEC_safe_push (rtx, heap, worklist, insn);
- bitmap_set_bit (marked, INSN_UID (insn));
+ SET_BIT (marked, INSN_UID (insn));
if (dump_file)
fprintf (dump_file, " Adding insn %d to worklist\n", INSN_UID (insn));
}
@@ -191,10 +190,10 @@ init_dce (bool fast)
if (dump_file)
df_dump (dump_file);
- bitmap_obstack_initialize (&dce_marked_bitmap_obstack);
bitmap_obstack_initialize (&dce_blocks_bitmap_obstack);
bitmap_obstack_initialize (&dce_tmp_bitmap_obstack);
- marked = BITMAP_ALLOC (&dce_marked_bitmap_obstack);
+ marked = sbitmap_alloc (get_max_uid () + 1);
+ sbitmap_zero (marked);
}
@@ -424,7 +423,7 @@ mark_reg_dependencies (rtx insn)
static void
end_ud_dce (void)
{
- BITMAP_FREE (marked);
+ sbitmap_free (marked);
gcc_assert (VEC_empty (rtx, worklist));
}
@@ -491,8 +490,7 @@ struct tree_opt_pass pass_ud_rtl_dce =
static void
fini_dce (void)
{
- BITMAP_FREE (marked);
- bitmap_obstack_release (&dce_marked_bitmap_obstack);
+ sbitmap_free (marked);
bitmap_obstack_release (&dce_blocks_bitmap_obstack);
bitmap_obstack_release (&dce_tmp_bitmap_obstack);
df_in_progress = false;
@@ -743,7 +741,7 @@ fast_dce (void)
/* So something was deleted that requires a redo. Do it on
the cheap. */
delete_unmarked_insns ();
- bitmap_clear (marked);
+ sbitmap_zero (marked);
bitmap_clear (processed);
bitmap_clear (redo_out);
Index: alloc-pool.c
===================================================================
--- alloc-pool.c (revision 124202)
+++ alloc-pool.c (working copy)
@@ -1,5 +1,5 @@
/* Functions to support a pool of allocatable objects.
- Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005, 2006
+ Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005, 2006, 2007
Free Software Foundation, Inc.
Contributed by Daniel Berlin <dan@cgsoftware.com>
@@ -161,7 +161,9 @@ create_alloc_pool (const char *name, siz
header_size = align_eight (sizeof (struct alloc_pool_list_def));
pool->block_size = (size * num) + header_size;
- pool->free_list = NULL;
+ pool->returned_free_list = NULL;
+ pool->virgin_free_list = NULL;
+ pool->virgin_elts_remaining = 0;
pool->elts_allocated = 0;
pool->elts_free = 0;
pool->blocks_allocated = 0;
@@ -223,7 +225,6 @@ void *
pool_alloc (alloc_pool pool)
{
alloc_pool_list header;
- char *block;
#ifdef GATHER_STATISTICS
struct alloc_pool_descriptor *desc = alloc_pool_descriptor (pool->name);
@@ -233,46 +234,57 @@ pool_alloc (alloc_pool pool)
gcc_assert (pool);
/* If there are no more free elements, make some more!. */
- if (!pool->free_list)
+ if (!pool->returned_free_list)
{
- size_t i;
- alloc_pool_list block_header;
-
- /* Make the block. */
- block = XNEWVEC (char, pool->block_size);
- block_header = (alloc_pool_list) block;
- block += align_eight (sizeof (struct alloc_pool_list_def));
+ char *block;
+ if (!pool->virgin_elts_remaining)
+ {
+ alloc_pool_list block_header;
+
+ /* Make the block. */
+ block = XNEWVEC (char, pool->block_size);
+ block_header = (alloc_pool_list) block;
+ block += align_eight (sizeof (struct alloc_pool_list_def));
#ifdef GATHER_STATISTICS
- desc->current += pool->block_size;
- if (desc->peak < desc->current)
- desc->peak = desc->current;
-#endif
-
- /* Throw it on the block list. */
- block_header->next = pool->block_list;
- pool->block_list = block_header;
-
- /* Now put the actual block pieces onto the free list. */
- for (i = 0; i < pool->elts_per_block; i++, block += pool->elt_size)
- {
+ desc->current += pool->block_size;
+ if (desc->peak < desc->current)
+ desc->peak = desc->current;
+#endif
+
+ /* Throw it on the block list. */
+ block_header->next = pool->block_list;
+ pool->block_list = block_header;
+
+ /* Make the block available for allocation. */
+ pool->virgin_free_list = block;
+ pool->virgin_elts_remaining = pool->elts_per_block;
+
+ /* Also update the number of elements we have free/allocated, and
+ increment the allocated block count. */
+ pool->elts_allocated += pool->elts_per_block;
+ pool->elts_free += pool->elts_per_block;
+ pool->blocks_allocated += 1;
+ }
+
+
+ /* We now know that we can take the first elt off the virgin list and
+ put it on the returned list. */
+ block = pool->virgin_free_list;
+ header = (alloc_pool_list) USER_PTR_FROM_ALLOCATION_OBJECT_PTR (block);
+ header->next = NULL;
#ifdef ENABLE_CHECKING
- /* Mark the element to be free. */
- ((allocation_object *) block)->id = 0;
+ /* Mark the element to be free. */
+ ((allocation_object *) block)->id = 0;
#endif
- header = (alloc_pool_list) USER_PTR_FROM_ALLOCATION_OBJECT_PTR (block);
- header->next = pool->free_list;
- pool->free_list = header;
- }
- /* Also update the number of elements we have free/allocated, and
- increment the allocated block count. */
- pool->elts_allocated += pool->elts_per_block;
- pool->elts_free += pool->elts_per_block;
- pool->blocks_allocated += 1;
+ pool->returned_free_list = header;
+ pool->virgin_free_list += pool->elt_size;
+ pool->virgin_elts_remaining--;
+
}
/* Pull the first free element from the free list, and return it. */
- header = pool->free_list;
- pool->free_list = header->next;
+ header = pool->returned_free_list;
+ pool->returned_free_list = header->next;
pool->elts_free--;
#ifdef ENABLE_CHECKING
@@ -305,8 +317,8 @@ pool_free (alloc_pool pool, void *ptr)
#endif
header = (alloc_pool_list) ptr;
- header->next = pool->free_list;
- pool->free_list = header;
+ header->next = pool->returned_free_list;
+ pool->returned_free_list = header;
pool->elts_free++;
}
/* Output per-alloc_pool statistics. */
Index: alloc-pool.h
===================================================================
--- alloc-pool.h (revision 124202)
+++ alloc-pool.h (working copy)
@@ -1,5 +1,5 @@
/* Functions to support a pool of allocatable objects
- Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003, 2004
+ Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2007
Free Software Foundation, Inc.
Contributed by Daniel Berlin <dan@cgsoftware.com>
@@ -37,7 +37,18 @@ typedef struct alloc_pool_def
ALLOC_POOL_ID_TYPE id;
#endif
size_t elts_per_block;
- alloc_pool_list free_list;
+
+ /* These are the elements that have been allocated at least once and freed. */
+ alloc_pool_list returned_free_list;
+
+ /* These are the elements that have not yet been allocated out of
+ the last block obtained from XNEWVEC. */
+ char* virgin_free_list;
+
+ /* The number of elements in the virgin_free_list that can be
+ allocated before needing another block. */
+ size_t virgin_elts_remaining;
+
size_t elts_allocated;
size_t elts_free;
size_t blocks_allocated;