From patchwork Fri May 1 22:46:21 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Marc Glisse X-Patchwork-Id: 467155 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]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id D18FE140318 for ; Sat, 2 May 2015 08:46:33 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass reason="1024-bit key; unprotected key" header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=yEagdo44; dkim-adsp=none (unprotected policy); dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; q=dns; s= default; b=NaO9tOUPcrgZ95bIsYsLyoYFEl6mb4jYC+Sv5fkY0bTAiYrEjgN6j bYuRDESfh/CzrhdOFl2KC0tdXvQea30q/WrOGgYoWElYFyBIVu//qKz1BcKtYW5A H2iOAUhuOPYTqxH7uKAsL68VKbkG5qSqA0/epFnodJzOXOX5e3K+TE= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; s= default; bh=7b5Uuojm9GuLf7Dz5kHb/Qyfods=; b=yEagdo44bsz0jOwjK1RJ BR1qC67TGY2YE58oRfnA3DI58LYD5LcBURR6gwb/Bt0rFVi7h+IWdzpBN8qAzkji 8pDGmMA11XcpAsTxY4adZPJXl3iHRIbczXNgd+Rt3SrO3Y4UV81VGdYqIrMkEmsy cHiU76ddR+vcwSzjxvAB9OE= Received: (qmail 103095 invoked by alias); 1 May 2015 22:46:26 -0000 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 Received: (qmail 103086 invoked by uid 89); 1 May 2015 22:46:26 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.0 required=5.0 tests=AWL, BAYES_00, KAM_ASCII_DIVIDERS, KAM_LAZY_DOMAIN_SECURITY, T_RP_MATCHES_RCVD autolearn=no version=3.3.2 X-HELO: mail2-relais-roc.national.inria.fr Received: from mail2-relais-roc.national.inria.fr (HELO mail2-relais-roc.national.inria.fr) (192.134.164.83) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (CAMELLIA256-SHA encrypted) ESMTPS; Fri, 01 May 2015 22:46:24 +0000 Received: from stedding.saclay.inria.fr (HELO stedding) ([193.55.250.194]) by mail2-relais-roc.national.inria.fr with ESMTP/TLS/AES128-SHA; 02 May 2015 00:46:21 +0200 Received: from glisse (helo=localhost) by stedding with local-esmtp (Exim 4.84) (envelope-from ) id 1YoJhN-00081n-6z for gcc-patches@gcc.gnu.org; Sat, 02 May 2015 00:46:21 +0200 Date: Sat, 2 May 2015 00:46:21 +0200 (CEST) From: Marc Glisse To: gcc-patches@gcc.gnu.org Subject: PR 64454: Improve VRP for % Message-ID: User-Agent: Alpine 2.02 (DEB 1266 2009-07-14) MIME-Version: 1.0 Hello, this patch tries to tighten a bit the range estimate for x%y. slp-perm-7.c started failing by vectorizing more than expected, I assumed it was a good thing and updated the test. I am less conservative than Jakub with division by 0, but I still don't really understand how empty ranges are supposed to be represented in VRP. Bootstrap+testsuite on x86_64-linux-gnu. 2015-05-02 Marc Glisse PR tree-optimization/64454 gcc/ * tree-vrp.c (extract_range_from_binary_expr_1) : Rewrite. gcc/testsuite/ * gcc.dg/tree-ssa/vrp97.c: New file. * gcc.dg/vect/slp-perm-7.c: Update. Index: gcc/testsuite/gcc.dg/tree-ssa/vrp97.c =================================================================== --- gcc/testsuite/gcc.dg/tree-ssa/vrp97.c (revision 0) +++ gcc/testsuite/gcc.dg/tree-ssa/vrp97.c (working copy) @@ -0,0 +1,13 @@ +/* PR tree-optimization/64454 */ +/* { dg-options "-O2 -fdump-tree-vrp1" } */ + +int f(int a, int b) +{ + if (a < -3 || a > 13) __builtin_unreachable(); + if (b < -6 || b > 9) __builtin_unreachable(); + int c = a % b; + return c >= -3 && c <= 8; +} + +/* { dg-final { scan-tree-dump "return 1;" "vrp1" } } */ +/* { dg-final { cleanup-tree-dump "vrp1" } } */ Index: gcc/testsuite/gcc.dg/vect/slp-perm-7.c =================================================================== --- gcc/testsuite/gcc.dg/vect/slp-perm-7.c (revision 222708) +++ gcc/testsuite/gcc.dg/vect/slp-perm-7.c (working copy) @@ -63,15 +63,15 @@ int main (int argc, const char* argv[]) foo (input, output, input2, output2); for (i = 0; i < N; i++) if (output[i] != check_results[i] || output2[i] != check_results2[i]) abort (); return 0; } -/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" { target vect_perm } } } */ +/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 2 "vect" { target vect_perm } } } */ /* { dg-final { scan-tree-dump-times "vectorizing stmts using SLP" 1 "vect" { target vect_perm } } } */ /* { dg-final { cleanup-tree-dump "vect" } } */ Index: gcc/tree-vrp.c =================================================================== --- gcc/tree-vrp.c (revision 222708) +++ gcc/tree-vrp.c (working copy) @@ -3189,40 +3189,83 @@ extract_range_from_binary_expr_1 (value_ } } else { extract_range_from_multiplicative_op_1 (vr, code, &vr0, &vr1); return; } } else if (code == TRUNC_MOD_EXPR) { - if (vr1.type != VR_RANGE - || range_includes_zero_p (vr1.min, vr1.max) != 0 - || vrp_val_is_min (vr1.min)) + if (range_is_null (&vr1)) + { + set_value_range_to_undefined (vr); + return; + } + // Some propagation of symbolic ranges should be possible + // at least in the unsigned case. + bool has_vr0 = vr0.type == VR_RANGE && !symbolic_range_p (&vr0); + bool has_vr1 = vr1.type == VR_RANGE && !symbolic_range_p (&vr1); + if (!has_vr0 && !has_vr1) { set_value_range_to_varying (vr); return; } type = VR_RANGE; - /* Compute MAX <|vr1.min|, |vr1.max|> - 1. */ - max = fold_unary_to_constant (ABS_EXPR, expr_type, vr1.min); - if (tree_int_cst_lt (max, vr1.max)) - max = vr1.max; - max = int_const_binop (MINUS_EXPR, max, build_int_cst (TREE_TYPE (max), 1)); - /* If the dividend is non-negative the modulus will be - non-negative as well. */ - if (TYPE_UNSIGNED (expr_type) - || value_range_nonnegative_p (&vr0)) - min = build_int_cst (TREE_TYPE (max), 0); + if (TYPE_UNSIGNED (expr_type)) + { + // A % B is at most A and smaller than B. + min = build_int_cst (expr_type, 0); + if (has_vr0 && (!has_vr1 || tree_int_cst_lt (vr0.max, vr1.max))) + max = vr0.max; + else + max = int_const_binop (MINUS_EXPR, vr1.max, + build_int_cst (expr_type, 1)); + } else - min = fold_unary_to_constant (NEGATE_EXPR, expr_type, max); + { + tree min1 = NULL_TREE; + tree max1 = NULL_TREE; + if (has_vr1) + { + // ABS (A % B) < ABS (B) + max1 = fold_unary_to_constant (ABS_EXPR, expr_type, vr1.min); + if (tree_int_cst_lt (max1, vr1.max)) + max1 = vr1.max; + max1 = int_const_binop (MINUS_EXPR, max1, + build_int_cst (expr_type, 1)); + min1 = fold_unary_to_constant (NEGATE_EXPR, expr_type, max1); + } + if (has_vr0) + { + // Either 0 <= A % B <= A or A <= A % B <= 0. + max = vr0.max; + min = vr0.min; + tree zero = build_int_cst (expr_type, 0); + if (tree_int_cst_lt (zero, min)) + min = zero; + if (tree_int_cst_lt (max, zero)) + max = zero; + if (has_vr1) + { + if (tree_int_cst_lt (min, min1)) + min = min1; + if (tree_int_cst_lt (max1, max)) + max = max1; + } + } + else + { + min = min1; + max = max1; + } + } } else if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR) { bool int_cst_range0, int_cst_range1; wide_int may_be_nonzero0, may_be_nonzero1; wide_int must_be_nonzero0, must_be_nonzero1; int_cst_range0 = zero_nonzero_bits_from_vr (expr_type, &vr0, &may_be_nonzero0, &must_be_nonzero0);