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: 172308 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:bcd1:0:b0:403:3b70:6f57 with SMTP id r17csp951380vqy; Thu, 30 Nov 2023 23:58:36 -0800 (PST) X-Google-Smtp-Source: AGHT+IE8CAM/392YtLCDTyieHh93Rza0psH3d+e9nSTBUo18xBQk5dFBfOaNlNmtg2S7xIgMl0J7 X-Received: by 2002:a05:620a:4883:b0:77d:7843:a06b with SMTP id ea3-20020a05620a488300b0077d7843a06bmr30355573qkb.4.1701417515967; Thu, 30 Nov 2023 23:58:35 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1701417515; cv=pass; d=google.com; s=arc-20160816; b=YWdPYnfd7ZkUlfuRo2ATCyzp0Ve5iDGvIh0hDWbY+s2d5llNBBiW/LvvThllHTQVT6 rDxaU+gquhd0g2m+ttoAey89HjkvM3jclzUrHgcgd44r08FIh13UJbJa0i0hEoxqQA0w f8OOXJc3OPdVYsunXbQybfHQAOdiB3akCpc1yY/RLbBUPIOh0A9FN4hX6V8vqeQIY53b WqLB4OPRWpMSbhlrgr/5edHpVU84iLc2KsNXMWJmJC8IP0cNPs5jzXFQQoGr8nkMahnI DRjOnMI75H3ofri3aIoCy6s7EhGomk9U1kWImicM4RhcRwR7UuAhyTNryeAacqG82VXr vlHA== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=errors-to:reply-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-disposition :mime-version:message-id:subject:cc:to:from:date:dkim-signature :arc-filter:dmarc-filter:delivered-to; bh=+FiC3tv7bO71rT/s7D9fu2ZvaYyoBOVQJNGPCzm7Gx0=; fh=FCjeRajqaQYHMkQtfIia8KT5yBac53mYOLLyJhYG/AY=; b=nRqfc1gE6xuMHRTKLcrN95Jj2Hdu9GJqA6TbTEO/9U6X9A8mmhTpLlCFUFRzqO9V7K ZAQqDyPClb4QNffxam+VTIXW+bdK+aNGu0b3ib3FpHNxDljcrw6lvM2nikcdCKlj+qpW 5UMPoqHIQVy1r3NgOPkNDsuXen/TiNkFm2FMf5QNVMgpI0rzD4HE+bxnA+tvCAGfeiuF hVTw52PCQQomQXbvBEhx7j45afeFj52DQjOa9kDQJLCw0uXZGG/HjyHTArZw/TddvFHw EHe+sCNf8aHdDzOu/I52rB5HFOxvTu7sgXbxur9U0Ol8a7TI02kSGpGbQwmXUZazDGzn 4/NQ== ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@redhat.com header.s=mimecast20190719 header.b=JfH+qGQy; arc=pass (i=1); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=redhat.com Received: from server2.sourceware.org (server2.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id l25-20020a05620a0c1900b0077da5fd278esi2547247qki.681.2023.11.30.23.58.35 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 30 Nov 2023 23:58:35 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@redhat.com header.s=mimecast20190719 header.b=JfH+qGQy; arc=pass (i=1); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=redhat.com Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id B671D385BAF9 for ; Fri, 1 Dec 2023 07:58:35 +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+ouuuleilei=gmail.com@gcc.gnu.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1784065572773918717 X-GMAIL-MSGID: 1784065572773918717 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;