From patchwork Tue Feb 6 21:15:53 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Jelinek X-Patchwork-Id: 197649 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7301:168b:b0:106:860b:bbdd with SMTP id ma11csp1829016dyb; Tue, 6 Feb 2024 13:16:45 -0800 (PST) X-Google-Smtp-Source: AGHT+IHc4uMmiUIv3oyaZo+gXuDixrNRUeGCuB60Gy/AM9aL1DXHfTNJXATkm32tceNURsKtisrJ X-Received: by 2002:a05:6871:114:b0:219:2ce7:29e0 with SMTP id y20-20020a056871011400b002192ce729e0mr3974682oab.4.1707254205320; Tue, 06 Feb 2024 13:16:45 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1707254205; cv=pass; d=google.com; s=arc-20160816; b=m46BQ1ep76TgP2YblKeXR0WErkENN5oIrlBZe8MD8Eh6l+Vr23Ui3pibO3VviPlQCd p+OLUvErsOllFZTbw4LE950GumGWxHmpdCZ/3k3KLBESdiRHC8NnB8DY3EB5ROPyfU1U cuUV1ux33CSVE9HylMhs2mKPMn235f1njD4P6zr9mq9gFEJnXaXdYamZjUM1lf4mHy2r I/J1HPYOW4H066LY5nyjejSnJmjS+3AqZeokza3AQAb/wBRbYNaKajEQT9Sqij6Ie8T2 RgS3yKDoV3v5aUbrAU1tq/xy2VwdK0Ro2YuBymyeXdnqIVGwjiIqT0v8RfS4tlYM5oQ9 zOPg== 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=7Zl0lLWvZDoef+3p/PJF4casI/vMFgb7S/Cwj/FIZ8k=; fh=/OJ6p3b2yrXvUXwvP2nP2SsFYSEo34cN9n2tZ7Az5Z0=; b=qSqWKObgZvgwQcrzr0PFle8/NeQUIiaEZTBwliCK/1/7WeI/pfsGkejPguIAJlJZjk PWGsmwJVn7FbK1+QtJZ1RDbbwn398wTJLROXotpxwbob6EPxSiU2iu6UqnMB7vsJiyse AnsX7tve2lLM6q+NgJe8GwsQ1xAOf1YAlifMpvKrcPu5uC8eRfDb/EmhLKryc4YecWtU h2RD/sd1lbu1brHnNsPMPlJFnOSk3z4WKHEEvupVVo2PKCN7q7YzJpYRqYPcTt0WV+fm 5QqUknFtw3ZmO6q0o8o74uW+r0Vva6a+XiIuYo+AQvVk6lKWMidREsxxow50WUp3tDlh 6h8A==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@redhat.com header.s=mimecast20190719 header.b="Lm5FZA/H"; 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 X-Forwarded-Encrypted: i=1; AJvYcCUHt9gG76cJsutxd1lGOcasTMQbFOBa+I7MAQqAFcGKd1S8D8fjs2qsE8lYeGg0i1ldYV7ocyCQhr8mklAY7pi0YfbCWw== Received: from server2.sourceware.org (server2.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id p13-20020a05622a00cd00b0042a9a5f09casi3230825qtw.179.2024.02.06.13.16.45 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 06 Feb 2024 13:16:45 -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="Lm5FZA/H"; 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 05A4D385801C for ; Tue, 6 Feb 2024 21:16:45 +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.133.124]) by sourceware.org (Postfix) with ESMTPS id 9B9B33858C2F for ; Tue, 6 Feb 2024 21:16:02 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 9B9B33858C2F 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 9B9B33858C2F Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=170.10.133.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1707254165; cv=none; b=kcH2fMsr7BtDmOKhL5/Yd6+bY3QO+TJyIE+xIm3i8N0N4LLI67H6ckm0l02+DJsZ6VsLvWinZXFzXxF37ke4eAxqeCfndyBmtajFKJuLIM45H+FWfh5dIap9qe3LGa+Pm6nixV2zJ8+Xv8I+pgQBv6PdgxsMaPLLWZvSmG5cOMY= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1707254165; c=relaxed/simple; bh=iMvSM2sriIxaC6btFriq1IOhFz6bbPcVWYAoiYFMksE=; h=DKIM-Signature:Date:From:To:Subject:Message-ID:MIME-Version; b=ddZYElvys46Xq+tg0O/6GcnpJBzvtjVDkVdNnDxXbplPYlUKC4jB01cg0MPpSzap0mqtaoivV60qS0KxC5f3BKGwU7KMgTP5dj1AZ1/wIIY7dQ+FFkDlWgaWTVy0bzF8uQ3wa8eoI03OJJnML4SMGX6796wcrsLOmkQ/gRZ3/mA= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1707254162; 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=7Zl0lLWvZDoef+3p/PJF4casI/vMFgb7S/Cwj/FIZ8k=; b=Lm5FZA/HKgpDa96gpZau1m8MgtVSIqQbt7yilfcWKlLqi1cPeyv35v9PuR5iaNRkYv/IQW m/GT3elSuAkz5hhSOGZGR5t2FftmS4WSyMs/ryuL1kk7StcersVFB85cyeJzyAG6BG0S6I Z2ZZDpjH5WJEzUwJGbOF9ORecZFAIAs= Received: from mimecast-mx02.redhat.com (mimecast-mx02.redhat.com [66.187.233.88]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-18-civs8qJpPdyr9lSi1MjciQ-1; Tue, 06 Feb 2024 16:15:58 -0500 X-MC-Unique: civs8qJpPdyr9lSi1MjciQ-1 Received: from smtp.corp.redhat.com (int-mx08.intmail.prod.int.rdu2.redhat.com [10.11.54.8]) (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 6BEF083722E; Tue, 6 Feb 2024 21:15:58 +0000 (UTC) Received: from tucnak.zalov.cz (unknown [10.39.192.70]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 25F62C1690E; Tue, 6 Feb 2024 21:15:58 +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 416LFtF61970232 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Tue, 6 Feb 2024 22:15:55 +0100 Received: (from jakub@localhost) by tucnak.zalov.cz (8.17.1/8.17.1/Submit) id 416LFrUc1970231; Tue, 6 Feb 2024 22:15:53 +0100 Date: Tue, 6 Feb 2024 22:15:53 +0100 From: Jakub Jelinek To: Richard Biener , Richard.Sandiford@arm.com Cc: gcc-patches@gcc.gnu.org Subject: [PATCH] wide-int: Fix mul_internal overflow handling [PR113753] Message-ID: MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.4.1 on 10.11.54.8 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Disposition: inline X-Spam-Status: No, score=-3.4 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, KAM_LOTSOFHASH, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H5, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham 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: 1790185785339590254 X-GMAIL-MSGID: 1790185785339590254 Hi! As the following testcases show, the overflow (needs_overflow) and high handling in wi::mul_internal seem to only work correctly for either small precisions (less than or equal to 32, that is handled by earlier simpler code, not the full Knuth's multiplication algorithm) or for precisions which are multiple of HOST_BITS_PER_WIDE_INT, so it happened to work fine in most pre-_BitInt era types (and for large bitfields we probably didn't have good coverage or were lucky and nothing was asking if there was overflow or not; I think high multiplication is typically used only when we have optab in corresponding mode). E.g. on the gcc.dg/bitint-87.c testcase, there were overflow warnings emitted only the the / 2wb * 3wb _BitInt(128) cases, but not in the other precisions. I found 3 issues when prec > HOST_BITS_PER_HALF_WIDE_INT and (prec % HOST_BITS_PER_WIDE_INT) != 0: 1) the checking for overflow was simply checking the values of the r array members from half_blocks_needed to 2 * half_blocks_needed - 1, for UNSIGNED overflow checking if any of them is non-zero, for SIGNED comparing them if any is different from top where top is computed from the sign bit of the result (see below); similarly, the highpart multiplication simply picks the half limbs at r + half_blocks_needed offset; and furthermore, for SIGNED there is an adjustment if either operand was negative which also just walks r half-limbs from half_blocks_needed onwards; this works great for precisions like 64 or 128, but for precisions like 129, 159, 160 or 161 doesn't, it would need to walk the bits in the half-limbs starting right above the most significant bit of the base precision; that can be up to a whole half-limb and all but one bit from the one below it earlier 2) as the comment says, the multiplication is originally done as unsigned multiplication, with adjustment of the high bits which subtracts the other operand once: if (wi::neg_p (op1)) { b = 0; for (i = 0; i < half_blocks_needed; i++) { t = (unsigned HOST_WIDE_INT)r[i + half_blocks_needed] - (unsigned HOST_WIDE_INT)v[i] - b; r[i + half_blocks_needed] = t & HALF_INT_MASK; b = t >> (HOST_BITS_PER_WIDE_INT - 1); } } and similarly for the other one. Now, this also only works nicely if a negative operand has just a single sign bit set in the given precision; but we were unpacking the operands with wi_unpack (..., SIGNED);, so say for the negative operand in 129-bit precision, that means the least significant bit of u[half_blocks_needed - 2] (or v instead of u depending on which argument it is) is the set sign bit, but then there are 31 further copies of the sign bit in u[half_blocks_needed - 2] and further 32 copies in u[half_blocks_needed - 1]; the above adjustment for signed operands doesn't really do the right job in such cases, it would need to subtract many more times the other operand 3) the computation of top for SIGNED top = r[(half_blocks_needed) - 1]; top = SIGN_MASK (top << (HOST_BITS_PER_WIDE_INT / 2)); top &= mask; also uses the most significant bit which fits into prec of the result only if prec is multiple of HOST_BITS_PER_WIDE_INT, otherwise we need to look at a different bit and sometimes it can be also a bit in r[half_blocks_needed - 2] For 1), while for UNSIGNED overflow it could be fairly easy to check the bits above prec in r half-limbs for being non-zero, doing all the shifts also in the SIGNED adjustment code in 2 further locations and finally for the high handling (unless we want to assert one doesn't do the highpart multiply for such precisions) would be quite ugly and hard to maintain, so I instead chose (implemented in the second hunk) to shift the beyond-precision bits up such that the expectations of the rest of the code are met, that is the LSB of r[half_blocks_needed] after adjustment is the bit immediately above the precision, etc. We don't need to care about the bits it shifts out, because the multiplication will yield at most 2 * prec bits. For 2), the patch changes the wi_unpack argument from SIGNED to UNSIGNED, so that we get all zero bits above the precision. And finally for 3) it does shifts and perhaps picks lower r half-limb so that it uses the actual MSB of the result within prec. Bootstrapped/regtested on x86_64-linux and i686-linux, and additionally tested with make check-gcc -k -j32 GCC_TEST_RUN_EXPENSIVE=1 RUNTESTFLAGS="GCC_TEST_RUN_EXPENSIVE=1 dg-torture.exp=*bitint*" Ok for trunk? 2024-02-06 Jakub Jelinek PR tree-optimization/113753 * wide-int.cc (wi::mul_internal): Unpack op1val and op2val with UNSIGNED rather than SIGNED. If high or needs_overflow and prec is not a multiple of HOST_BITS_PER_WIDE_INT, shift left bits above prec so that they start with r[half_blocks_needed] lowest bit. Fix up computation of top mask for SIGNED. * gcc.dg/torture/bitint-56.c: New test. * gcc.dg/bitint-87.c: New test. Jakub --- gcc/wide-int.cc.jj 2024-02-06 08:43:15.069885709 +0100 +++ gcc/wide-int.cc 2024-02-06 10:29:18.137373518 +0100 @@ -1483,8 +1483,8 @@ wi::mul_internal (HOST_WIDE_INT *val, co } /* We do unsigned mul and then correct it. */ - wi_unpack (u, op1val, op1len, half_blocks_needed, prec, SIGNED); - wi_unpack (v, op2val, op2len, half_blocks_needed, prec, SIGNED); + wi_unpack (u, op1val, op1len, half_blocks_needed, prec, UNSIGNED); + wi_unpack (v, op2val, op2len, half_blocks_needed, prec, UNSIGNED); /* The 2 is for a full mult. */ memset (r, 0, half_blocks_needed * 2 @@ -1503,6 +1503,28 @@ wi::mul_internal (HOST_WIDE_INT *val, co r[j + half_blocks_needed] = k; } + unsigned int shift; + if ((high || needs_overflow) && (shift = prec % HOST_BITS_PER_WIDE_INT) != 0) + { + /* The high or needs_overflow code assumes that the high bits + only appear from r[half_blocks_needed] up to + r[half_blocks_needed * 2 - 1]. If prec is not a multiple + of HOST_BITS_PER_WIDE_INT, shift the bits above prec up + to make that code simple. */ + if (shift == HOST_BITS_PER_HALF_WIDE_INT) + memmove (&r[half_blocks_needed], &r[half_blocks_needed - 1], + sizeof (r[0]) * half_blocks_needed); + else + { + unsigned int skip = shift < HOST_BITS_PER_HALF_WIDE_INT; + if (!skip) + shift -= HOST_BITS_PER_HALF_WIDE_INT; + for (i = 2 * half_blocks_needed - 1; i >= half_blocks_needed; i--) + r[i] = ((r[i - skip] << (-shift % HOST_BITS_PER_HALF_WIDE_INT)) + | (r[i - skip - 1] >> shift)); + } + } + /* We did unsigned math above. For signed we must adjust the product (assuming we need to see that). */ if (sgn == SIGNED && (high || needs_overflow)) @@ -1543,8 +1565,12 @@ wi::mul_internal (HOST_WIDE_INT *val, co top = 0; else { - top = r[(half_blocks_needed) - 1]; - top = SIGN_MASK (top << (HOST_BITS_PER_WIDE_INT / 2)); + top = r[half_blocks_needed - 1 + - ((-prec % HOST_BITS_PER_WIDE_INT) + >= HOST_BITS_PER_HALF_WIDE_INT)]; + top = SIGN_MASK (((unsigned HOST_WIDE_INT) top) + << (HOST_BITS_PER_WIDE_INT / 2 + + (-prec % HOST_BITS_PER_HALF_WIDE_INT))); top &= mask; } --- gcc/testsuite/gcc.dg/torture/bitint-56.c.jj 2024-02-06 08:53:45.584120553 +0100 +++ gcc/testsuite/gcc.dg/torture/bitint-56.c 2024-02-06 08:53:45.584120553 +0100 @@ -0,0 +1,25 @@ +/* PR tree-optimization/113753 */ +/* { dg-do run { target bitint } } */ +/* { dg-options "-std=c23 -pedantic-errors" } */ +/* { dg-skip-if "" { ! run_expensive_tests } { "*" } { "-O0" "-O2" } } */ +/* { dg-skip-if "" { ! run_expensive_tests } { "-flto" } { "" } } */ + +#if __BITINT_MAXWIDTH__ >= 129 +unsigned _BitInt(128) +foo (unsigned u, unsigned _BitInt(128) a, unsigned _BitInt(128) b) +{ + unsigned _BitInt(129) m = a % b; + return u * m / u; +} +#endif + +int +main () +{ +#if __BITINT_MAXWIDTH__ >= 129 + if (foo (0xfa637c33, 0x37af7fe8b0000000000000000wb, + 0xfffffffff0000000000000000wb) + != 0x16f7e93f6d726b38b38d0b753wb) + __builtin_abort (); +#endif +} --- gcc/testsuite/gcc.dg/bitint-87.c.jj 2024-01-13 00:05:00.077372302 +0100 +++ gcc/testsuite/gcc.dg/bitint-87.c 2024-02-06 10:41:33.403167442 +0100 @@ -0,0 +1,24 @@ +/* PR tree-optimization/113753 */ +/* { dg-do compile { target bitint575 } } */ +/* { dg-options "-std=gnu23" } */ + +_BitInt(161) a = 1461501637330902918203684832716283019655932542975wb / 2wb * 2wb; +_BitInt(160) b = 730750818665451459101842416358141509827966271487wb / 2wb * 2wb; +_BitInt(159) c = 365375409332725729550921208179070754913983135743wb / 2wb * 2wb; +_BitInt(129) d = 340282366920938463463374607431768211455wb / 2wb * 2wb; +_BitInt(128) e = 170141183460469231731687303715884105727wb / 2wb * 2wb; +_BitInt(161) f = (-1461501637330902918203684832716283019655932542975wb - 1wb) / 2wb * 2wb; +_BitInt(160) g = (-730750818665451459101842416358141509827966271487wb - 1wb) / 2wb * 2wb; +_BitInt(159) h = (-365375409332725729550921208179070754913983135743wb - 1wb) / 2wb * 2wb; +_BitInt(129) i = (-340282366920938463463374607431768211455wb - 1wb) / 2wb * 2wb; +_BitInt(128) j = (-170141183460469231731687303715884105727wb - 1wb) / 2wb * 2wb; +_BitInt(161) k = 1461501637330902918203684832716283019655932542975wb / 2wb * 3wb; /* { dg-warning "integer overflow in expression of type '_BitInt\\\(161\\\)' results in" } */ +_BitInt(160) l = 730750818665451459101842416358141509827966271487wb / 2wb * 3wb; /* { dg-warning "integer overflow in expression of type '_BitInt\\\(160\\\)' results in" } */ +_BitInt(159) m = 365375409332725729550921208179070754913983135743wb / 2wb * 3wb; /* { dg-warning "integer overflow in expression of type '_BitInt\\\(159\\\)' results in" } */ +_BitInt(129) n = 340282366920938463463374607431768211455wb / 2wb * 3wb; /* { dg-warning "integer overflow in expression of type '_BitInt\\\(129\\\)' results in" } */ +_BitInt(128) o = 170141183460469231731687303715884105727wb / 2wb * 3wb; /* { dg-warning "integer overflow in expression of type '_BitInt\\\(128\\\)' results in" } */ +_BitInt(161) p = (-1461501637330902918203684832716283019655932542975wb - 1wb) / 2wb * 3wb; /* { dg-warning "integer overflow in expression of type '_BitInt\\\(161\\\)' results in" } */ +_BitInt(160) q = (-730750818665451459101842416358141509827966271487wb - 1wb) / 2wb * 3wb; /* { dg-warning "integer overflow in expression of type '_BitInt\\\(160\\\)' results in" } */ +_BitInt(159) r = (-365375409332725729550921208179070754913983135743wb - 1wb) / 2wb * 3wb; /* { dg-warning "integer overflow in expression of type '_BitInt\\\(159\\\)' results in" } */ +_BitInt(129) s = (-340282366920938463463374607431768211455wb - 1wb) / 2wb * 3wb; /* { dg-warning "integer overflow in expression of type '_BitInt\\\(129\\\)' results in" } */ +_BitInt(128) t = (-170141183460469231731687303715884105727wb - 1wb) / 2wb * 3wb; /* { dg-warning "integer overflow in expression of type '_BitInt\\\(128\\\)' results in" } */