CbC/CbC_gcc: gcc/predict.c comparison

comparison gcc/predict.c @ 55:77e2b8dfacca gcc-4.4.5

update it from 4.4.3 to 4.5.0

author	ryoma <e075725@ie.u-ryukyu.ac.jp>
date	Fri, 12 Feb 2010 23:39:51 +0900
parents	a06113de4d67
children	b7f97abdc517

comparison

equal deleted inserted replaced

-:c156f1bd5cd9
+:77e2b8dfacca
 /* Branch prediction routines for the GNU compiler.
-Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008
+Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009
 Free Software Foundation, Inc.
 This file is part of GCC.
 GCC is free software; you can redistribute it and/or modify it under
 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
 		   1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX.  */
 static sreal real_zero, real_one, real_almost_one, real_br_prob_base,
 	     real_inv_br_prob_base, real_one_half, real_bb_freq_max;
 /* Random guesstimation given names.
 PROV_VERY_UNLIKELY should be small enough so basic block predicted
 by it gets bellow HOT_BB_FREQUENCY_FRANCTION.  */
 #define PROB_VERY_UNLIKELY	(REG_BR_PROB_BASE / 2000 - 1)
 #define PROB_EVEN		(REG_BR_PROB_BASE / 2)
 #define PROB_VERY_LIKELY	(REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
 #define PROB_ALWAYS		(REG_BR_PROB_BASE)
 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 compute_function_frequency (void);
 static void choose_function_section (void);
 static bool can_predict_insn_p (const_rtx);
 /* Information we hold about each branch predictor.
 Filled using information from predict.def.  */
 || lookup_attribute ("cold", DECL_ATTRIBUTES (edge->caller->decl)))
 return false;
 if (lookup_attribute ("hot", DECL_ATTRIBUTES (edge->caller->decl)))
 return true;
 if (flag_guess_branch_prob
-&& edge->frequency < (CGRAPH_FREQ_MAX
+&& edge->frequency <= (CGRAPH_FREQ_BASE
-			    / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION)))
+			     / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION)))
 return false;
 return true;
 }
 /* Return true in case BB can be CPU intensive and should be optimized
 struct edge_prediction *i;
 void **preds = pointer_map_contains (bb_predictions, bb);
 if (!preds)
 return false;
 for (i = (struct edge_prediction *) *preds; i; i = i->ep_next)
 if (i->ep_predictor == predictor)
 return true;
 return false;
 }
 /* Return true when the probability of edge is reliable.
 The profile guessing code is good at predicting branch outcome (ie.
 taken/not taken), that is predicted right slightly over 75% of time.
 It is however notoriously poor on predicting the probability itself.
 In general the profile appear a lot flatter (with probabilities closer
 to 50%) than the reality so it is bad idea to use it to drive optimization
 to edge E.  */
 void
 remove_predictions_associated_with_edge (edge e)
 {
 void **preds;
 if (!bb_predictions)
 return;
 preds = pointer_map_contains (bb_predictions, e->src);
 {
 rtx prob_note;
 rtx *pnote;
 rtx note;
 int best_probability = PROB_EVEN;
-int best_predictor = END_PREDICTORS;
+enum br_predictor best_predictor = END_PREDICTORS;
 int combined_probability = REG_BR_PROB_BASE / 2;
 int d;
 bool first_match = false;
 bool found = false;
 /* We implement "first match" heuristics and use probability guessed
 by predictor with smallest index.  */
 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 if (REG_NOTE_KIND (note) == REG_BR_PRED)
 {
-	int predictor = INTVAL (XEXP (XEXP (note, 0), 0));
+	enum br_predictor predictor = ((enum br_predictor)
+				       INTVAL (XEXP (XEXP (note, 0), 0)));
 	int probability = INTVAL (XEXP (XEXP (note, 0), 1));
 	found = true;
 	if (best_predictor > predictor)
 	  best_probability = probability, best_predictor = predictor;
 while (*pnote)
 {
 if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
 	{
-	  int predictor = INTVAL (XEXP (XEXP (*pnote, 0), 0));
+	  enum br_predictor predictor = ((enum br_predictor)
+					 INTVAL (XEXP (XEXP (*pnote, 0), 0)));
 	  int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
 	  dump_prediction (dump_file, predictor, probability, bb,
 			   !first_match || best_predictor == predictor);
 	  *pnote = XEXP (*pnote, 1);
 static void
 combine_predictions_for_bb (basic_block bb)
 {
 int best_probability = PROB_EVEN;
-int best_predictor = END_PREDICTORS;
+enum br_predictor best_predictor = END_PREDICTORS;
 int combined_probability = REG_BR_PROB_BASE / 2;
 int d;
 bool first_match = false;
 bool found = false;
 struct edge_prediction *pred;
 	  second = e;
 	if (!first)
 	  first = e;
 }
 /* When there is no successor or only one choice, prediction is easy.
 We are lazy for now and predict only basic blocks with two outgoing
 edges.  It is possible to predict generic case too, but we have to
 ignore first match heuristics and do more involved combining.  Implement
 this later.  */
 {
 /* We implement "first match" heuristics and use probability guessed
 	 by predictor with smallest index.  */
 for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
 	{
-	  int predictor = pred->ep_predictor;
+	  enum br_predictor predictor = pred->ep_predictor;
 	  int probability = pred->ep_probability;
 	  if (pred->ep_edge != first)
 	    probability = REG_BR_PROB_BASE - probability;
 	           int probability2 = pred->ep_probability;
 		   if (pred2->ep_edge != first)
 		     probability2 = REG_BR_PROB_BASE - probability2;
 		   if ((probability < REG_BR_PROB_BASE / 2) !=
 		       (probability2 < REG_BR_PROB_BASE / 2))
 		     break;
 		   /* If the same predictor later gave better result, go for it! */
 		   if ((probability >= REG_BR_PROB_BASE / 2 && (probability2 > probability))
 if (preds)
 {
 for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
 	{
-	  int predictor = pred->ep_predictor;
+	  enum br_predictor predictor = pred->ep_predictor;
 	  int probability = pred->ep_probability;
 	  if (pred->ep_edge != EDGE_SUCC (bb, 0))
 	    probability = REG_BR_PROB_BASE - probability;
 	  dump_prediction (dump_file, predictor, probability, bb,
 static void
 predict_loops (void)
 {
 loop_iterator li;
 struct loop *loop;
-scev_initialize ();
 /* Try to predict out blocks in a loop that are not part of a
 natural loop.  */
 FOR_EACH_LOOP (li, loop, 0)
 {
 		 We limit the minimal probability by 2% to avoid
 		 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
 		 as this was causing regression in perl benchmark containing such
 		 a wide loop.  */
 	      int probability = ((REG_BR_PROB_BASE
 		                  - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
 				 / n_exits);
 	      if (probability < HITRATE (2))
 		probability = HITRATE (2);
 		if (e->dest->index < NUM_FIXED_BLOCKS
 		    || !flow_bb_inside_loop_p (loop, e->dest))
 		  predict_edge (e, PRED_LOOP_EXIT, probability);
 	    }
 	}
 /* Free basic blocks from get_loop_body.  */
 free (bbs);
 }
-scev_finalize ();
 }
 /* Attempt to predict probabilities of BB outgoing edges using local
 properties.  */
 static void
 return NULL;
 }
 return NULL;
 }
 /* Return constant EXPR will likely have at execution time, NULL if unknown.
 The function is used by builtin_expect branch predictor so the evidence
 must come from this construct and additional possible constant folding.
 We may want to implement more involved value guess (such as value range
 propagation based prediction), but such tricks shall go to new
 implementation.  */
 static tree
 gcc_assert (!*value);
 return false;
 }
 #endif
-/* Predict branch probabilities and estimate profile of the tree CFG.  */
+/* Predict branch probabilities and estimate profile for basic block BB.  */
-static unsigned int
+static void
+tree_estimate_probability_bb (basic_block bb)
+{
+edge e;
+edge_iterator ei;
+gimple last;
+FOR_EACH_EDGE (e, ei, bb->succs)
+{
+/* Predict early returns to be probable, as we've already taken
+	 care for error returns and other cases are often used for
+	 fast paths through function.
+	 Since we've already removed the return statements, we are
+	 looking for CFG like:
+	 if (conditional)
+	 {
+	 ..
+	 goto return_block
+	 }
+	 some other blocks
+	 return_block:
+	 return_stmt.  */
+if (e->dest != bb->next_bb
+	  && e->dest != EXIT_BLOCK_PTR
+	  && single_succ_p (e->dest)
+	  && single_succ_edge (e->dest)->dest == EXIT_BLOCK_PTR
+	  && (last = last_stmt (e->dest)) != NULL
+	  && gimple_code (last) == GIMPLE_RETURN)
+	{
+	  edge e1;
+	  edge_iterator ei1;
+	  if (single_succ_p (bb))
+	    {
+	      FOR_EACH_EDGE (e1, ei1, bb->preds)
+		if (!predicted_by_p (e1->src, PRED_NULL_RETURN)
+		    && !predicted_by_p (e1->src, PRED_CONST_RETURN)
+		    && !predicted_by_p (e1->src, PRED_NEGATIVE_RETURN))
+		  predict_edge_def (e1, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
+	    }
+	  else
+	    if (!predicted_by_p (e->src, PRED_NULL_RETURN)
+		&& !predicted_by_p (e->src, PRED_CONST_RETURN)
+		&& !predicted_by_p (e->src, PRED_NEGATIVE_RETURN))
+	      predict_edge_def (e, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
+	}
+/* Look for block we are guarding (ie we dominate it,
+	 but it doesn't postdominate us).  */
+if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
+	  && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
+	  && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
+	{
+	  gimple_stmt_iterator bi;
+	  /* The call heuristic claims that a guarded function call
+	     is improbable.  This is because such calls are often used
+	     to signal exceptional situations such as printing error
+	     messages.  */
+	  for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi);
+	       gsi_next (&bi))
+	    {
+	      gimple stmt = gsi_stmt (bi);
+	      if (is_gimple_call (stmt)
+		  /* Constant and pure calls are hardly used to signalize
+		     something exceptional.  */
+		  && gimple_has_side_effects (stmt))
+		{
+		  predict_edge_def (e, PRED_CALL, NOT_TAKEN);
+		  break;
+		}
+	    }
+	}
+}
+tree_predict_by_opcode (bb);
+}
+/* Predict branch probabilities and estimate profile of the tree CFG.
+This function can be called from the loop optimizers to recompute
+the profile information.  */
+void
 tree_estimate_probability (void)
 {
 basic_block bb;
-loop_optimizer_init (0);
-if (dump_file && (dump_flags & TDF_DETAILS))
-flow_loops_dump (dump_file, NULL, 0);
 add_noreturn_fake_exit_edges ();
 connect_infinite_loops_to_exit ();
 /* We use loop_niter_by_eval, which requires that the loops have
 preheaders.  */
 create_preheaders (CP_SIMPLE_PREHEADERS);
 calculate_dominance_info (CDI_POST_DOMINATORS);
 bb_predictions = pointer_map_create ();
 tree_bb_level_predictions ();
-mark_irreducible_loops ();
 record_loop_exits ();
 if (number_of_loops () > 1)
 predict_loops ();
 FOR_EACH_BB (bb)
-{
+tree_estimate_probability_bb (bb);
-edge e;
-edge_iterator ei;
-gimple last;
-FOR_EACH_EDGE (e, ei, bb->succs)
-	{
-	  /* Predict early returns to be probable, as we've already taken
-	     care for error returns and other cases are often used for
-	     fast paths through function.
-	     Since we've already removed the return statements, we are
-	     looking for CFG like:
-	       if (conditional)
-	         {
-		   ..
-		   goto return_block
-	         }
-	       some other blocks
-	     return_block:
-	       return_stmt.  */
-	  if (e->dest != bb->next_bb
-	      && e->dest != EXIT_BLOCK_PTR
-	      && single_succ_p (e->dest)
-	      && single_succ_edge (e->dest)->dest == EXIT_BLOCK_PTR
-	      && (last = last_stmt (e->dest)) != NULL
-	      && gimple_code (last) == GIMPLE_RETURN)
-	    {
-	      edge e1;
-	      edge_iterator ei1;
-	      if (single_succ_p (bb))
-		{
-		  FOR_EACH_EDGE (e1, ei1, bb->preds)
-		    if (!predicted_by_p (e1->src, PRED_NULL_RETURN)
-			&& !predicted_by_p (e1->src, PRED_CONST_RETURN)
-			&& !predicted_by_p (e1->src, PRED_NEGATIVE_RETURN))
-		      predict_edge_def (e1, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
-		}
-	       else
-		if (!predicted_by_p (e->src, PRED_NULL_RETURN)
-		    && !predicted_by_p (e->src, PRED_CONST_RETURN)
-		    && !predicted_by_p (e->src, PRED_NEGATIVE_RETURN))
-		  predict_edge_def (e, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
-	    }
-	  /* Look for block we are guarding (ie we dominate it,
-	     but it doesn't postdominate us).  */
-	  if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
-	      && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
-	      && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
-	    {
-	      gimple_stmt_iterator bi;
-	      /* The call heuristic claims that a guarded function call
-		 is improbable.  This is because such calls are often used
-		 to signal exceptional situations such as printing error
-		 messages.  */
-	      for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi);
-		   gsi_next (&bi))
-		{
-		  gimple stmt = gsi_stmt (bi);
-		  if (is_gimple_call (stmt)
-		      /* Constant and pure calls are hardly used to signalize
-			 something exceptional.  */
-		      && gimple_has_side_effects (stmt))
-		    {
-		      predict_edge_def (e, PRED_CALL, NOT_TAKEN);
-		      break;
-		    }
-		}
-	    }
-	}
-tree_predict_by_opcode (bb);
-}
 FOR_EACH_BB (bb)
 combine_predictions_for_bb (bb);
 #ifdef ENABLE_CHECKING
 pointer_map_traverse (bb_predictions, assert_is_empty, NULL);
 bb_predictions = NULL;
 estimate_bb_frequencies ();
 free_dominance_info (CDI_POST_DOMINATORS);
 remove_fake_exit_edges ();
+}
+/* Predict branch probabilities and estimate profile of the tree CFG.
+This is the driver function for PASS_PROFILE.  */
+static unsigned int
+tree_estimate_probability_driver (void)
+{
+unsigned nb_loops;
+loop_optimizer_init (0);
+if (dump_file && (dump_flags & TDF_DETAILS))
+flow_loops_dump (dump_file, NULL, 0);
+mark_irreducible_loops ();
+nb_loops = number_of_loops ();
+if (nb_loops > 1)
+scev_initialize ();
+tree_estimate_probability ();
+if (nb_loops > 1)
+scev_finalize ();
 loop_optimizer_finalize ();
 if (dump_file && (dump_flags & TDF_DETAILS))
 gimple_dump_cfg (dump_file, dump_flags);
 if (profile_status == PROFILE_ABSENT)
 profile_status = PROFILE_GUESSED;
 e = find_edge (bb, head);
 if (e)
 	{
 	  sreal tmp;
 	  /* EDGE_INFO (e)->back_edge_prob
 	     = ((e->probability * BLOCK_INFO (bb)->frequency)
 	     / REG_BR_PROB_BASE); */
 	  sreal_init (&tmp, e->probability, 0);
 	  sreal_mul (&tmp, &tmp, &BLOCK_INFO (bb)->frequency);
 	  sreal_mul (&EDGE_INFO (e)->back_edge_prob,
 		     &tmp, &real_inv_br_prob_base);
 	}
 	      {
 		if (!nextbb)
 		  nextbb = e->dest;
 		else
 		  BLOCK_INFO (last)->next = e->dest;
 		last = e->dest;
 	      }
 	  }
 }
 }
 counts_to_freqs (void)
 {
 gcov_type count_max, true_count_max = 0;
 basic_block bb;
-FOR_EACH_BB (bb)
+FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 true_count_max = MAX (bb->count, true_count_max);
 count_max = MAX (true_count_max, 1);
 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max;
 if (flag_reorder_functions)
 choose_function_section ();
 }
 /* Decide whether function is hot, cold or unlikely executed.  */
-static void
+void
 compute_function_frequency (void)
 {
 basic_block bb;
 if (!profile_info || !flag_branch_probabilities)
 tree
 build_predict_expr (enum br_predictor predictor, enum prediction taken)
 {
 tree t = build1 (PREDICT_EXPR, void_type_node,
 		   build_int_cst (NULL, predictor));
-PREDICT_EXPR_OUTCOME (t) = taken;
+SET_PREDICT_EXPR_OUTCOME (t, taken);
 return t;
 }
 const char *
 predictor_name (enum br_predictor predictor)
 {
 return predictor_info[predictor].name;
 }
 struct gimple_opt_pass pass_profile =
 {
 {
 GIMPLE_PASS,
 "profile",				/* name */
 gate_estimate_probability,		/* gate */
-tree_estimate_probability,		/* execute */
+tree_estimate_probability_driver,	/* execute */
 NULL,					/* sub */
 NULL,					/* next */
 0,					/* static_pass_number */
 TV_BRANCH_PROB,			/* tv_id */
 PROP_cfg,				/* properties_required */
 0,					/* todo_flags_start */
 TODO_ggc_collect | TODO_verify_ssa			/* todo_flags_finish */
 }
 };
 struct gimple_opt_pass pass_strip_predict_hints =
 {
 {
 GIMPLE_PASS,
-NULL,					/* name */
+"*strip_predict_hints",		/* name */
 NULL,					/* gate */
 strip_predict_hints,			/* execute */
 NULL,					/* sub */
 NULL,					/* next */
 0,					/* static_pass_number */

Mercurial > hg > CbC > CbC_gcc

comparison gcc/predict.c @ 55:77e2b8dfacca gcc-4.4.5