From patchwork Fri Mar 8 14:34:32 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Marek Polacek X-Patchwork-Id: 226133 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 884A52C0377 for ; Sat, 9 Mar 2013 01:35:23 +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=1363358124; 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=U6OE3KQeLZCiU7BDK/1m 8LNNXrc=; b=myRZ59VmWGPfo6eCrA9Lw6V8R2BImDGRxMKvAXi4UIIkxJTDRW/m fXN9GoxYFR3/cKQ4JK36Q4i4BcwzI9z3RDWr6d3kMu3Uuz28uLnSzpZ5tedIPVvi n5zrTN/fVczgVU/ChfzCWgwZUkF7HDJ3l7mfmatOATUC4KIvj05cTZ8= 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=pyg6ybbc9YpWoj9YcMkXwUvAQzmxIRhVwNyw2H8qamCuWaVj10Z/bCEJq6ccrf 9kSDItMlnZoSyqBYv9Erj42OTE4pH9wW58TSfYyW/DkNn1Gm1FYep7sy2e28r8ov jE7w853YClZpPMhemrjJeOY+5q9ytYx58/ox6mb4dKA88=; Received: (qmail 18062 invoked by alias); 8 Mar 2013 14:35:14 -0000 Received: (qmail 17734 invoked by uid 22791); 8 Mar 2013 14:35:11 -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; Fri, 08 Mar 2013 14:34:37 +0000 Received: from int-mx10.intmail.prod.int.phx2.redhat.com (int-mx10.intmail.prod.int.phx2.redhat.com [10.5.11.23]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id r28EYbkc022250 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Fri, 8 Mar 2013 09:34:37 -0500 Received: from redhat.com (ovpn-116-20.ams2.redhat.com [10.36.116.20]) by int-mx10.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id r28EYXli009206 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO); Fri, 8 Mar 2013 09:34:35 -0500 Date: Fri, 8 Mar 2013 15:34:32 +0100 From: Marek Polacek To: Jakub Jelinek Cc: Richard Biener , GCC Patches Subject: Re: [PATCH] Fix PR56478 Message-ID: <20130308143432.GC18923@redhat.com> References: <20130228182748.GD15445@redhat.com> <20130228184315.GU12913@tucnak.redhat.com> <20130305090750.GF28076@redhat.com> <20130307142535.GD12913@tucnak.redhat.com> <20130308121637.GB18923@redhat.com> <20130308123014.GQ12913@tucnak.redhat.com> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <20130308123014.GQ12913@tucnak.redhat.com> 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 Here's a final version. I've used !compare_step.is_negative (). Moreover, sanity checked by printing out old and new probability and comparing them after check-gcc. So this should be prety safe now. I will apply the patch shortly. 2013-03-08 Marek Polacek Jakub Jelinek PR tree-optimization/56478 * predict.c (is_comparison_with_loop_invariant_p): Change the type of loop_step to tree. (predict_loops): Adjust. (predict_iv_comparison): Perform the computations on double_ints. * gcc.dg/torture/pr56478.c: New test. Marek --- gcc/predict.c.mp 2013-03-07 20:01:01.078417558 +0100 +++ gcc/predict.c 2013-03-08 14:42:26.445834030 +0100 @@ -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 (gim 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 (gim 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; } @@ -1178,7 +1178,7 @@ predict_iv_comparison (struct loop *loop gimple stmt; tree compare_var, compare_base; enum tree_code compare_code; - int compare_step; + tree compare_step_var; edge then_edge; edge_iterator ei; @@ -1192,7 +1192,7 @@ predict_iv_comparison (struct loop *loop return; if (!is_comparison_with_loop_invariant_p (stmt, loop, &compare_var, &compare_code, - &compare_step, + &compare_step_var, &compare_base)) return; @@ -1224,34 +1224,78 @@ predict_iv_comparison (struct loop *loop && 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; + bool of, overflow = false; + double_int mod, compare_count, tem, loop_count; - if ((compare_step > 0) + 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_var); + + /* (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.is_negative ()) ^ (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.is_negative ()) + compare_count = double_int_zero; + if (loop_count.is_negative ()) + loop_count = double_int_zero; + if (loop_count.is_zero ()) 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); + { + /* If loop_count is too big, such that REG_BR_PROB_BASE * loop_count + could overflow, shift both loop_count and compare_count right + a bit so that it doesn't overflow. Note both counts are known not + to be negative at this point. */ + int clz_bits = clz_hwi (loop_count.high); + gcc_assert (REG_BR_PROB_BASE < 32768); + if (clz_bits < 16) + { + loop_count.arshift (16 - clz_bits, HOST_BITS_PER_DOUBLE_INT); + compare_count.arshift (16 - clz_bits, HOST_BITS_PER_DOUBLE_INT); + } + tem = compare_count.mul_with_sign (double_int::from_shwi + (REG_BR_PROB_BASE), true, &of); + gcc_assert (!of); + tem = tem.divmod (loop_count, true, TRUNC_DIV_EXPR, &mod); + probability = tem.to_uhwi (); + } + + 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. */ --- gcc/testsuite/gcc.dg/torture/pr56478.c.mp 2013-03-08 11:35:55.763742165 +0100 +++ gcc/testsuite/gcc.dg/torture/pr56478.c 2013-03-08 14:41:41.605693921 +0100 @@ -0,0 +1,12 @@ +/* PR tree-optimization/56478 */ +/* { dg-do compile } */ + +int a; + +void +foo () +{ + int b; + for (b = 0;; b++) + a = 0 < -__LONG_LONG_MAX__ - 1 - b ? : 0; +}