From patchwork Fri Jan 8 20:07:11 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Jelinek X-Patchwork-Id: 565056 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 79BBC140AEB for ; Sat, 9 Jan 2016 07:07:29 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=wPrr+YQA; 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:cc:subject:message-id:reply-to:mime-version :content-type; q=dns; s=default; b=mm5oZdZbXYQwL61396/HS6PteoLBy rkFK6vac8U2lRIh/mb3SSBjvJQNtDSUj/Gxbj6A9QQ+tMDlzdd9y5aPtMHMhVni9 kStvrTuzQrDZ4y05Nq0c4PrgZ0Uyo2k+TFr1omaWwUwvFUZFBd+X0StNC/mAk4Io lmHPpo9WqT3dBk= 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:cc:subject:message-id:reply-to:mime-version :content-type; s=default; bh=AUzJN0SfuOY6JE3w6GBdObon5Mw=; b=wPr r+YQAykkKQhMifcaE82soaTZ28bIKJSvnpSS3XRvE0JX7Siz/nfuqmBx8tUwZmEt ISlanP3ke1lDIfmxQgrNXZSJaJHUyCJ2wfoF+HPRdR+cjYg+H+Zeu66cXbwDk/Gj 7YohD7AGR7ubgt4kNta+eWF2L8Wxyg3FPcBS1F/U= Received: (qmail 69659 invoked by alias); 8 Jan 2016 20:07:21 -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 69648 invoked by uid 89); 8 Jan 2016 20:07:20 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.8 required=5.0 tests=AWL, BAYES_00, RP_MATCHES_RCVD, SPF_HELO_PASS autolearn=ham version=3.3.2 spammy=ABS, 1, 27, minus_one, 1ll X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-GCM-SHA384 encrypted) ESMTPS; Fri, 08 Jan 2016 20:07:18 +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 (Postfix) with ESMTPS id 2EECF325DBB; Fri, 8 Jan 2016 20:07:17 +0000 (UTC) Received: from tucnak.zalov.cz ([10.3.113.3]) by int-mx11.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id u08K7FlB018970 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=NO); Fri, 8 Jan 2016 15:07:16 -0500 Received: from tucnak.zalov.cz (localhost [127.0.0.1]) by tucnak.zalov.cz (8.15.2/8.15.2) with ESMTP id u08K7Dp2010834; Fri, 8 Jan 2016 21:07:14 +0100 Received: (from jakub@localhost) by tucnak.zalov.cz (8.15.2/8.15.2/Submit) id u08K7BMr010833; Fri, 8 Jan 2016 21:07:11 +0100 Date: Fri, 8 Jan 2016 21:07:11 +0100 From: Jakub Jelinek To: Richard Biener Cc: gcc-patches@gcc.gnu.org Subject: [PATCH] Fix X % -Y => X % Y optimization (PR tree-optimization/69097, PR middle-end/50865) Message-ID: <20160108200711.GB18720@tucnak.redhat.com> Reply-To: Jakub Jelinek MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.23 (2014-03-12) X-IsSubscribed: yes Hi! As mentioned in the PRs, the X % -Y to X % Y optimization for signed modulo is not valid unless we can prove that it won't be INT_MIN % -(-1), which is valid, but where INT_MIN % -1 is invalid. The following patch use range info to figure that out. Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? 2016-01-08 Jakub Jelinek PR middle-end/50865 PR tree-optimization/69097 * fold-const.h (expr_not_equal_to): New prototype. * fold-const.c: Include stringpool.h and tree-ssanames.h. (expr_not_equal_to): New function. * match.pd (X % -Y is the same as X % Y): Don't optimize unless X is known not to be equal to minimum or Y is known not to be equal to -1. * tree-vrp.c (simplify_div_or_mod_using_ranges): Add GSI argument. fold TRUNC_MOD_EXPR if the second argument is not a power of two. (simplify_stmt_using_ranges): Adjust caller. (vrp_finalize): Call set_value_range on SSA_NAMEs before calling substitute_and_fold. * gcc.c-torture/execute/pr50865.c: New test. * gcc.c-torture/execute/pr69097-1.c: New test. * gcc.c-torture/execute/pr69097-2.c: New test. * gcc.dg/pr69097-1.c: New test. * gcc.dg/pr69097-2.c: New test. Jakub --- gcc/fold-const.h.jj 2016-01-05 12:38:17.020555325 +0100 +++ gcc/fold-const.h 2016-01-08 13:22:25.921536489 +0100 @@ -177,6 +177,7 @@ extern bool merge_ranges (int *, tree *, tree, tree); extern tree sign_bit_p (tree, const_tree); extern tree exact_inverse (tree, tree); +extern bool expr_not_equal_to (tree t, const wide_int &); extern tree const_unop (enum tree_code, tree, tree); extern tree const_binop (enum tree_code, tree, tree, tree); extern bool negate_mathfn_p (combined_fn); --- gcc/fold-const.c.jj 2016-01-05 12:38:17.011555454 +0100 +++ gcc/fold-const.c 2016-01-08 13:22:25.925536432 +0100 @@ -74,6 +74,8 @@ along with GCC; see the file COPYING3. #include "tree-into-ssa.h" #include "md5.h" #include "case-cfn-macros.h" +#include "stringpool.h" +#include "tree-ssanames.h" #ifndef LOAD_EXTEND_OP #define LOAD_EXTEND_OP(M) UNKNOWN @@ -9101,6 +9103,45 @@ tree_expr_nonzero_p (tree t) return ret; } +/* Return true if T is known not to be equal to an integer W. */ + +bool +expr_not_equal_to (tree t, const wide_int &w) +{ + wide_int min, max, nz; + value_range_type rtype; + switch (TREE_CODE (t)) + { + case INTEGER_CST: + return wi::ne_p (t, w); + + case SSA_NAME: + if (!INTEGRAL_TYPE_P (TREE_TYPE (t))) + return false; + rtype = get_range_info (t, &min, &max); + if (rtype == VR_RANGE) + { + if (wi::lt_p (max, w, TYPE_SIGN (TREE_TYPE (t)))) + return true; + if (wi::lt_p (w, min, TYPE_SIGN (TREE_TYPE (t)))) + return true; + } + else if (rtype == VR_ANTI_RANGE + && wi::le_p (min, w, TYPE_SIGN (TREE_TYPE (t))) + && wi::le_p (w, max, TYPE_SIGN (TREE_TYPE (t)))) + return true; + /* If T has some known zero bits and W has any of those bits set, + then T is known not to be equal to W. */ + if (wi::ne_p (wi::zext (wi::bit_and_not (w, get_nonzero_bits (t)), + TYPE_PRECISION (TREE_TYPE (t))), 0)) + return true; + return false; + + default: + return false; + } +} + /* Fold a binary expression of code CODE and type TYPE with operands OP0 and OP1. LOC is the location of the resulting expression. Return the folded expression if folding is successful. Otherwise, --- gcc/match.pd.jj 2016-01-05 12:38:16.979555912 +0100 +++ gcc/match.pd 2016-01-08 13:23:28.815653802 +0100 @@ -295,7 +295,13 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (trunc_mod @0 (convert? (negate @1))) (if (!TYPE_UNSIGNED (type) && !TYPE_OVERFLOW_TRAPS (type) - && tree_nop_conversion_p (type, TREE_TYPE (@1))) + && tree_nop_conversion_p (type, TREE_TYPE (@1)) + /* Avoid this transformation if X might be INT_MIN or + Y might be -1, because we would then change valid + INT_MIN % -(-1) into invalid INT_MIN % -1. */ + && (expr_not_equal_to (@0, TYPE_MIN_VALUE (type)) + || expr_not_equal_to (@1, wi::minus_one (TYPE_PRECISION + (TREE_TYPE (@1)))))) (trunc_mod @0 (convert @1)))) /* X - (X / Y) * Y is the same as X % Y. */ --- gcc/tree-vrp.c.jj 2016-01-04 14:55:51.000000000 +0100 +++ gcc/tree-vrp.c 2016-01-08 13:53:11.101943765 +0100 @@ -8942,7 +8942,7 @@ simplify_truth_ops_using_ranges (gimple_ modulo. */ static bool -simplify_div_or_mod_using_ranges (gimple *stmt) +simplify_div_or_mod_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt) { enum tree_code rhs_code = gimple_assign_rhs_code (stmt); tree val = NULL; @@ -8971,12 +8971,19 @@ simplify_div_or_mod_using_ranges (gimple } if (!integer_pow2p (op1)) - return false; - - if (TYPE_UNSIGNED (TREE_TYPE (op0))) { - val = integer_one_node; + /* X % -Y can be only optimized into X % Y either if + X is not INT_MIN, or Y is not -1. Fold it now, as after + remove_range_assertions the range info might be not available + anymore. */ + if (rhs_code == TRUNC_MOD_EXPR + && fold_stmt (gsi, follow_single_use_edges)) + return true; + return false; } + + if (TYPE_UNSIGNED (TREE_TYPE (op0))) + val = integer_one_node; else { bool sop = false; @@ -9890,7 +9897,7 @@ simplify_stmt_using_ranges (gimple_stmt_ case TRUNC_MOD_EXPR: if (TREE_CODE (rhs1) == SSA_NAME && INTEGRAL_TYPE_P (TREE_TYPE (rhs1))) - return simplify_div_or_mod_using_ranges (stmt); + return simplify_div_or_mod_using_ranges (gsi, stmt); break; /* Transform ABS (X) into X or -X as appropriate. */ @@ -10200,16 +10207,6 @@ vrp_finalize (bool warn_array_bounds_p) fprintf (dump_file, "\n"); } - substitute_and_fold (op_with_constant_singleton_value_range, - vrp_fold_stmt, false); - - if (warn_array_bounds && warn_array_bounds_p) - check_all_array_refs (); - - /* We must identify jump threading opportunities before we release - the datastructures built by VRP. */ - identify_jump_threads (); - /* Set value range to non pointer SSA_NAMEs. */ for (i = 0; i < num_vr_values; i++) if (vr_value[i]) @@ -10230,6 +10227,16 @@ vrp_finalize (bool warn_array_bounds_p) vr_value[i]->max); } + substitute_and_fold (op_with_constant_singleton_value_range, + vrp_fold_stmt, false); + + if (warn_array_bounds && warn_array_bounds_p) + check_all_array_refs (); + + /* We must identify jump threading opportunities before we release + the datastructures built by VRP. */ + identify_jump_threads (); + /* Free allocated memory. */ for (i = 0; i < num_vr_values; i++) if (vr_value[i]) --- gcc/testsuite/gcc.c-torture/execute/pr50865.c.jj 2016-01-08 14:44:28.749265388 +0100 +++ gcc/testsuite/gcc.c-torture/execute/pr50865.c 2016-01-08 14:52:07.000000000 +0100 @@ -0,0 +1,27 @@ +/* PR middle-end/50865 */ + +#define INT64_MIN (-__LONG_LONG_MAX__ - 1) + +int +main () +{ + volatile long long l1 = 1; + volatile long long l2 = -1; + volatile long long l3 = -1; + + if ((INT64_MIN % 1LL) != 0) + __builtin_abort (); + if ((INT64_MIN % l1) != 0) + __builtin_abort (); + if (l2 == -1) + { + if ((INT64_MIN % 1LL) != 0) + __builtin_abort (); + } + else if ((INT64_MIN % -l2) != 0) + __builtin_abort (); + if ((INT64_MIN % -l3) != 0) + __builtin_abort (); + + return 0; +} --- gcc/testsuite/gcc.c-torture/execute/pr69097-1.c.jj 2016-01-08 14:08:11.577422788 +0100 +++ gcc/testsuite/gcc.c-torture/execute/pr69097-1.c 2016-01-08 14:06:51.000000000 +0100 @@ -0,0 +1,14 @@ +/* PR tree-optimization/69097 */ + +int a, b; +unsigned int c; + +int +main () +{ + int d = b; + b = ~(~a + (~d | b)); + a = ~(~c >> b); + c = a % b; + return 0; +} --- gcc/testsuite/gcc.c-torture/execute/pr69097-2.c.jj 2016-01-08 14:08:14.726378977 +0100 +++ gcc/testsuite/gcc.c-torture/execute/pr69097-2.c 2016-01-08 14:07:49.000000000 +0100 @@ -0,0 +1,30 @@ +/* PR tree-optimization/69097 */ + +__attribute__((noinline, noclone)) int +f1 (int x, int y) +{ + return x % y; +} + +__attribute__((noinline, noclone)) int +f2 (int x, int y) +{ + return x % -y; +} + +__attribute__((noinline, noclone)) int +f3 (int x, int y) +{ + int z = -y; + return x % z; +} + +int +main () +{ + if (f1 (-__INT_MAX__ - 1, 1) != 0 + || f2 (-__INT_MAX__ - 1, -1) != 0 + || f3 (-__INT_MAX__ - 1, -1) != 0) + __builtin_abort (); + return 0; +} --- gcc/testsuite/gcc.dg/pr69097-1.c.jj 2016-01-08 14:23:01.631064387 +0100 +++ gcc/testsuite/gcc.dg/pr69097-1.c 2016-01-08 14:02:45.000000000 +0100 @@ -0,0 +1,140 @@ +/* PR tree-optimization/69097 */ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ +/* All the x % -y below should be optimized into x % y, as + it should never be INT_MIN % -(-1). */ +/* { dg-final { scan-tree-dump-not "-y" "optimized" } } */ + +int +f1 (int x, int y) +{ + if (x == -__INT_MAX__ - 1) + __builtin_unreachable (); + return x % -y; +} + +int +f2 (int x, int y) +{ + if (x < -__INT_MAX__) + __builtin_unreachable (); + return x % -y; +} + +int +f3 (int x, int y) +{ + if (y == -1) + __builtin_unreachable (); + return x % -y; +} + +int +f4 (int x, int y) +{ + if (y < 0) + __builtin_unreachable (); + return x % -y; +} + +int +f5 (int x, int y) +{ + if (y >= -1) + __builtin_unreachable (); + return x % -y; +} + +int +f6 (int x, int y) +{ + if (y < 0 || y > 24) + __builtin_unreachable (); + return x % -y; +} + +int +f7 (int x, int y) +{ + if (y <= -17 || y >= -1) + __builtin_unreachable (); + return x % -y; +} + +int +f8 (int x, int y) +{ + if (y >= -13 && y <= 15) + __builtin_unreachable (); + return x % -y; +} + +int +f9 (int x, int y) +{ + return x % -(y & ~4); +} + +int +f10 (int x, int y) +{ + if (x != -__INT_MAX__ - 1) + return x % -y; + return 34; +} + +int +f11 (int x, int y) +{ + if (x >= -__INT_MAX__) + return x % -y; + return 34; +} + +int +f12 (int x, int y) +{ + if (y != -1) + return x % -y; + return 34; +} + +int +f13 (int x, int y) +{ + if (y >= 0) + return x % -y; + return 34; +} + +int +f14 (int x, int y) +{ + if (y < -1) + return x % -y; + return 34; +} + +int +f15 (int x, int y) +{ + if (y >= 0 && y <= 24) + return x % -y; + return 34; +} + +int +f16 (int x, int y) +{ + if (y > -17 && y < -1) + return x % -y; + return 34; +} + +int +f17 (int x, int y) +{ + if (y < -13 || y > 15) + return x % -y; + return 34; +} --- gcc/testsuite/gcc.dg/pr69097-2.c.jj 2016-01-08 14:23:14.032892362 +0100 +++ gcc/testsuite/gcc.dg/pr69097-2.c 2016-01-08 14:29:59.550327493 +0100 @@ -0,0 +1,138 @@ +/* PR tree-optimization/69097 */ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ +/* { dg-final { scan-tree-dump-times "-y" 17 "optimized" } } */ + +int +f1 (int x, int y) +{ + if (x == -__INT_MAX__) + __builtin_unreachable (); + return x % -y; +} + +int +f2 (int x, int y) +{ + if (x >= -__INT_MAX__ + 1) + __builtin_unreachable (); + return x % -y; +} + +int +f3 (int x, int y) +{ + if (y == -2) + __builtin_unreachable (); + return x % -y; +} + +int +f4 (int x, int y) +{ + if (y < -1) + __builtin_unreachable (); + return x % -y; +} + +int +f5 (int x, int y) +{ + if (y >= 0) + __builtin_unreachable (); + return x % -y; +} + +int +f6 (int x, int y) +{ + if (y < -1 || y > 24) + __builtin_unreachable (); + return x % -y; +} + +int +f7 (int x, int y) +{ + if (y <= -17 || y >= 0) + __builtin_unreachable (); + return x % -y; +} + +int +f8 (int x, int y) +{ + if (y >= -13 && y <= -2) + __builtin_unreachable (); + return x % -y; +} + +int +f9 (int x, int y) +{ + return x % -y; +} + +int +f10 (int x, int y) +{ + if (x != -__INT_MAX__) + return x % -y; + return 34; +} + +int +f11 (int x, int y) +{ + if (x < -__INT_MAX__ + 2) + return x % -y; + return 34; +} + +int +f12 (int x, int y) +{ + if (y != -2) + return x % -y; + return 34; +} + +int +f13 (int x, int y) +{ + if (y >= -1) + return x % -y; + return 34; +} + +int +f14 (int x, int y) +{ + if (y < 0) + return x % -y; + return 34; +} + +int +f15 (int x, int y) +{ + if (y >= -1 && y <= 24) + return x % -y; + return 34; +} + +int +f16 (int x, int y) +{ + if (y > -17 && y < 0) + return x % -y; + return 34; +} + +int +f17 (int x, int y) +{ + if (y < -13 || y > -4) + return x % -y; + return 34; +}