Fix branch prediction issue (example 6 from Regehr's blog)

[Jan Hubicka <hubicka at ucw dot cz>]

Hi,
the return heuristics is broken since it looks at edge and then it tries to add predicion
on every path leading to the edge. Instead it puts the prediction on every path leading to
source BB of the edge that is not quite the same.  This results in the loop in testcase
being predicted as unlikely, as was observed by Jakub.

Fixed by the attached patch. I also dropped special casing abnormals at few place since
other places in predict don't do that. Those are remainders from time when Eh edges was
abnormal, mostly.

Bootstrapped/regtested x86_64-linux, comitted.
Honza

	PR middle-end/46939
	* predic.c (predict_paths_leading_to_edge): New function.
	(apply_return_prediction): Use it.
	(predict_paths_for_bb): Do not special case abnormals.
	* gcc.target/i386/pr46939.c: New testcase.
Index: testsuite/gcc.target/i386/pr46939.c
===================================================================
*** testsuite/gcc.target/i386/pr46939.c	(revision 0)
--- testsuite/gcc.target/i386/pr46939.c	(revision 0)
***************
*** 0 ****
--- 1,118 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2" } */
+ int
+ php_filter_parse_int (char const *str, unsigned int str_len, long *ret)
+ {
+   long ctx_value;
+   int sign;
+   int digit;
+   char const *end;
+   int tmp;
+   char const *tmp___0;
+   char const *tmp___1;
+ 
+   sign = 0;
+   digit = 0;
+   end = str + str_len;
+   switch ((int) *str)
+     {
+     case 45:
+       sign = 1;
+     case 43:
+       str++;
+     default:;
+       break;
+     }
+   if ((unsigned long) str < (unsigned long) end)
+     {
+       if ((int const) *str >= 49)
+ 	{
+ 	  if ((int const) *str <= 57)
+ 	    {
+ 	      if (sign)
+ 		{
+ 		  tmp = -1;
+ 		}
+ 	      else
+ 		{
+ 		  tmp = 1;
+ 		}
+ 	      tmp___0 = str;
+ 	      str++;
+ 	      ctx_value = (long) (tmp * (int) ((int const) *tmp___0 - 48));
+ 	    }
+ 	  else
+ 	    {
+ 	      return (-1);
+ 	    }
+ 	}
+       else
+ 	{
+ 	  return (-1);
+ 	}
+     }
+   else
+     {
+       return (-1);
+     }
+   if (end - str > 19)
+     {
+       return (-1);
+     }
+   while ((unsigned long) str < (unsigned long) end)
+     {
+       if ((int const) *str >= 48)
+ 	{
+ 	  if ((int const) *str <= 57)
+ 	    {
+ 	      tmp___1 = str;
+ 	      str++;
+ 	      digit = (int) ((int const) *tmp___1 - 48);
+ 	      if (!sign)
+ 		{
+ 		  if (ctx_value <=
+ 		      (9223372036854775807L - (long) digit) / 10L)
+ 		    {
+ 		      ctx_value = ctx_value * 10L + (long) digit;
+ 		    }
+ 		  else
+ 		    {
+ 		      goto _L;
+ 		    }
+ 		}
+ 	      else
+ 		{
+ 		_L:
+ 		  if (sign)
+ 		    {
+ 		      if (ctx_value >=
+ 			  ((-0x7FFFFFFFFFFFFFFF - 1) + (long) digit) / 10L)
+ 			{
+ 			  ctx_value = ctx_value * 10L - (long) digit;
+ 			}
+ 		      else
+ 			{
+ 			  return (-1);
+ 			}
+ 		    }
+ 		  else
+ 		    {
+ 		      return (-1);
+ 		    }
+ 		}
+ 	    }
+ 	  else
+ 	    {
+ 	      return (-1);
+ 	    }
+ 	}
+       else
+ 	{
+ 	  return (-1);
+ 	}
+     }
+   *ret = ctx_value;
+   return (1);
+ }
+ 
+ /* { dg-final { scan-assembler-not "idiv" } } */
Index: predict.c
===================================================================
*** predict.c	(revision 167855)
--- predict.c	(working copy)
*************** static sreal real_zero, real_one, real_a
*** 77,82 ****
--- 77,83 ----
  static void combine_predictions_for_insn (rtx, basic_block);
  static void dump_prediction (FILE *, enum br_predictor, int, basic_block, int);
  static void predict_paths_leading_to (basic_block, enum br_predictor, enum prediction);
+ static void predict_paths_leading_to_edge (edge, enum br_predictor, enum prediction);
  static bool can_predict_insn_p (const_rtx);
  
  /* Information we hold about each branch predictor.
*************** apply_return_prediction (void)
*** 1558,1565 ****
        {
  	pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
  	if (pred != PRED_NO_PREDICTION)
! 	  predict_paths_leading_to (gimple_phi_arg_edge (phi, i)->src, pred,
! 				    direction);
        }
  }
  
--- 1559,1566 ----
        {
  	pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
  	if (pred != PRED_NO_PREDICTION)
! 	  predict_paths_leading_to_edge (gimple_phi_arg_edge (phi, i), pred,
! 				         direction);
        }
  }
  
*************** predict_paths_for_bb (basic_block cur, b
*** 1805,1812 ****
        edge_iterator ei2;
        bool found = false;
  
!       /* Ignore abnormals, we predict them as not taken anyway.  */
!       if (e->flags & (EDGE_EH | EDGE_FAKE | EDGE_ABNORMAL))
  	continue;
        gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));
  
--- 1806,1813 ----
        edge_iterator ei2;
        bool found = false;
  
!       /* Ignore fake edges and eh, we predict them as not taken anyway.  */
!       if (e->flags & (EDGE_EH | EDGE_FAKE))
  	continue;
        gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));
  
*************** predict_paths_for_bb (basic_block cur, b
*** 1814,1820 ****
  	 and does not lead to BB.  */
        FOR_EACH_EDGE (e2, ei2, e->src->succs)
  	if (e2 != e
! 	    && !(e2->flags & (EDGE_EH | EDGE_FAKE | EDGE_ABNORMAL))
  	    && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb))
  	  {
  	    found = true;
--- 1815,1821 ----
  	 and does not lead to BB.  */
        FOR_EACH_EDGE (e2, ei2, e->src->succs)
  	if (e2 != e
! 	    && !(e2->flags & (EDGE_EH | EDGE_FAKE))
  	    && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb))
  	  {
  	    found = true;
*************** predict_paths_leading_to (basic_block bb
*** 1844,1849 ****
--- 1845,1875 ----
  {
    predict_paths_for_bb (bb, bb, pred, taken);
  }
+ 
+ /* Like predict_paths_leading_to but take edge instead of basic block.  */
+ 
+ static void
+ predict_paths_leading_to_edge (edge e, enum br_predictor pred,
+ 			       enum prediction taken)
+ {
+   bool has_nonloop_edge = false;
+   edge_iterator ei;
+   edge e2;
+ 
+   basic_block bb = e->src;
+   FOR_EACH_EDGE (e2, ei, bb->succs)
+     if (e2->dest != e->src && e2->dest != e->dest
+ 	&& !(e->flags & (EDGE_EH | EDGE_FAKE))
+ 	&& !dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->dest))
+       {
+ 	has_nonloop_edge = true;
+ 	break;
+       }
+   if (!has_nonloop_edge)
+     predict_paths_for_bb (bb, bb, pred, taken);
+   else
+     predict_edge_def (e, pred, taken);
+ }
  
  /* This is used to carry information about basic blocks.  It is
     attached to the AUX field of the standard CFG block.  */