public inbox for gcc-bugs@sourceware.org help / color / mirror / Atom feed
* [Bug middle-end/54493] New: -fguess-branch-probability takes ages @ 2012-09-05 13:31 rguenth at gcc dot gnu.org 2012-09-12 14:19 ` [Bug middle-end/54493] " rguenth at gcc dot gnu.org 2012-09-12 14:38 ` rguenth at gcc dot gnu.org 0 siblings, 2 replies; 3+ messages in thread From: rguenth at gcc dot gnu.org @ 2012-09-05 13:31 UTC (permalink / raw) To: gcc-bugs http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54493 Bug #: 54493 Summary: -fguess-branch-probability takes ages Classification: Unclassified Product: gcc Version: 4.8.0 Status: UNCONFIRMED Keywords: compile-time-hog Severity: normal Priority: P3 Component: middle-end AssignedTo: unassigned@gcc.gnu.org ReportedBy: rguenth@gcc.gnu.org For the testcase in PR54492 -fguess-branch-probability (default on at -O1) takes ages. ^ permalink raw reply [flat|nested] 3+ messages in thread
* [Bug middle-end/54493] -fguess-branch-probability takes ages 2012-09-05 13:31 [Bug middle-end/54493] New: -fguess-branch-probability takes ages rguenth at gcc dot gnu.org @ 2012-09-12 14:19 ` rguenth at gcc dot gnu.org 2012-09-12 14:38 ` rguenth at gcc dot gnu.org 1 sibling, 0 replies; 3+ messages in thread From: rguenth at gcc dot gnu.org @ 2012-09-12 14:19 UTC (permalink / raw) To: gcc-bugs http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54493 Richard Guenther <rguenth at gcc dot gnu.org> changed: What |Removed |Added ---------------------------------------------------------------------------- Status|UNCONFIRMED |NEW Last reconfirmed| |2012-09-12 Ever Confirmed|0 |1 --- Comment #1 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-09-12 14:19:23 UTC --- Because we accumulate gazillion predictors per BB and do linear scans over them: bool gimple_predicted_by_p (const_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 = (struct edge_prediction *) *preds; i; i = i->ep_next) if (i->ep_predictor == predictor) return true; return false; } Instrumenting gimple_predict_edge shows Adding 22 to edge 2->100003 Adding 22 to edge 2->3 Adding 22 to edge 2->4 Adding 22 to edge 2->5 Adding 22 to edge 2->6 Adding 22 to edge 2->7 Adding 22 to edge 2->8 Adding 22 to edge 2->9 Adding 22 to edge 2->10 Adding 22 to edge 2->11 Adding 22 to edge 2->12 Adding 22 to edge 2->13 Adding 22 to edge 2->14 Adding 22 to edge 2->15 Adding 22 to edge 2->16 Adding 22 to edge 2->17 Adding 22 to edge 2->18 Adding 22 to edge 2->19 Adding 22 to edge 2->20 Adding 22 to edge 2->21 Adding 22 to edge 2->22 ... Adding 22 to edge 2->17332 Adding 22 to edge 2->17333 Adding (and continuing). 22 is the br_predictor (PRED_TREE_EARLY_RETURN). It seems to me that we should have at most one predictor of each kind per basic-block, no? Testcase repeated: int foo (int a, int b, int c) { int d; switch (a) { #define X(N) \ case N ## 0: d = a + b; break; \ case N ## 1: d = a + b; break; \ case N ## 2: d = a + b; break; \ case N ## 3: d = a + b; break; \ case N ## 4: d = a + b; break; \ case N ## 5: d = a + b; break; \ case N ## 6: d = a + b; break; \ case N ## 7: d = a + b; break; \ case N ## 8: d = a + b; break; \ case N ## 9: d = a + b; break; #define XX(N) \ X(N ## 0) X(N ## 1) X(N ## 2) X(N ## 3) X(N ## 4) X(N ## 5) X(N ## 6) X(N ## 7) X(N ## 8) X(N ## 9) #define XXX(N) \ XX(N ## 0) XX(N ## 1) XX(N ## 2) XX(N ## 3) XX(N ## 4) XX(N ## 5) XX(N ## 6) XX(N ## 7) XX(N ## 8) XX(N ## 9) #define XXXX(N) \ XXX(N ## 0) XXX(N ## 1) XXX(N ## 2) XXX(N ## 3) XXX(N ## 4) XXX(N ## 5) XXX(N ## 6) XXX(N ## 7) XXX(N ## 8) XXX(N ## 9) #define XXXXX(N) \ XXXX(N ## 0) XXXX(N ## 1) XXXX(N ## 2) XXXX(N ## 3) XXXX(N ## 4) XXXX(N ## 5) XXXX(N ## 6) XXXX(N ## 7) XXXX(N ## 8) XXXX(N ## 9) XXXXX(1) #if 0 XXXXX(2) XXXXX(3) XXXXX(4) XXXXX(5) XXXXX(6) XXXXX(7) XXXXX(8) XXXXX(9) #endif } return d; } ^ permalink raw reply [flat|nested] 3+ messages in thread
* [Bug middle-end/54493] -fguess-branch-probability takes ages 2012-09-05 13:31 [Bug middle-end/54493] New: -fguess-branch-probability takes ages rguenth at gcc dot gnu.org 2012-09-12 14:19 ` [Bug middle-end/54493] " rguenth at gcc dot gnu.org @ 2012-09-12 14:38 ` rguenth at gcc dot gnu.org 1 sibling, 0 replies; 3+ messages in thread From: rguenth at gcc dot gnu.org @ 2012-09-12 14:38 UTC (permalink / raw) To: gcc-bugs http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54493 --- Comment #2 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-09-12 14:37:51 UTC --- Something like Index: gcc/predict.c =================================================================== --- gcc/predict.c (revision 191222) +++ gcc/predict.c (working copy) @@ -525,8 +525,9 @@ void gimple_predict_edge (edge e, enum br_predictor predictor, int probability) { gcc_assert (profile_status != PROFILE_GUESSED); - if ((e->src != ENTRY_BLOCK_PTR && EDGE_COUNT (e->src->succs) > 1) - && flag_guess_branch_prob && optimize) + if (flag_guess_branch_prob && optimize + && (e->src != ENTRY_BLOCK_PTR && EDGE_COUNT (e->src->succs) > 1) + && !gimple_predicted_by_p (e->src, predictor)) { struct edge_prediction *i = XNEW (struct edge_prediction); void **preds = pointer_map_insert (bb_predictions, e->src); of course that doesn't try to merge the predictors probability nor the edge it is for. Why are the predictors stored per block and not per edge? Another approach would be to fix this special case: && 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); which ends up adding all those (bogus?!) predications to the entry block. Simplified we have foo (int a, int b, int c) { int d; <bb 2>: switch (a_2(D)) <default: <L10>, case 10: <L0>, ... <L0>: d_5 = a_2(D) + b_4(D); goto <bb 13> (<L10>); ... <L9>: d_14 = a_2(D) + b_4(D); # d_1 = PHI <d_3(D)(2), d_5(3), d_6(4), d_7(5), d_8(6), d_9(7), d_10(8), d_11(9), d_12(10), d_13(11), d_14(12)> <L10>: return d_1; and we are adding the loads of !PRED_TREE_EARLY_RETURN to bb 2. Thus as we are only adding PRED_TREE_EARLY_RETURN at this point we can also do @@ -2113,13 +2113,15 @@ tree_estimate_probability_bb (basic_bloc 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)) + && !predicted_by_p (e1->src, PRED_NEGATIVE_RETURN) + && !predicted_by_p (e1->src, PRED_TREE_EARLY_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)) + && !predicted_by_p (e->src, PRED_NEGATIVE_RETURN) + && !predicted_by_p (e->src, PRED_TREE_EARLY_RETURN)) predict_edge_def (e, PRED_TREE_EARLY_RETURN, NOT_TAKEN); } (those predicted_by_p sequences are also inefficient as they repeat the linear walk ...) Honza? ^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2012-09-12 14:38 UTC | newest] Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2012-09-05 13:31 [Bug middle-end/54493] New: -fguess-branch-probability takes ages rguenth at gcc dot gnu.org 2012-09-12 14:19 ` [Bug middle-end/54493] " rguenth at gcc dot gnu.org 2012-09-12 14:38 ` rguenth at gcc dot gnu.org
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).