From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 15260 invoked by alias); 12 Sep 2012 14:19:44 -0000 Received: (qmail 15248 invoked by uid 22791); 12 Sep 2012 14:19:42 -0000 X-SWARE-Spam-Status: No, hits=-4.3 required=5.0 tests=ALL_TRUSTED,AWL,BAYES_00,KHOP_THREADED X-Spam-Check-By: sourceware.org Received: from localhost (HELO gcc.gnu.org) (127.0.0.1) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 12 Sep 2012 14:19:25 +0000 From: "rguenth at gcc dot gnu.org" To: gcc-bugs@gcc.gnu.org Subject: [Bug middle-end/54493] -fguess-branch-probability takes ages Date: Wed, 12 Sep 2012 14:19:00 -0000 X-Bugzilla-Reason: CC X-Bugzilla-Type: changed X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: gcc X-Bugzilla-Component: middle-end X-Bugzilla-Keywords: compile-time-hog X-Bugzilla-Severity: normal X-Bugzilla-Who: rguenth at gcc dot gnu.org X-Bugzilla-Status: NEW X-Bugzilla-Priority: P3 X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org X-Bugzilla-Target-Milestone: --- X-Bugzilla-Changed-Fields: Status Last reconfirmed Ever Confirmed Message-ID: In-Reply-To: References: X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/ Auto-Submitted: auto-generated Content-Type: text/plain; charset="UTF-8" MIME-Version: 1.0 Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-bugs-owner@gcc.gnu.org X-SW-Source: 2012-09/txt/msg00932.txt.bz2 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54493 Richard Guenther changed: What |Removed |Added ---------------------------------------------------------------------------- Status|UNCONFIRMED |NEW Last reconfirmed| |2012-09-12 Ever Confirmed|0 |1 --- Comment #1 from Richard Guenther 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; }