From patchwork Wed Jan 31 14:21:19 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Jelinek X-Patchwork-Id: 194778 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7301:2087:b0:106:209c:c626 with SMTP id gs7csp1921528dyb; Wed, 31 Jan 2024 06:22:16 -0800 (PST) X-Google-Smtp-Source: AGHT+IFYmUh1qPZgnMyMIiArGf631+iQfnwpXftPaPXDJt8YT6hj2WgW3wi5Yk57vTEsOG3HGk66 X-Received: by 2002:a05:620a:1a1c:b0:784:8c4:dbfd with SMTP id bk28-20020a05620a1a1c00b0078408c4dbfdmr1917829qkb.30.1706710935861; Wed, 31 Jan 2024 06:22:15 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1706710935; cv=pass; d=google.com; s=arc-20160816; b=bAtaRLGd5zGLgY5+2khFGziLrV10yt5/n+ojxoPpHZqHoOUbg+7dD02ygW5mE56e6I oNCutADZpC4Jm8OJc2CeypCNMTs4R6bes+0FzvFvb0/z35HFOGvOphCg3AK6WExURk/f JX4PtZqyXswAPFrAqbFbG11p1Sqji+7FZlERa8B9yANo3s3rx1AQXcEvc+WBm4XGpcfK 2MnQvDhNUzmpZI+2sQkRoQkBIENV3IkfRTUEMfyZFqDZOp50uD5Euk6X/Z79S3nr/enq HRqj6rfXhIc0gbk6PaAGEfeU03R5hbiHcFLiNG/tzhqbSv+/p1yK9Oq4i/km3l7pHHdh EDoA== 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:in-reply-to :mime-version:references:message-id:subject:cc:to:from:date :dkim-signature:arc-filter:dmarc-filter:delivered-to; bh=eNA9gwr+QAhk4ohAo1jXl9DJ/GbKQhiRkZquAuNWCuk=; fh=0SuXljzmx67yKNYRXvC9TEC5cSDpf5g+kN2S3N7VKZM=; b=dRIQFMcy/NTF2SI1ZHlkk1Nwt79+VnXkkEhtuwY3P9xHCQNKDr5EyX1PU05HfIY6+8 pds6fYWIrfRaHNdLFpp6aSEwzN/855BMFsnDWapNMoTea7daEDqP1c5Ptg+CUBfunuMn ziLANaGQ03xlzOHfYd13BLC21Zmn/CZsahWbhipESd/cxvvAcZBzeAsjuo7shuiLQngr otfdh5gXwm7rwINZY1M/7K9MI8AUyW3V0x2BfOrqD7gJu4SaSLaon0LcEXlXRdxfC59K Il67jli3vJnkRbxcEqvuPmi8emFSf2lIpJ5rTh9UKl/14/iOB1j2Jwy2kiolq8mLoeaL swJg==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@redhat.com header.s=mimecast20190719 header.b=bpiYM3c3; arc=pass (i=1); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c 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; AJvYcCV8N5/rdsKOzYLm0HPgyLBydGBO+9o+L9UJpAUb8ImAcWGp6UfbYF+KMNDz7J6Wp8YkveuQ5BJiAPDs930YcjijeZPyPQ== Received: from server2.sourceware.org (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id a12-20020a05620a16cc00b00784853150efsi3118276qkn.84.2024.01.31.06.22.15 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 31 Jan 2024 06:22:15 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=pass header.i=@redhat.com header.s=mimecast20190719 header.b=bpiYM3c3; arc=pass (i=1); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c 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 84F5C3858013 for ; Wed, 31 Jan 2024 14:22:15 +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 64C243858D20 for ; Wed, 31 Jan 2024 14:21:25 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 64C243858D20 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 64C243858D20 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=1706710888; cv=none; b=iYXkfYnRxqzk/xUjQKUBNGF8MuwiYOkoLK5P1qXvF+6ve3aDIlAGQtuxfztVylSLM9GYX9MT/1cpkCV2stIkPxJ/6jdncxu6cLSZ91/jKKpaftka+eLvLVd9SKvcVpB0nc/qo8492x+Wb4iFsVPYVjibhXQYEVpmWNUOJyTAvm4= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1706710888; c=relaxed/simple; bh=tCSAW6+M31NpatC+KFLBnpXLunA2/8vgapttidUUJbE=; h=DKIM-Signature:Date:From:To:Subject:Message-ID:MIME-Version; b=Ir97zPh8+nOoi2U4veC22Q06Gs8iNeXumk+g/WyPyc/Bz3M7yvdn+FCdEvjXiUKOhT0gItv5Qz2X8REZ2eqtoQyBDOeaenuBkXr1P7n2BSdM6dU8x0pwlufTagMNnP4urT8aCoKJU86RZOHZ6Mt9QtqwBS644+TXlaBTDBXBXZw= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1706710885; 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:in-reply-to:in-reply-to: references:references; bh=eNA9gwr+QAhk4ohAo1jXl9DJ/GbKQhiRkZquAuNWCuk=; b=bpiYM3c3EtPG2ejUpWBq1mlzKnhwX85gEuQ4+LnkE16bgWE6qBQlGCHBTpayVHli+COLOC gB7ij3NMdT+MZnxTksFXN/uYgDkF9P79ZRizPQoOxnC0VSR9gA7B3kgElIuVj+Jh2jvK0y iVIywTy/7tDhsvj4KgSD7Qn7khPWaZo= 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-212-ySVh9QG_MdyiO6gxKjEu8Q-1; Wed, 31 Jan 2024 09:21:23 -0500 X-MC-Unique: ySVh9QG_MdyiO6gxKjEu8Q-1 Received: from smtp.corp.redhat.com (int-mx01.intmail.prod.int.rdu2.redhat.com [10.11.54.1]) (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 0D71D84AEEC for ; Wed, 31 Jan 2024 14:21:23 +0000 (UTC) Received: from tucnak.zalov.cz (unknown [10.39.192.70]) by smtp.corp.redhat.com (Postfix) with ESMTPS id C571D3C2E; Wed, 31 Jan 2024 14:21:22 +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 40VELKIl288247 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Wed, 31 Jan 2024 15:21:20 +0100 Received: (from jakub@localhost) by tucnak.zalov.cz (8.17.1/8.17.1/Submit) id 40VELJff288246; Wed, 31 Jan 2024 15:21:19 +0100 Date: Wed, 31 Jan 2024 15:21:19 +0100 From: Jakub Jelinek To: "Joseph S. Myers" Cc: gcc-patches@gcc.gnu.org Subject: [PATCH] libgcc, v2: Fix up _BitInt division [PR113604] Message-ID: References: MIME-Version: 1.0 In-Reply-To: X-Scanned-By: MIMEDefang 3.4.1 on 10.11.54.1 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Disposition: inline X-Spam-Status: No, score=-3.9 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: 1789616126474803413 X-GMAIL-MSGID: 1789616126474803413 Hi! On Sat, Jan 27, 2024 at 08:53:42AM +0100, Jakub Jelinek wrote: > The following testcase ends up with SIGFPE in __divmodbitint4. > The problem is a thinko in my attempt to implement Knuth's algorithm. Here is an updated version of the patch, the libgcc part is the same, but I've added a new testcase which tests the behavior of all the changed cases, so it has a case where uv1:uv0 / vv1 is 1:1, where it is 1:0 and rhat + vv1 overflows and where it is 1:0 and rhat + vv1 does not overflow, and includes tests also from Zdenek's other failing tests. Previously successfully bootstrapped/regtested on x86_64-linux and i686-linux, the new version has been retested with make check-gcc GCC_TEST_RUN_EXPENSIVE=1 RUNTESTFLAGS="GCC_TEST_RUN_EXPENSIVE=1 dg-torture.exp='bitint-53.c bitint-55.c'" Ok for trunk? 2024-01-31 Jakub Jelinek PR libgcc/113604 * libgcc2.c (__divmodbitint4): If uv1 >= vv1, subtract vv1 from uv1:uv0 once or twice as needed, rather than subtracting vv1:vv1. * gcc.dg/torture/bitint-53.c: New test. * gcc.dg/torture/bitint-55.c: New test. Jakub --- libgcc/libgcc2.c.jj 2024-01-12 10:10:16.000000000 +0100 +++ libgcc/libgcc2.c 2024-01-26 10:27:10.932017695 +0100 @@ -1863,12 +1863,46 @@ __divmodbitint4 (UBILtype *q, SItype qpr if (uv1 >= vv1) { /* udiv_qrnnd doesn't support quotients which don't - fit into UWtype, so subtract from uv1:uv0 vv1 - first. */ - uv1 -= vv1 + __builtin_sub_overflow (uv0, vv1, &uv0); - udiv_qrnnd (qhat, rhat, uv1, uv0, vv1); - if (!__builtin_add_overflow (rhat, vv1, &rhat)) - goto again; + fit into UWtype, while Knuth's algorithm originally + uses a double-word by word to double-word division. + Fortunately, the algorithm guarantees that uv1 <= vv1, + because if uv1 > vv1, then even if v would have all + bits in all words below vv1 set, the previous iteration + would be supposed to use qhat larger by 1 and subtract + v. With uv1 == vv1 and uv0 >= vv1 the double-word + qhat in Knuth's algorithm would be 1 in the upper word + and 1 in the lower word, say for + uv1 0x8000000000000000ULL + uv0 0xffffffffffffffffULL + vv1 0x8000000000000000ULL + 0x8000000000000000ffffffffffffffffuwb + / 0x8000000000000000uwb == 0x10000000000000001uwb, and + exactly like that also for any other value + > 0x8000000000000000ULL in uv1 and vv1 and uv0 >= uv1. + So we need to subtract one or at most two vv1s from + uv1:uv0 (qhat because of that decreases by 1 or 2 and + is then representable in UWtype) and need to increase + rhat by vv1 once or twice because of that. Now, if + we need to subtract 2 vv1s, i.e. if + uv1 == vv1 && uv0 >= vv1, then rhat (which is uv0 - vv1) + + vv1 computation can't overflow, because it is equal + to uv0 and therefore the original algorithm in that case + performs goto again, but the second vv1 addition must + overflow already because vv1 has msb set from the + canonicalization. */ + uv1 -= __builtin_sub_overflow (uv0, vv1, &uv0); + if (uv1 >= vv1) + { + uv1 -= __builtin_sub_overflow (uv0, vv1, &uv0); + udiv_qrnnd (qhat, rhat, uv1, uv0, vv1); + rhat += 2 * vv1; + } + else + { + udiv_qrnnd (qhat, rhat, uv1, uv0, vv1); + if (!__builtin_add_overflow (rhat, vv1, &rhat)) + goto again; + } } else { --- gcc/testsuite/gcc.dg/torture/bitint-53.c.jj 2024-01-26 07:23:31.651790252 +0100 +++ gcc/testsuite/gcc.dg/torture/bitint-53.c 2024-01-26 07:23:20.608945843 +0100 @@ -0,0 +1,26 @@ +/* PR libgcc/113604 */ +/* { 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__ >= 256 +unsigned _BitInt (256) x; + +void +foo (unsigned _BitInt (256) a, unsigned _BitInt (128) b) +{ + x = a / b; +} +#endif + +int +main () +{ +#if __BITINT_MAXWIDTH__ >= 256 + foo (0xfffffffffffffffffffffc0000000000000000000004uwb, 0x7ffffffffffffffffffffffffffuwb); + if (x != 0x1fffffffffffffffffuwb) + __builtin_abort (); +#endif + return 0; +} --- gcc/testsuite/gcc.dg/torture/bitint-55.c.jj 2024-01-31 12:32:54.554483584 +0100 +++ gcc/testsuite/gcc.dg/torture/bitint-55.c 2024-01-31 15:13:18.411851415 +0100 @@ -0,0 +1,66 @@ +/* PR libgcc/113604 */ +/* { 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__ >= 513 +signed _BitInt(513) +foo (signed _BitInt(513) x, signed _BitInt(513) y) +{ + return x % y; +} +#endif + +#if __BITINT_MAXWIDTH__ >= 512 +unsigned _BitInt(512) +bar (unsigned _BitInt(512) x, unsigned _BitInt(512) y) +{ + return x % y; +} +#endif + +#if __BITINT_MAXWIDTH__ >= 256 +unsigned _BitInt(256) +baz (unsigned _BitInt(256) x, unsigned _BitInt(256) y) +{ + return x % y; +} +#endif + +int +main () +{ +#if __BITINT_MAXWIDTH__ >= 513 + if (foo (11155754932722990178552651944728825929130437979239421228991532051555943675wb, + 32783817256434357484609367438786815wb) != 0wb) + __builtin_abort (); + if (foo (542904728531209767665756029992981529373473101602268731408384wb, + 235447394450476261134537147263765988105wb) + != 235447394450476261116090403190056436489wb) + __builtin_abort (); + if (foo (542904728531209767665690117878483036079552477922114364506112wb, + 235447394450476261134537147263765988105wb) + != 169535279951982967195466723035689534217wb) + __builtin_abort (); + if (foo (542904728531209767665690117878483036079534031178040654954496wb, + 235447394450476261134537147263765988105wb) + != 169535279951982967177019978961979982601wb) + __builtin_abort (); + if (foo (542904728531209767665454670484032559818581851459155356811264wb, + 235447394450476261134537147263765988105wb) + != 169535279951982967359377407340447827474wb) + __builtin_abort (); +#endif +#if __BITINT_MAXWIDTH__ >= 512 + if (bar (6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503042048uwb, + 170141183460469231731687303715884105735uwb) != 19208uwb) + __builtin_abort (); +#endif +#if __BITINT_MAXWIDTH__ >= 256 + if (baz (115792089237316195423570985008687907853269984665640564039457584007913129639926uwb, + 68056473384187692692674921486353642292uwb) != 6uwb) + __builtin_abort (); +#endif + return 0; +}