This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[dataflow]: PATCH COMMITTED to improve performance.
- From: Kenneth Zadeck <zadeck at naturalbridge dot com>
- To: GCC Patches <gcc-patches at gcc dot gnu dot org>, Seongbae Park <seongbae dot park at gmail dot com>, Steven Bosscher <stevenb dot gcc at gmail dot com>, "Berlin, Daniel" <dberlin at dberlin dot org>, "Zadeck, Kenneth" <zadeck at naturalbridge dot com>
- Date: Tue, 02 Jan 2007 10:06:45 -0500
- Subject: [dataflow]: PATCH COMMITTED to improve performance.
This patch does three things:
1) It cleans up the set of dataflow problems used in register
allocation. Now the urec problem is only used once, in global alloc if
you are optimizing. There are also fewer calls in the path to rescan
all of the insns.
2) An additional flag was added to the df-refs to indicate that this ref
should be make regs_ever_live true for its regno. There are a set of
counters for each hardreg that keep track of these refs. The counters
are then used to initialize the regs_ever_live array. This keeps us
from having to search the possibly long list of refs for the regno to
find one that would make the reg_ever_live element true.
3) Fixed up a few places where I had not encapsulated regs_ever_live.
This has been bootstrapped and regression tested on x86-64, x86-32, ppc,
and ia-64.
Kenny
2007-01-02 Kenneth Zadeck <zadeck@naturalbridge.com>
* df-scan.c (df_reg_chain_create, df_reg_chain_unlink,
df_ref_create_structure, df_hard_reg_used_p): Added code to
process df->hard_regs_live_count.
(df_ref_is_record_live, df_reg_chain_find_ref): Deleted.
(df_refs_add_to_chains): Removed ifdefed code.
(df_compute_regs_ever_live): Fixed "&" vs "&&" problem.
* df-core (rest_of_handle_df_initialize,
rest_of_handle_df_finish): Added code to
process df->hard_regs_live_count.
* global.c (global_alloc): Repositioned use of urec problem.
(build_insn_chain): Changed use of DF_RA_LIVE_TOP to df_get_live_top.
(rest_of_handle_global_alloc): Removed call to df_analyze for no
optimize case.
* local-alloc.c (update_equiv_regs): Added calls to
df_notes_rescan where eq notes are hacked.
(block_alloc): Changed DF_RA_LIVE_TOP to DF_LR_TOP.
(rest_of_handle_local_alloc): Removed addition of urec problem.
* function.c (regno_clobbered_at_setjmp): Changed df_get_live_out
to DF_LIVE_OUT.
* (df_ref_flags.DF_REGS_EVER_LIVE): New flag.
(df.hard_regs_live_count): New bitmap.
(DF_LR_TOP, DF_REG_EVER_LIVE_P): New macro.
(df_get_live_out): Removed.
(df_get_live_top): Added.
* df-problems.c (df_get_live_in): Does not look at DF_LIVE.
(df_get_live_out): Deleted.
(df_get_live_top): Added.
* config/sh/sh.c (calc_live_regs): Changed regs_ever_live to
df_regs_ever_live_p.
* config/mn10300/mn10300.c (fp_regs_to_save): Ditto.
* config/darwin.c (machopic_legitimize_pic_address) Changed
regs_ever_live to df_set_regs_ever_live.
* reload1.c (reload): Corrected the set of bitmaps to modify after
reloading.
Index: df-scan.c
===================================================================
--- df-scan.c (revision 120281)
+++ df-scan.c (working copy)
@@ -145,9 +145,6 @@ static bool df_ref_is_equal (struct df_r
static struct df_ref *df_ref_chain_find_ref (struct df_ref *,
struct df_ref *,
df_ref_compare_func_t);
-static struct df_ref *df_reg_chain_find_ref (struct df_ref *,
- struct df_ref *,
- df_ref_compare_func_t);
#endif /* DEBUG_DF_RESCAN */
@@ -681,6 +678,12 @@ df_reg_chain_create (struct df_reg_info
reg_info->reg_chain = ref;
reg_info->n_refs++;
+ if (DF_REF_FLAGS_IS_SET (ref, DF_REGS_EVER_LIVE))
+ {
+ gcc_assert (DF_REF_REGNO (ref) < FIRST_PSEUDO_REGISTER);
+ df->hard_regs_live_count[DF_REF_REGNO (ref)]++;
+ }
+
gcc_assert (DF_REF_NEXT_REG (ref) == NULL);
gcc_assert (DF_REF_PREV_REG (ref) == NULL);
@@ -773,6 +776,11 @@ df_reg_chain_unlink (struct df_ref *ref)
df_chain_unlink (ref);
reg_info->n_refs--;
+ if (DF_REF_FLAGS_IS_SET (ref, DF_REGS_EVER_LIVE))
+ {
+ gcc_assert (DF_REF_REGNO (ref) < FIRST_PSEUDO_REGISTER);
+ df->hard_regs_live_count[DF_REF_REGNO (ref)]--;
+ }
/* Unlink from the reg chain. If there is no prev, this is the
first of the list. If not, just join the next and prev. */
@@ -1404,29 +1412,6 @@ df_ref_is_equal (struct df_ref *ref1, st
}
-/* Return true if the first ref should be recorded in regs_ever_live . */
-
-static bool
-df_ref_is_record_live (struct df_ref *ref1,
- struct df_ref *ref2 __attribute__ ((__unused__)))
-{
- unsigned int regno;
-
- /* If this ref is a def. */
- if (DF_REF_TYPE (ref1) == DF_REF_REG_DEF)
- return !DF_REF_FLAGS_IS_SET (ref1, DF_REF_MAY_CLOBBER)
- && !DF_REF_IS_ARTIFICIAL (ref1);
-
- /* If this ref is not a def. */
- regno = DF_REF_REGNO (ref1);
-
- return !DF_REF_IS_ARTIFICIAL (ref1)
- && !(TEST_HARD_REG_BIT (elim_reg_set, regno)
- && (regno == FRAME_POINTER_REGNUM
- || regno == ARG_POINTER_REGNUM));
-}
-
-
/* Find a matching df_ref in the ref chain. */
static struct df_ref *
@@ -1460,22 +1445,6 @@ df_ref_chain_find_ref_by_regno (struct d
return NULL;
}
-/* Find a matching df_ref in the ref chain */
-
-static struct df_ref *
-df_reg_chain_find_ref (struct df_ref *chain,
- struct df_ref *this_ref,
- df_ref_compare_func_t func)
-{
- while (chain)
- {
- if (func (chain, this_ref))
- return chain;
- chain = chain->next_reg;
- }
-
- return NULL;
-}
#endif /* DEBUG_DF_RESCAN */
@@ -1800,10 +1769,6 @@ df_refs_add_to_chains (rtx insn,
/* A beginning of a group of mw hardregs */
struct df_insn_info *insn_info = DF_INSN_GET (insn);
-#if 0
- hardreg = df_mw_hardreg_find_hardreg (insn_info->mw_hardregs, ref);
- /* Matching hardreg group not found. Create one. */
-#endif
hardreg = pool_alloc (problem_data->mw_reg_pool);
hardreg->next = insn_info->mw_hardregs;
insn_info->mw_hardregs = hardreg;
@@ -1857,6 +1822,26 @@ df_ref_create_structure (rtx reg, rtx *l
DF_REF_NEXT_REG (this_ref) = NULL;
DF_REF_PREV_REG (this_ref) = NULL;
+ /* We need to clear this bit because fwprop, and in the future
+ possibly other optimizations sometimes create new refs using ond
+ refs as the model. */
+ DF_REF_FLAGS_CLEAR (this_ref, DF_REGS_EVER_LIVE);
+
+ /* See if this ref needs to have DF_REGS_EVER_LIVE bit set. */
+ if ((regno < FIRST_PSEUDO_REGISTER)
+ && (!DF_REF_IS_ARTIFICIAL (this_ref)))
+ {
+ if (DF_REF_TYPE (this_ref) == DF_REF_REG_DEF)
+ {
+ if (!DF_REF_FLAGS_IS_SET (this_ref, DF_REF_MAY_CLOBBER))
+ DF_REF_FLAGS_SET (this_ref, DF_REGS_EVER_LIVE);
+ }
+ else if (!(TEST_HARD_REG_BIT (elim_reg_set, regno)
+ && (regno == FRAME_POINTER_REGNUM
+ || regno == ARG_POINTER_REGNUM)))
+ DF_REF_FLAGS_SET (this_ref, DF_REGS_EVER_LIVE);
+ }
+
return this_ref;
}
@@ -3225,13 +3210,7 @@ bool
df_hard_reg_used_p (unsigned int i)
{
gcc_assert (df);
-
- return (df_reg_chain_find_ref (DF_REG_DEF_CHAIN (i), NULL,
- df_ref_is_record_live) != NULL
- || df_reg_chain_find_ref (DF_REG_USE_CHAIN (i), NULL,
- df_ref_is_record_live) != NULL
- || df_reg_chain_find_ref (DF_REG_EQ_USE_CHAIN (i), NULL,
- df_ref_is_record_live) != NULL);
+ return DF_REG_EVER_LIVE_P (i);
}
@@ -3272,7 +3251,7 @@ df_compute_regs_ever_live (bool reset)
memset (regs_ever_live, 0, sizeof (regs_ever_live));
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
- if (df_hard_reg_used_p (i) & (!regs_ever_live[i]))
+ if ((!regs_ever_live[i]) && df_hard_reg_used_p (i))
{
regs_ever_live[i] = true;
changed = true;
Index: df-core.c
===================================================================
--- df-core.c (revision 120281)
+++ df-core.c (working copy)
@@ -693,7 +693,11 @@ rest_of_handle_df_initialize (void)
block. */
df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
df_ur->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
-
+
+ df->hard_regs_live_count = XNEWVEC (unsigned int, FIRST_PSEUDO_REGISTER);
+ memset (df->hard_regs_live_count, 0,
+ sizeof (unsigned int) * FIRST_PSEUDO_REGISTER);
+
df_hard_reg_init ();
/* After reload, some ports add certain bits to regs_ever_live so
this cannot be reset. */
@@ -740,6 +744,7 @@ rest_of_handle_df_finish (void)
if (df->postorder)
free (df->postorder);
+ free (df->hard_regs_live_count);
free (df);
df = NULL;
return 0;
Index: global.c
===================================================================
--- global.c (revision 120281)
+++ global.c (working copy)
@@ -396,9 +396,11 @@ global_alloc (void)
max_allocno = 0;
/* Do not recompute the register info. Local_alloc has played with
this in a way that global expects. */
- df_insn_rescan_all ();
+ /* Create a new version of df that has the special version of UR. */
+ df_urec_add_problem ();
df_set_flags (DF_RI_NO_UPDATE);
df_analyze ();
+ df_set_flags (DF_NO_INSN_RESCAN);
/* A machine may have certain hard registers that
are safe to use only within a basic block. */
@@ -1899,7 +1901,7 @@ build_insn_chain (rtx first)
CLEAR_REG_SET (live_relevant_regs);
- EXECUTE_IF_SET_IN_BITMAP (DF_RA_LIVE_TOP (b), 0, i, bi)
+ EXECUTE_IF_SET_IN_BITMAP (df_get_live_top (b), 0, i, bi)
{
if (i < FIRST_PSEUDO_REGISTER
? ! TEST_HARD_REG_BIT (eliminable_regset, i)
@@ -2076,7 +2078,7 @@ rest_of_handle_global_alloc (void)
else
{
build_insn_chain (get_insns ());
- df_analyze ();
+ df_set_flags (DF_NO_INSN_RESCAN);
failure = reload (get_insns (), 0);
}
Index: local-alloc.c
===================================================================
--- local-alloc.c (revision 120255)
+++ local-alloc.c (working copy)
@@ -953,10 +953,12 @@ update_equiv_regs (void)
if (note == 0 && REG_BASIC_BLOCK (regno) >= 0
&& MEM_P (SET_SRC (set))
&& validate_equiv_mem (insn, dest, SET_SRC (set)))
- REG_NOTES (insn) = note = gen_rtx_EXPR_LIST (REG_EQUIV,
- copy_rtx (SET_SRC (set)),
- REG_NOTES (insn));
-
+ {
+ REG_NOTES (insn) = note = gen_rtx_EXPR_LIST (REG_EQUIV,
+ copy_rtx (SET_SRC (set)),
+ REG_NOTES (insn));
+ df_notes_rescan (insn);
+ }
if (note)
{
int regno = REGNO (dest);
@@ -1068,6 +1070,7 @@ update_equiv_regs (void)
the register. */
reg_equiv_init[regno]
= gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX);
+ df_notes_rescan (init_insn);
}
}
}
@@ -1274,7 +1277,7 @@ block_alloc (int b)
/* Initialize table of hardware registers currently live. */
- REG_SET_TO_HARD_REG_SET (regs_live, DF_RA_LIVE_TOP (BASIC_BLOCK (b)));
+ REG_SET_TO_HARD_REG_SET (regs_live, DF_LR_TOP (BASIC_BLOCK (b)));
/* This loop scans the instructions of the basic block
and assigns quantities to registers.
@@ -2491,14 +2494,12 @@ rest_of_handle_local_alloc (void)
{
int rebuild_notes;
- /* Create a new version of df that has the special version of UR. */
- df_urec_add_problem ();
df_ri_add_problem (DF_RI_LIFE + DF_RI_SETJMP);
/* There is just too much going on in the register allocators to
keep things up to date. At the end we have to rescan anyway
because things change when the reload_completed flag is set.
So we just turn off scanning and we will rescan by hand. */
- df_set_flags (DF_NO_INSN_RESCAN);
+ df_set_flags (DF_DEFER_INSN_RESCAN);
df_analyze ();
/* If we are not optimizing, then this is the only place before
Index: function.c
===================================================================
--- function.c (revision 120255)
+++ function.c (working copy)
@@ -3534,7 +3534,7 @@ regno_clobbered_at_setjmp (bitmap setjmp
return 0;
return ((REG_N_SETS (regno) > 1
- || REGNO_REG_SET_P (df_get_live_out (ENTRY_BLOCK_PTR), regno))
+ || REGNO_REG_SET_P (DF_LIVE_OUT (ENTRY_BLOCK_PTR), regno))
&& REGNO_REG_SET_P (setjmp_crosses, regno));
}
Index: df.h
===================================================================
--- df.h (revision 120281)
+++ df.h (working copy)
@@ -133,12 +133,15 @@ enum df_ref_flags
the hardregs. */
DF_REF_MW_HARDREG_GROUP = 1 << 10,
- /* These two flags are markers for general purpose use.
- Used for verification of existing refs. */
- DF_REF_REF_MARKER = 1 << 11,
+ /* This bit is true if this ref can make regs_ever_live true for
+ this regno. */
+ DF_REGS_EVER_LIVE = 1 << 11,
- DF_REF_REG_MARKER = 1 << 12
+ /* These two flags are markers for general purpose use.
+ Used for verification of existing refs. */
+ DF_REF_REF_MARKER = 1 << 12,
+ DF_REF_REG_MARKER = 1 << 13
};
@@ -487,6 +490,10 @@ struct df
int *postorder; /* The current set of basic blocks in postorder. */
int n_blocks; /* The number of blocks in postorder. */
+ /* An array [FIRST_PSEUDO_REGISTER], indexed by regno, of the number of
+ refs that qualify as being in regs_ever_live. */
+ unsigned int *hard_regs_live_count;
+
/* Problem specific control infomation. */
enum df_changeable_flags changeable_flags;
};
@@ -507,13 +514,14 @@ struct df
/* Live in for register allocation also takes into account several other factors. */
#define DF_RA_LIVE_IN(BB) (DF_UREC_BB_INFO(BB)->in)
-#define DF_RA_LIVE_OUT(BB) (DF_UREC_BB_INFO(BB)->out)
#define DF_RA_LIVE_TOP(BB) (DF_UREC_BB_INFO(BB)->top)
+#define DF_RA_LIVE_OUT(BB) (DF_UREC_BB_INFO(BB)->out)
/* These macros are currently used by only reg-stack since it is not
tolerant of uninitialized variables. This intolerance should be
fixed because it causes other problems. */
#define DF_LR_IN(BB) (DF_LR_BB_INFO(BB)->in)
+#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
@@ -597,6 +605,7 @@ struct df
#define DF_REG_EQ_USE_GET(REG) (df->eq_use_regs[(REG)])
#define DF_REG_EQ_USE_CHAIN(REG) (df->eq_use_regs[(REG)]->reg_chain)
#define DF_REG_EQ_USE_COUNT(REG) (df->eq_use_regs[(REG)]->n_refs)
+#define DF_REG_EVER_LIVE_P(REG) (df->hard_regs_live_count[REG] != 0)
/* Macros to access the elements within the reg_info structure table. */
@@ -842,7 +851,7 @@ extern struct df_link *df_chain_create (
extern void df_chain_unlink (struct df_ref *);
extern void df_chain_copy (struct df_ref *, struct df_link *);
extern bitmap df_get_live_in (basic_block);
-extern bitmap df_get_live_out (basic_block);
+extern bitmap df_get_live_top (basic_block);
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);
Index: df-problems.c
===================================================================
--- df-problems.c (revision 120281)
+++ df-problems.c (working copy)
@@ -59,37 +59,36 @@ static bitmap seen_in_insn = NULL;
/*----------------------------------------------------------------------------
Public functions access functions for the dataflow problems.
----------------------------------------------------------------------------*/
-/* Get the live in set for BB no matter what problem happens to be
- defined. */
+/* Get the live at in set for BB no matter what problem happens to be
+ defined. This function is used by the register allocators who
+ choose different dataflow problems depending on the optimization
+ level. */
bitmap
df_get_live_in (basic_block bb)
{
gcc_assert (df_lr);
- if (df_live)
- return DF_LIVE_IN (bb);
- else if (df_urec)
+ if (df_urec)
return DF_RA_LIVE_IN (bb);
else
return DF_LR_IN (bb);
}
-
-/* Get the live out set for BB no matter what problem happens to be
- defined. */
+/* Get the live at top set for BB no matter what problem happens to be
+ defined. This function is used by the register allocators who
+ choose different dataflow problems depending on the optimization
+ level. */
bitmap
-df_get_live_out (basic_block bb)
+df_get_live_top (basic_block bb)
{
gcc_assert (df_lr);
- if (df_live)
- return DF_LIVE_OUT (bb);
- else if (df_urec)
- return DF_RA_LIVE_OUT (bb);
+ if (df_urec)
+ return DF_RA_LIVE_TOP (bb);
else
- return DF_LR_OUT (bb);
+ return DF_LR_TOP (bb);
}
@@ -4216,7 +4215,7 @@ df_ri_bb_compute (unsigned int bb_index,
struct df_ref *use;
int luid = 0;
- bitmap_copy (live, df_get_live_out (bb));
+ bitmap_copy (live, DF_LIVE_OUT (bb));
bitmap_clear (artificial_uses);
if (df_ri_problem_p (DF_RI_LIFE))
Index: config/sh/sh.c
===================================================================
--- config/sh/sh.c (revision 120281)
+++ config/sh/sh.c (working copy)
@@ -5861,7 +5861,7 @@ calc_live_regs (HARD_REG_SET *live_regs_
/* If we can save a lot of saves by switching to double mode, do that. */
else if ((TARGET_SH4 || TARGET_SH2A_DOUBLE) && TARGET_FMOVD && TARGET_FPU_SINGLE)
for (count = 0, reg = FIRST_FP_REG; reg <= LAST_FP_REG; reg += 2)
- if (df_regs_ever_live_p (reg) && regs_ever_live[reg+1]
+ if (df_regs_ever_live_p (reg) && df_regs_ever_live_p (reg+1)
&& (! call_really_used_regs[reg]
|| interrupt_handler)
&& ++count > 2)
Index: config/mn10300/mn10300.c
===================================================================
--- config/mn10300/mn10300.c (revision 120281)
+++ config/mn10300/mn10300.c (working copy)
@@ -537,7 +537,7 @@ fp_regs_to_save (void)
return 0;
for (i = FIRST_FP_REGNUM; i <= LAST_FP_REGNUM; ++i)
- if (regs_ever_live[i] && ! call_used_regs[i])
+ if (df_regs_ever_live_p (i) && ! call_used_regs[i])
++n;
return n;
Index: config/darwin.c
===================================================================
--- config/darwin.c (revision 120255)
+++ config/darwin.c (working copy)
@@ -778,7 +778,7 @@ machopic_legitimize_pic_address (rtx ori
#endif
if (reload_in_progress)
- regs_ever_live[REGNO (pic)] = 1;
+ df_set_regs_ever_live (REGNO (pic), true);
pic_ref = gen_rtx_PLUS (Pmode, pic,
gen_pic_offset (XEXP (orig, 0),
pic_base));
@@ -849,7 +849,7 @@ machopic_legitimize_pic_address (rtx ori
pic_offset_table_rtx));
#endif
if (reload_in_progress)
- regs_ever_live[REGNO (pic)] = 1;
+ df_set_regs_ever_live (REGNO (pic), true);
pic_ref = gen_rtx_PLUS (Pmode,
pic,
gen_pic_offset (orig, pic_base));
Index: reload1.c
===================================================================
--- reload1.c (revision 120281)
+++ reload1.c (working copy)
@@ -1103,8 +1103,8 @@ reload (rtx first, int global)
if (! frame_pointer_needed)
FOR_EACH_BB (bb)
{
- CLEAR_REGNO_REG_SET (DF_RA_LIVE_IN (bb), HARD_FRAME_POINTER_REGNUM);
- /* CLEAR_REGNO_REG_SET (DF_RA_LIVE_OUT (bb), HARD_FRAME_POINTER_REGNUM); */
+ bitmap_clear_bit (df_get_live_in (bb), HARD_FRAME_POINTER_REGNUM);
+ bitmap_clear_bit (df_get_live_top (bb), HARD_FRAME_POINTER_REGNUM);
}
/* Come here (with failure set nonzero) if we can't get enough spill