Do not predict one edge by the same path based predictor multiple times

[Jan Hubicka <hubicka at ucw dot cz>]

Hi,
paths that predict control dependence edges which controls execution of some unlikely
piece of code may end up putting multiple predictions at one edge (such that if one
edge controls calls to multiple noreturn functions). These predictions can then combine
into quite insanely small probabilities which is not really expected behaviour.
This patch limits predict_paths_for_bb to drop at most one branch prediction on the
edge (and also fixes potential nonlinearlity).

Bootstrapped/regtested x86_64-linux, will commit it shortly.

Honza

	* predict.c (edge_predicted_by_p): New function.
	(predict_paths_for_bb): Do not put multiple predictions of the same type
	on one edge.

Index: predict.c
===================================================================
--- predict.c	(revision 236815)
+++ predict.c	(working copy)
@@ -478,6 +478,31 @@ gimple_predicted_by_p (const_basic_block
   return false;
 }
 
+/* Return true if the one of outgoing edges is already predicted by
+   PREDICTOR for edge E predicted as TAKEN.  */
+
+bool
+edge_predicted_by_p (edge e, enum br_predictor predictor, bool taken)
+{
+  struct edge_prediction *i;
+  basic_block bb = e->src;
+  edge_prediction **preds = bb_predictions->get (bb);
+  if (!preds)
+    return false;
+
+  int probability = predictor_info[(int) predictor].hitrate;
+
+  if (taken != TAKEN)
+    probability = REG_BR_PROB_BASE - probability;
+
+  for (i = *preds; i; i = i->ep_next)
+    if (i->ep_predictor == predictor
+	&& i->ep_edge == e
+	&& i->ep_probability == probability)
+      return true;
+  return false;
+}
+
 /* Return true when the probability of edge is reliable.
 
    The profile guessing code is good at predicting branch outcome (ie.
@@ -2415,7 +2440,10 @@ predict_paths_for_bb (basic_block cur, b
 	 regions that are only reachable by abnormal edges.  We simply
 	 prevent visiting given BB twice.  */
       if (found)
-        predict_edge_def (e, pred, taken);
+	{
+	  if (!edge_predicted_by_p (e, pred, taken))
+            predict_edge_def (e, pred, taken);
+	}
       else if (bitmap_set_bit (visited, e->src->index))
 	predict_paths_for_bb (e->src, e->src, pred, taken, visited);
     }