2 new branch predictors

[Jan Hubicka <jh at suse dot cz>]

Hi,
this patch adds remaining two heuristics documented by ball&larus paper.  I
don't add the loop header heuristics as documented there, as I believe the
jump.c implementation to be superrior.

I will need to do some experiments later, but -fprofile-branches seems to
be broken at the moment.

Honza

Ne čen 10 00:40:51 CEST 2001  Jan Hubicka  <jh@suse.cz>
	* predict.def (PRED_CALL, PRED_ERROR_RETURN): New.
	* predict.c (estimate_probability): Calculate dominance
	information; improve detection of NORETURN heuristics;
	add call/error_return heuiristics; tweak comparison heuristics
	to recognize -1.

*** predict.def.old	Sun Jun 10 00:39:33 2001
--- predict.def	Sun Jun 10 00:24:15 2001
*************** DEF_PREDICTOR (PRED_LOOP_BRANCH, "loop b
*** 44,47 ****
--- 44,49 ----
  DEF_PREDICTOR (PRED_LOOP_EXIT, "loop exit", PROB_LIKELY)
  DEF_PREDICTOR (PRED_LOOP_HEADER, "loop header", PROB_LIKELY)
  DEF_PREDICTOR (PRED_POINTER, "pointer", PROB_LIKELY)
+ DEF_PREDICTOR (PRED_CALL, "call", PROB_LIKELY)
+ DEF_PREDICTOR (PRED_ERROR_RETURN, "error return", PROB_LIKELY)
  DEF_PREDICTOR (PRED_OPCODE, "opcode", PROB_LIKELY)
*** predict.c.work2	Sun Jun 10 00:09:17 2001
--- predict.c	Sun Jun 10 00:40:17 2001
*************** void
*** 240,247 ****
--- 240,253 ----
  estimate_probability (loops_info)
       struct loops *loops_info;
  {
+   sbitmap *dominators, *post_dominators;
    int i;
  
+   dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
+   post_dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
+   calculate_dominance_info (NULL, dominators, 0);
+   calculate_dominance_info (NULL, post_dominators, 1);
+ 
    /* Try to predict out blocks in a loop that are not part of a
       natural loop.  */
    for (i = 0; i < loops_info->num; i++)
*************** estimate_probability (loops_info)
*** 282,291 ****
       is used as the prediction for the branch.  */
    for (i = 0; i < n_basic_blocks - 1; i++)
      {
!       rtx last_insn = BLOCK_END (i);
        rtx cond, earliest;
        edge e;
  
        if (GET_CODE (last_insn) != JUMP_INSN
  	  || ! any_condjump_p (last_insn))
  	continue;
--- 288,314 ----
       is used as the prediction for the branch.  */
    for (i = 0; i < n_basic_blocks - 1; i++)
      {
!       basic_block bb = BASIC_BLOCK (i);
!       rtx last_insn = bb->end;
        rtx cond, earliest;
        edge e;
  
+       /* If block has no sucessor, predict all possible paths to
+          it as unprobable, as the block contains call to noreturn
+ 	 function and thus can be executed only once.  */
+       if (bb->succ == NULL)
+ 	{
+ 	  int y;
+ 	  for (y = 0; y < n_basic_blocks; y++)
+ 	    if (!TEST_BIT (post_dominators[y], i))
+ 	      {
+ 		for (e = BASIC_BLOCK (y)->succ; e; e = e->succ_next)
+ 		if (e->dest->index >= 0
+ 		    && TEST_BIT (post_dominators[e->dest->index], i))
+ 		  predict_edge_def (e, PRED_NORETURN, NOT_TAKEN);
+ 	      }
+ 	}
+ 
        if (GET_CODE (last_insn) != JUMP_INSN
  	  || ! any_condjump_p (last_insn))
  	continue;
*************** estimate_probability (loops_info)
*** 293,304 ****
        if (find_reg_note (last_insn, REG_BR_PROB, 0))
  	continue;
  
!       /* If one of the successor blocks has no successors, predict
! 	 that side not taken.  */
!       /* ??? Ought to do the same for any subgraph with no exit.  */
!       for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next)
! 	if (e->dest->succ == NULL)
! 	  predict_edge_def (e, PRED_NORETURN, NOT_TAKEN);
  
        cond = get_condition (last_insn, &earliest);
        if (! cond)
--- 316,354 ----
        if (find_reg_note (last_insn, REG_BR_PROB, 0))
  	continue;
  
!       for (e = bb->succ; e; e = e->succ_next)
! 	{
! 	  /* Predict edges to blocks that does return immediately to be
! 	     improbable.  These are usually used to signal error states.  */
! 	  if (e->dest == EXIT_BLOCK_PTR
! 	      || (e->dest->succ && !e->dest->succ->succ_next
! 		  && e->dest->succ->dest == EXIT_BLOCK_PTR))
! 	    predict_edge_def (e, PRED_ERROR_RETURN, NOT_TAKEN);
! 
! 	  /* Look for block we are guarding (ie we dominate it,
! 	     but it don't postdominate us).  */
! 	  if (e->dest != EXIT_BLOCK_PTR
! 	      && e->dest != bb
! 	      && TEST_BIT (dominators[e->dest->index], e->src->index)
! 	      && !TEST_BIT (post_dominators[e->src->index], e->dest->index))
! 	    {
! 	      rtx insn;
! 	      /* An call heuristics claims that such guarded function call
! 		 is improbable.  This is because such calls are often used
! 		 to signalize exceptional situations such as printing error
! 		 messages.  */
! 	      for (insn = e->dest->head; insn != NEXT_INSN (e->dest->end);
! 		   insn = NEXT_INSN (insn))
! 		if (GET_CODE (insn) == CALL_INSN
! 		    /* Constant and pure calls are hardly used to signalize
! 		       something exceptional.  */
! 		    && ! CONST_CALL_P (insn))
! 		  {
! 		    predict_edge_def (e, PRED_CALL, NOT_TAKEN);
! 		    break;
! 		  }
! 	    }
! 	}
  
        cond = get_condition (last_insn, &earliest);
        if (! cond)
*************** estimate_probability (loops_info)
*** 359,365 ****
  	  break;
  	case LE:
  	case LT:
! 	  if (XEXP (cond, 1) == const0_rtx)
  	    predict_insn_def (last_insn, PRED_OPCODE, NOT_TAKEN);
  	  break;
  	case GE:
--- 409,417 ----
  	  break;
  	case LE:
  	case LT:
! 	  if (XEXP (cond, 1) == const0_rtx
! 	      || (GET_CODE (XEXP (cond, 1)) == CONST_INT
! 		  && INTVAL (XEXP (cond, 1)) == -1))
  	    predict_insn_def (last_insn, PRED_OPCODE, NOT_TAKEN);
  	  break;
  	case GE:
*************** estimate_probability (loops_info)
*** 385,390 ****
--- 437,444 ----
  	continue;
        combine_predictions_for_insn (last_insn, BASIC_BLOCK (i));
      }
+   sbitmap_vector_free (post_dominators);
+   sbitmap_vector_free (dominators);
  }
  
  /* __builtin_expect dropped tokens into the insn stream describing