From patchwork Fri Dec 30 03:22:50 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dehao Chen X-Patchwork-Id: 133604 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 F2EE6B6FC3 for ; Fri, 30 Dec 2011 14:23: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=1325820194; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: MIME-Version:Received:Received:Date:Message-ID:Subject:From:To: Content-Type:Mailing-List:Precedence:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:Sender:Delivered-To; bh=2kWP7G+ oiHD078FeaR3bVRtqjaA=; b=tD0bZdi4y6CHUpuUCexT/gvhSY5514VU1K6cpHD Z+vx6FAF+pBx/XbSR3sH3HaCUlYcun9IdH14NPd0ynZdHOEpkINYh7GOXSjq72Kb yBrAKLvb6R42bSv9DbiaRY33ykpvsbyt/iv/nzjmex6XxsYychBY3ZyZ5IudKhHU nrTk= 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:Received:MIME-Version:Received:Received:Date:Message-ID:Subject:From:To:X-System-Of-Record:Content-Type:X-IsSubscribed:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=gEdNBxJw6UKrUVQH9VFF/zjXz9pxM5wqSQoRRUZSGjECz19BP+nX3shnG+JjY9 fAMEOmMDWvCueBcuZCKS9pesDEJRtlvOsVJpbPJdZZAO52RuGd8492ZaTsaSxYww k8QUIjFsXSCl6YbNP9f4gqe7z1xmEiTcWUc21wa7yK5DM=; Received: (qmail 9595 invoked by alias); 30 Dec 2011 03:23:08 -0000 Received: (qmail 9579 invoked by uid 22791); 30 Dec 2011 03:23:06 -0000 X-SWARE-Spam-Status: No, hits=-3.3 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, RCVD_IN_DNSWL_LOW, RP_MATCHES_RCVD, TW_TM X-Spam-Check-By: sourceware.org Received: from mail-iy0-f175.google.com (HELO mail-iy0-f175.google.com) (209.85.210.175) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 30 Dec 2011 03:22:51 +0000 Received: by iakh37 with SMTP id h37so22203453iak.20 for ; Thu, 29 Dec 2011 19:22:51 -0800 (PST) Received: by 10.42.152.134 with SMTP id i6mr25991573icw.13.1325215370835; Thu, 29 Dec 2011 19:22:50 -0800 (PST) MIME-Version: 1.0 Received: by 10.42.152.134 with SMTP id i6mr25991567icw.13.1325215370741; Thu, 29 Dec 2011 19:22:50 -0800 (PST) Received: by 10.50.23.70 with HTTP; Thu, 29 Dec 2011 19:22:50 -0800 (PST) Date: Fri, 30 Dec 2011 11:22:50 +0800 Message-ID: Subject: [PATCH]: Add static branch predict heuristic of comparing IV to loop_bound variable From: Dehao Chen To: gcc-patches@gcc.gnu.org X-System-Of-Record: true 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 Hello, This patch add a static branch predict heuristic for the following cases: for (int i = 0; i < bound; i++) { if (i < bound - 2) computation_1(); else computation_2(); } In this case, we would predict the branch to be taken because it's comparing loop induction variable to loop bound variable. Tested with bootstrap, and no regression in the gcc testsuite. Is it ok for mainline? Thanks, Dehao http://codereview.appspot.com/5504086 gcc/ChangeLog 2011-12-30 Dehao Chen * predict.c (find_qualified_ssa_name): New (find_ssa_name_in_expr): New (find_ssa_name_in_assign_stmt): New (is_comparison_with_loop_invariant_p): New (is_bound_expr_similar): New (predict_iv_comparison): New (predict_loops): Add heuristic for loop-nested branches that compare an induction variable to a loop bound variable. * predict.def (PRED_LOOP_IV_COMPARE): New macro gcc/testsuite/ChangeLog 2011-12-30 Dehao Chen * gcc.dg/predict-1.c: Check if LOOP_IV_COMPARE static predict heuristic is working properly. * gcc.dg/predict-2.c: Likewise. * gcc/dg/predict-3.c: Likewise. Index: gcc/testsuite/gcc.dg/predict-3.c =================================================================== --- gcc/testsuite/gcc.dg/predict-3.c (revision 0) +++ gcc/testsuite/gcc.dg/predict-3.c (revision 0) @@ -0,0 +1,19 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */ + +extern int global; + +int bar(int); + +void foo (int bound) +{ + int i, ret = 0; + for (i = 0; i <= bound; i++) + { + if (i != bound) + global += bar (i); + } +} + +/* { dg-final { scan-tree-dump "loop iv compare heuristics" "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 0) +++ gcc/testsuite/gcc.dg/predict-1.c (revision 0) @@ -0,0 +1,19 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */ + +extern int global; + +int bar(int); + +void foo (int bound) +{ + int i, ret = 0; + for (i = 0; i < bound; i++) + { + if (i > bound - 2) + global += bar (i); + } +} + +/* { dg-final { scan-tree-dump "loop iv compare heuristics" "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 0) +++ gcc/testsuite/gcc.dg/predict-2.c (revision 0) @@ -0,0 +1,19 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */ + +extern int global; + +int bar(int); + +void foo (int bound) +{ + int i, ret = 0; + for (i = 0; i < bound; i++) + { + if (i > bound * bound ) + global += bar (i); + } +} + +/* { dg-final { scan-tree-dump-not "loop iv compare heuristics" "profile_estimate"} } */ +/* { dg-final { cleanup-tree-dump "profile_estimate" } } */ Index: gcc/predict.c =================================================================== --- gcc/predict.c (revision 182738) +++ gcc/predict.c (working copy) @@ -946,6 +946,292 @@ } } +/* Check if T1 and T2 satisfy the IV_COMPARE condition. + Return the SSA_NAME if the condition satisfies, NULL otherwise. + + T1 and T2 should be one of the following cases: + 1. T1 is SSA_NAME, T2 is NULL + 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4] + 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */ + +static tree +find_qualified_ssa_name (tree t1, tree t2) +{ + tree ret = NULL; + int value = 0; + + if (!t1) + return NULL; + else if (TREE_CODE (t1) == SSA_NAME) + ret = t1; + else if (TREE_CODE (t1) == INTEGER_CST) + value = TREE_INT_CST_LOW (t1); + else + return NULL; + + if (!t2) + return ret; + else if (TREE_CODE (t2) == INTEGER_CST) + value = TREE_INT_CST_LOW (t2); + else if (TREE_CODE (t2) == SSA_NAME) + { + if (ret) + return NULL; + else + ret = t2; + } + + if (value <= 4 && value >= -4) + return ret; + else + return NULL; +} + +/* Return the SSA_NAME in T or T's operands. + Return NULL if T does not satisfy IV_COMPARE condition. */ + +static tree +find_ssa_name_in_expr (tree t) +{ + if (TREE_CODE (t) == SSA_NAME) + return t; + + if (!BINARY_CLASS_P (t)) + return NULL; + + switch (TREE_OPERAND_LENGTH (t)) + { + case 1: + return find_qualified_ssa_name (TREE_OPERAND (t, 0), NULL); + case 2: + return find_qualified_ssa_name (TREE_OPERAND (t, 0), + TREE_OPERAND (t, 1)); + default: + return NULL; + } +} + +/* Return the SSA_NAME in the rhs of assignment STMT. + Return NULL if STMT does not satisfy IV_COMPARE condition. */ + +static tree +find_ssa_name_in_assign_stmt (gimple stmt) +{ + gcc_assert (is_gimple_assign (stmt)); + + if (gimple_assign_rhs3 (stmt) != NULL) + return NULL; + + return find_qualified_ssa_name (gimple_assign_rhs1 (stmt), + gimple_assign_rhs2 (stmt)); +} + +/* Check the compare STMT in LOOP. If it compares an induction + variable to a loop invariant, return true, and save + LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP. + Otherwise return false and set LOOP_INVAIANT to NULL. */ + +static bool +is_comparison_with_loop_invariant_p (gimple stmt, struct loop *loop, + tree *loop_invariant, + enum tree_code *compare_code, + int *loop_step) +{ + tree op0, op1, bound; + affine_iv iv0, iv1; + enum tree_code code; + int step; + + code = gimple_cond_code (stmt); + *loop_invariant = NULL; + + switch (code) + { + case GT_EXPR: + case GE_EXPR: + case NE_EXPR: + case LT_EXPR: + case LE_EXPR: + case EQ_EXPR: + break; + + default: + return false; + } + + op0 = gimple_cond_lhs (stmt); + op1 = gimple_cond_rhs (stmt); + + if (TREE_CODE (op0) != SSA_NAME || TREE_CODE (op1) != SSA_NAME) + return false; + if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, true)) + return false; + if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, true)) + return false; + if (TREE_CODE (iv0.step) != INTEGER_CST + || TREE_CODE (iv1.step) != INTEGER_CST) + return false; + if ((integer_zerop (iv0.step) && integer_zerop (iv1.step)) + || (!integer_zerop (iv0.step) && !integer_zerop (iv1.step))) + return false; + + if (integer_zerop (iv0.step)) + { + if (code != NE_EXPR && code != EQ_EXPR) + code = invert_tree_comparison (code, false); + bound = iv0.base; + step = TREE_INT_CST_LOW (iv1.step); + } + else + { + bound = iv1.base; + step = TREE_INT_CST_LOW (iv0.step); + } + + bound = find_ssa_name_in_expr (bound); + if (!bound) + return false; + + *loop_invariant = bound; + *compare_code = code; + *loop_step = step; + return true; +} + +/* Compare two SSA_NAMEs: returns TRUE if T1 and T2 reference + a similar variable. */ + +static bool +is_bound_expr_similar (tree t1, tree t2) +{ + gimple stmt; + tree ssa_name_1 = NULL; + tree ssa_name_2 = NULL; + + gcc_assert (TREE_CODE (t1) == SSA_NAME); + gcc_assert (TREE_CODE (t2) == SSA_NAME); + + if (t1 == t2) + return true; + + /* Check to see if t1 is expressed/defined with t2. */ + stmt = SSA_NAME_DEF_STMT (t1); + gcc_assert (stmt != NULL); + if (is_gimple_assign (stmt)) + { + ssa_name_1 = find_ssa_name_in_assign_stmt (stmt); + if (ssa_name_1 && ssa_name_1 == t2) + return true; + } + + /* Check to see if t2 is expressed/defined with t1. */ + stmt = SSA_NAME_DEF_STMT (t2); + gcc_assert (stmt != NULL); + if (is_gimple_assign (stmt)) + { + ssa_name_2 = find_ssa_name_in_assign_stmt (stmt); + if (ssa_name_2 && ssa_name_2 == t1) + return true; + } + + /* Compare if t1 and t2's def_stmts are identical. */ + if (ssa_name_2 != NULL && ssa_name_1 == ssa_name_2) + return true; + else + return false; +} + +/* Predict branch probability of BB when BB contains a branch that compares + an induction variable in LOOP to LOOP_BOUND_VAR. The loop exit is + compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP. + + E.g. + for (int i = 0; i < bound; i++) { + if (i < bound - 2) + computation_1(); + else + computation_2(); + } + + In this loop, we will predict the branch inside the loop to be taken. */ + +static void +predict_iv_comparison (struct loop *loop, basic_block bb, + tree loop_bound_var, + enum tree_code loop_bound_code, + int loop_bound_step) +{ + gimple stmt; + tree compare_var; + enum tree_code compare_code; + int compare_step; + edge then_edge; + edge_iterator ei; + + if (predicted_by_p (bb, PRED_LOOP_ITERATIONS_GUESSED) + || predicted_by_p (bb, PRED_LOOP_ITERATIONS) + || predicted_by_p (bb, PRED_LOOP_EXIT)) + return; + + stmt = last_stmt (bb); + if (!stmt || gimple_code (stmt) != GIMPLE_COND) + return; + if (!is_comparison_with_loop_invariant_p (stmt, loop, &compare_var, + &compare_code, + &compare_step)) + return; + + /* Find the taken edge. */ + FOR_EACH_EDGE (then_edge, ei, bb->succs) + if (then_edge->flags & EDGE_TRUE_VALUE) + break; + + /* When comparing an IV to a loop invariant, NE is more likely to be + taken while EQ is more likely to be not-taken. */ + if (compare_code == NE_EXPR) + { + predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN); + return; + } + else if (compare_code == EQ_EXPR) + { + predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN); + return; + } + + if (!is_bound_expr_similar (loop_bound_var, compare_var)) + 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 (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); +} + /* Predict edge probabilities by exploiting loop structure. */ static void @@ -963,6 +1249,11 @@ VEC (edge, heap) *exits; struct tree_niter_desc niter_desc; edge ex; + struct nb_iter_bound *nb_iter; + enum tree_code loop_bound_code = ERROR_MARK; + int loop_bound_step = 0; + tree loop_bound_var = NULL; + gimple stmt = NULL; exits = get_loop_exit_edges (loop); n_exits = VEC_length (edge, exits); @@ -1010,6 +1301,24 @@ } VEC_free (edge, heap, exits); + /* Find information about loop bound variables. */ + for (nb_iter = loop->bounds; nb_iter; + nb_iter = nb_iter->next) + if (nb_iter->stmt + && gimple_code (nb_iter->stmt) == GIMPLE_COND) + { + stmt = nb_iter->stmt; + break; + } + if (!stmt && last_stmt (loop->header) + && gimple_code (last_stmt (loop->header)) == GIMPLE_COND) + stmt = last_stmt (loop->header); + if (stmt) + is_comparison_with_loop_invariant_p (stmt, loop, + &loop_bound_var, + &loop_bound_code, + &loop_bound_step); + bbs = get_loop_body (loop); for (j = 0; j < loop->num_nodes; j++) @@ -1071,6 +1380,10 @@ || !flow_bb_inside_loop_p (loop, e->dest)) predict_edge (e, PRED_LOOP_EXIT, probability); } + if (loop_bound_var) + predict_iv_comparison (loop, bb, loop_bound_var, + loop_bound_code, + loop_bound_step); } /* Free basic blocks from get_loop_body. */ Index: gcc/predict.def =================================================================== --- gcc/predict.def (revision 182738) +++ gcc/predict.def (working copy) @@ -116,3 +116,7 @@ /* Branches to a mudflap bounds check are extremely unlikely. */ DEF_PREDICTOR (PRED_MUDFLAP, "mudflap check", PROB_VERY_LIKELY, 0) + +/* Branches to compare induction variable to a loop bound is + extremely likely. */ +DEF_PREDICTOR (PRED_LOOP_IV_COMPARE, "loop iv compare", PROB_VERY_LIKELY, 0)