estimate_probabilities patch

[Richard Henderson]

Expands on Zack's recent patch so that we test both sides of
a branch.  Currently we'd mispredict

int f(int p)
{
  int x;
  if (!p)
    x = bar();
  else
    abort ();
  return x;
}

Also, use 90% instead of 50% for "predict taken".



r~


        * predict.c (estimate_probability): Examine both sides of
        a branch for no exits.  Use 90% not 50% for predict taken.
        Reorg for one copy of note generation code.

Index: predict.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/predict.c,v
retrieving revision 1.7
diff -c -p -d -r1.7 predict.c
*** predict.c	2000/04/22 18:34:59	1.7
--- predict.c	2000/04/22 19:03:47
*************** estimate_probability (loops_info)
*** 103,136 ****
      {
        rtx last_insn = BLOCK_END (i);
        rtx cond, earliest;
!       int prob = 0;
        edge e;
  
        if (GET_CODE (last_insn) != JUMP_INSN
  	  || ! condjump_p (last_insn) || simplejump_p (last_insn))
  	continue;
        if (find_reg_note (last_insn, REG_BR_PROB, 0))
  	continue;
        cond = get_condition (last_insn, &earliest);
        if (! cond)
  	continue;
  
!       /* If the jump branches around a block with no successors,
! 	 predict it to be taken.  */
!       prob = 0;
        for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next)
! 	if ((e->flags & EDGE_FALLTHRU) && e->dest->succ == NULL)
  	  {
! 	    prob = REG_BR_PROB_BASE;
! 	    break;
  	  }
-       if (prob)
- 	{
- 	  REG_NOTES (last_insn)
- 	    = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
- 				 REG_NOTES (last_insn));
- 	  continue;
- 	}
  
        /* Try "pointer heuristic."
  	 A comparison ptr == 0 is predicted as false.
--- 103,134 ----
      {
        rtx last_insn = BLOCK_END (i);
        rtx cond, earliest;
!       int prob;
        edge e;
  
        if (GET_CODE (last_insn) != JUMP_INSN
  	  || ! condjump_p (last_insn) || simplejump_p (last_insn))
  	continue;
+ 
        if (find_reg_note (last_insn, REG_BR_PROB, 0))
  	continue;
+ 
        cond = get_condition (last_insn, &earliest);
        if (! cond)
  	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)
  	  {
! 	    if (e->flags & EDGE_FALLTHRU)
! 	      prob = REG_BR_PROB_BASE;
! 	    else
! 	      prob = 0;
! 	    goto emitnote;
  	  }
  
        /* Try "pointer heuristic."
  	 A comparison ptr == 0 is predicted as false.
*************** estimate_probability (loops_info)
*** 143,149 ****
  	      && (XEXP (cond, 1) == const0_rtx
  		  || (GET_CODE (XEXP (cond, 1)) == REG
  		      && REGNO_POINTER_FLAG (REGNO (XEXP (cond, 1))))))
! 	    prob = REG_BR_PROB_BASE / 10;
  	  break;
  	case NE:
  	  if (GET_CODE (XEXP (cond, 0)) == REG
--- 141,150 ----
  	      && (XEXP (cond, 1) == const0_rtx
  		  || (GET_CODE (XEXP (cond, 1)) == REG
  		      && REGNO_POINTER_FLAG (REGNO (XEXP (cond, 1))))))
! 	    {
! 	      prob = REG_BR_PROB_BASE / 10;
! 	      goto emitnote;
! 	    }
  	  break;
  	case NE:
  	  if (GET_CODE (XEXP (cond, 0)) == REG
*************** estimate_probability (loops_info)
*** 151,167 ****
  	      && (XEXP (cond, 1) == const0_rtx
  		  || (GET_CODE (XEXP (cond, 1)) == REG
  		      && REGNO_POINTER_FLAG (REGNO (XEXP (cond, 1))))))
! 	    prob = REG_BR_PROB_BASE / 2;
  	  break;
  	default:
! 	  prob = 0;
! 	}
!       if (prob)
! 	{
! 	  REG_NOTES (last_insn)
! 	    = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
! 				 REG_NOTES (last_insn));
! 	  continue;
  	}
  
        /* Try "opcode heuristic."
--- 152,165 ----
  	      && (XEXP (cond, 1) == const0_rtx
  		  || (GET_CODE (XEXP (cond, 1)) == REG
  		      && REGNO_POINTER_FLAG (REGNO (XEXP (cond, 1))))))
! 	    {
! 	      prob = REG_BR_PROB_BASE - (REG_BR_PROB_BASE / 10);
! 	      goto emitnote;
! 	    }
  	  break;
+ 
  	default:
! 	  break;
  	}
  
        /* Try "opcode heuristic."
*************** estimate_probability (loops_info)
*** 172,201 ****
  	{
  	case CONST_INT:
  	  /* Unconditional branch.  */
! 	  prob = REG_BR_PROB_BASE / 2;
! 	  break;
  	case EQ:
  	  prob = REG_BR_PROB_BASE / 10;
! 	  break;
  	case NE:
! 	  prob = REG_BR_PROB_BASE / 2;
! 	  break;
  	case LE:
  	case LT:
  	  if (XEXP (cond, 1) == const0_rtx)
! 	    prob = REG_BR_PROB_BASE / 10;
  	  break;
  	case GE:
  	case GT:
  	  if (XEXP (cond, 1) == const0_rtx
  	      || (GET_CODE (XEXP (cond, 1)) == CONST_INT
  		  && INTVAL (XEXP (cond, 1)) == -1))
! 	    prob = REG_BR_PROB_BASE / 2;
  	  break;
  
  	default:
! 	  prob = 0;
  	}
        REG_NOTES (last_insn)
  	= gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
  			     REG_NOTES (last_insn));
--- 170,211 ----
  	{
  	case CONST_INT:
  	  /* Unconditional branch.  */
! 	  prob = (cond == const0_rtx ? 0 : REG_BR_PROB_BASE);
! 	  goto emitnote;
! 
  	case EQ:
  	  prob = REG_BR_PROB_BASE / 10;
! 	  goto emitnote;
  	case NE:
! 	  prob = REG_BR_PROB_BASE - (REG_BR_PROB_BASE / 10);
! 	  goto emitnote;
  	case LE:
  	case LT:
  	  if (XEXP (cond, 1) == const0_rtx)
! 	    {
! 	      prob = REG_BR_PROB_BASE / 10;
! 	      goto emitnote;
! 	    }
  	  break;
  	case GE:
  	case GT:
  	  if (XEXP (cond, 1) == const0_rtx
  	      || (GET_CODE (XEXP (cond, 1)) == CONST_INT
  		  && INTVAL (XEXP (cond, 1)) == -1))
! 	    {
! 	      prob = REG_BR_PROB_BASE - (REG_BR_PROB_BASE / 10);
! 	      goto emitnote;
! 	    }
  	  break;
  
  	default:
! 	  break;
  	}
+ 
+       /* If we havn't chosen something by now, predict 50-50.  */
+       prob = REG_BR_PROB_BASE / 2;
+ 
+     emitnote:
        REG_NOTES (last_insn)
  	= gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
  			     REG_NOTES (last_insn));