Re: c/7344: performance regression on huge case statements

[Jan Hubicka <jh at suse dot cz>]

> 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.  */