From patchwork Thu Mar 29 02:55:51 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Dehao Chen X-Patchwork-Id: 149359 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 69C35B6EEC for ; Thu, 29 Mar 2012 13:56:12 +1100 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1333594572; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: MIME-Version:Received:Received:In-Reply-To:References:Date: Message-ID:Subject:From:To:Cc:Content-Type: Content-Transfer-Encoding:Mailing-List:Precedence:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:Sender: Delivered-To; bh=LRFXcif1jDwIrEYz6zCjJXshEAY=; b=K98W75/AkK/K9mT qjJfSBTF54MXSn9jyMFoGQ61LRvsz7NiFU1haSF/xI+uq9l+D6PHNNbPEJ20N522 V7zD2QVQsqUde9dbxVp/2X5qs8skllDQmxDoUbYlhOFDAeaDfW0mX35LO8A7nobu ykocM35iC/wB3xtJM2FMgX/5MMIo= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:X-Google-DKIM-Signature:Received:MIME-Version:Received:Received:In-Reply-To:References:Date:Message-ID:Subject:From:To:Cc:Content-Type:Content-Transfer-Encoding:X-System-Of-Record:X-Gm-Message-State:X-IsSubscribed:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=HRYHtI15YATNTJTlBklfThx/KOZWY2sgr3RG0MUIVLkQ7F9nOtpKqUvbUtUi5s GFx0UZPdaZwvhYgqNKTILqV9cbt1CDJ4uO/q7El6KuNY5ZIBhcxe2+MdUzri3Ruj y/YqNPus3NRa/Ri0avmuimaU1U/6lX8l0mdOPeZLUD2xU=; Received: (qmail 19516 invoked by alias); 29 Mar 2012 02:56:08 -0000 Received: (qmail 19507 invoked by uid 22791); 29 Mar 2012 02:56:06 -0000 X-SWARE-Spam-Status: No, hits=-2.9 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, RCVD_IN_DNSWL_LOW, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mail-gx0-f175.google.com (HELO mail-gx0-f175.google.com) (209.85.161.175) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 29 Mar 2012 02:55:53 +0000 Received: by ggcy3 with SMTP id y3so1293612ggc.20 for ; Wed, 28 Mar 2012 19:55:52 -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:content-transfer-encoding:x-system-of-record :x-gm-message-state; bh=GrBrqhxdqQAWISacf37/SZK+jbAM8qBlOjhc3DaDO9o=; b=QOW7vfn/y+eoj0VS6renecTBz/ERQJAMtyPdQYyOgsP0IuZY8XFFDTqZHs6B2v1Ru5 t/AIxjSzycx46Zxuw1fMZrAdFSVeOB66rUQTzUSeCTS8tdjNncO/UJ6Zet5O/FLdlgcW 9y8/ITGtwsXeecDMjcAHde4FNh+1L/hznc0yZfjuG2GTWzJhxI5vNtewNhmHRYp413nW mlFtnhNKr3Vz9qj0Skv/javK7eoaO/OrMpeNIlRQC/4mj2Ww45DQSb/hEb3AE8vuxi1T klyg9GkteXYXkgvGRK6JOQSP1zPifySe/audTM96MzuS+I15KZ3NmbMD/PmkUCQN6hZH ReZA== Received: by 10.68.135.7 with SMTP id po7mr702186pbb.132.1332989751934; Wed, 28 Mar 2012 19:55:51 -0700 (PDT) MIME-Version: 1.0 Received: by 10.68.135.7 with SMTP id po7mr702167pbb.132.1332989751837; Wed, 28 Mar 2012 19:55:51 -0700 (PDT) Received: by 10.142.172.14 with HTTP; Wed, 28 Mar 2012 19:55:51 -0700 (PDT) In-Reply-To: References: Date: Thu, 29 Mar 2012 10:55:51 +0800 Message-ID: Subject: Re: [google] Refine static branch prediction (iv-compare heuristic) From: Dehao Chen To: Xinliang David Li Cc: gcc-patches@gcc.gnu.org X-System-Of-Record: true X-Gm-Message-State: ALoCoQnETeNviWRjbIyBgesqBDhM5uM0re9Z7eSiHlC/EpE08A6w62/k92zJW569n006KtAyxNkC2buM3bEeczbOyPG9BDnpIimciQeAjLhgTXi+3Y6RF3UHEAdWAyTKW3CHoozpYZ8uoZsogT0RoUF6KWnBKfGozA== X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Thanks, attached is the updated patch. Dehao On Thu, Mar 29, 2012 at 8:06 AM, Xinliang David Li wrote: > Can the test case be improved so that expected prediction results is > checked (with the help of more dumping such as blah blah is predicted > to be taken/not taken with probability xyz) ? > > Also the more test cases need to be added to cover more cases >base, > > base +1, >=base +2, < base+1, <=base+1 etc -- even though expression > reassociation will normalize them ... > > Thanks, > > David > > On Wed, Mar 28, 2012 at 4:54 PM, Dehao Chen wrote: >> Hi, >> >> This patch handles the comparison of iv against the loop iv initial >> value. Previously, we only handle the comparison of iv against its >> bound. >> >> Bootstrapped and passed all regression tests. >> >> Ok for google branches? >> >> Thanks, >> Dehao >> >> 2012-03-29  Dehao Chen   >> >>        * predict.c (predict_iv_comparison): Add the comparison of induction >>        variable against its initial value. >> >> 2012-03-29  Dehao Chen   >> >>        * gcc.dg/predict-5.c: Check if LOOP_IV_COMPARE static predict >>        heuristic is working properly. >> >> Index: gcc/testsuite/gcc.dg/predict-5.c >> =================================================================== >> --- gcc/testsuite/gcc.dg/predict-5.c    (revision 0) >> +++ gcc/testsuite/gcc.dg/predict-5.c    (revision 0) >> @@ -0,0 +1,21 @@ >> +/* { dg-do compile } */ >> +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */ >> + >> +extern int global; >> + >> +int bar(int); >> + >> +void foo (int base, int bound) >> +{ >> +  int i, ret = 0; >> +  for (i = base; i <= bound; i++) >> +    { >> +      if (i > base + 2) >> +       global += bar (i); >> +      else >> +        global += bar (i + 1); >> +    } >> +} >> + >> +/* { dg-final { scan-tree-dump "loop iv compare heuristics" >> "profile_estimate"} } */ >> +/* { dg-final { cleanup-tree-dump "profile_estimate" } } */ >> Index: gcc/predict.c >> =================================================================== >> --- gcc/predict.c       (revision 185903) >> +++ gcc/predict.c       (working copy) >> @@ -1185,8 +1185,7 @@ >>       return; >>     } >> >> -  if (!expr_coherent_p (loop_bound_var, compare_var) >> -      || loop_iv_base_var != compare_base) >> +  if (loop_iv_base_var != compare_base) >>     return; >> >>   /* If loop bound, base and compare bound are all constents, we can >> @@ -1230,34 +1229,52 @@ >>       return; >>     } >> >> -  if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR) >> -      && (compare_code == LT_EXPR || compare_code == LE_EXPR)) >> -    predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN); >> -  else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR) >> -          && (compare_code == GT_EXPR || compare_code == GE_EXPR)) >> -    predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN); >> -  else if (loop_bound_code == NE_EXPR) >> -    { >> -      /* If the loop backedge condition is "(i != bound)", we do >> -        the comparison based on the step of IV: >> -          * step < 0 : backedge condition is like (i > bound) >> -          * step > 0 : backedge condition is like (i < bound)  */ >> -      gcc_assert (loop_bound_step != 0); >> +  if (expr_coherent_p (loop_bound_var, compare_var)) >> +    { >> +      if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR) >> +         && (compare_code == LT_EXPR || compare_code == LE_EXPR)) >> +       predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN); >> +      else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR) >> +              && (compare_code == GT_EXPR || compare_code == GE_EXPR)) >> +       predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN); >> +      else if (loop_bound_code == NE_EXPR) >> +       { >> +         /* If the loop backedge condition is "(i != bound)", we do >> +            the comparison based on the step of IV: >> +            * step < 0 : backedge condition is like (i > bound) >> +            * step > 0 : backedge condition is like (i < bound)  */ >> +         gcc_assert (loop_bound_step != 0); >> +         if (loop_bound_step > 0 >> +             && (compare_code == LT_EXPR >> +                 || compare_code == LE_EXPR)) >> +           predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN); >> +         else if (loop_bound_step < 0 >> +                  && (compare_code == GT_EXPR >> +                      || compare_code == GE_EXPR)) >> +           predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN); >> +         else >> +           predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN); >> +       } >> +      else >> +       /* The branch is predicted not-taken if loop_bound_code is >> +          opposite with compare_code.  */ >> +       predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN); >> +    } >> +  else if (expr_coherent_p (loop_iv_base_var, compare_var)) >> +    { >> +      /* For cases like: >> +          for (i = s; i < h; i++) >> +            if (i > s + 2) .... >> +        The branch should be predicted taken.  */ >>       if (loop_bound_step > 0 >> -         && (compare_code == LT_EXPR >> -             || compare_code == LE_EXPR)) >> +         && (compare_code == GT_EXPR || compare_code == GE_EXPR)) >>        predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN); >>       else if (loop_bound_step < 0 >> -              && (compare_code == GT_EXPR >> -                  || compare_code == GE_EXPR)) >> +              && (compare_code == LT_EXPR || compare_code == LE_EXPR)) >>        predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN); >>       else >>        predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN); >>     } >> -  else >> -    /* The branch is predicted not-taken if loop_bound_code is >> -       opposite with compare_code.  */ >> -    predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN); >>  } >> >>  /* Predict edge probabilities by exploiting loop structure.  */ Index: gcc/testsuite/gcc.dg/predict-3.c =================================================================== --- gcc/testsuite/gcc.dg/predict-3.c (revision 185903) +++ gcc/testsuite/gcc.dg/predict-3.c (working copy) @@ -10,10 +10,16 @@ int i, ret = 0; for (i = 0; i <= bound; i++) { + if (i < bound - 2) + global += bar (i); + if (i <= bound) + global += bar (i); + if (i + 1 < bound) + global += bar (i); if (i != bound) global += bar (i); } } -/* { dg-final { scan-tree-dump "loop iv compare heuristics" "profile_estimate"} } */ +/* { dg-final { scan-tree-dump-times "loop iv compare heuristics: 100.0%" 4 "profile_estimate"} } */ /* { dg-final { cleanup-tree-dump "profile_estimate" } } */ Index: gcc/testsuite/gcc.dg/predict-4.c =================================================================== --- gcc/testsuite/gcc.dg/predict-4.c (revision 185903) +++ gcc/testsuite/gcc.dg/predict-4.c (working copy) @@ -15,5 +15,5 @@ } } -/* { dg-final { scan-tree-dump "loop iv compare heuristics" "profile_estimate"} } */ +/* { dg-final { scan-tree-dump "loop iv compare heuristics: 50.0%" "profile_estimate"} } */ /* { dg-final { cleanup-tree-dump "profile_estimate" } } */ Index: gcc/testsuite/gcc.dg/predict-1.c =================================================================== --- gcc/testsuite/gcc.dg/predict-1.c (revision 185903) +++ gcc/testsuite/gcc.dg/predict-1.c (working copy) @@ -10,10 +10,18 @@ int i, ret = 0; for (i = 0; i < bound; i++) { + if (i > bound) + global += bar (i); + if (i >= bound + 2) + global += bar (i); if (i > bound - 2) global += bar (i); + if (i + 2 > bound) + global += bar (i); + if (i == 10) + global += bar (i); } } -/* { dg-final { scan-tree-dump "loop iv compare heuristics" "profile_estimate"} } */ +/* { dg-final { scan-tree-dump-times "loop iv compare heuristics: 0.0%" 5 "profile_estimate"} } */ /* { dg-final { cleanup-tree-dump "profile_estimate" } } */ Index: gcc/testsuite/gcc.dg/predict-5.c =================================================================== --- gcc/testsuite/gcc.dg/predict-5.c (revision 0) +++ gcc/testsuite/gcc.dg/predict-5.c (revision 0) @@ -0,0 +1,25 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */ + +extern int global; + +int bar (int); + +void foo (int base, int bound) +{ + int i, ret = 0; + for (i = base; i <= bound; i++) + { + if (i > base) + global += bar (i); + if (i > base + 1) + global += bar (i); + if (i >= base + 3) + global += bar (i); + if (i - 2 >= base) + global += bar (i); + } +} + +/* { dg-final { scan-tree-dump-times "loop iv compare heuristics: 100.0%" 4 "profile_estimate"} } */ +/* { dg-final { cleanup-tree-dump "profile_estimate" } } */ Index: gcc/testsuite/gcc.dg/predict-2.c =================================================================== --- gcc/testsuite/gcc.dg/predict-2.c (revision 185903) +++ gcc/testsuite/gcc.dg/predict-2.c (working copy) @@ -5,12 +5,20 @@ int bar(int); -void foo (int bound) +void foo (int base, int bound) { int i, ret = 0; - for (i = 0; i < bound; i++) + for (i = base; i < bound; i++) { - if (i > bound * bound ) + if (i > bound * bound) + global += bar (i); + if (i > bound + 10) + global += bar (i); + if (i <= bound + 10) + global += bar (i); + if (i > base + 10) + global += bar (i); + if (i < base - 10) global += bar (i); } } Index: gcc/testsuite/gcc.dg/predict-6.c =================================================================== --- gcc/testsuite/gcc.dg/predict-6.c (revision 0) +++ gcc/testsuite/gcc.dg/predict-6.c (revision 0) @@ -0,0 +1,25 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */ + +extern int global; + +int bar (int); + +void foo (int base, int bound) +{ + int i, ret = 0; + for (i = base; i <= bound; i++) + { + if (i < base) + global += bar (i); + if (i < base + 1) + global += bar (i); + if (i <= base + 3) + global += bar (i); + if (i - 1 < base) + global += bar (i); + } +} + +/* { dg-final { scan-tree-dump-times "loop iv compare heuristics: 0.0%" 4 "profile_estimate"} } */ +/* { dg-final { cleanup-tree-dump "profile_estimate" } } */ Index: gcc/predict.c =================================================================== --- gcc/predict.c (revision 185903) +++ gcc/predict.c (working copy) @@ -1070,6 +1070,8 @@ bound = get_base_value (bound); if (!bound) return false; + if (TREE_CODE (base) != INTEGER_CST) + base = get_base_value (base); *loop_invariant = bound; *compare_code = code; @@ -1185,8 +1187,7 @@ return; } - if (!expr_coherent_p (loop_bound_var, compare_var) - || loop_iv_base_var != compare_base) + if (!expr_coherent_p(loop_iv_base_var, compare_base)) return; /* If loop bound, base and compare bound are all constents, we can @@ -1230,34 +1231,52 @@ return; } - if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR) - && (compare_code == LT_EXPR || compare_code == LE_EXPR)) - predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN); - else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR) - && (compare_code == GT_EXPR || compare_code == GE_EXPR)) - predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN); - else if (loop_bound_code == NE_EXPR) - { - /* If the loop backedge condition is "(i != bound)", we do - the comparison based on the step of IV: - * step < 0 : backedge condition is like (i > bound) - * step > 0 : backedge condition is like (i < bound) */ - gcc_assert (loop_bound_step != 0); + if (expr_coherent_p (loop_bound_var, compare_var)) + { + if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR) + && (compare_code == LT_EXPR || compare_code == LE_EXPR)) + predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN); + else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR) + && (compare_code == GT_EXPR || compare_code == GE_EXPR)) + predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN); + else if (loop_bound_code == NE_EXPR) + { + /* If the loop backedge condition is "(i != bound)", we do + the comparison based on the step of IV: + * step < 0 : backedge condition is like (i > bound) + * step > 0 : backedge condition is like (i < bound) */ + gcc_assert (loop_bound_step != 0); + if (loop_bound_step > 0 + && (compare_code == LT_EXPR + || compare_code == LE_EXPR)) + predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN); + else if (loop_bound_step < 0 + && (compare_code == GT_EXPR + || compare_code == GE_EXPR)) + predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN); + else + predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN); + } + else + /* The branch is predicted not-taken if loop_bound_code is + opposite with compare_code. */ + predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN); + } + else if (expr_coherent_p (loop_iv_base_var, compare_var)) + { + /* For cases like: + for (i = s; i < h; i++) + if (i > s + 2) .... + The branch should be predicted taken. */ if (loop_bound_step > 0 - && (compare_code == LT_EXPR - || compare_code == LE_EXPR)) + && (compare_code == GT_EXPR || compare_code == GE_EXPR)) predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN); else if (loop_bound_step < 0 - && (compare_code == GT_EXPR - || compare_code == GE_EXPR)) + && (compare_code == LT_EXPR || compare_code == LE_EXPR)) predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN); else predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN); } - else - /* The branch is predicted not-taken if loop_bound_code is - opposite with compare_code. */ - predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN); } /* Predict edge probabilities by exploiting loop structure. */