From patchwork Wed May 30 09:31:00 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dehao Chen X-Patchwork-Id: 161910 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 8D1C4B703C for ; Wed, 30 May 2012 19:31:23 +1000 (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=1338975084; 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:Mailing-List: Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:Sender:Delivered-To; bh=ekga6QbqCSIShxJ/mn8PMtsbNJE=; b=TsQ/nJbaphusd/QLJLxlDfe0U1+uY89KYQQCEMMcR7KYQUDS2jpmI9S09TCj/C A9o+IYWM+53EmRgtrwuqUYBAo9N4AVUysENIhewBmMwLBolbQPUOBnIZXX/DpSOJ xpv2ykNbnikQNobvz/8u7g8pZ69bPXQlgfuxCJQ2I7/wg= 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: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=XkMeICrcCRz31tqiKcI+bmSpOQsyVmic4LfgIyopvFtRlIbjd8CQWC7ZxQDqpt G26bNaHxp8FilhMa4px5ttCs3CVJo8Y5kXt5rHNIXpozpuQImuzT35cwM0H/2NwA wMGsihcRVcvQCl87YkZgurXErrqioJDLVRqp9McKwyHFQ=; Received: (qmail 535 invoked by alias); 30 May 2012 09:31:16 -0000 Received: (qmail 524 invoked by uid 22791); 30 May 2012 09:31:14 -0000 X-SWARE-Spam-Status: No, hits=-5.3 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; Wed, 30 May 2012 09:31:01 +0000 Received: by pbbrq2 with SMTP id rq2so6809335pbb.20 for ; Wed, 30 May 2012 02:31:00 -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=wScQBdolPFX9LwlOmyiTpCtwRaF0PlhI6jXD/xOAYRk=; b=C0PwNojYkMP0kf+Cypof7pq1nj3qaNjZzW0CDUdgE84xNlP5/vYooUG86PyTdwDVKo WVdmE43mEzZ/ydq7T3N6lVntgcAO3947Mp91j7NebxG5hGFes8CnZKqMYubxp7LP6vdu uZ5vqUUiY0mkaSZFC3opK9Ati4o6V4nfG8oGYQSWd8DQgAGsGc6L74LCNHRjw+i1rNU2 G2u56mx5IWF2Q0vh24rAQvxVpGLnku+r8eSxIAhrnqwYfvrX1M616X4XiifK2Xuq9QQm txhbAHKUboyaUGYqOwIPD2cnib/wjCIpO3zGy/elROalyfwsJH3xUh4UvqRRCmWFOoSl gepA== Received: by 10.68.132.199 with SMTP id ow7mr47124192pbb.144.1338370260773; Wed, 30 May 2012 02:31:00 -0700 (PDT) MIME-Version: 1.0 Received: by 10.68.132.199 with SMTP id ow7mr47124164pbb.144.1338370260646; Wed, 30 May 2012 02:31:00 -0700 (PDT) Received: by 10.68.204.198 with HTTP; Wed, 30 May 2012 02:31:00 -0700 (PDT) In-Reply-To: References: Date: Wed, 30 May 2012 17:31:00 +0800 Message-ID: Subject: Re: Predict for loop exits in short-circuit conditions From: Dehao Chen To: gcc-patches@gcc.gnu.org Cc: Jan Hubicka , David Li X-System-Of-Record: true X-Gm-Message-State: ALoCoQn2JoqHa3isZ9AfeRC5MaG3M2nP1fVVHKyzhQ/peN65d5EwrhvESLxyKsMIf0n31dxxZXAPlkls0PYu+WQpURPTDGwnbWYAEJbGwtv5VQkj0wLrx5L1MEf8i6CO9ODzspp1ygTrh4j/OOhjRutOZoHMd+fwDg== 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, I've updated the patch to invoke predict_extra_loop_exits in the right place. Attached is the new patch. Bootstrapped and passed gcc testsuite. Thanks, Dehao Index: testsuite/g++.dg/predict-loop-exit-1.C =================================================================== --- testsuite/g++.dg/predict-loop-exit-1.C (revision 0) +++ testsuite/g++.dg/predict-loop-exit-1.C (revision 0) @@ -0,0 +1,13 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */ + +int g; +int foo(); +void test() { + while (foo() && g < 10) + g++; + return; +} + +/* { dg-final { scan-tree-dump-times "loop exit heuristics:" 3 "profile_estimate"} } */ +/* { dg-final { cleanup-tree-dump "profile_estimate" } } */ Index: testsuite/g++.dg/predict-loop-exit-3.C =================================================================== --- testsuite/g++.dg/predict-loop-exit-3.C (revision 0) +++ testsuite/g++.dg/predict-loop-exit-3.C (revision 0) @@ -0,0 +1,13 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */ + +int g; +int foo(); +void test() { + while (foo() && (g < 10 || g > 20)) + g++; + return; +} + +/* { dg-final { scan-tree-dump-times "loop exit heuristics:" 3 "profile_estimate"} } */ +/* { dg-final { cleanup-tree-dump "profile_estimate" } } */ Index: testsuite/g++.dg/predict-loop-exit-2.C =================================================================== --- testsuite/g++.dg/predict-loop-exit-2.C (revision 0) +++ testsuite/g++.dg/predict-loop-exit-2.C (revision 0) @@ -0,0 +1,13 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */ + +int g; +int foo(); +void test() { + while (foo() || g < 10) + g++; + return; +} + +/* { dg-final { scan-tree-dump-times "loop exit heuristics:" 2 "profile_estimate"} } */ +/* { dg-final { cleanup-tree-dump "profile_estimate" } } */ Index: predict.c =================================================================== --- predict.c (revision 187922) +++ predict.c (working copy) @@ -1294,7 +1294,93 @@ predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN); } } - + +/* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop + exits are resulted from short-circuit conditions that will generate an + if_tmp. E.g.: + + if (foo() || global > 10) + break; + + This will be translated into: + + BB3: + loop header... + BB4: + if foo() goto BB6 else goto BB5 + BB5: + if global > 10 goto BB6 else goto BB7 + BB6: + goto BB7 + BB7: + iftmp = (PHI 0(BB5), 1(BB6)) + if iftmp == 1 goto BB8 else goto BB3 + BB8: + outside of the loop... + + The edge BB7->BB8 is loop exit because BB8 is outside of the loop. + From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop + exits. This function takes BB7->BB8 as input, and finds out the extra loop + exits to predict them using PRED_LOOP_EXIT. */ + +static void +predict_extra_loop_exits (edge exit_edge) +{ + unsigned i; + bool check_value_one; + gimple phi_stmt; + tree cmp_rhs, cmp_lhs; + gimple cmp_stmt = last_stmt (exit_edge->src); + + if (!cmp_stmt || gimple_code (cmp_stmt) != GIMPLE_COND) + return; + cmp_rhs = gimple_cond_rhs (cmp_stmt); + cmp_lhs = gimple_cond_lhs (cmp_stmt); + if (!TREE_CONSTANT (cmp_rhs) + || !(integer_zerop (cmp_rhs) || integer_onep (cmp_rhs))) + return; + if (TREE_CODE (cmp_lhs) != SSA_NAME) + return; + + /* If check_value_one is true, only the phi_args with value '1' will lead + to loop exit. Otherwise, only the phi_args with value '0' will lead to + loop exit. */ + check_value_one = (((integer_onep (cmp_rhs)) + ^ (gimple_cond_code (cmp_stmt) == EQ_EXPR)) + ^ ((exit_edge->flags & EDGE_TRUE_VALUE) != 0)); + + phi_stmt = SSA_NAME_DEF_STMT (cmp_lhs); + if (!phi_stmt || gimple_code (phi_stmt) != GIMPLE_PHI) + return; + + for (i = 0; i < gimple_phi_num_args (phi_stmt); i++) + { + edge e1; + edge_iterator ei; + tree val = gimple_phi_arg_def (phi_stmt, i); + edge e = gimple_phi_arg_edge (phi_stmt, i); + + if (!TREE_CONSTANT (val) || !(integer_zerop (val) || integer_onep (val))) + continue; + if (check_value_one ^ integer_onep (val)) + continue; + if (VEC_length (edge, e->src->succs) != 1) + { + if (!predicted_by_p (exit_edge->src, PRED_LOOP_ITERATIONS_GUESSED) + && !predicted_by_p (exit_edge->src, PRED_LOOP_ITERATIONS) + && !predicted_by_p (exit_edge->src, PRED_LOOP_EXIT)) + predict_edge_def (e, PRED_LOOP_EXIT, NOT_TAKEN); + continue; + } + + FOR_EACH_EDGE (e1, ei, e->src->preds) + if (!predicted_by_p (exit_edge->src, PRED_LOOP_ITERATIONS_GUESSED) + && !predicted_by_p (exit_edge->src, PRED_LOOP_ITERATIONS) + && !predicted_by_p (exit_edge->src, PRED_LOOP_EXIT)) + predict_edge_def (e1, PRED_LOOP_EXIT, NOT_TAKEN); + } +} + /* Predict edge probabilities by exploiting loop structure. */ static void @@ -1330,6 +1416,8 @@ int probability; enum br_predictor predictor; + predict_extra_loop_exits (ex); + if (number_of_iterations_exit (loop, ex, &niter_desc, false)) niter = niter_desc.niter; if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)