Speedup to propagate_one_insn
Jan Hubicka
jh@suse.cz
Thu Feb 5 16:35:00 GMT 2004
Hi,
while looking into profiles, I noticed that actually majority of time spent in
propagate_one_insn (that is 2nd most hot function) is spent by computing
REG_LIVE_LENGTH array. This patch reorganize the code to avoid this quadratic
bottleneck saving over 1% of compialtion time at -O0/-O1 combine.c.
I think the first part of patch can be safe for 3.4 branch too, the other part
would probably need some time for testing in mainline. I am not sure about the
corelation with auto_inc passes - I think they are never done together with
final REG_INFO update, but if they are, I will have to add some code to them.
At the moment I just sanity check it.
I verified that the change has no effect on code produced for combine.c and
even all the -da dumps byte compare.
Finally I noticed that there are two useless calls to update the
information and removed them. If they are supposed to be used somewhere
they needs to be fixed as they don't initialize the datastructures so
part of the info would cummulate twice that is wrong.
Bootstrapped/regetsted i686-pc-gnu-linux, OK?
Honza
2004-02-05 Jan Hubicka <jh@suse.cz>
* recog.c (split_all_insns): Do not update reg info.
* regrename.c (regrename_optimize): Likewise.
* toplev.c (rest_of_handle_reorder_blocks): Likewise.
* flow.c (struct propagate_block_info): Add insn_num field.
(reg_deaths): New array.
(life_analysis): Free reg_deaths info.
(allocate_reg_life_data): Allocate reg_deaths array.
(propagate_one_insn): Use new array.
(init_propagate_block): Initialize it.
(free_propagate_block_info): Finish compuation of REG_LIVE_LENGTH
(attempt_auto_inc): Sanity check that REG_INFO is not computed
at same time.
(mark_used_regs): Update new array.
Index: recog.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/recog.c,v
retrieving revision 1.196
diff -c -3 -p -r1.196 recog.c
*** recog.c 2 Feb 2004 00:17:17 -0000 1.196
--- recog.c 5 Feb 2004 10:58:17 -0000
*************** split_all_insns (int upd_life)
*** 2795,2801 ****
if (changed && upd_life)
update_life_info (blocks, UPDATE_LIFE_GLOBAL_RM_NOTES,
! PROP_DEATH_NOTES | PROP_REG_INFO);
#ifdef ENABLE_CHECKING
verify_flow_info ();
--- 2795,2801 ----
if (changed && upd_life)
update_life_info (blocks, UPDATE_LIFE_GLOBAL_RM_NOTES,
! PROP_DEATH_NOTES);
#ifdef ENABLE_CHECKING
verify_flow_info ();
Index: regrename.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/regrename.c,v
retrieving revision 1.74
diff -c -3 -p -r1.74 regrename.c
*** regrename.c 2 Feb 2004 00:17:17 -0000 1.74
--- regrename.c 5 Feb 2004 10:58:17 -0000
*************** regrename_optimize (void)
*** 360,366 ****
count_or_remove_death_notes (NULL, 1);
update_life_info (NULL, UPDATE_LIFE_LOCAL,
! PROP_REG_INFO | PROP_DEATH_NOTES);
}
static void
--- 360,366 ----
count_or_remove_death_notes (NULL, 1);
update_life_info (NULL, UPDATE_LIFE_LOCAL,
! PROP_DEATH_NOTES);
}
static void
Index: toplev.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.c,v
retrieving revision 1.873
diff -c -3 -p -r1.873 toplev.c
*** toplev.c 30 Jan 2004 17:43:23 -0000 1.873
--- toplev.c 5 Feb 2004 10:58:17 -0000
*************** rest_of_handle_reorder_blocks (tree decl
*** 2331,2337 ****
but should not be terribly bad. */
if (changed && HAVE_conditional_execution)
update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES,
! PROP_DEATH_NOTES | PROP_REG_INFO);
close_dump_file (DFI_bbro, print_rtl_with_bb, insns);
}
--- 2331,2337 ----
but should not be terribly bad. */
if (changed && HAVE_conditional_execution)
update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES,
! PROP_DEATH_NOTES);
close_dump_file (DFI_bbro, print_rtl_with_bb, insns);
}
Index: cp/tree.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cp/tree.c,v
retrieving revision 1.362
diff -c -3 -p -r1.362 tree.c
*** cp/tree.c 2 Feb 2004 16:53:09 -0000 1.362
--- cp/tree.c 5 Feb 2004 10:58:18 -0000
*************** cp_cannot_inline_tree_fn (tree* fnp)
*** 2080,2087 ****
return 1;
/* Don't auto-inline anything that might not be bound within
! this unit of translation. */
! if (!DECL_DECLARED_INLINE_P (fn) && !(*targetm.binds_local_p) (fn))
{
DECL_UNINLINABLE (fn) = 1;
return 1;
--- 2080,2091 ----
return 1;
/* Don't auto-inline anything that might not be bound within
! this unit of translation.
! Exclude comdat functions from this rule. While they can be bound
! to the other unit, they all must be the same. This is especilly
! important so templates can inline. */
! if (!DECL_DECLARED_INLINE_P (fn) && !(*targetm.binds_local_p) (fn)
! /*&& !DECL_COMDAT (fn)*/)
{
DECL_UNINLINABLE (fn) = 1;
return 1;
Index: flow.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/flow.c,v
retrieving revision 1.576
diff -c -3 -p -r1.576 flow.c
*** flow.c 2 Feb 2004 00:17:14 -0000 1.576
--- flow.c 5 Feb 2004 16:20:29 -0000
*************** struct propagate_block_info
*** 264,274 ****
--- 264,280 ----
/* Flags controlling the set of information propagate_block collects. */
int flags;
+ /* Index of instruction being processed. */
+ int insn_num;
};
/* Number of dead insns removed. */
static int ndead;
+ /* When PROP_REG_INFO set, array containing information at what
+ instruction given register died. */
+ static int *reg_deaths;
+
/* Maximum length of pbi->mem_set_list before we start dropping
new elements on the floor. */
#define MAX_MEM_SET_LIST_LEN 100
*************** update_life_info (sbitmap blocks, enum u
*** 734,739 ****
--- 745,755 ----
}
});
}
+ if (reg_deaths)
+ {
+ free (reg_deaths);
+ reg_deaths = NULL;
+ }
timevar_pop ((extent == UPDATE_LIFE_LOCAL || blocks)
? TV_LIFE_UPDATE : TV_LIFE);
if (ndead && rtl_dump_file)
*************** allocate_reg_life_data (void)
*** 1457,1462 ****
--- 1473,1481 ----
int i;
max_regno = max_reg_num ();
+ if (reg_deaths)
+ abort ();
+ reg_deaths = xcalloc (sizeof (*reg_deaths), max_regno);
/* Recalculate the register space, in case it has grown. Old style
vector oriented regsets would set regset_{size,bytes} here also. */
*************** propagate_one_insn (struct propagate_blo
*** 1783,1788 ****
--- 1802,1810 ----
mark_used_regs (pbi, XEXP (XEXP (note, 0), 0), cond, insn);
/* The stack ptr is used (honorarily) by a CALL insn. */
+ if ((flags & PROP_REG_INFO)
+ && !REGNO_REG_SET_P (pbi->reg_live, STACK_POINTER_REGNUM))
+ reg_deaths[STACK_POINTER_REGNUM] = pbi->insn_num;
SET_REGNO_REG_SET (pbi->reg_live, STACK_POINTER_REGNUM);
/* Calls may also reference any of the global registers,
*************** propagate_one_insn (struct propagate_blo
*** 1793,1803 ****
}
}
! /* On final pass, update counts of how many insns in which each reg
! is live. */
! if (flags & PROP_REG_INFO)
! EXECUTE_IF_SET_IN_REG_SET (pbi->reg_live, 0, i,
! { REG_LIVE_LENGTH (i)++; });
return prev;
}
--- 1815,1821 ----
}
}
! pbi->insn_num++;
return prev;
}
*************** init_propagate_block_info (basic_block b
*** 1820,1825 ****
--- 1838,1844 ----
pbi->cond_local_set = cond_local_set;
pbi->cc0_live = 0;
pbi->flags = flags;
+ pbi->insn_num = 0;
if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
pbi->reg_next_use = xcalloc (max_reg_num (), sizeof (rtx));
*************** free_propagate_block_info (struct propag
*** 1976,1981 ****
--- 1995,2010 ----
BITMAP_XFREE (pbi->reg_cond_reg);
#endif
+ if (pbi->flags & PROP_REG_INFO)
+ {
+ int num = pbi->insn_num;
+ int i;
+
+ EXECUTE_IF_SET_IN_REG_SET (pbi->reg_live, 0, i,
+ { REG_LIVE_LENGTH (i) += num - reg_deaths[i];
1>G+ reg_deaths[i] = 0;
+ });
+ }
if (pbi->reg_next_use)
free (pbi->reg_next_use);
*************** mark_set_1 (struct propagate_block_info
*** 2803,2809 ****
{
for (i = regno_first; i <= regno_last; ++i)
if (!(not_dead & (((unsigned long) 1) << (i - regno_first))))
! CLEAR_REGNO_REG_SET (pbi->reg_live, i);
}
}
else if (GET_CODE (reg) == REG)
--- 2832,2846 ----
{
for (i = regno_first; i <= regno_last; ++i)
if (!(not_dead & (((unsigned long) 1) << (i - regno_first))))
! {
! if ((pbi->flags & PROP_REG_INFO)
! && REGNO_REG_SET_P (pbi->reg_live, i))
! {
! REG_LIVE_LENGTH (i) += pbi->insn_num - reg_deaths[i];
! reg_deaths[i] = 0;
! }
! CLEAR_REGNO_REG_SET (pbi->reg_live, i);
! }
}
}
else if (GET_CODE (reg) == REG)
*************** attempt_auto_inc (struct propagate_block
*** 3334,3339 ****
--- 3371,3380 ----
on this insn, which is incorrect. */
SET_REGNO_REG_SET (pbi->reg_live, regno);
+ /* We shall not do the autoinc during final pass. */
+ if (flags & PROP_REG_INFO)
+ abort ();
+
/* If there are any calls between INSN and INCR, show
that REGNO now crosses them. */
for (temp = insn; temp != incr; temp = NEXT_INSN (temp))
*************** attempt_auto_inc (struct propagate_block
*** 3365,3370 ****
--- 3406,3414 ----
/* If the original source was dead, it's dead now. */
rtx note;
+ /* We shall not do the autoinc during final pass. */
+ if (flags & PROP_REG_INFO)
+ abort ();
while ((note = find_reg_note (incr, REG_DEAD, NULL_RTX)) != NULL_RTX)
{
remove_note (incr, note);
*************** mark_used_reg (struct propagate_block_in
*** 3550,3555 ****
--- 3594,3608 ----
REG_FREQ (regno_first) += REG_FREQ_FROM_BB (pbi->bb);
REG_N_REFS (regno_first)++;
}
+ for (i = regno_first; i <= regno_last; ++i)
+ if (! REGNO_REG_SET_P (pbi->reg_live, i))
+ {
+ #ifdef ENABLE_CHECKING
+ if (reg_deaths[i])
+ abort ();
+ #endif
+ reg_deaths[i] = pbi->insn_num;
+ }
}
/* Record and count the insns in which a reg dies. If it is used in
More information about the Gcc-patches
mailing list