From patchwork Fri Dec 1 07:58:01 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Jelinek X-Patchwork-Id: 81078 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 3FE203858422 for ; Fri, 1 Dec 2023 07:58:28 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTPS id 46A0E3858422 for ; Fri, 1 Dec 2023 07:58:10 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 46A0E3858422 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 46A0E3858422 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=170.10.129.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1701417492; cv=none; b=wXyrkxgU91gqSWMJ3XXjCl/7JsLLEbRhsMJc+GKlCZnIgMpjYQMnouZtJ10mW5etaOw3Xe1C0IJBGbaG4743nX9FKxv5VjlLS2EHIFlZCebEQvFr/CE/lKxc/C8ysq73R5HbRvc3nwAYbPKBRWZ7cJjEO3Wb42WPzIT3bhRvutU= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1701417492; c=relaxed/simple; bh=YD6i9Cw8ZzDK1PYi1H8S3VVQKzRqxJi1HkWTC/86+3Q=; h=DKIM-Signature:Date:From:To:Subject:Message-ID:MIME-Version; b=HzokCGfbQyh9ctH260ht4yBPiH2YkEvGxtjQc1Wspn8oMQh7EeuTLaMzMB3/acKpXR2UHTf2c/1skJldM3DpRgK0+Fv0xeae+MKE71lpaDIBMyF61l0kuh2iDrmz7/3zIyKIXM3g3CxhH5dQ0dwGc+gIAo+FzzQNSfR0LfbtWrQ= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1701417489; h=from:from:reply-to:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=+FiC3tv7bO71rT/s7D9fu2ZvaYyoBOVQJNGPCzm7Gx0=; b=JfH+qGQypR3wQ/TBeVmJeX8nAgTP5BuCyEu2e9eXa/DldjhCzpt1McZCRX34KM291z1O7e HsygLCvN4HpB5PO7hLPpGiE1C8YmNvC7+oninENC5eM5U8E1pOMNBiff9uhwRt/eqfIhEN L0J31DyoP5GzbzVyGHBbcrgOiuNRb2I= Received: from mimecast-mx02.redhat.com (mx-ext.redhat.com [66.187.233.73]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-387-7B8kVMlRM62JLLk8d_WqkQ-1; Fri, 01 Dec 2023 02:58:05 -0500 X-MC-Unique: 7B8kVMlRM62JLLk8d_WqkQ-1 Received: from smtp.corp.redhat.com (int-mx07.intmail.prod.int.rdu2.redhat.com [10.11.54.7]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id AACF33C000AF; Fri, 1 Dec 2023 07:58:05 +0000 (UTC) Received: from tucnak.zalov.cz (unknown [10.39.195.157]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 6DF851C060AE; Fri, 1 Dec 2023 07:58:05 +0000 (UTC) Received: from tucnak.zalov.cz (localhost [127.0.0.1]) by tucnak.zalov.cz (8.17.1/8.17.1) with ESMTPS id 3B17w2Kb540238 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Fri, 1 Dec 2023 08:58:03 +0100 Received: (from jakub@localhost) by tucnak.zalov.cz (8.17.1/8.17.1/Submit) id 3B17w2aa540237; Fri, 1 Dec 2023 08:58:02 +0100 Date: Fri, 1 Dec 2023 08:58:01 +0100 From: Jakub Jelinek To: Richard Biener Cc: gcc-patches@gcc.gnu.org Subject: [PATCH] lower-bitint: Fix up maximum addition/subtraction/multiplication result computations Message-ID: MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.4.1 on 10.11.54.7 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Disposition: inline X-Spam-Status: No, score=-3.2 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_H4, RCVD_IN_MSPIKE_WL, SCC_5_SHORT_WORD_LINES, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE autolearn=no autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: Jakub Jelinek Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Hi! When debugging PR112750, I've noticed some issues in the computation of precisions and the following patch attempts to fix those. The pass uses range_to_prec function, which possibly using ranger returns minimum precision of some operand in the style that libgcc _BitInt entrypoints expect, i.e. for operands with unsigned types either the precision of that type or with help of ranger wi::min_precision (upper_bound, UNSIGNED) (done both if the types are really unsigned or even when lower_bound is non-negative), while for operands with signed types either negated precision of that type or with help of ranger negated value of maximum of SIGNED min_precisions of lower and upper bound. Because _BitInt in C only supports unsigned precisions >= 1 and signed precisions >= 2, the function also ensures that 0 is never returned (returns 1 instead) and should ensure that -1 is never returned (should return -2). That is the first bug I found though, for the ranger case it ensured that, but if an operand would be signed 1-bit precision (that means non-BITINT_TYPE) operand, it could return -1. Another thing is that both lower_addsub_overflow and lower_mul_overflow compute from the prec0 and prec1 of the operands (returned by range_to_prec with the above value meanings) prec2, which is how many bits of the result we actually need to compute to know the infinite precision result. This is then used by arith_overflow function together with prec (TYPE_PRECISION (type)), type (type of the result), prec0 and prec1 to compute which range of bits should be tested (if any, or that there is never an overflow) and with which kind (require those bits to be zero vs. check if all those bits together all all zeros/ones). The arith_overflow function has one special case, when prec0 >= 0 && prec1 >= 0 and operation is not .SUB_OVERFLOW; in that case we treat prec2 as minimum precision to express any infinite precision unsigned result (the result is never negative in that case), while in all other cases prec2 is treated as minimum precision to express any infinite precision signed result (because the result can be also negative). The computations of those values were apparently incorrect for all of .{ADD,SUB}_OVERFLOW (in that case only if one operand was signed and the other unsigned) and for .MUL_OVERFLOW it was sometimes too large. It took me a while to get to the right expression how to compute that, I've started with writing into the comment the possible results for different prec0 and prec1 values (used just 8/-8/10/-10 as placeholders for equal or different absolute values of the 2 precisions and cases with positive and/or negative signs) and then turned into the attached test program that actually printed what I was writing to make sure I didn't make mistakes in it and in the end also verified the computation, this time for all combinations of 1..14 and -2..-14 precisions. The UNSIGNED vs. SIGNED in the table is what arith_overflow expects the prec2 to be (see above mentioned exception). Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? 2023-12-01 Jakub Jelinek * gimple-lower-bitint.cc (range_to_prec): Don't return -1 for signed types. (bitint_large_huge::lower_addsub_overflow): Fix up computation of prec2. (bitint_large_huge::lower_mul_overflow): Likewise. Jakub int main () { int p[] = { 1, 0, 0x1, 2, 0, 0x3, 3, 0, 0x7, 4, 0, 0xf, 5, 0, 0x1f, 6, 0, 0x3f, 7, 0, 0x7f, 8, 0, 0xff, 9, 0, 0x1ff, 10, 0, 0x3ff, 11, 0, 0x7ff, 12, 0, 0xfff, 13, 0, 0x1fff, 14, 0, 0x3fff, -2, -0x2, 0x1, -3, -0x4, 0x3, -4, -0x8, 0x7, -5, -0x10, 0xf, -6, -0x20, 0x1f, -7, -0x40, 0x3f, -8, -0x80, 0x7f, -9, -0x100, 0xff, -10, -0x200, 0x1ff, -11, -0x400, 0x3ff, -12, -0x800, 0x7ff, -13, -0x1000, 0xfff, -14, -0x2000, 0x1fff }; for (int op = 0; op <= 2; op++) for (int a = 0; a < 27; ++a) for (int b = 0; b < 27; ++b) { int mina = p[3 * a + 1]; int maxa = p[3 * a + 2]; int minb = p[3 * b + 1]; int maxb = p[3 * b + 2]; int prec0 = p[3 * a]; int prec1 = p[3 * b]; long long int min, max; if (op == 0) { max = min = mina + minb; if (min > maxa + minb) min = maxa + minb; if (min > mina + maxb) min = mina + maxb; if (min > maxa + maxb) min = maxa + maxb; if (max < maxa + minb) max = maxa + minb; if (max < mina + maxb) max = mina + maxb; if (max < maxa + maxb) max = maxa + maxb; } else if (op == 1) { max = min = mina - minb; if (min > maxa - minb) min = maxa - minb; if (min > mina - maxb) min = mina - maxb; if (min > maxa - maxb) min = maxa - maxb; if (max < maxa - minb) max = maxa - minb; if (max < mina - maxb) max = mina - maxb; if (max < maxa - maxb) max = maxa - maxb; } else { max = min = ((long long) mina) * minb; if (min > ((long long) maxa) * minb) min = ((long long) maxa) * minb; if (min > ((long long) mina) * maxb) min = ((long long) mina) * maxb; if (min > ((long long) maxa) * maxb) min = ((long long) maxa) * maxb; if (max < ((long long) maxa) * minb) max = ((long long) maxa) * minb; if (max < ((long long) mina) * maxb) max = ((long long) mina) * maxb; if (max < ((long long) maxa) * maxb) max = ((long long) maxa) * maxb; } int uns = op != 1 && prec0 > 0 && prec1 > 0; int prec; if (uns) { if (min != 0) __builtin_abort (); prec = 64 - __builtin_clzll (max); } else { prec = 64 - __builtin_clrsbll (min); if (prec < 64 - __builtin_clrsbll (max)) prec = 64 - __builtin_clrsbll (max); } char buf[32]; if (min == 0) __builtin_sprintf (buf, "0"); else __builtin_sprintf (buf, "-0x%llx", -min); __builtin_printf (" %3d %c %3d [%s,0x%llx] %2d %sSIGNED\n", prec0, op == 0 ? '+' : op == 1 ? '-' : '*', prec1, buf, max, prec, uns ? "UN" : ""); #define MAX(X,Y) ((X) > (Y) ? (X) : (Y)) int prec2 = MAX (prec0 < 0 ? -prec0 : prec0, prec1 < 0 ? -prec1 : prec1); if (op != 2) prec2 = (((prec0 < 0) == (prec1 < 0) || (prec0 < 0 ? (prec2 == -prec0 && prec2 != prec1) : (prec2 == -prec1 && prec2 != prec0))) ? prec2 + 1 : prec2 + 2); if (op == 2) { prec2 = (prec0 < 0 ? -prec0 : prec0) + (prec1 < 0 ? -prec1 : prec1); if (prec0 == 1 || prec1 == 1) --prec2; } if (prec2 != prec) __builtin_abort (); } } --- gcc/gimple-lower-bitint.cc.jj 2023-11-30 12:46:34.715093396 +0100 +++ gcc/gimple-lower-bitint.cc 2023-11-30 17:24:59.828026693 +0100 @@ -1963,7 +1963,7 @@ range_to_prec (tree op, gimple *stmt) if (TYPE_UNSIGNED (type)) return prec; else - return -prec; + return MIN ((int) -prec, -2); } if (!TYPE_UNSIGNED (TREE_TYPE (op))) @@ -3792,11 +3792,45 @@ bitint_large_huge::lower_addsub_overflow int prec = TYPE_PRECISION (type); int prec0 = range_to_prec (arg0, stmt); int prec1 = range_to_prec (arg1, stmt); - int prec2 = ((prec0 < 0) == (prec1 < 0) - ? MAX (prec0 < 0 ? -prec0 : prec0, - prec1 < 0 ? -prec1 : prec1) + 1 - : MAX (prec0 < 0 ? -prec0 : prec0 + 1, - prec1 < 0 ? -prec1 : prec1 + 1) + 1); + /* If PREC0 >= 0 && PREC1 >= 0 and CODE is not MINUS_EXPR, PREC2 is + the be minimum unsigned precision of any possible operation's + result, otherwise it is minimum signed precision. + Some examples: + If PREC0 or PREC1 is 8, it means that argument is [0, 0xff], + if PREC0 or PREC1 is 10, it means that argument is [0, 0x3ff], + if PREC0 or PREC1 is -8, it means that argument is [-0x80, 0x7f], + if PREC0 or PREC1 is -10, it means that argument is [-0x200, 0x1ff]. + PREC0 CODE PREC1 RESULT PREC2 SIGNED vs. UNSIGNED + 8 + 8 [0, 0x1fe] 9 UNSIGNED + 8 + 10 [0, 0x4fe] 11 UNSIGNED + -8 + -8 [-0x100, 0xfe] 9 SIGNED + -8 + -10 [-0x280, 0x27e] 11 SIGNED + 8 + -8 [-0x80, 0x17e] 10 SIGNED + 8 + -10 [-0x200, 0x2fe] 11 SIGNED + 10 + -8 [-0x80, 0x47e] 12 SIGNED + 8 - 8 [-0xff, 0xff] 9 SIGNED + 8 - 10 [-0x3ff, 0xff] 11 SIGNED + 10 - 8 [-0xff, 0x3ff] 11 SIGNED + -8 - -8 [-0xff, 0xff] 9 SIGNED + -8 - -10 [-0x27f, 0x27f] 11 SIGNED + -10 - -8 [-0x27f, 0x27f] 11 SIGNED + 8 - -8 [-0x7f, 0x17f] 10 SIGNED + 8 - -10 [-0x1ff, 0x2ff] 11 SIGNED + 10 - -8 [-0x7f, 0x47f] 12 SIGNED + -8 - 8 [-0x17f, 0x7f] 10 SIGNED + -8 - 10 [-0x47f, 0x7f] 12 SIGNED + -10 - 8 [-0x2ff, 0x1ff] 11 SIGNED */ + int prec2 = MAX (prec0 < 0 ? -prec0 : prec0, + prec1 < 0 ? -prec1 : prec1); + /* If operands are either both signed or both unsigned, + we need just one additional bit. */ + prec2 = (((prec0 < 0) == (prec1 < 0) + /* If one operand is signed and one unsigned and + the signed one has larger precision, we need + just one extra bit, otherwise two. */ + || (prec0 < 0 ? (prec2 == -prec0 && prec2 != prec1) + : (prec2 == -prec1 && prec2 != prec0))) + ? prec2 + 1 : prec2 + 2); int prec3 = MAX (prec0 < 0 ? -prec0 : prec0, prec1 < 0 ? -prec1 : prec1); prec3 = MAX (prec3, prec); @@ -4201,8 +4235,9 @@ bitint_large_huge::lower_mul_overflow (t arg0 = handle_operand_addr (arg0, stmt, NULL, &prec0); arg1 = handle_operand_addr (arg1, stmt, NULL, &prec1); int prec2 = ((prec0 < 0 ? -prec0 : prec0) - + (prec1 < 0 ? -prec1 : prec1) - + ((prec0 < 0) != (prec1 < 0))); + + (prec1 < 0 ? -prec1 : prec1)); + if (prec0 == 1 || prec1 == 1) + --prec2; tree var = NULL_TREE; tree orig_obj = obj; bool force_var = false;