From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [216.205.24.124]) by sourceware.org (Postfix) with ESMTP id E99033955CA6 for ; Wed, 25 Nov 2020 10:05:20 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org E99033955CA6 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-39-VffIf3ncPCu2ZEdfuR4wng-1; Wed, 25 Nov 2020 05:05:16 -0500 X-MC-Unique: VffIf3ncPCu2ZEdfuR4wng-1 Received: from smtp.corp.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id D33C9835DE1; Wed, 25 Nov 2020 10:05:15 +0000 (UTC) Received: from tucnak.zalov.cz (ovpn-113-127.ams2.redhat.com [10.36.113.127]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 6CC344D; Wed, 25 Nov 2020 10:05:15 +0000 (UTC) Received: from tucnak.zalov.cz (localhost [127.0.0.1]) by tucnak.zalov.cz (8.16.1/8.16.1) with ESMTPS id 0APA5CaF1411859 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Wed, 25 Nov 2020 11:05:12 +0100 Received: (from jakub@localhost) by tucnak.zalov.cz (8.16.1/8.16.1/Submit) id 0APA5BPp1411858; Wed, 25 Nov 2020 11:05:11 +0100 Date: Wed, 25 Nov 2020 11:05:11 +0100 From: Jakub Jelinek To: Richard Biener Cc: gcc-patches@gcc.gnu.org Subject: [PATCH] middle-end: __builtin_mul_overflow expansion improvements [PR95862] Message-ID: <20201125100511.GY3788@tucnak> Reply-To: Jakub Jelinek MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.11 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=us-ascii Content-Disposition: inline X-Spam-Status: No, score=-6.0 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 25 Nov 2020 10:05:22 -0000 Hi! The following patch adds some improvements for __builtin_mul_overflow expansion. One optimization is for the u1 * u2 -> sr case, as documented we normally do: u1 * u2 -> sr res = (S) (u1 * u2) ovf = res < 0 || main_ovf (true) where main_ovf (true) stands for jump on unsigned multiplication overflow. If we know that the most significant bits of both operands are clear (such as when they are zero extended from something smaller), we can emit better coe by handling it like s1 * s2 -> sr, i.e. just jump on overflow after signed multiplication. Another two cases are s1 * s2 -> ur or s1 * u2 -> ur, if we know the minimum precision needed to encode all values of both arguments summed together is smaller or equal to destination precision (such as when the two arguments are sign (or zero) extended from half precision types, we know the overflows happen only iff one argument is negative and the other argument is positive (not zero), because even if both have maximum possible values, the maximum is still representable (e.g. for char * char -> unsigned short 0x7f * 0x7f = 0x3f01 and for char * unsigned char -> unsigned short 0x7f * 0xffU = 0x7e81) and as the result is unsigned, all negative results do overflow, but are also representable if we consider the result signed - all of them have the MSB set. So, it is more efficient to just do the normal multiplication in that case and compare the result considered as signed value against 0, if it is smaller, overflow happened. And the get_min_precision change is to improve the char to short handling, we have there in the IL _2 = (int) arg_1(D); promotion from C promotions from char or unsigned char arg, and the caller adds a NOP_EXPR cast to short or unsigned short. get_min_precision punts on the narrowing cast though, it handled only widening casts, but we can handle narrowing casts fine too, by recursing on the narrowing cast operands and using it only if it has in the end smaller minimal precision, which would duplicate the sign bits (or zero bits) to both the bits above the narrowing conversion and also at least one below that. Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? 2020-10-25 Jakub Jelinek PR rtl-optimization/95862 * internal-fn.c (get_min_precision): For narrowing conversion, recurse on the operand and if the operand precision is smaller than the current one, return that smaller precision. (expand_mul_overflow): For s1 * u2 -> ur and s1 * s2 -> ur cases if the sum of minimum precisions of both operands is smaller or equal to the result precision, just perform normal multiplication and set overflow to the sign bit of the multiplication result. For u1 * u2 -> sr if both arguments have the MSB known zero, use normal s1 * s2 -> sr expansion. * gcc.dg/builtin-artih-overflow-5.c: New test. --- gcc/internal-fn.c.jj 2020-10-13 09:25:28.444909391 +0200 +++ gcc/internal-fn.c 2020-11-24 15:54:32.684762538 +0100 @@ -553,6 +553,16 @@ get_min_precision (tree arg, signop sign if (++cnt > 30) return prec + (orig_sign != sign); } + if (CONVERT_EXPR_P (arg) + && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (arg, 0))) + && TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (arg, 0))) > prec) + { + /* We have e.g. (unsigned short) y_2 where int y_2 = (int) x_1(D); + If y_2's min precision is smaller than prec, return that. */ + int oprec = get_min_precision (TREE_OPERAND (arg, 0), sign); + if (oprec < prec) + return oprec + (orig_sign != sign); + } if (TREE_CODE (arg) != SSA_NAME) return prec + (orig_sign != sign); wide_int arg_min, arg_max; @@ -1357,6 +1367,37 @@ expand_mul_overflow (location_t loc, tre NULL, done_label, profile_probability::very_likely ()); goto do_error_label; case 3: + if (get_min_precision (arg1, UNSIGNED) + + get_min_precision (arg0, SIGNED) <= GET_MODE_PRECISION (mode)) + { + /* If the first operand is sign extended from narrower type, the + second operand is zero extended from narrower type and + the sum of the two precisions is smaller or equal to the + result precision: if the first argument is at runtime + non-negative, maximum result will be 0x7e81 or 0x7f..fe80..01 + and there will be no overflow, if the first argument is + negative and the second argument zero, the result will be + 0 and there will be no overflow, if the first argument is + negative and the second argument positive, the result when + treated as signed will be negative (minimum -0x7f80 or + -0x7f..f80..0) there there will be always overflow. So, do + res = (U) (s1 * u2) + ovf = (S) res < 0 */ + struct separate_ops ops; + ops.code = MULT_EXPR; + ops.type + = build_nonstandard_integer_type (GET_MODE_PRECISION (mode), + 1); + ops.op0 = make_tree (ops.type, op0); + ops.op1 = make_tree (ops.type, op1); + ops.op2 = NULL_TREE; + ops.location = loc; + res = expand_expr_real_2 (&ops, NULL_RTX, mode, EXPAND_NORMAL); + do_compare_rtx_and_jump (res, const0_rtx, GE, false, + mode, NULL_RTX, NULL, done_label, + profile_probability::very_likely ()); + goto do_error_label; + } rtx_code_label *do_main_label; do_main_label = gen_label_rtx (); do_compare_rtx_and_jump (op0, const0_rtx, GE, false, mode, NULL_RTX, @@ -1374,7 +1415,16 @@ expand_mul_overflow (location_t loc, tre /* u1 * u2 -> sr */ if (uns0_p && uns1_p && !unsr_p) { - uns = true; + if ((pos_neg0 | pos_neg1) == 1) + { + /* If both arguments are zero extended from narrower types, + the MSB will be clear on both and so we can pretend it is + a normal s1 * s2 -> sr multiplication. */ + uns0_p = false; + uns1_p = false; + } + else + uns = true; /* Rest of handling of this case after res is computed. */ goto do_main; } @@ -1455,6 +1505,37 @@ expand_mul_overflow (location_t loc, tre profile_probability::very_likely ()); goto do_error_label; } + if (get_min_precision (arg0, SIGNED) + + get_min_precision (arg1, SIGNED) <= GET_MODE_PRECISION (mode)) + { + /* If both operands are sign extended from narrower types and + the sum of the two precisions is smaller or equal to the + result precision: if both arguments are at runtime + non-negative, maximum result will be 0x3f01 or 0x3f..f0..01 + and there will be no overflow, if both arguments are negative, + maximum result will be 0x40..00 and there will be no overflow + either, if one argument is positive and the other argument + negative, the result when treated as signed will be negative + and there will be always overflow, and if one argument is + zero and the other negative the result will be zero and no + overflow. So, do + res = (U) (s1 * s2) + ovf = (S) res < 0 */ + struct separate_ops ops; + ops.code = MULT_EXPR; + ops.type + = build_nonstandard_integer_type (GET_MODE_PRECISION (mode), + 1); + ops.op0 = make_tree (ops.type, op0); + ops.op1 = make_tree (ops.type, op1); + ops.op2 = NULL_TREE; + ops.location = loc; + res = expand_expr_real_2 (&ops, NULL_RTX, mode, EXPAND_NORMAL); + do_compare_rtx_and_jump (res, const0_rtx, GE, false, + mode, NULL_RTX, NULL, done_label, + profile_probability::very_likely ()); + goto do_error_label; + } /* The general case, do all the needed comparisons at runtime. */ rtx_code_label *do_main_label, *after_negate_label; rtx rop0, rop1; --- gcc/testsuite/gcc.dg/builtin-artih-overflow-5.c.jj 2020-11-24 16:13:49.482793354 +0100 +++ gcc/testsuite/gcc.dg/builtin-artih-overflow-5.c 2020-11-24 16:13:44.980843796 +0100 @@ -0,0 +1,87 @@ +/* PR rtl-optimization/95862 */ +/* { dg-do compile } */ +/* { dg-options "-O2" } */ + +int +f1 (int a, int b) +{ + unsigned long long c; + return __builtin_mul_overflow (a, b, &c); +} + +int +f2 (int a, unsigned b) +{ + unsigned long long c; + return __builtin_mul_overflow (a, b, &c); +} + +int +f3 (unsigned a, unsigned b) +{ + long long c; + return __builtin_mul_overflow (a, b, &c); +} + +int +f4 (int a, unsigned b) +{ + long long c; + return __builtin_mul_overflow (a, b, &c); +} + +short +f5 (short a, short b) +{ + unsigned c; + return __builtin_mul_overflow (a, b, &c); +} + +short +f6 (short a, unsigned short b) +{ + unsigned c; + return __builtin_mul_overflow (a, b, &c); +} + +short +f7 (unsigned short a, unsigned short b) +{ + int c; + return __builtin_mul_overflow (a, b, &c); +} + +short +f8 (short a, unsigned short b) +{ + int c; + return __builtin_mul_overflow (a, b, &c); +} + +signed char +f9 (signed char a, signed char b) +{ + unsigned short c; + return __builtin_mul_overflow (a, b, &c); +} + +signed char +f10 (signed char a, unsigned char b) +{ + unsigned short c; + return __builtin_mul_overflow (a, b, &c); +} + +signed char +f11 (unsigned char a, unsigned char b) +{ + short c; + return __builtin_mul_overflow (a, b, &c); +} + +signed char +f12 (signed char a, unsigned char b) +{ + short c; + return __builtin_mul_overflow (a, b, &c); +} Jakub