From patchwork Mon May 28 03:06:44 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dehao Chen X-Patchwork-Id: 161571 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 0B463B6F9D for ; Mon, 28 May 2012 13:07:10 +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=1338779232; 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=M9txtFt f6AJEdjTcI91xXmD2RCk=; b=wKhsbRHVNswul9Fr9Uz+ApTRYMA8EP3r22LVaOr oP9dKWrUvXRDn1v8shKFE9B2PITlLFWMaQeUwVRrfPs9MgoH5lj6yFfUMkfO14Hd rRU2GHwNTEprD3hX/TcgMjRRW0zKH/NGyWk1HDs94h2m1nyrJWVHIfbLC4VS1ytA Vmog= 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=hUN+XtwaObo5yAMkjhk1hNn0lwGoyBKCdbd8wLQCdxMQnq6YurGJtkBqv+4r9X /jxXH74GIJHHgXokqeouSdsb/SgdQLGOHQdB5L3qz+jvl3SQzZXkyTl2XziQeUQQ WIQZlxTrbgbpb/zpj6QBw9rsitS+gA3VGHvlCITJfDzzw=; Received: (qmail 17987 invoked by alias); 28 May 2012 03:07:06 -0000 Received: (qmail 17974 invoked by uid 22791); 28 May 2012 03:07:04 -0000 X-SWARE-Spam-Status: No, hits=-4.5 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, KHOP_RCVD_TRUST, 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; Mon, 28 May 2012 03:06:45 +0000 Received: by pbbrq2 with SMTP id rq2so3799440pbb.20 for ; Sun, 27 May 2012 20:06:44 -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=8TY4IZNhxN9HB/oPB2vJPeaZD191ZWQfbuPTG6UgHaU=; b=jFBpbHN24FXBmOaKBVL17yAX4CZM3kGLCVdf+CFJRValwpSKnxGVCC8KTLeMtKpXbf KZ2Dd5cqepf8eIcUk3g81/Jbs7J9Q6pQUPp9glZWBnxS63Lj1Ca2Ape5V/3P/fyZLRqa kcPeyR+Ecbn4WoP6IptBKsbCAIrLjeXNP0AuuGEKKmJvaoAyLHHUZoiINV1wdw2IjgIZ KqWN40WIP61EqXOWQDf7xDg442eDy0RBAxA6DWqMs/zamRCMPiZxx+Jlb3ZdYq8LTlHL L0zY1+/87VNSxaQt8KRWSjmkH/gjvXptBt4QJ7lv6+G655LNV7HSmUD9aP7Zfnb20vXI kWDQ== Received: by 10.68.223.138 with SMTP id qu10mr22591301pbc.124.1338174404465; Sun, 27 May 2012 20:06:44 -0700 (PDT) MIME-Version: 1.0 Received: by 10.68.223.138 with SMTP id qu10mr22591274pbc.124.1338174404284; Sun, 27 May 2012 20:06:44 -0700 (PDT) Received: by 10.68.204.198 with HTTP; Sun, 27 May 2012 20:06:44 -0700 (PDT) Date: Mon, 28 May 2012 11:06:44 +0800 Message-ID: Subject: Predict for loop exits in short-circuit conditions From: Dehao Chen To: gcc-patches@gcc.gnu.org Cc: David Li X-System-Of-Record: true X-Gm-Message-State: ALoCoQmrxbu93OEk9wYsMve1/2NeFs1KqNSjjU7H4ZXIHRtcKcNg3NF/0qBEPJR5QrPk7qPfC74IoPtuO7Vsel6xz4OLlB2clFZwhwUpvJpo6Z+U536Tg7OPyLiiqjiHNWiLUHPYkPrTRI1X5d8AYZNh+82C9XV50Q== 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 implements static branch prediction for loop exit conditions that cannot be identified by original heuristic (edge->dst is outside of the loop). It can find extra loop exits for short circuit conditions. Bootstrapped and passed gcc testsuite. Is it ok for trunk? Thanks, Dehao gcc/ChangeLog 2012-05-28 Dehao Chen * predict.c (predict_extra_loop_exit): New function to predict for extra loop exits resulted from short-circuit conditions. gcc/testsuite/ChangeLog 2012-05-28 Dehao Chen * g++.dg/predict-loop-exit-1.C: New test. * g++.dg/predict-loop-exit-2.C: New test. * g++.dg/predict-loop-exit-3.C: New test. Index: gcc/testsuite/g++.dg/predict-loop-exit-1.C =================================================================== --- gcc/testsuite/g++.dg/predict-loop-exit-1.C (revision 0) +++ gcc/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: gcc/testsuite/g++.dg/predict-loop-exit-3.C =================================================================== --- gcc/testsuite/g++.dg/predict-loop-exit-3.C (revision 0) +++ gcc/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: gcc/testsuite/g++.dg/predict-loop-exit-2.C =================================================================== --- gcc/testsuite/g++.dg/predict-loop-exit-2.C (revision 0) +++ gcc/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: gcc/predict.c =================================================================== --- gcc/predict.c (revision 187922) +++ gcc/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 @@ -1362,6 +1448,7 @@ probability = ((REG_BR_PROB_BASE + nitercst / 2) / nitercst); predict_edge (ex, predictor, probability); + predict_extra_loop_exits (ex); } VEC_free (edge, heap, exits);