From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 20235 invoked by alias); 31 Jul 2012 10:20:36 -0000 Received: (qmail 20216 invoked by uid 22791); 31 Jul 2012 10:20:35 -0000 X-SWARE-Spam-Status: No, hits=-5.4 required=5.0 tests=AWL,BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,KHOP_RCVD_TRUST,KHOP_THREADED,RCVD_IN_DNSWL_LOW,RCVD_IN_HOSTKARMA_YE,TW_TM,T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mail-pb0-f47.google.com (HELO mail-pb0-f47.google.com) (209.85.160.47) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 31 Jul 2012 10:20:21 +0000 Received: by pbbrq2 with SMTP id rq2so11134293pbb.20 for ; Tue, 31 Jul 2012 03:20:21 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:x-system-of-record:x-gm-message-state; bh=HPeroxOSHL/19jO3UsKeLOwyHYOsxoQmSnIr5YCREBI=; b=Jbx6+VBpBwlC2t1nTlyYYTYcEs6OkJeKMVJL7+KzyVozV0MOkhnJ1/G+ioWUtJLxOe aCp5vCmlbDtYBGrSHdK6iizbm8jMUqrXSPvPafsaVnWCRcPe0fbpzYiazDIHjwcjKnI7 tPEIEfO8Bl3OxQrWSVkmm1zmQauh8U/cn3qnrFlz+j/ByeTu3fshAE0kUtjuaAJTEkNM Ct1lpapZQ9PZJ5fCifWiMiTTSIhR3MNweKaDD15rMScn55h5F1EhanMCC25kDIdsas8T Al48zW1Y50zykUptoXs+y4ZwVjMwZmBK5M792p3fbu8fdDDpC4acSTtOkD+gOjVG9cYm /DcQ== Received: by 10.68.221.227 with SMTP id qh3mr42482459pbc.115.1343730021491; Tue, 31 Jul 2012 03:20:21 -0700 (PDT) MIME-Version: 1.0 Received: by 10.68.221.227 with SMTP id qh3mr42482429pbc.115.1343730021299; Tue, 31 Jul 2012 03:20:21 -0700 (PDT) Received: by 10.68.49.231 with HTTP; Tue, 31 Jul 2012 03:20:21 -0700 (PDT) In-Reply-To: References: Date: Tue, 31 Jul 2012 10:24:00 -0000 Message-ID: Subject: Re: [PATCH] Fix the LOOP_BRANCH prediction From: Dehao Chen To: Richard Guenther Cc: gcc-patches@gcc.gnu.org, Jan Hubicka , David Li Content-Type: text/plain; charset=ISO-8859-1 X-System-Of-Record: true X-Gm-Message-State: ALoCoQnpLvhp2NqSLh1v5zlH40tGLBxTkJ8yl8G02EzuWUD5U6iuMSqQQTh4yAkZwInDo+76UAd0I4B1DRF8Zj0jIyu2Gpz4Rxh/CHxVIZL1PoZy8Sx/lh7RZndllfixSb9D4rezHixxiipEvbxCQg7FqWb/GdEDcSwOsDK1h6AWxd8I2PKgBG9LRL0e7TK1LPIVvBpVVFR/ X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org X-SW-Source: 2012-07/txt/msg01546.txt.bz2 Are you suggesting a patch like this: Index: gcc/predict.c =================================================================== --- gcc/predict.c (revision 189835) +++ gcc/predict.c (working copy) @@ -1319,6 +1319,7 @@ tree loop_bound_var = NULL; tree loop_iv_base = NULL; gimple stmt = NULL; + int header_found = 0; exits = get_loop_exit_edges (loop); n_exits = VEC_length (edge, exits); @@ -1387,9 +1388,20 @@ bbs = get_loop_body (loop); + /* Loop branch heuristics - predict an edge back to a + loop's head as taken. */ + if (loop->latch && loop->latch->loop_father == loop) + { + edge e = find_edge (loop->latch, loop->header); + if (e) + { + header_found = 1; + predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN); + } + } + for (j = 0; j < loop->num_nodes; j++) { - int header_found = 0; edge e; edge_iterator ei; @@ -1402,21 +1414,9 @@ if (predicted_by_p (bb, PRED_CONTINUE)) continue; - /* Loop branch heuristics - predict an edge back to a - loop's head as taken. */ - if (bb == loop->latch) - { - e = find_edge (loop->latch, loop->header); - if (e) - { - header_found = 1; - predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN); - } - } - /* Loop exit heuristics - predict an edge exiting the loop if the conditional has no loop header successors as not taken. */ - if (!header_found + if (!(header_found && bb == loop->latch) /* If we already used more reliable loop exit predictors, do not bother with PRED_LOOP_EXIT. */ && !predicted_by_p (bb, PRED_LOOP_ITERATIONS_GUESSED) On Tue, Jul 31, 2012 at 5:18 PM, Richard Guenther wrote: > On Tue, Jul 31, 2012 at 5:17 AM, Dehao Chen wrote: >> Hi, >> >> This patch fixed the problem when a LOOP_EXIT edge for the inner loop >> happened to target at the LOOP_LATCH of the outer loop. As the outer >> loop is processed first, the LOOP_BRANCH heuristic is honored >> (first_match), thus the inner loop's trip count is 0. (The attached >> unittest demonstrates this). >> >> Bootstrapped and passed gcc regression test. >> >> Is it ok for trunk? >> >> Thanks, >> Dehao >> >> gcc/ChangeLog >> >> 2012-07-30 Dehao Chen >> >> * predict.c (predict_loops): Fix the prediction of LOOP_BRANCH. >> >> gcc/testsuite/ChangeLog >> >> 2012-07-31 Dehao Chen >> >> * gcc.dg/predict-7.c: New test. >> >> Index: gcc/testsuite/gcc.dg/predict-7.c >> =================================================================== >> --- gcc/testsuite/gcc.dg/predict-7.c (revision 0) >> +++ gcc/testsuite/gcc.dg/predict-7.c (revision 0) >> @@ -0,0 +1,17 @@ >> +/* { dg-do compile } */ >> +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */ >> + >> +extern int global; >> + >> +int bar (int); >> + >> +void foo (int base) >> +{ >> + int i; >> + while (global < 10) >> + for (i = base; i < 10; i++) >> + bar (i); >> +} >> + >> +/* { dg-final { scan-tree-dump-times "loop branch heuristics" 0 >> "profile_estimate"} } */ >> +/* { dg-final { cleanup-tree-dump "profile_estimate" } } */ >> Index: gcc/predict.c >> =================================================================== >> --- gcc/predict.c (revision 189835) >> +++ gcc/predict.c (working copy) >> @@ -1404,7 +1404,7 @@ >> >> /* Loop branch heuristics - predict an edge back to a >> loop's head as taken. */ >> - if (bb == loop->latch) >> + if (bb == loop->latch && bb->loop_father == loop) >> { >> e = find_edge (loop->latch, loop->header); >> if (e) > > I think this heuristic should instead move out of the loop iterating over loop > nodes and be done before like > > if (loop->latch) > { > e = find_edge (loop->latch, loop->header); > ... > } > > which also makes header_found initialized before we visit loop blocks. > > Instead the code > > /* Loop exit heuristics - predict an edge exiting the loop if the > conditional has no loop header successors as not taken. */ > if (!header_found > /* If we already used more reliable loop exit predictors, do not > bother with PRED_LOOP_EXIT. */ > ... > FOR_EACH_EDGE (e, ei, bb->succs) > if (e->dest->index < NUM_FIXED_BLOCKS > || !flow_bb_inside_loop_p (loop, e->dest)) > predict_edge (e, PRED_LOOP_EXIT, probability); > > looks wrong for bb's that are parts of an inner loop of loop - assuming we > only want to predicate exits from loop and not exits from an inner loop > that also happen to exit loop (we will do that when predicating the inner loop). You are right. And if we want to change this, we'd also need to modify get_loop_exit_edges to only count edges whose src is in the same loop level. However, this is relatively minor issue because it only predicts inaccurate bias ratio, while in the testcase I gave, LOOP_BRANCH is predicting in the wrong direction. Thanks, Dehao > > Is that what you experienced? > > Thanks, > Richard.