From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 124208 invoked by alias); 22 Feb 2017 21:41:04 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 124177 invoked by uid 89); 22 Feb 2017 21:41:02 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-11.9 required=5.0 tests=BAYES_00,GIT_PATCH_2,GIT_PATCH_3,RP_MATCHES_RCVD,SPF_HELO_PASS autolearn=ham version=3.3.2 spammy=SIGNED, 20170209, 2017-02-09 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 ESMTP; Wed, 22 Feb 2017 21:40:58 +0000 Received: from int-mx10.intmail.prod.int.phx2.redhat.com (int-mx10.intmail.prod.int.phx2.redhat.com [10.5.11.23]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 2A17A8123E for ; Wed, 22 Feb 2017 21:40:57 +0000 (UTC) Received: from tucnak.zalov.cz (ovpn-117-76.ams2.redhat.com [10.36.117.76]) by int-mx10.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id v1MLetkI015002 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=NO); Wed, 22 Feb 2017 16:40:56 -0500 Received: from tucnak.zalov.cz (localhost [127.0.0.1]) by tucnak.zalov.cz (8.15.2/8.15.2) with ESMTP id v1MLelGa006952; Wed, 22 Feb 2017 22:40:52 +0100 Received: (from jakub@localhost) by tucnak.zalov.cz (8.15.2/8.15.2/Submit) id v1MLek7w006951; Wed, 22 Feb 2017 22:40:46 +0100 Date: Wed, 22 Feb 2017 21:50:00 -0000 From: Jakub Jelinek To: Jeff Law Cc: gcc-patches@gcc.gnu.org Subject: [PATCH] Optimize divmod expansion (PR middle-end/79665) Message-ID: <20170222214046.GA1849@tucnak> Reply-To: Jakub Jelinek MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.7.1 (2016-10-04) X-IsSubscribed: yes X-SW-Source: 2017-02/txt/msg01409.txt.bz2 Hi! If both arguments of integer division or modulo are known to be non-negative in corresponding signed type, then signed as well as unsigned division/modulo shall have the exact same result and therefore we can choose between those two depending on which one is faster (or shorter for -Os), which varries a lot depending on target and especially for constant divisors on the exact divisor. expand_divmod itself is too complicated and we don't even have the ability to ask about costs e.g. for highpart multiplication without actually expanding it, so this patch just in that case tries both sequences, computes their costs and uses the cheaper (and for equal cost honors the actual original signedness of the operation). Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? 2017-02-22 Jakub Jelinek PR middle-end/79665 * internal-fn.c (get_range_pos_neg): Moved to ... * tree.c (get_range_pos_neg): ... here. No longer static. * tree.h (get_range_pos_neg): New prototype. * expr.c (expand_expr_real_2) : If both arguments are known to be in between 0 and signed maximum inclusive, try to expand both unsigned and signed divmod and use the cheaper one from those. --- gcc/internal-fn.c.jj 2017-02-11 09:14:56.000000000 +0100 +++ gcc/internal-fn.c 2017-02-22 10:09:03.503254909 +0100 @@ -413,86 +413,6 @@ expand_FALLTHROUGH (internal_fn, gcall * "invalid use of attribute %"); } -/* Helper function for expand_addsub_overflow. Return 1 - if ARG interpreted as signed in its precision is known to be always - positive or 2 if ARG is known to be always negative, or 3 if ARG may - be positive or negative. */ - -static int -get_range_pos_neg (tree arg) -{ - if (arg == error_mark_node) - return 3; - - int prec = TYPE_PRECISION (TREE_TYPE (arg)); - int cnt = 0; - if (TREE_CODE (arg) == INTEGER_CST) - { - wide_int w = wi::sext (arg, prec); - if (wi::neg_p (w)) - return 2; - else - return 1; - } - while (CONVERT_EXPR_P (arg) - && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (arg, 0))) - && TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg, 0))) <= prec) - { - arg = TREE_OPERAND (arg, 0); - /* Narrower value zero extended into wider type - will always result in positive values. */ - if (TYPE_UNSIGNED (TREE_TYPE (arg)) - && TYPE_PRECISION (TREE_TYPE (arg)) < prec) - return 1; - prec = TYPE_PRECISION (TREE_TYPE (arg)); - if (++cnt > 30) - return 3; - } - - if (TREE_CODE (arg) != SSA_NAME) - return 3; - wide_int arg_min, arg_max; - while (get_range_info (arg, &arg_min, &arg_max) != VR_RANGE) - { - gimple *g = SSA_NAME_DEF_STMT (arg); - if (is_gimple_assign (g) - && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (g))) - { - tree t = gimple_assign_rhs1 (g); - if (INTEGRAL_TYPE_P (TREE_TYPE (t)) - && TYPE_PRECISION (TREE_TYPE (t)) <= prec) - { - if (TYPE_UNSIGNED (TREE_TYPE (t)) - && TYPE_PRECISION (TREE_TYPE (t)) < prec) - return 1; - prec = TYPE_PRECISION (TREE_TYPE (t)); - arg = t; - if (++cnt > 30) - return 3; - continue; - } - } - return 3; - } - if (TYPE_UNSIGNED (TREE_TYPE (arg))) - { - /* For unsigned values, the "positive" range comes - below the "negative" range. */ - if (!wi::neg_p (wi::sext (arg_max, prec), SIGNED)) - return 1; - if (wi::neg_p (wi::sext (arg_min, prec), SIGNED)) - return 2; - } - else - { - if (!wi::neg_p (wi::sext (arg_min, prec), SIGNED)) - return 1; - if (wi::neg_p (wi::sext (arg_max, prec), SIGNED)) - return 2; - } - return 3; -} - /* Return minimum precision needed to represent all values of ARG in SIGNed integral type. */ --- gcc/tree.c.jj 2017-02-09 14:55:34.000000000 +0100 +++ gcc/tree.c 2017-02-22 10:10:36.525062066 +0100 @@ -14205,6 +14205,88 @@ verify_type (const_tree t) } +/* Return 1 if ARG interpreted as signed in its precision is known to be + always positive or 2 if ARG is known to be always negative, or 3 if + ARG may be positive or negative. */ + +int +get_range_pos_neg (tree arg) +{ + if (arg == error_mark_node) + return 3; + + int prec = TYPE_PRECISION (TREE_TYPE (arg)); + int cnt = 0; + if (TREE_CODE (arg) == INTEGER_CST) + { + wide_int w = wi::sext (arg, prec); + if (wi::neg_p (w)) + return 2; + else + return 1; + } + while (CONVERT_EXPR_P (arg) + && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (arg, 0))) + && TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg, 0))) <= prec) + { + arg = TREE_OPERAND (arg, 0); + /* Narrower value zero extended into wider type + will always result in positive values. */ + if (TYPE_UNSIGNED (TREE_TYPE (arg)) + && TYPE_PRECISION (TREE_TYPE (arg)) < prec) + return 1; + prec = TYPE_PRECISION (TREE_TYPE (arg)); + if (++cnt > 30) + return 3; + } + + if (TREE_CODE (arg) != SSA_NAME) + return 3; + wide_int arg_min, arg_max; + while (get_range_info (arg, &arg_min, &arg_max) != VR_RANGE) + { + gimple *g = SSA_NAME_DEF_STMT (arg); + if (is_gimple_assign (g) + && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (g))) + { + tree t = gimple_assign_rhs1 (g); + if (INTEGRAL_TYPE_P (TREE_TYPE (t)) + && TYPE_PRECISION (TREE_TYPE (t)) <= prec) + { + if (TYPE_UNSIGNED (TREE_TYPE (t)) + && TYPE_PRECISION (TREE_TYPE (t)) < prec) + return 1; + prec = TYPE_PRECISION (TREE_TYPE (t)); + arg = t; + if (++cnt > 30) + return 3; + continue; + } + } + return 3; + } + if (TYPE_UNSIGNED (TREE_TYPE (arg))) + { + /* For unsigned values, the "positive" range comes + below the "negative" range. */ + if (!wi::neg_p (wi::sext (arg_max, prec), SIGNED)) + return 1; + if (wi::neg_p (wi::sext (arg_min, prec), SIGNED)) + return 2; + } + else + { + if (!wi::neg_p (wi::sext (arg_min, prec), SIGNED)) + return 1; + if (wi::neg_p (wi::sext (arg_max, prec), SIGNED)) + return 2; + } + return 3; +} + + + + /* Return true if ARG is marked with the nonnull attribute in the current function signature. */ --- gcc/tree.h.jj 2017-02-09 14:55:34.000000000 +0100 +++ gcc/tree.h 2017-02-22 10:11:05.448691171 +0100 @@ -4876,6 +4876,7 @@ extern bool gimple_canonical_types_compa bool trust_type_canonical = true); extern bool type_with_interoperable_signedness (const_tree); extern bitmap get_nonnull_args (const_tree); +extern int get_range_pos_neg (tree); /* Return simplified tree code of type that is used for canonical type merging. */ --- gcc/expr.c.jj 2017-01-19 16:58:23.000000000 +0100 +++ gcc/expr.c 2017-02-22 10:22:20.290996636 +0100 @@ -8809,6 +8809,34 @@ expand_expr_real_2 (sepops ops, rtx targ where some terms of the dividend have coeffs divisible by it. */ expand_operands (treeop0, treeop1, subtarget, &op0, &op1, EXPAND_NORMAL); + if (SCALAR_INT_MODE_P (mode) + && optimize >= 2 + && get_range_pos_neg (treeop0) == 1 + && get_range_pos_neg (treeop1) == 1) + { + /* If both arguments are known to be positive when interpreted + as signed, we can expand it as both signed and unsigned + division or modulo. Choose the cheaper sequence in that case. */ + bool speed_p = optimize_insn_for_speed_p (); + do_pending_stack_adjust (); + start_sequence (); + rtx uns_ret = expand_divmod (0, code, mode, op0, op1, target, 1); + rtx_insn *uns_insns = get_insns (); + end_sequence (); + start_sequence (); + rtx sgn_ret = expand_divmod (0, code, mode, op0, op1, target, 0); + rtx_insn *sgn_insns = get_insns (); + end_sequence (); + unsigned uns_cost = seq_cost (uns_insns, speed_p); + unsigned sgn_cost = seq_cost (sgn_insns, speed_p); + if (uns_cost < sgn_cost || (uns_cost == sgn_cost && unsignedp)) + { + emit_insn (uns_insns); + return uns_ret; + } + emit_insn (sgn_insns); + return sgn_ret; + } return expand_divmod (0, code, mode, op0, op1, target, unsignedp); case RDIV_EXPR: Jakub