This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Profile updating
- From: Jan Hubicka <jh at suse dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Mon, 16 Aug 2004 11:39:52 +0200
- Subject: Profile updating
Hi,
this patch lets profile to be updated after basic block splitting. As
discussed with Richard briefly on the summit, I don't require everyone
to properly distribute probabilities when splitting up single condjump
into multiple, instead I simply do the default branch prediciton to
guess the missing gap.
For tree-like splits it would be possible to compute the frequencies via
solving the CFG same way as we do while reading feedback falling back to
branch prediction only for unsolvable cases.. My experience is that
this is not too important (at least for i386) and it will be tricky to
get it working right with frequencies, but I might implement it if the
profile will be too inaccurate.
Bootstrapped/regtested i686-pc-gnu-linux. I will commit it into
mainline in a day in the case no one will find some problems. This is
used for a while on tree-profiling branch to preserve the tree guessed
profile. Since the tree guessed profiles now works almost consistenly
better on tree-profiling branch then RTL guesses, I will push out the
patches shortly even tought there are still considerable rooms for
improvements.
Honza
2004-08-16 Jan Hubicka <jh@suse.cz>
* basic-block.h (gues_outgoing_edge_probabilities): Declare.
* cfgbuild.c (compute_outgoing_frequencies): Guess missing
probabilities.
* predict.c (bb_estimate_probability_locally): Break out from ...
(estimate_probability): .... here.
(guess_outgoing_edge_proabilities): New function.
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.205
diff -c -3 -p -r1.205 basic-block.h
*** basic-block.h 4 Aug 2004 21:37:03 -0000 1.205
--- basic-block.h 15 Aug 2004 22:54:29 -0000
*************** extern bool rtl_predicted_by_p (basic_bl
*** 612,617 ****
--- 612,618 ----
extern void tree_predict_edge (edge, enum br_predictor, int);
extern void rtl_predict_edge (edge, enum br_predictor, int);
extern void predict_edge_def (edge, enum br_predictor, enum prediction);
+ extern void guess_outgoing_edge_probabilities (basic_block);
/* In flow.c */
extern void init_flow (void);
Index: cfgbuild.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgbuild.c,v
retrieving revision 1.51
diff -c -3 -p -r1.51 cfgbuild.c
*** cfgbuild.c 4 Aug 2004 21:37:03 -0000 1.51
--- cfgbuild.c 15 Aug 2004 22:54:29 -0000
*************** compute_outgoing_frequencies (basic_bloc
*** 644,662 ****
if (b->succ && b->succ->succ_next && !b->succ->succ_next->succ_next)
{
rtx note = find_reg_note (BB_END (b), REG_BR_PROB, NULL);
- int probability;
! if (!note)
! return;
! probability = INTVAL (XEXP (note, 0));
! e = BRANCH_EDGE (b);
! e->probability = probability;
! e->count = ((b->count * probability + REG_BR_PROB_BASE / 2)
! / REG_BR_PROB_BASE);
! f = FALLTHRU_EDGE (b);
! f->probability = REG_BR_PROB_BASE - probability;
! f->count = b->count - e->count;
}
if (b->succ && !b->succ->succ_next)
--- 644,663 ----
if (b->succ && b->succ->succ_next && !b->succ->succ_next->succ_next)
{
rtx note = find_reg_note (BB_END (b), REG_BR_PROB, NULL);
! if (note)
! {
! int probability = INTVAL (XEXP (note, 0));
! e = BRANCH_EDGE (b);
! e->probability = probability;
! e->count = ((b->count * probability + REG_BR_PROB_BASE / 2)
! / REG_BR_PROB_BASE);
! f = FALLTHRU_EDGE (b);
! f->probability = REG_BR_PROB_BASE - probability;
! f->count = b->count - e->count;
! return;
! }
}
if (b->succ && !b->succ->succ_next)
*************** compute_outgoing_frequencies (basic_bloc
*** 664,669 ****
--- 665,679 ----
e = b->succ;
e->probability = REG_BR_PROB_BASE;
e->count = b->count;
+ return;
+ }
+ if (flag_guess_branch_prob && b->succ)
+ {
+ guess_outgoing_edge_probabilities (b);
+ if (b->count)
+ for (e = b->succ; e; e = e->succ_next)
+ e->count = ((b->count * e->probability + REG_BR_PROB_BASE / 2)
+ / REG_BR_PROB_BASE);
}
}
*************** find_many_sub_basic_blocks (sbitmap bloc
*** 715,721 ****
}
}
! compute_outgoing_frequencies (bb);
}
FOR_EACH_BB (bb)
--- 725,732 ----
}
}
! if (profile_status != PROFILE_ABSENT)
! compute_outgoing_frequencies (bb);
}
FOR_EACH_BB (bb)
Index: predict.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/predict.c,v
retrieving revision 1.110
diff -c -3 -p -r1.110 predict.c
*** predict.c 4 Aug 2004 21:37:03 -0000 1.110
--- predict.c 15 Aug 2004 22:54:30 -0000
*************** predict_loops (struct loops *loops_info,
*** 615,620 ****
--- 615,720 ----
}
}
+ /* Attempt to predict probabilities of BB outgoing edges using local
+ properties. */
+ static void
+ bb_estimate_probability_locally (basic_block bb)
+ {
+ rtx last_insn = BB_END (bb);
+ rtx cond;
+
+ if (! can_predict_insn_p (last_insn))
+ return;
+ cond = get_condition (last_insn, NULL, false, false);
+ if (! cond)
+ return;
+
+ /* Try "pointer heuristic."
+ A comparison ptr == 0 is predicted as false.
+ Similarly, a comparison ptr1 == ptr2 is predicted as false. */
+ if (COMPARISON_P (cond)
+ && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
+ || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
+ {
+ if (GET_CODE (cond) == EQ)
+ predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
+ else if (GET_CODE (cond) == NE)
+ predict_insn_def (last_insn, PRED_POINTER, TAKEN);
+ }
+ else
+
+ /* Try "opcode heuristic."
+ EQ tests are usually false and NE tests are usually true. Also,
+ most quantities are positive, so we can make the appropriate guesses
+ about signed comparisons against zero. */
+ switch (GET_CODE (cond))
+ {
+ case CONST_INT:
+ /* Unconditional branch. */
+ predict_insn_def (last_insn, PRED_UNCONDITIONAL,
+ cond == const0_rtx ? NOT_TAKEN : TAKEN);
+ break;
+
+ case EQ:
+ case UNEQ:
+ /* Floating point comparisons appears to behave in a very
+ unpredictable way because of special role of = tests in
+ FP code. */
+ if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
+ ;
+ /* Comparisons with 0 are often used for booleans and there is
+ nothing useful to predict about them. */
+ else if (XEXP (cond, 1) == const0_rtx
+ || XEXP (cond, 0) == const0_rtx)
+ ;
+ else
+ predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
+ break;
+
+ case NE:
+ case LTGT:
+ /* Floating point comparisons appears to behave in a very
+ unpredictable way because of special role of = tests in
+ FP code. */
+ if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
+ ;
+ /* Comparisons with 0 are often used for booleans and there is
+ nothing useful to predict about them. */
+ else if (XEXP (cond, 1) == const0_rtx
+ || XEXP (cond, 0) == const0_rtx)
+ ;
+ else
+ predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
+ break;
+
+ case ORDERED:
+ predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
+ break;
+
+ case UNORDERED:
+ predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
+ break;
+
+ case LE:
+ case LT:
+ if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
+ || XEXP (cond, 1) == constm1_rtx)
+ predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
+ break;
+
+ case GE:
+ case GT:
+ if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
+ || XEXP (cond, 1) == constm1_rtx)
+ predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
+ break;
+
+ default:
+ break;
+ }
+ }
+
+
/* Statically estimate the probability that a branch will be taken and produce
estimated profile. When profile feedback is present never executed portions
of function gets estimated. */
*************** estimate_probability (struct loops *loop
*** 636,642 ****
FOR_EACH_BB (bb)
{
rtx last_insn = BB_END (bb);
- rtx cond;
edge e;
if (! can_predict_insn_p (last_insn))
--- 736,741 ----
*************** estimate_probability (struct loops *loop
*** 680,773 ****
}
}
}
!
! cond = get_condition (last_insn, NULL, false, false);
! if (! cond)
! continue;
!
! /* Try "pointer heuristic."
! A comparison ptr == 0 is predicted as false.
! Similarly, a comparison ptr1 == ptr2 is predicted as false. */
! if (COMPARISON_P (cond)
! && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
! || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
! {
! if (GET_CODE (cond) == EQ)
! predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
! else if (GET_CODE (cond) == NE)
! predict_insn_def (last_insn, PRED_POINTER, TAKEN);
! }
! else
!
! /* Try "opcode heuristic."
! EQ tests are usually false and NE tests are usually true. Also,
! most quantities are positive, so we can make the appropriate guesses
! about signed comparisons against zero. */
! switch (GET_CODE (cond))
! {
! case CONST_INT:
! /* Unconditional branch. */
! predict_insn_def (last_insn, PRED_UNCONDITIONAL,
! cond == const0_rtx ? NOT_TAKEN : TAKEN);
! break;
!
! case EQ:
! case UNEQ:
! /* Floating point comparisons appears to behave in a very
! unpredictable way because of special role of = tests in
! FP code. */
! if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
! ;
! /* Comparisons with 0 are often used for booleans and there is
! nothing useful to predict about them. */
! else if (XEXP (cond, 1) == const0_rtx
! || XEXP (cond, 0) == const0_rtx)
! ;
! else
! predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
! break;
!
! case NE:
! case LTGT:
! /* Floating point comparisons appears to behave in a very
! unpredictable way because of special role of = tests in
! FP code. */
! if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
! ;
! /* Comparisons with 0 are often used for booleans and there is
! nothing useful to predict about them. */
! else if (XEXP (cond, 1) == const0_rtx
! || XEXP (cond, 0) == const0_rtx)
! ;
! else
! predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
! break;
!
! case ORDERED:
! predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
! break;
!
! case UNORDERED:
! predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
! break;
!
! case LE:
! case LT:
! if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
! || XEXP (cond, 1) == constm1_rtx)
! predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
! break;
!
! case GE:
! case GT:
! if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
! || XEXP (cond, 1) == constm1_rtx)
! predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
! break;
!
! default:
! break;
! }
}
/* Attach the combined probability to each conditional jump. */
--- 779,785 ----
}
}
}
! bb_estimate_probability_locally (bb);
}
/* Attach the combined probability to each conditional jump. */
*************** estimate_probability (struct loops *loop
*** 808,813 ****
--- 820,833 ----
if (profile_status == PROFILE_ABSENT)
profile_status = PROFILE_GUESSED;
}
+
+ /* Set edge->probability for each succestor edge of BB. */
+ void
+ guess_outgoing_edge_probabilities (basic_block bb)
+ {
+ bb_estimate_probability_locally (bb);
+ combine_predictions_for_insn (BB_END (bb), bb);
+ }
/* Predict using opcode of the last statement in basic block. */