From patchwork Wed Mar 28 23:54:59 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dehao Chen X-Patchwork-Id: 149332 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 2BC6FB6F62 for ; Thu, 29 Mar 2012 10:55:20 +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=1333583722; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: MIME-Version:Received:Received:Date:Message-ID:Subject:From:To: Cc:Content-Type:Mailing-List:Precedence:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:Sender:Delivered-To; bh=z1AK/ia M/woJJ7LPDVKPsYk/X3Q=; b=yGDfxkPk85UgC9e69lOm0z/xHhl/bYWoDXeTV97 CL3R//1zQez/8s85UhPYkLFlDEMRIVKol8XBIQrZ6eCW6X/KhqD8dSbl/PlRaK+c 4eTOblceLdJO0UEc+pF2WvAtHH/AOl1Kb7nhTTaNAlWUgZh6jl/irb2nrrgI8j8T jcGY= 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:Date:Message-ID:Subject:From:To:Cc:Content-Type: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=ZlUd3TMbVEbun+hIMqfkaHZ8CbT2XykZdJSXMN0UFjFzK2I9FCH40g2fRmZhdQ QlliHjfjM+ct1JJEBk5lLnVSzJKLjE6G3hJmWWOpAj7NPMD34bX8fLRuzPuM4qFq Tj76fI+cfcq0zbFMBNQGx1/+kNOPipNq0sHrb6ys/6gdY=; Received: (qmail 14885 invoked by alias); 28 Mar 2012 23:55:13 -0000 Received: (qmail 14876 invoked by uid 22791); 28 Mar 2012 23:55:12 -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-pb0-f47.google.com (HELO mail-pb0-f47.google.com) (209.85.160.47) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 28 Mar 2012 23:54:59 +0000 Received: by pbcum15 with SMTP id um15so2497073pbc.20 for ; Wed, 28 Mar 2012 16:54:59 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=mime-version:date:message-id:subject:from:to:cc:content-type :x-system-of-record:x-gm-message-state; bh=pIwflfMOLbW0Z5ZCscIIqsLd5PJ+bplEV8rT8HbvD90=; b=MFGd+hqocYBW6rVSxy11KE0LFkKnnoGUCy0hNglF1oyJk1dRo2LV6Ml8Kagfi60xDZ tSJ/0XMPaufB9ICi8aUUTS59gyqUWnYc13B3ANNMzzYrGryjAwSR/TKNw21a38qG7dXY THBzl79U979mXJfVNaKi9+ycAtHF8HzUNQZA5dcYMU5ZL31FA6TAdgSFxnQ8hiouBryK Iv17OFYL6ZLDjhdECnYCAk04ryRPMclqMT+RlTWKxptLKhGngraDnkNJnZfXQo8ft0re AWs/oGQJ0Irl1kI0TratAOFbGf7iUXpxOBQjI96HT+LsZOBx26i+0gZ+QwIRtBI8HbDn 8kSg== Received: by 10.68.73.103 with SMTP id k7mr641531pbv.132.1332978899478; Wed, 28 Mar 2012 16:54:59 -0700 (PDT) MIME-Version: 1.0 Received: by 10.68.73.103 with SMTP id k7mr641522pbv.132.1332978899409; Wed, 28 Mar 2012 16:54:59 -0700 (PDT) Received: by 10.142.172.14 with HTTP; Wed, 28 Mar 2012 16:54:59 -0700 (PDT) Date: Thu, 29 Mar 2012 07:54:59 +0800 Message-ID: Subject: [google] Refine static branch prediction (iv-compare heuristic) From: Dehao Chen To: gcc-patches@gcc.gnu.org Cc: David Li X-System-Of-Record: true X-Gm-Message-State: ALoCoQktREAZHyGrnlotd4ouzWqjAw7HIZJkbwH2cSf5c5nWKof5vLEduJLkeAANF/NakQlsvX9t6tXu391MMQZ69hk65egY+L3XonFqHzFZGYCikw76UFpf/H2q1rumVtrrzXR9mRQ1Jj0D4kIQgyVIlKc0DIw4OA== 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 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. */