From patchwork Tue May 16 08:39:03 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: =?utf-8?q?Marc_Poulhi=C3=A8s?= X-Patchwork-Id: 94514 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b0ea:0:b0:3b6:4342:cba0 with SMTP id b10csp269997vqo; Tue, 16 May 2023 01:41:16 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ4ECfR1uUheID30oyvIbwZpfyk7mSWPJ6A25UR5MUycqEGx//WBzfbcsiLqV0SrAg5cCU4I X-Received: by 2002:a17:907:16a5:b0:957:2e48:5657 with SMTP id hc37-20020a17090716a500b009572e485657mr34277426ejc.68.1684226475916; Tue, 16 May 2023 01:41:15 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1684226475; cv=none; d=google.com; s=arc-20160816; b=H4vlSCfUBD7646bVObvq9eTKzg0/y67sImwRHHEmEArQG+JeezmzyKlNpc/1SruFMG hqA3IOQ04l/3HeNtTTK5dCrJMQPUDh8KQ3j6cJQnntdJR34UxbeeHaNlMEatWJQENS3I rT0pWtl1U3lsucIUhzk0ISv5iEl7c1FnxGMuvs56BWq8aK2xG/ZKOgrHU/nX3QSiis1b 7ky4R/wlrlN/qSxsRP6uLfHC/+BKwkDmeAbcyON/7lKR0Rjl7VHhVSBvA0IeXINZghDk mjp1kXD4c3jZYJ4yzkCntgg0U7bFhLiEP2O94xgbYwWI0ffyEoQ9tSlvog2F+zlblmFR xivQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:from:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence :content-transfer-encoding:mime-version:message-id:date:subject:cc :to:dmarc-filter:delivered-to:dkim-signature:dkim-filter; bh=6TxQDpfmTdXqMxQrcu+Yhy6dlmdY9/DVrf7IZsowWpQ=; b=Ve11rpji7R66G5c8O9Aru0qcj4J8t3ocrcZsGzkt+f/xfT2fzi8LsayQSbMqkwzBFE +NvmzAn/3dwpgsxO7ohk4K6e3/I00KJZZAaZ3N9aLBScvNgnFi/n8dyY350wlsXQLE4W 0gnjymwNBCtwg3kkY+emGbJ6glXXh1Rs29TXOudRvMSZt7audcq9U0toDl/sBGtOOwu5 0eXNyTGl9W28waUuvkKDbFaqYAq/MskXwi4fvYauXjDW9XJewff+ZNzxKSkIMAiZY6tW eV1AGmo/Y4sG5j9UABxMgpJm44a4Dc1LV82sUkrlWc1gym+b181a3YGz/lxoWeu3Cxru 1oIA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=F8ZZVBm5; 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=gnu.org Received: from sourceware.org (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id h24-20020a1709070b1800b009665a6d2f60si13983911ejl.910.2023.05.16.01.41.15 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 16 May 2023 01:41:15 -0700 (PDT) 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=@gcc.gnu.org header.s=default header.b=F8ZZVBm5; 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=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 30FD538555BC for ; Tue, 16 May 2023 08:40:20 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 30FD538555BC DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1684226420; bh=6TxQDpfmTdXqMxQrcu+Yhy6dlmdY9/DVrf7IZsowWpQ=; h=To:Cc:Subject:Date:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=F8ZZVBm5YAkuEyInpU4k0KjQINWWZI3n7EOQEJK9z4O2kej3fphBFS329biRgRAfN 6Ma1UcGwySK51hYPhRAfwx5dEdvzp6k8gp66hw6ScdstWFcO5q1V5kT1pIiwKJq15P 6c1bfuGXJYhvnI0ZrmzCXrJzbYUD+UGB9ih997a0= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-wm1-x332.google.com (mail-wm1-x332.google.com [IPv6:2a00:1450:4864:20::332]) by sourceware.org (Postfix) with ESMTPS id BD06C3857014 for ; Tue, 16 May 2023 08:39:23 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org BD06C3857014 Received: by mail-wm1-x332.google.com with SMTP id 5b1f17b1804b1-3f450815d02so46653655e9.0 for ; Tue, 16 May 2023 01:39:23 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684226362; x=1686818362; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=6TxQDpfmTdXqMxQrcu+Yhy6dlmdY9/DVrf7IZsowWpQ=; b=KLSdxYjxuASjuMZZ3NL8CBT8DaLp4N80snk0mW1o4G7nvwcqmyWbAX0rnf2hYs/VgD qmMUwsXnazlGunER2IbiXNPcVEi5TBNtbyHjt7WRKoRM3zxzYJIfGfJennfcHrVocZ50 YQws09d9ooEK0dPFSy/iGHFyx3ukew6qygQsjvGny0TDFp5cRHDXWd+b8VpdUwK7xoiK T4ptEzJbCU/CrIsevGBbaDLmS+QERwYkSI8KH3214ZDGgawUu5zwFI9rqvxyp5ss7VQ2 decfsn+1UR874SZvVN1lF7ritx6pgtugAAhbBYE9RNhBjHY4qKIXuQYi0T4cUCwXBQqF u/5g== X-Gm-Message-State: AC+VfDzWjXaproUG5T1h2sYg/cTrK6wsm88WYL1o98OByLj1UxKuj+3o vn+BSm599SAPFjw4IBKmTgKJNGTXC88JaFRRY8VovQ== X-Received: by 2002:a7b:c4c3:0:b0:3f1:72ec:4020 with SMTP id g3-20020a7bc4c3000000b003f172ec4020mr25337324wmk.1.1684226362348; Tue, 16 May 2023 01:39:22 -0700 (PDT) Received: from poulhies-Precision-5550.telnowedge.local (lmontsouris-659-1-24-67.w81-250.abo.wanadoo.fr. [81.250.175.67]) by smtp.gmail.com with ESMTPSA id v5-20020a5d6785000000b003047ea78b42sm1757866wru.43.2023.05.16.01.39.21 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 16 May 2023 01:39:21 -0700 (PDT) To: gcc-patches@gcc.gnu.org Cc: Yannick Moy Subject: [COMMITTED] ada: Restore proof of System.Arith_Double Date: Tue, 16 May 2023 10:39:03 +0200 Message-Id: <20230516083903.1500563-1-poulhies@adacore.com> X-Mailer: git-send-email 2.40.0 MIME-Version: 1.0 X-Spam-Status: No, score=-13.0 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_ASCII_DIVIDERS, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, 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.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: =?utf-8?q?Marc_Poulhi=C3=A8s_via_Gcc-patches?= From: =?utf-8?q?Marc_Poulhi=C3=A8s?= Reply-To: =?utf-8?q?Marc_Poulhi=C3=A8s?= Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1766039461107841712?= X-GMAIL-MSGID: =?utf-8?q?1766039461107841712?= From: Yannick Moy Use Assert_And_Cut to simplify proof of second part of the Scaled_Divide. Add intermediate assertions and simplify where necessary. gcc/ada/ * libgnat/s-aridou.adb: (Big3): Remove override made useless. (Lemma_Quot_Rem): Add new lemma and justify it, as no prover manages to prove it. (Lemma_Div_Pow2): Use new lemma Lemma_Quot_Rem. (Prove_Scaled_Mult_Decomposition_Regroup3): Retype for simplification. (Scaled_Divide): Remove useless assertions.Decompose some assertions with cut operations. Use Assert_And_Cut for second half. Add assertions. Tested on x86_64-pc-linux-gnu, committed on master. --- gcc/ada/libgnat/s-aridou.adb | 150 +++++++++++++++++++++++++++-------- 1 file changed, 119 insertions(+), 31 deletions(-) diff --git a/gcc/ada/libgnat/s-aridou.adb b/gcc/ada/libgnat/s-aridou.adb index 67ebdd44a0c..15f87646563 100644 --- a/gcc/ada/libgnat/s-aridou.adb +++ b/gcc/ada/libgnat/s-aridou.adb @@ -45,7 +45,8 @@ is Contract_Cases => Ignore, Ghost => Ignore, Loop_Invariant => Ignore, - Assert => Ignore); + Assert => Ignore, + Assert_And_Cut => Ignore); pragma Suppress (Overflow_Check); pragma Suppress (Range_Check); @@ -141,13 +142,6 @@ is with Ghost; -- X1&X2&X3 as a big integer - function Big3 (X1, X2, X3 : Big_Integer) return Big_Integer is - (Big_2xxSingle * Big_2xxSingle * X1 - + Big_2xxSingle * X2 - + X3) - with Ghost; - -- Version of Big3 on big integers - function Le3 (X1, X2, X3, Y1, Y2, Y3 : Single_Uns) return Boolean with Post => Le3'Result = (Big3 (X1, X2, X3) <= Big3 (Y1, Y2, Y3)); @@ -1543,15 +1537,36 @@ is Post => X / Double_Uns'(2) ** I / Double_Uns'(2) = X / Double_Uns'(2) ** (I + 1); + procedure Lemma_Quot_Rem (X, Div, Q, R : Double_Uns) + with + Ghost, + Pre => Div /= 0 + and then X = Q * Div + R + and then Q <= Double_Uns'Last / Div + and then R <= Double_Uns'Last - Q * Div + and then R < Div, + Post => Q = X / Div; + pragma Annotate (GNATprove, False_Positive, "postcondition might fail", + "Q is the quotient of X by Div"); + procedure Lemma_Div_Pow2 (X : Double_Uns; I : Natural) is Div1 : constant Double_Uns := Double_Uns'(2) ** I; Div2 : constant Double_Uns := Double_Uns'(2); Left : constant Double_Uns := X / Div1 / Div2; + R2 : constant Double_Uns := X / Div1 - Left * Div2; + pragma Assert (R2 < Div2); + R1 : constant Double_Uns := X - X / Div1 * Div1; + pragma Assert (R1 < Div1); begin + pragma Assert (X = Left * (Div1 * Div2) + R2 * Div1 + R1); + pragma Assert (R2 * Div1 + R1 < Div1 * Div2); + Lemma_Quot_Rem (X, Div1 * Div2, Left, R2 * Div1 + R1); pragma Assert (Left = X / (Div1 * Div2)); pragma Assert (Div1 * Div2 = Double_Uns'(2) ** (I + 1)); end Lemma_Div_Pow2; + procedure Lemma_Quot_Rem (X, Div, Q, R : Double_Uns) is null; + XX : Double_Uns := X; begin @@ -2115,12 +2130,15 @@ is -- fourth component. procedure Prove_Scaled_Mult_Decomposition_Regroup3 - (D1, D2, D3, D4 : Big_Integer) + (D1, D2, D3, D4 : Single_Uns) with Ghost, Pre => Scale < Double_Size - and then Is_Scaled_Mult_Decomposition (D1, D2, D3, D4), - Post => Is_Scaled_Mult_Decomposition (0, 0, Big3 (D1, D2, D3), D4); + and then Is_Scaled_Mult_Decomposition + (Big (Double_Uns (D1)), Big (Double_Uns (D2)), + Big (Double_Uns (D3)), Big (Double_Uns (D4))), + Post => Is_Scaled_Mult_Decomposition (0, 0, Big3 (D1, D2, D3), + Big (Double_Uns (D4))); -- Proves scaled decomposition of Mult after regrouping on third -- component. @@ -2492,7 +2510,7 @@ is ---------------------------------------------- procedure Prove_Scaled_Mult_Decomposition_Regroup3 - (D1, D2, D3, D4 : Big_Integer) + (D1, D2, D3, D4 : Single_Uns) is null; ------------------ @@ -2825,9 +2843,6 @@ is Big_2xxSingle * Big (T2) = Big_2xxSingle * (Big (Double_Uns (Lo (T1))) + Big (Double_Uns (D (3)))))); - Lemma_Mult_Distribution (Big_2xxSingle, - Big (Double_Uns (D (3))), - Big (Double_Uns (Lo (T1)))); Lemma_Hi_Lo (T2, Hi (T2), Lo (T2)); D (3) := Lo (T2); @@ -2840,11 +2855,20 @@ is (Big (Double_Uns (Hi (T1))) + Big (Double_Uns (Hi (T2))) = Big (Double_Uns (D (2)))); pragma Assert - (Is_Mult_Decomposition + (By (Is_Mult_Decomposition (D1 => 0, D2 => Big (Double_Uns (D (2))), D3 => Big (Double_Uns (D (3))), - D4 => Big (Double_Uns (D (4))))); + D4 => Big (Double_Uns (D (4)))), + Big_2xxSingle * Big_2xxSingle * Big (Double_Uns (D (2))) = + Big_2xxSingle * Big_2xxSingle * Big (Double_Uns (Hi (T1))) + + Big_2xxSingle * Big_2xxSingle * Big (Double_Uns (Hi (T2))) + and then + Big_2xxSingle * Big (T2) = + Big_2xxSingle * Big_2xxSingle * Big (Double_Uns (Hi (T2))) + + Big_2xxSingle * Big (Double_Uns (Lo (T2))) + and then + Big (Double_Uns (Lo (T2))) = Big (Double_Uns (D (3))))); else D (2) := 0; @@ -2861,10 +2885,32 @@ is D (1) := 0; end if; - pragma Assert (Is_Mult_Decomposition (D1 => Big (Double_Uns (D (1))), - D2 => Big (Double_Uns (D (2))), - D3 => Big (Double_Uns (D (3))), - D4 => Big (Double_Uns (D (4))))); + pragma Assert_And_Cut + -- Restate the precondition + (Z /= 0 + and then In_Double_Int_Range + (if Round then Round_Quotient (Big (X) * Big (Y), Big (Z), + Big (X) * Big (Y) / Big (Z), + Big (X) * Big (Y) rem Big (Z)) + else Big (X) * Big (Y) / Big (Z)) + -- Restate the value of local variables + and then Zu = abs Z + and then Zhi = Hi (Zu) + and then Zlo = Lo (Zu) + and then Mult = abs (Big (X) * Big (Y)) + and then Quot = Big (X) * Big (Y) / Big (Z) + and then Big_R = Big (X) * Big (Y) rem Big (Z) + and then + (if Round then + Big_Q = Round_Quotient (Big (X) * Big (Y), Big (Z), Quot, Big_R) + else + Big_Q = Quot) + -- Summarize first part of the procedure + and then D'Initialized + and then Is_Mult_Decomposition (D1 => Big (Double_Uns (D (1))), + D2 => Big (Double_Uns (D (2))), + D3 => Big (Double_Uns (D (3))), + D4 => Big (Double_Uns (D (4))))); -- Now it is time for the dreaded multiple precision division. First an -- easy case, check for the simple case of a one digit divisor. @@ -2873,8 +2919,13 @@ is if D (1) /= 0 or else D (2) >= Zlo then if D (1) > 0 then pragma Assert - (Mult >= Big_2xxSingle * Big_2xxSingle * Big_2xxSingle - * Big (Double_Uns (D (1)))); + (By (Mult >= Big_2xxSingle * Big_2xxSingle * Big_2xxSingle + * Big (Double_Uns (D (1))), + Big_2xxSingle * Big_2xxSingle * Big (Double_Uns (D (2))) >= 0 + and then + Big_2xxSingle * Big (Double_Uns (D (3))) >= 0 + and then + Big (Double_Uns (D (4))) >= 0)); Lemma_Double_Big_2xxSingle; Lemma_Mult_Positive (Big_2xxDouble, Big_2xxSingle); Lemma_Ge_Mult (Big (Double_Uns (D (1))), @@ -2915,6 +2966,14 @@ is elsif (D (1) & D (2)) >= Zu then Lemma_Hi_Lo (D (1) & D (2), D (1), D (2)); Lemma_Ge_Commutation (D (1) & D (2), Zu); + pragma Assert + (By (Mult >= Big_2xxSingle * Big_2xxSingle * Big (D (1) & D (2)), + By (Mult >= Big_2xxSingle * Big_2xxSingle * Big_2xxSingle + * Big (Double_Uns (D (1))) + + Big_2xxSingle * Big_2xxSingle * Big (Double_Uns (D (2))), + Big_2xxSingle * Big (Double_Uns (D (3))) >= 0 + and then + Big (Double_Uns (D (4))) >= 0))); Prove_Overflow; Raise_Error; @@ -2928,8 +2987,19 @@ is -- First normalize the divisor so that it has the leading bit on. -- We do this by finding the appropriate left shift amount. + Lemma_Hi_Lo (D (1) & D (2), D (1), D (2)); Lemma_Lt_Commutation (D (1) & D (2), Zu); - pragma Assert (Mult < Big_2xxDouble * Big (Zu)); + pragma Assert + (By (Mult < Big_2xxDouble * Big (Zu), + By (Mult < Big_2xxSingle * Big_2xxSingle * (Big (Zu) - 1) + + Big_2xxSingle * Big_2xxSingle, + Big_2xxSingle * Big_2xxSingle * Big_2xxSingle + * Big (Double_Uns (D (1))) + + Big_2xxSingle * Big_2xxSingle * Big (Double_Uns (D (2))) + <= Big_2xxSingle * Big_2xxSingle * (Big (Zu) - 1) + and then + Big_2xxSingle * Big (Double_Uns (D (3))) + Big (Double_Uns (D (4))) + < Big_2xxSingle * Big_2xxSingle))); Shift := Single_Size; Mask := Single_Uns'Last; @@ -3127,7 +3197,14 @@ is Big (D (1) & D (2)), Big_2xxSingle * Big (Double_Uns (D (3))) + Big (Double_Uns (D (4)))); - pragma Assert (Big (D (1) & D (2)) < Big (Zu)); + pragma Assert + (By (Big (D (1) & D (2)) < Big (Zu), + By (Big (D (1) & D (2)) * Big_2xxDouble < Big (Zu) * Big_2xxDouble, + By (Big_2xxSingle * Big (Double_Uns (D (3))) + + Big (Double_Uns (D (4))) >= 0, + By (Big_2xxSingle * Big (Double_Uns (D (3))) >= 0, + Big (Double_Uns (D (3))) >= 0 and then Big_2xxSingle >= 0) + and then Big (Double_Uns (D (4))) >= 0)))); -- Loop to compute quotient digits, runs twice for Qd (1) and Qd (2) @@ -3142,6 +3219,11 @@ is Big_2xxSingle * Big3 (X1, X2, X3) + Big (Double_Uns (X4)) = Big3 (X2, X3, X4); + procedure Prove_Mult_Big_2xxSingle_Twice (X : Big_Integer) + with + Ghost, + Post => Big_2xxSingle * Big_2xxSingle * X = Big_2xxDouble * X; + --------------------------- -- Prove_First_Iteration -- --------------------------- @@ -3149,6 +3231,8 @@ is procedure Prove_First_Iteration (X1, X2, X3, X4 : Single_Uns) is null; + procedure Prove_Mult_Big_2xxSingle_Twice (X : Big_Integer) is null; + -- Local ghost variables Qd1 : Single_Uns := 0 with Ghost; @@ -3160,11 +3244,10 @@ is begin Prove_Scaled_Mult_Decomposition_Regroup3 - (Big (Double_Uns (D (1))), - Big (Double_Uns (D (2))), - Big (Double_Uns (D (3))), - Big (Double_Uns (D (4)))); - pragma Assert (Mult * Big_2xx (Scale) = Big_2xxSingle * D123 + D4); + (D (1), D (2), D (3), D (4)); + pragma Assert + (By (Mult * Big_2xx (Scale) = Big_2xxSingle * D123 + D4, + Is_Scaled_Mult_Decomposition (0, 0, D123, D4))); for J in 1 .. 2 loop Lemma_Hi_Lo (D (J) & D (J + 1), D (J), D (J + 1)); @@ -3343,8 +3426,13 @@ is Big (Double_Uns'(1)) * Big_2xxDouble); pragma Assert (Big_2xxDouble * Big (Double_Uns'(1)) = Big_2xxDouble); + Prove_Mult_Big_2xxSingle_Twice (Big (Double_Uns (D (J)))); pragma Assert - (Big3 (D (J), D (J + 1), D (J + 2)) >= Big_2xxDouble); + (By (Big3 (D (J), D (J + 1), D (J + 2)) >= Big_2xxDouble, + By (Big (Double_Uns (D (J))) * + (Big_2xxSingle * Big_2xxSingle) >= Big_2xxDouble, + Big (Double_Uns (D (J))) * Big_2xxDouble + >= Big_2xxDouble))); pragma Assert (False); end if;