From patchwork Tue Mar 5 09:07:50 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Marek Polacek X-Patchwork-Id: 224969 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 924AE2C031A for ; Tue, 5 Mar 2013 20:08:08 +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=1363079288; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To:User-Agent: Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:Sender:Delivered-To; bh=8CnPgqdca+JUVoptWCLg z2I5yzg=; b=nFUe6X5x87CQ+mFHgCsA6nsoiWheYBIi+1vJHm4ktqnMPBUxTAg8 2KjSgNIwq31HwvAa8ja1qCjxZEqjQHcqtctrBpX4169TqVkS0nG7MFE2x12pBG/z Al9s/GueOrO3jrJb9XGAnUBqKl/aGVOykHHcBSaAOEmYZVMAWMxup3c= 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:Date:From:To:Cc:Subject:Message-ID:References:MIME-Version:Content-Type:Content-Disposition:In-Reply-To:User-Agent:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=d9pZwMwolg+XvbdOV+FUIaSJROSuP+eX6KbOg+KLW23X3SN+965U0ANwsBZpvn oOI+qBKViY5F2N8z9ktxoHkMrVFCXOGoZHVkw6ime07EO/e2yCQfjEO/28shU64E lUyM1JZ9V7ziGoDOAfq0cTOKQKwzRBBFksZbhrFlHd0qc=; Received: (qmail 30747 invoked by alias); 5 Mar 2013 09:08:03 -0000 Received: (qmail 30733 invoked by uid 22791); 5 Mar 2013 09:08:02 -0000 X-SWARE-Spam-Status: No, hits=-6.6 required=5.0 tests=AWL, BAYES_00, KHOP_RCVD_UNTRUST, KHOP_SPAMHAUS_DROP, RCVD_IN_DNSWL_HI, RCVD_IN_HOSTKARMA_W, RP_MATCHES_RCVD, SPF_HELO_PASS, TW_CL, TW_TM X-Spam-Check-By: sourceware.org Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 05 Mar 2013 09:07:55 +0000 Received: from int-mx11.intmail.prod.int.phx2.redhat.com (int-mx11.intmail.prod.int.phx2.redhat.com [10.5.11.24]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id r2597s2i023996 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Tue, 5 Mar 2013 04:07:55 -0500 Received: from redhat.com (ovpn-116-20.ams2.redhat.com [10.36.116.20]) by int-mx11.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id r2597paJ000486 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO); Tue, 5 Mar 2013 04:07:53 -0500 Date: Tue, 5 Mar 2013 10:07:50 +0100 From: Marek Polacek To: Richard Biener Cc: Jakub Jelinek , GCC Patches Subject: Re: [PATCH] Fix PR56478 Message-ID: <20130305090750.GF28076@redhat.com> References: <20130228182748.GD15445@redhat.com> <20130228184315.GU12913@tucnak.redhat.com> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.20 (2009-06-14) 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 On Fri, Mar 01, 2013 at 11:10:40AM +0100, Richard Biener wrote: > Don't use NULL_TREE built_int_cst - doing so hints at that you want to > use double_ints. Generally doing computation with trees is expensive. > You want to avoid that at all cost. Use double-ints (yeah, you have to > use the clunky divmod_with_overflow interface). So this is a WIP patch, which uses double_ints. I apologize for my dumbness, but I haven't figured out how to do the normalization here. It's probably something simple, but... The point of the normalization would be that when multiplying the normalized number with 10000 (aka REG_BR_PROB_BASE), the result fits into plain int, right? If you could suggest what to do with that, that would be appreciated. Thanks. Marek --- a/gcc/predict.c +++ b/gcc/predict.c @@ -1028,13 +1028,13 @@ 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 *loop_step, tree *loop_iv_base) { tree op0, op1, bound, base; affine_iv iv0, iv1; enum tree_code code; - int step; + tree step; code = gimple_cond_code (stmt); *loop_invariant = NULL; @@ -1077,7 +1077,7 @@ is_comparison_with_loop_invariant_p (gimple stmt, struct loop *loop, bound = iv0.base; base = iv1.base; if (host_integerp (iv1.step, 0)) - step = tree_low_cst (iv1.step, 0); + step = iv1.step; else return false; } @@ -1086,7 +1086,7 @@ is_comparison_with_loop_invariant_p (gimple stmt, struct loop *loop, bound = iv1.base; base = iv0.base; if (host_integerp (iv0.step, 0)) - step = tree_low_cst (iv0.step, 0); + step = iv0.step; else return false; } @@ -1154,6 +1154,16 @@ expr_coherent_p (tree t1, tree t2) return false; } +static double_int +normalize (double_int n) +{ + int msb = HOST_BITS_PER_WIDE_INT - clz_hwi (n.to_shwi ()); + if (msb > HOST_BITS_PER_INT - 16) + {} + // ??? n = n.rshift (?, ?, ?); + return n; +} + /* Predict branch probability of BB when BB contains a branch that compares an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP. @@ -1178,7 +1188,7 @@ predict_iv_comparison (struct loop *loop, basic_block bb, gimple stmt; tree compare_var, compare_base; enum tree_code compare_code; - int compare_step; + tree compare_step; edge then_edge; edge_iterator ei; @@ -1224,34 +1234,68 @@ predict_iv_comparison (struct loop *loop, basic_block bb, && host_integerp (compare_base, 0)) { int probability; - HOST_WIDE_INT compare_count; - HOST_WIDE_INT loop_bound = tree_low_cst (loop_bound_var, 0); - HOST_WIDE_INT compare_bound = tree_low_cst (compare_var, 0); - HOST_WIDE_INT base = tree_low_cst (compare_base, 0); - HOST_WIDE_INT loop_count = (loop_bound - base) / compare_step; - - if ((compare_step > 0) + bool of, overflow = false; + double_int mod, compare_count, tem, loop_count; + + double_int loop_bound = tree_to_double_int (loop_bound_var); + double_int compare_bound = tree_to_double_int (compare_var); + double_int base = tree_to_double_int (compare_base); + double_int compare_step = tree_to_double_int (compare_step); + + /* (loop_bound - base) / compare_step */ + tem = loop_bound.sub_with_overflow (base, &of); + overflow |= of; + loop_count = tem.divmod_with_overflow (compare_step, + 0, TRUNC_DIV_EXPR, + &mod, &of); + overflow |= of; + + if ((compare_step.scmp (double_int_zero) == 1) ^ (compare_code == LT_EXPR || compare_code == LE_EXPR)) - compare_count = (loop_bound - compare_bound) / compare_step; + { + /* (loop_bound - compare_bound) / compare_step */ + tem = loop_bound.sub_with_overflow (compare_bound, &of); + overflow |= of; + compare_count = tem.divmod_with_overflow (compare_step, + 0, TRUNC_DIV_EXPR, + &mod, &of); + overflow |= of; + } else - compare_count = (compare_bound - base) / compare_step; - + { + /* (compare_bound - base) / compare_step */ + tem = compare_bound.sub_with_overflow (base, &of); + overflow |= of; + compare_count = tem.divmod_with_overflow (compare_step, + 0, TRUNC_DIV_EXPR, + &mod, &of); + overflow |= of; + } if (compare_code == LE_EXPR || compare_code == GE_EXPR) - compare_count ++; + ++compare_count; if (loop_bound_code == LE_EXPR || loop_bound_code == GE_EXPR) - loop_count ++; - if (compare_count < 0) - compare_count = 0; - if (loop_count < 0) - loop_count = 0; - - if (loop_count == 0) + ++loop_count; + if (compare_count.scmp (double_int_zero) == -1) + compare_count = double_int_zero; + if (loop_count.scmp (double_int_zero) == -1) + loop_count = double_int_zero; + if (loop_count.scmp (double_int_zero) == 0) probability = 0; - else if (compare_count > loop_count) + else if (compare_count.scmp (loop_count) == 1) probability = REG_BR_PROB_BASE; else - probability = (double) REG_BR_PROB_BASE * compare_count / loop_count; - predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability); + { + tem = compare_count.divmod_with_overflow (loop_count, + 0, TRUNC_DIV_EXPR, + &mod, &of); + overflow |= of; + gcc_assert (REG_BR_PROB_BASE < 65536); + probability = (double) REG_BR_PROB_BASE * normalize (tem).to_shwi (); + } + + if (!overflow) + predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability); + return; } @@ -1402,7 +1446,7 @@ predict_loops (void) edge ex; struct nb_iter_bound *nb_iter; enum tree_code loop_bound_code = ERROR_MARK; - int loop_bound_step = 0; + tree loop_bound_step = NULL; tree loop_bound_var = NULL; tree loop_iv_base = NULL; gimple stmt = NULL; @@ -1549,7 +1593,7 @@ predict_loops (void) if (loop_bound_var) predict_iv_comparison (loop, bb, loop_bound_var, loop_iv_base, loop_bound_code, - loop_bound_step); + tree_low_cst (loop_bound_step, 0)); } /* Free basic blocks from get_loop_body. */