This is the mail archive of the
gcc-prs@gcc.gnu.org
mailing list for the GCC project.
Re: c/7344: performance regression on huge case statements
- From: Jan Hubicka <jh at suse dot cz>
- To: nobody at gcc dot gnu dot org
- Cc: gcc-prs at gcc dot gnu dot org,
- Date: 11 Oct 2002 14:26:01 -0000
- Subject: Re: c/7344: performance regression on huge case statements
- Reply-to: Jan Hubicka <jh at suse dot cz>
The following reply was made to PR c/7344; it has been noted by GNATS.
From: Jan Hubicka <jh@suse.cz>
To: Nathanael Nerode <neroden@twcny.rr.com>
Cc: gcc-gnats@gcc.gnu.org, rschiele@uni-mannheim.de,
gcc-bugs@gcc.gnu.org, nobody@gcc.gnu.org, jh@suse.cz,
gcc-patches@gcc.gnu.org
Subject: Re: c/7344: performance regression on huge case statements
Date: Fri, 11 Oct 2002 16:21:48 +0200
> http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&pr=7344
>
> I'm tired of investigating this, but it seems likely that the problem
> was introduced with the introduction of et-forest.c, since that's where
> the loop is. This was introduced by Pavel Nejedly and committed to
> mainline by Jan Hubicka (along with most of the surrounding code).
>
> (So that's why I'm ccing you; it looks like you caused it, so maybe you
> can figure out how to fix it. :-/)
Hi,
this patch cuts the time spent by et-foresting down to about 10%.
It still makes sense to do the caching if we will run into this problem
more commonly or there are some rooms for improvements in the et-tree
itself. The testcase still shows some interesting hot spots so I would
like to look at these first as they seems to be more common scenario for
3.3 that does not use dominance information that much.
Honza
Fri Oct 11 15:41:23 CEST 2002 Jan Hubicka <jh@suse.cz>
* predict.c (can_predict_insn_p): New function.
(estimate_probability): Avoid unnecesary work.
(process_note_prediction): Likewise.
* toplev.c (rest_of_compilation): Account early branch prediction pass
as TV_BRANCH_PROB.
Index: predict.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/predict.c,v
retrieving revision 1.74
diff -c -3 -p -r1.74 predict.c
*** predict.c 3 Oct 2002 19:43:00 -0000 1.74
--- predict.c 11 Oct 2002 13:40:52 -0000
*************** static void process_note_prediction PAR
*** 80,85 ****
--- 80,86 ----
static bool last_basic_block_p PARAMS ((basic_block));
static void compute_function_frequency PARAMS ((void));
static void choose_function_section PARAMS ((void));
+ static bool can_predict_insn_p PARAMS ((rtx));
/* Information we hold about each branch predictor.
Filled using information from predict.def. */
*************** predict_edge (e, predictor, probability)
*** 230,235 ****
--- 231,248 ----
predict_insn (last_insn, predictor, probability);
}
+ /* Return true when we can store prediction on insn INSN.
+ At the moment we represent predictions only on conditional
+ jumps, not at computed jump or other complicated cases. */
+ static bool
+ can_predict_insn_p (insn)
+ rtx insn;
+ {
+ return (GET_CODE (insn) == JUMP_INSN
+ && any_condjump_p (insn)
+ && BLOCK_FOR_INSN (insn)->succ->succ_next);
+ }
+
/* Predict edge E by given predictor if possible. */
void
*************** estimate_probability (loops_info)
*** 440,446 ****
statements construct loops via "non-loop" constructs
in the source language and are better to be handled
separately. */
! if (predicted_by_p (bb, PRED_CONTINUE))
continue;
/* Loop branch heuristics - predict an edge back to a
--- 453,460 ----
statements construct loops via "non-loop" constructs
in the source language and are better to be handled
separately. */
! if (!can_predict_insn_p (bb->end)
! || predicted_by_p (bb, PRED_CONTINUE))
continue;
/* Loop branch heuristics - predict an edge back to a
*************** estimate_probability (loops_info)
*** 474,480 ****
rtx cond, earliest;
edge e;
! if (GET_CODE (last_insn) != JUMP_INSN || ! any_condjump_p (last_insn))
continue;
for (e = bb->succ; e; e = e->succ_next)
--- 488,494 ----
rtx cond, earliest;
edge e;
! if (! can_predict_insn_p (last_insn))
continue;
for (e = bb->succ; e; e = e->succ_next)
*************** process_note_prediction (bb, heads, domi
*** 763,769 ****
/* Now find the edge that leads to our branch and aply the prediction. */
! if (y == last_basic_block)
return;
for (e = BASIC_BLOCK (y)->succ; e; e = e->succ_next)
if (e->dest->index >= 0
--- 777,783 ----
/* Now find the edge that leads to our branch and aply the prediction. */
! if (y == last_basic_block || !can_predict_insn_p (BASIC_BLOCK (y)->end))
return;
for (e = BASIC_BLOCK (y)->succ; e; e = e->succ_next)
if (e->dest->index >= 0
*************** estimate_bb_frequencies (loops)
*** 1148,1156 ****
{
rtx last_insn = bb->end;
! if (GET_CODE (last_insn) != JUMP_INSN || !any_condjump_p (last_insn)
! /* Avoid handling of conditional jumps jumping to fallthru edge. */
! || bb->succ->succ_next == NULL)
{
/* We can predict only conditional jumps at the moment.
Expect each edge to be equally probable.
--- 1162,1168 ----
{
rtx last_insn = bb->end;
! if (!can_predict_insn_p (last_insn))
{
/* We can predict only conditional jumps at the moment.
Expect each edge to be equally probable.
Index: toplev.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/toplev.c,v
retrieving revision 1.681
diff -c -3 -p -r1.681 toplev.c
*** toplev.c 9 Oct 2002 23:17:51 -0000 1.681
--- toplev.c 11 Oct 2002 13:40:54 -0000
*************** rest_of_compilation (decl)
*** 2590,2596 ****
--- 2590,2598 ----
delete_unreachable_blocks ();
/* Turn NOTE_INSN_PREDICTIONs into branch predictions. */
+ timevar_push (TV_BRANCH_PROB);
note_prediction_to_br_prob ();
+ timevar_pop (TV_BRANCH_PROB);
/* We may have potential sibling or tail recursion sites. Select one
(of possibly multiple) methods of performing the call. */