[patch] Move predictions list out of basic block
Zdenek Dvorak
rakdver@atrey.karlin.mff.cuni.cz
Sat Apr 21 11:37:00 GMT 2007
Hello,
the "predictions" field of basic block is currently used only inside a
single pass (profile estimation). This patch moves it to a separate table,
thus saving one pointer per bb.
Bootstrapped & regtested on i686.
Zdenek
* predict.c: Include pointer-set.h.
(bb_predictions): New variable.
(tree_predicted_by_p, tree_predict_edge,
remove_predictions_associated_with_edge): Use bb_predictions map
instead of bb->predictions.
(clear_bb_predictions, assert_is_empty): New functions.
(combine_predictions_for_bb): Use bb_predictions map. Call
clear_bb_predictions.
(tree_estimate_probability): Create and free bb_predictions map.
* Makefile.in (predict.o): Add pointer-set.h dependency.
* basic-block.h (struct basic_block_def): Remove predictions
field.
* cfgrtl.c (rtl_verify_flow_info_1): Do not check bb->predictions.
Index: predict.c
===================================================================
*** predict.c (revision 124007)
--- predict.c (working copy)
*************** Software Foundation, 51 Franklin Street,
*** 60,65 ****
--- 60,66 ----
#include "timevar.h"
#include "tree-scalar-evolution.h"
#include "cfgloop.h"
+ #include "pointer-set.h"
/* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
*************** rtl_predicted_by_p (basic_block bb, enum
*** 174,179 ****
--- 175,185 ----
return false;
}
+ /* This map contains for a basic block the list of predictions for the
+ outgoing edges. */
+
+ static struct pointer_map_t *bb_predictions;
+
/* Return true if the one of outgoing edges is already predicted by
PREDICTOR. */
*************** bool
*** 181,187 ****
tree_predicted_by_p (basic_block bb, enum br_predictor predictor)
{
struct edge_prediction *i;
! for (i = bb->predictions; i; i = i->ep_next)
if (i->ep_predictor == predictor)
return true;
return false;
--- 187,198 ----
tree_predicted_by_p (basic_block bb, enum br_predictor predictor)
{
struct edge_prediction *i;
! void **preds = pointer_map_contains (bb_predictions, bb);
!
! if (!preds)
! return false;
!
! for (i = *preds; i; i = i->ep_next)
if (i->ep_predictor == predictor)
return true;
return false;
*************** tree_predict_edge (edge e, enum br_predi
*** 283,292 ****
if ((e->src != ENTRY_BLOCK_PTR && EDGE_COUNT (e->src->succs) > 1)
&& flag_guess_branch_prob && optimize)
{
! struct edge_prediction *i = ggc_alloc (sizeof (struct edge_prediction));
! i->ep_next = e->src->predictions;
! e->src->predictions = i;
i->ep_probability = probability;
i->ep_predictor = predictor;
i->ep_edge = e;
--- 294,304 ----
if ((e->src != ENTRY_BLOCK_PTR && EDGE_COUNT (e->src->succs) > 1)
&& flag_guess_branch_prob && optimize)
{
! struct edge_prediction *i = XNEW (struct edge_prediction);
! void **preds = pointer_map_insert (bb_predictions, e->src);
! i->ep_next = *preds;
! *preds = i;
i->ep_probability = probability;
i->ep_predictor = predictor;
i->ep_edge = e;
*************** tree_predict_edge (edge e, enum br_predi
*** 298,316 ****
void
remove_predictions_associated_with_edge (edge e)
{
! if (e->src->predictions)
{
! struct edge_prediction **prediction = &e->src->predictions;
while (*prediction)
{
if ((*prediction)->ep_edge == e)
! *prediction = (*prediction)->ep_next;
else
prediction = &((*prediction)->ep_next);
}
}
}
/* Return true when we can store prediction on insn INSN.
At the moment we represent predictions only on conditional
jumps, not at computed jump or other complicated cases. */
--- 310,360 ----
void
remove_predictions_associated_with_edge (edge e)
{
! void **preds;
!
! if (!bb_predictions)
! return;
!
! preds = pointer_map_contains (bb_predictions, e->src);
!
! if (preds)
{
! struct edge_prediction **prediction = (struct edge_prediction **) preds;
! struct edge_prediction *next;
!
while (*prediction)
{
if ((*prediction)->ep_edge == e)
! {
! next = (*prediction)->ep_next;
! free (*prediction);
! *prediction = next;
! }
else
prediction = &((*prediction)->ep_next);
}
}
}
+ /* Clears the list of predictions stored for BB. */
+
+ static void
+ clear_bb_predictions (basic_block bb)
+ {
+ void **preds = pointer_map_contains (bb_predictions, bb);
+ struct edge_prediction *pred, *next;
+
+ if (!preds)
+ return;
+
+ for (pred = *preds; pred; pred = next)
+ {
+ next = pred->ep_next;
+ free (pred);
+ }
+ *preds = NULL;
+ }
+
/* Return true when we can store prediction on insn INSN.
At the moment we represent predictions only on conditional
jumps, not at computed jump or other complicated cases. */
*************** combine_predictions_for_bb (basic_block
*** 538,543 ****
--- 582,588 ----
int nedges = 0;
edge e, first = NULL, second = NULL;
edge_iterator ei;
+ void **preds;
FOR_EACH_EDGE (e, ei, bb->succs)
if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
*************** combine_predictions_for_bb (basic_block
*** 559,565 ****
{
if (!bb->count)
set_even_probabilities (bb);
! bb->predictions = NULL;
if (dump_file)
fprintf (dump_file, "%i edges in bb %i predicted to even probabilities\n",
nedges, bb->index);
--- 604,610 ----
{
if (!bb->count)
set_even_probabilities (bb);
! clear_bb_predictions (bb);
if (dump_file)
fprintf (dump_file, "%i edges in bb %i predicted to even probabilities\n",
nedges, bb->index);
*************** combine_predictions_for_bb (basic_block
*** 569,599 ****
if (dump_file)
fprintf (dump_file, "Predictions for bb %i\n", bb->index);
! /* We implement "first match" heuristics and use probability guessed
! by predictor with smallest index. */
! for (pred = bb->predictions; pred; pred = pred->ep_next)
{
! int predictor = pred->ep_predictor;
! int probability = pred->ep_probability;
!
! if (pred->ep_edge != first)
! probability = REG_BR_PROB_BASE - probability;
!
! found = true;
! if (best_predictor > predictor)
! best_probability = probability, best_predictor = predictor;
!
! d = (combined_probability * probability
! + (REG_BR_PROB_BASE - combined_probability)
! * (REG_BR_PROB_BASE - probability));
!
! /* Use FP math to avoid overflows of 32bit integers. */
! if (d == 0)
! /* If one probability is 0% and one 100%, avoid division by zero. */
! combined_probability = REG_BR_PROB_BASE / 2;
! else
! combined_probability = (((double) combined_probability) * probability
! * REG_BR_PROB_BASE / d + 0.5);
}
/* Decide which heuristic to use. In case we didn't match anything,
--- 614,649 ----
if (dump_file)
fprintf (dump_file, "Predictions for bb %i\n", bb->index);
! preds = pointer_map_contains (bb_predictions, bb);
! if (preds)
{
! /* We implement "first match" heuristics and use probability guessed
! by predictor with smallest index. */
! for (pred = *preds; pred; pred = pred->ep_next)
! {
! int predictor = pred->ep_predictor;
! int probability = pred->ep_probability;
!
! if (pred->ep_edge != first)
! probability = REG_BR_PROB_BASE - probability;
!
! found = true;
! if (best_predictor > predictor)
! best_probability = probability, best_predictor = predictor;
!
! d = (combined_probability * probability
! + (REG_BR_PROB_BASE - combined_probability)
! * (REG_BR_PROB_BASE - probability));
!
! /* Use FP math to avoid overflows of 32bit integers. */
! if (d == 0)
! /* If one probability is 0% and one 100%, avoid division by zero. */
! combined_probability = REG_BR_PROB_BASE / 2;
! else
! combined_probability = (((double) combined_probability)
! * probability
! * REG_BR_PROB_BASE / d + 0.5);
! }
}
/* Decide which heuristic to use. In case we didn't match anything,
*************** combine_predictions_for_bb (basic_block
*** 617,633 ****
combined_probability = best_probability;
dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
! for (pred = bb->predictions; pred; pred = pred->ep_next)
{
! int 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,
! !first_match || best_predictor == predictor);
}
! bb->predictions = NULL;
if (!bb->count)
{
--- 667,686 ----
combined_probability = best_probability;
dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
! if (preds)
{
! for (pred = *preds; pred; pred = pred->ep_next)
! {
! int 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,
! !first_match || best_predictor == predictor);
! }
}
! clear_bb_predictions (bb);
if (!bb->count)
{
*************** call_expr:;
*** 1278,1283 ****
--- 1331,1350 ----
free (heads);
}
+ #ifdef ENABLE_CHECKING
+
+ /* Callback for pointer_map_traverse, asserts that the pointer map is
+ empty. */
+
+ static bool
+ assert_is_empty (void *key ATTRIBUTE_UNUSED, void **value,
+ void *data ATTRIBUTE_UNUSED)
+ {
+ gcc_assert (!*value);
+ return false;
+ }
+ #endif
+
/* Predict branch probabilities and estimate profile of the tree CFG. */
static unsigned int
tree_estimate_probability (void)
*************** tree_estimate_probability (void)
*** 1295,1300 ****
--- 1362,1368 ----
create_preheaders (CP_SIMPLE_PREHEADERS);
calculate_dominance_info (CDI_POST_DOMINATORS);
+ bb_predictions = pointer_map_create ();
tree_bb_level_predictions ();
mark_irreducible_loops ();
*************** tree_estimate_probability (void)
*** 1383,1388 ****
--- 1451,1462 ----
FOR_EACH_BB (bb)
combine_predictions_for_bb (bb);
+ #ifdef ENABLE_CHECKING
+ pointer_map_traverse (bb_predictions, assert_is_empty, NULL);
+ #endif
+ pointer_map_destroy (bb_predictions);
+ bb_predictions = NULL;
+
strip_builtin_expect ();
estimate_bb_frequencies ();
free_dominance_info (CDI_POST_DOMINATORS);
Index: Makefile.in
===================================================================
*** Makefile.in (revision 124007)
--- Makefile.in (working copy)
*************** predict.o: predict.c $(CONFIG_H) $(SYSTE
*** 2685,2691 ****
hard-reg-set.h output.h toplev.h $(RECOG_H) $(FUNCTION_H) except.h \
$(TM_P_H) $(PREDICT_H) sreal.h $(PARAMS_H) $(TARGET_H) $(CFGLOOP_H) \
$(COVERAGE_H) $(SCEV_H) $(GGC_H) predict.def $(TIMEVAR_H) $(TREE_DUMP_H) \
! $(TREE_FLOW_H) tree-pass.h $(EXPR_H)
lists.o: lists.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) toplev.h \
$(RTL_H) $(GGC_H) gt-lists.h
bb-reorder.o : bb-reorder.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
--- 2685,2691 ----
hard-reg-set.h output.h toplev.h $(RECOG_H) $(FUNCTION_H) except.h \
$(TM_P_H) $(PREDICT_H) sreal.h $(PARAMS_H) $(TARGET_H) $(CFGLOOP_H) \
$(COVERAGE_H) $(SCEV_H) $(GGC_H) predict.def $(TIMEVAR_H) $(TREE_DUMP_H) \
! $(TREE_FLOW_H) tree-pass.h $(EXPR_H) pointer-set.h
lists.o: lists.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) toplev.h \
$(RTL_H) $(GGC_H) gt-lists.h
bb-reorder.o : bb-reorder.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
Index: basic-block.h
===================================================================
*** basic-block.h (revision 124007)
--- basic-block.h (working copy)
*************** struct basic_block_def GTY((chain_next (
*** 240,248 ****
/* Chain of PHI nodes for this block. */
tree phi_nodes;
- /* A list of predictions. */
- struct edge_prediction *predictions;
-
/* Expected number of executions: calculated in profile.c. */
gcov_type count;
--- 240,245 ----
Index: cfgrtl.c
===================================================================
*** cfgrtl.c (revision 124007)
--- cfgrtl.c (working copy)
*************** rtl_verify_flow_info_1 (void)
*** 1716,1727 ****
bb->index);
err = 1;
}
-
- if (bb->predictions)
- {
- error ("bb prediction set for block %d, but it is not used in RTL land", bb->index);
- err = 1;
- }
}
/* Now check the basic blocks (boundaries etc.) */
--- 1716,1721 ----
More information about the Gcc-patches
mailing list