From patchwork Thu Aug 3 12:09:06 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: 1816422 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=dWLKxFsL; dkim-atps=neutral Received: from server2.sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4RGnjq47Chz1yZl for ; Thu, 3 Aug 2023 22:10:39 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 9192D385701B for ; Thu, 3 Aug 2023 12:10:37 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 9192D385701B DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1691064637; bh=Ga6o82L6rB3IZLRLF7wOeglxa2VFHorf9ELZ3lzRPi0=; h=To:Cc:Subject:Date:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=dWLKxFsL9IFAxADBKiIF5jdVJ+rPxFJMMsfdtpe9VkOv8sfi9nC+joGkkhu+Uu3+U oJy6Kf+H5wJic41jYSpIaf+a0Kzxy7onVr50cXNttFgNoV0E4Bf43QVWmwhiH1d8O4 ItqcWwcn4oHZmsSkIoyJUF5v8bjbTHhh9xxbVC9w= 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 C0FC23857016 for ; Thu, 3 Aug 2023 12:09:08 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org C0FC23857016 Received: by mail-wm1-x332.google.com with SMTP id 5b1f17b1804b1-3fbd33a57b6so9170605e9.2 for ; Thu, 03 Aug 2023 05:09:08 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1691064547; x=1691669347; 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=Ga6o82L6rB3IZLRLF7wOeglxa2VFHorf9ELZ3lzRPi0=; b=FCuFHmca9dZVOCUPTOY2YmVOv+4w14YT7XHn3mjWdvJetsM7mNuWp1qy8OL/t14uAK zBNFrb9/oc9LgVo0BLAnlQibOSBjmOhclJPjt7wJM8tTeHoCU83J6RiSzAcLAThr2S7w nY8LKIPkC2ENsbbV5h5ppzKG8JtvWA4zrszks2t+k3M3LG3JdG5V7kGCncbSz32IdB0Y tdFD2W78LwomiZQadp9GGdQiV5qwpi0Jbk8vkMTM1kxpHohFYSMOES0WxeSwNZ0Qacyi tSCZ6YjXNRsdOxujx0aWFK3HBwpMTOAKqrw3Cehu0l0BFMFCd0Yg/rqzaTOf8fTL9BhR HnRQ== X-Gm-Message-State: ABy/qLYs+bHGKN5gNSao4+yd661vebTJ1/4enhLhMVDBcn/V2GvQXTHF jlcTrXB1k+XhdAgtCwsTQWaD1X7NhW1BzMXtngqzDA== X-Google-Smtp-Source: APBJJlFQNiktlXL1CPIzT1DcmXNmSQN1Z2Y+i7jZnYTQyE5KPUj0XIcjb0rtCmx5F6wDcSxNbzOVRw== X-Received: by 2002:a7b:ce86:0:b0:3fe:ba7:f1ed with SMTP id q6-20020a7bce86000000b003fe0ba7f1edmr7589796wmj.25.1691064547208; Thu, 03 Aug 2023 05:09:07 -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 n2-20020a05600c294200b003fd2d33ea53sm4180583wmd.14.2023.08.03.05.09.06 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 03 Aug 2023 05:09:06 -0700 (PDT) To: gcc-patches@gcc.gnu.org Cc: Vasiliy Fofanov Subject: [COMMITTED] ada: Rewrite Set_Image_*_Unsigned routines to remove recursion. Date: Thu, 3 Aug 2023 14:09:06 +0200 Message-Id: <20230803120906.2526729-1-poulhies@adacore.com> X-Mailer: git-send-email 2.40.0 MIME-Version: 1.0 X-Spam-Status: No, score=-13.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, 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+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" From: Vasiliy Fofanov This rewriting removes algorithm inefficiencies due to unnecessary recursion and copying. The new version has much smaller and statically known stack requirements and is additionally up to 2x faster. gcc/ada/ * libgnat/s-imageb.adb (Set_Image_Based_Unsigned): Rewritten. * libgnat/s-imagew.adb (Set_Image_Width_Unsigned): Likewise. Tested on x86_64-pc-linux-gnu, committed on master. --- gcc/ada/libgnat/s-imageb.adb | 71 ++++++++++++------------------ gcc/ada/libgnat/s-imagew.adb | 84 ++++++++++++------------------------ 2 files changed, 55 insertions(+), 100 deletions(-) diff --git a/gcc/ada/libgnat/s-imageb.adb b/gcc/ada/libgnat/s-imageb.adb index 6aa311a13e5..037f15b58c7 100644 --- a/gcc/ada/libgnat/s-imageb.adb +++ b/gcc/ada/libgnat/s-imageb.adb @@ -88,68 +88,53 @@ package body System.Image_B is S : out String; P : in out Natural) is - Start : constant Natural := P; - F, T : Natural; + Start : constant Natural := P + 1; BU : constant Uns := Uns (B); Hex : constant array (Uns range 0 .. 15) of Character := "0123456789ABCDEF"; - procedure Set_Digits (T : Uns); - -- Set digits of absolute value of T + Nb_Digits : Natural := 1; + T : Uns := V; - ---------------- - -- Set_Digits -- - ---------------- + begin - procedure Set_Digits (T : Uns) is - begin - if T >= BU then - Set_Digits (T / BU); - P := P + 1; - S (P) := Hex (T mod BU); - else - P := P + 1; - S (P) := Hex (T); - end if; - end Set_Digits; + -- First we compute the number of characters needed for representing + -- the number. + loop + T := T / BU; + exit when T = 0; + Nb_Digits := Nb_Digits + 1; + end loop; - -- Start of processing for Set_Image_Based_Unsigned + P := Start; - begin + -- Pad S with spaces up to W reduced by Nb_Digits plus extra 3-4 + -- characters needed for displaying the base. + while P < Start + W - Nb_Digits - 3 - B / 10 loop + S (P) := ' '; + P := P + 1; + end loop; if B >= 10 then - P := P + 1; S (P) := '1'; + P := P + 1; end if; + S (P) := Hex (BU mod 10); P := P + 1; - S (P) := Character'Val (Character'Pos ('0') + B mod 10); - P := P + 1; S (P) := '#'; - - Set_Digits (V); - P := P + 1; - S (P) := '#'; - - -- Add leading spaces if required by width parameter - - if P - Start < W then - F := P; - P := Start + W; - T := P; - while F > Start loop - S (T) := S (F); - T := T - 1; - F := F - 1; - end loop; + -- We now populate digits from the end of the value to the beginning + T := V; + for J in reverse P .. P + Nb_Digits - 1 loop + S (J) := Hex (T mod BU); + T := T / BU; + end loop; - for J in Start + 1 .. T loop - S (J) := ' '; - end loop; - end if; + P := P + Nb_Digits; + S (P) := '#'; end Set_Image_Based_Unsigned; diff --git a/gcc/ada/libgnat/s-imagew.adb b/gcc/ada/libgnat/s-imagew.adb index 00b63eb87d6..28ba37ced1e 100644 --- a/gcc/ada/libgnat/s-imagew.adb +++ b/gcc/ada/libgnat/s-imagew.adb @@ -86,66 +86,36 @@ package body System.Image_W is S : out String; P : in out Natural) is - Start : constant Natural := P; - F, T : Natural; - - procedure Set_Digits (T : Uns); - -- Set digits of absolute value of T - - ---------------- - -- Set_Digits -- - ---------------- - - procedure Set_Digits (T : Uns) is - begin - if T >= 10 then - Set_Digits (T / 10); - pragma Assert (P >= (S'First - 1) and P < S'Last and - P < Natural'Last); - -- No check is done since, as documented in the specification, - -- the caller guarantees that S is long enough to hold the result. - P := P + 1; - S (P) := Character'Val (T mod 10 + Character'Pos ('0')); - - else - pragma Assert (P >= (S'First - 1) and P < S'Last and - P < Natural'Last); - -- No check is done since, as documented in the specification, - -- the caller guarantees that S is long enough to hold the result. - P := P + 1; - S (P) := Character'Val (T + Character'Pos ('0')); - end if; - end Set_Digits; - - -- Start of processing for Set_Image_Width_Unsigned + Start : constant Natural := P + 1; + Nb_Digits : Natural := 1; + T : Uns := V; begin - Set_Digits (V); - - -- Add leading spaces if required by width parameter - - if P - Start < W then - F := P; - P := P + (W - (P - Start)); - T := P; - - while F > Start loop - pragma Assert (T >= S'First and T <= S'Last and - F >= S'First and F <= S'Last); - -- No check is done since, as documented in the specification, - -- the caller guarantees that S is long enough to hold the result. - S (T) := S (F); - T := T - 1; - F := F - 1; - end loop; - for J in Start + 1 .. T loop - pragma Assert (J >= S'First and J <= S'Last); - -- No check is done since, as documented in the specification, - -- the caller guarantees that S is long enough to hold the result. - S (J) := ' '; - end loop; - end if; + -- First we compute the number of characters needed for representing + -- the number. + loop + T := T / 10; + exit when T = 0; + Nb_Digits := Nb_Digits + 1; + end loop; + + P := Start; + + -- Pad S with spaces up to W reduced by Nb_Digits + while P < Start + W - Nb_Digits loop + S (P) := ' '; + P := P + 1; + end loop; + + -- We now populate digits from the end of the value to the beginning + T := V; + for J in reverse P .. P + Nb_Digits - 1 loop + S (J) := Character'Val (T mod 10 + Character'Pos ('0')); + T := T / 10; + end loop; + + P := P + Nb_Digits - 1; end Set_Image_Width_Unsigned;