This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[new-regalloc-branch] Add simple rematerialization support
- To: gcc-patches at gcc dot gnu dot org
- Subject: [new-regalloc-branch] Add simple rematerialization support
- From: Daniel Berlin <dan at cgsoftware dot com>
- Date: Sun, 29 Jul 2001 14:35:15 -0400
Lazy spill code motion, then lattice based remat, are next on the
list.
2001-07-29 Daniel Berlin <dan@cgsoftware.com>
Add support for simple rematerialization (not lattice based right
now, very trivial, but already has a large positive impact).
* ra.c (rematerializable): New function. Determine if a value is
rematerializable.
(parts_to_webs): If it's rematerializable, modify the spill cost
to be the cost of rematerializing the RTL in question.
(rewrite_program): If we can rematerialize, do it.
(toplevel): New variable, emitted_remat.
(dump_ra): Print out number of rematerializations.
(reg_alloc): Init emitted_remat to 0.
Index: ra.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/ra.c,v
retrieving revision 1.1.2.24
diff -c -3 -p -w -B -b -r1.1.2.24 ra.c
*** ra.c 2001/07/27 18:09:19 1.1.2.24
--- ra.c 2001/07/29 18:34:12
***************
*** 41,46 ****
--- 41,51 ----
*/
/* TODO
+
+ * Lattice based rematerialization
+ * Fix spill costs for rematerialization (if any part of a web is
+ rematerializable, the spill cost becomes very small, even if the
+ rest of the web isn't)
* do lots of commenting
* look through all XXX's and do something about them
* handle REG_NO_CONFLICTS blocks correctly (the current ad hoc approach
*************** static int one_pass PARAMS ((struct df *
*** 354,359 ****
--- 359,365 ----
static void dump_constraints PARAMS ((void));
static void dump_ra PARAMS ((struct df *));
static void init_ra PARAMS ((void));
+ static int rematerializable PARAMS ((struct ref *));
void reg_alloc PARAMS ((void));
/* XXX use Daniels compressed bitmaps here. */
*************** undef_to_bitmap (wp, undefined)
*** 597,603 ****
{
if (*undefined < 15)
{
! struct undef_table_s u = undef_table[*undefined];
*undefined = u.new_undef;
return get_sub_conflicts (wp, u.size, u.word);
}
--- 603,610 ----
{
if (*undefined < 15)
{
! struct undef_table_s u;
! u = undef_table[*undefined];
*undefined = u.new_undef;
return get_sub_conflicts (wp, u.size, u.word);
}
*************** handle_asm_insn (df, insn)
*** 1314,1320 ****
--- 1321,1329 ----
}
else
{
+ #if 0
int c;
+ #endif
COPY_HARD_REG_SET (conflict, usable_regs
[reg_preferred_class (web->regno)]);
IOR_HARD_REG_SET (conflict, usable_regs
*************** parts_to_webs (df, part2web)
*** 1766,1772 ****
struct df *df;
struct web **part2web;
{
! unsigned int i;
unsigned int webnum;
struct ref **ref_use, **ref_def;
struct web_part *wp_first_use = &web_parts[df->def_id];
--- 1775,1781 ----
struct df *df;
struct web **part2web;
{
! unsigned int i,j;
unsigned int webnum;
struct ref **ref_use, **ref_def;
struct web_part *wp_first_use = &web_parts[df->def_id];
*************** parts_to_webs (df, part2web)
*** 1927,1932 ****
--- 1936,1948 ----
web->defs -= web->num_defs;
web->uses -= web->num_uses;
web->weight *= (1 + web->add_hardregs);
+ for (j = 0; j < web->num_defs; j++)
+ {
+ if (rematerializable (web->defs[j]))
+ {
+ web->spill_cost = rtx_cost (DF_REF_INSN (web->defs[j]), 0);
+ }
+ }
}
}
*************** hardregset_to_string (s)
*** 3172,3178 ****
int i = HARD_REG_SET_LONGS - 1;
c += sprintf (c, "{ ");
for (;i >= 0; i--)
! c += sprintf (c, HOST_WIDE_INT_PRINT_HEX "%s", s[i], i ? ", " : "");
c += sprintf (c, " }");
#endif
return string;
--- 3188,3197 ----
int i = HARD_REG_SET_LONGS - 1;
c += sprintf (c, "{ ");
for (;i >= 0; i--)
! {
! c += sprintf (c, HOST_WIDE_INT_PRINT_HEX, s[i]);
! c += sprintf (c, "%s", i ? ", " : "");
! }
c += sprintf (c, " }");
#endif
return string;
*************** allocate_spill_web (web)
*** 3587,3592 ****
--- 3606,3612 ----
static unsigned int emitted_spill_loads;
static unsigned int emitted_spill_stores;
+ static unsigned int emitted_remat;
/* Rewrite the program to include the spill code. */
static void
*************** rewrite_program (void)
*** 3611,3616 ****
--- 3631,3638 ----
rtx insn = DF_REF_INSN (web->defs[j]);
rtx following = NEXT_INSN (insn);
basic_block bb = BLOCK_FOR_INSN (insn);
+ if (!rematerializable (web->defs[j]))
+ {
/* Happens when spill_coalescing() deletes move insns. */
if (!INSN_P (insn))
continue;
*************** rewrite_program (void)
*** 3636,3642 ****
set_block_for_insn (insn, bb);
emitted_spill_stores++;
}
!
bitmap_clear (b);
for (j = 0; j < web->num_uses; j++)
{
--- 3658,3669 ----
set_block_for_insn (insn, bb);
emitted_spill_stores++;
}
! else
! {
! if (rtl_dump_file)
! fprintf (rtl_dump_file, "We *should* rematerialize uses of def ID %d for web %d\n", DF_REF_ID (web->defs[j]), web->id);
! }
! }
bitmap_clear (b);
for (j = 0; j < web->num_uses; j++)
{
*************** rewrite_program (void)
*** 3644,3649 ****
--- 3671,3700 ----
rtx insn = DF_REF_INSN (web->uses[j]);
rtx prev = PREV_INSN (insn);
basic_block bb = BLOCK_FOR_INSN (insn);
+ if (DF_REF_CHAIN (web->uses[j]) && rematerializable (DF_REF_CHAIN (web->uses[j])->ref))
+ {
+ if (!INSN_P (insn))
+ continue;
+ if (bitmap_bit_p (b, INSN_UID (insn)))
+ continue;
+ bitmap_set_bit (b, INSN_UID (insn));
+ start_sequence ();
+ emit_insn (PATTERN (DF_REF_INSN (DF_REF_CHAIN (web->uses[j])->ref)));
+ insns = get_insns ();
+ end_sequence ();
+ emit_insns_before (insns, insn);
+ if (bb->head == insn)
+ bb->head = NEXT_INSN (prev);
+ for (; insn != prev; insn = PREV_INSN (insn))
+ set_block_for_insn (insn, bb);
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, "Poof! We rematerialized use %d for web %d, associated with def %d\n",
+ j, web->id, DF_REF_ID (DF_REF_CHAIN (web->uses[j])->ref));
+ emitted_remat++;
+ }
+ else
+ {
+
/* Happens when spill_coalescing() deletes move insns. */
if (!INSN_P (insn))
continue;
*************** rewrite_program (void)
*** 3671,3676 ****
--- 3722,3729 ----
}
}
+ }
+
BITMAP_XFREE (b);
/*if (! validate_change (insn, df->defs[i]->loc, web->stack_slot, 0)) */
*************** emit_colors (df)
*** 3712,3718 ****
continue;
if (web->reg_rtx || web->regno < FIRST_PSEUDO_REGISTER)
abort ();
- //web->reg_rtx = gen_rtx_REG (PSEUDO_REGNO_MODE (web->regno), web->color);
web->reg_rtx = gen_reg_rtx (PSEUDO_REGNO_MODE (web->regno));
}
max_regno = max_reg_num ();
--- 3765,3770 ----
*************** dump_ra (df)
*** 3980,3987 ****
debug_msg (0, " %4d\n", web->id);
}
debug_msg (0, "\n");
! debug_msg (0, "Added spill insns (overall): %d loads, %d stores\n",
! emitted_spill_loads, emitted_spill_stores);
if (deleted_move_insns)
debug_msg (0, "Deleted %d move insns.\n", deleted_move_insns);
debug_msg (0, "\n");
--- 4032,4039 ----
debug_msg (0, " %4d\n", web->id);
}
debug_msg (0, "\n");
! debug_msg (0, "Added spill insns (overall): %d loads, %d stores, %d remats\n",
! emitted_spill_loads, emitted_spill_stores, emitted_remat);
if (deleted_move_insns)
debug_msg (0, "Deleted %d move insns.\n", deleted_move_insns);
debug_msg (0, "\n");
*************** init_ra (void)
*** 4027,4033 ****
orig_max_uid = get_max_uid ();
compute_bb_for_insn (get_max_uid ());
}
!
/* Main register allocator entry point. */
void
reg_alloc (void)
--- 4079,4096 ----
orig_max_uid = get_max_uid ();
compute_bb_for_insn (get_max_uid ());
}
! static
! int rematerializable (ref)
! struct ref *ref;
! {
! rtx set;
! set = single_set (DF_REF_INSN (ref));
! if (!set)
! return 0;
! if (CONSTANT_P (SET_SRC (set)))
! return 1;
! return 0;
! }
/* Main register allocator entry point. */
void
reg_alloc (void)
*************** reg_alloc (void)
*** 4042,4047 ****
--- 4105,4111 ----
count_or_remove_death_notes (NULL, 1);
emitted_spill_loads = 0;
emitted_spill_stores = 0;
+ emitted_remat = 0;
deleted_move_insns = 0;
do
{
*************** reg_alloc (void)
*** 4049,4055 ****
if (pass++ > 40)
internal_error ("Didn't find a coloring.\n");
df = df_init ();
! df_analyse (df, 0, DF_HARD_REGS | DF_RD_CHAIN | DF_RU_CHAIN);
if (rtl_dump_file)
{
rtx insn;
--- 4113,4119 ----
if (pass++ > 40)
internal_error ("Didn't find a coloring.\n");
df = df_init ();
! df_analyse (df, 0, DF_HARD_REGS | DF_RD_CHAIN | DF_RU_CHAIN | DF_DU_CHAIN | DF_UD_CHAIN );
if (rtl_dump_file)
{
rtx insn;
*************** reg_alloc (void)
*** 4089,4099 ****
print_rtl_with_bb (rtl_dump_file, get_insns ()); */
no_new_pseudos = 1;
compute_bb_for_insn (get_max_uid ());
- allocate_reg_info (max_reg_num (), 0, 1);
no_new_pseudos = 0;
store_motion();
allocate_reg_info (max_reg_num (), 0, 1);
no_new_pseudos = 1;
find_basic_blocks (get_insns (), max_reg_num (), rtl_dump_file);
life_analysis (get_insns (), rtl_dump_file, PROP_FINAL);
recompute_reg_usage (get_insns (), TRUE);
--- 4153,4163 ----
print_rtl_with_bb (rtl_dump_file, get_insns ()); */
no_new_pseudos = 1;
compute_bb_for_insn (get_max_uid ());
no_new_pseudos = 0;
store_motion();
allocate_reg_info (max_reg_num (), 0, 1);
no_new_pseudos = 1;
+ cleanup_cfg (CLEANUP_EXPENSIVE);
find_basic_blocks (get_insns (), max_reg_num (), rtl_dump_file);
life_analysis (get_insns (), rtl_dump_file, PROP_FINAL);
recompute_reg_usage (get_insns (), TRUE);
--
"When I go, I'm flying Air Bizarre. It's a good airline. You
buy a one way round trip ticket. You leave any Monday, and they
bring you back the previous Friday... That way you still have
the weekend.
"-Steven Wright