[gcc r14-4681] wide-int-print: Don't print large numbers hexadecimally for print_dec{, s, u}

[gcc r14-4681] wide-int-print: Don't print large numbers hexadecimally for print_dec{, s, u}

[Jakub Jelinek]

https://gcc.gnu.org/g:fbdf88a1f6de2399101ecea948ff1abbf82459fc

commit r14-4681-gfbdf88a1f6de2399101ecea948ff1abbf82459fc
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Tue Oct 17 14:25:00 2023 +0200

    wide-int-print: Don't print large numbers hexadecimally for print_dec{,s,u}
    
    The following patch implements printing of wide_int/widest_int numbers
    decimally when asked for that using print_dec{,s,u}, even if they have
    precision larger than 64 and get_len () above 1 (right now we printed
    them hexadecimally and even negative numbers as huge positive hexadecimal).
    
    In order to avoid the expensive division/modulo by 10^19 twice, once to
    estimate how many will be needed and another to actually print it, the
    patch prints the 19 digit chunks in reverse order (from least significant
    to most significant) and then reorders those with linear complexity to form
    the right printed number.
    Tested with printing both 256 and 320 bit numbers (first as an example
    of even number of 19 digit chunks plus one shorter above it, the second
    as an example of odd number of 19 digit chunks plus one shorter above it).
    
    The l * HOST_BITS_PER_WIDE_INT / 3 + 3 estimatition thinking about it now
    is one byte too much (one byte for -, one for '\0') and too conservative,
    so we could go with l * HOST_BITS_PER_WIDE_INT / 3 + 2 as well, or e.g.
    l * HOST_BITS_PER_WIDE_INT * 10 / 33 + 3 as even less conservative
    estimation (though more expensive to compute in inline code).
    But that l * HOST_BITS_PER_WIDE_INT / 4 + 4; is likely one byte too much
    as well, 2 bytes for 0x, one byte for '\0' and where does the 4th one come
    from?  Of course all of these assuming HOST_BITS_PER_WIDE_INT is a multiple
    of 64...
    
    2023-10-17  Jakub Jelinek  <jakub@redhat.com>
    
            * wide-int-print.h (print_dec_buf_size): For length, divide number
            of bits by 3 and add 3 instead of division by 4 and adding 4.
            * wide-int-print.cc (print_decs): Remove superfluous ()s.  Don't call
            print_hex, instead call print_decu on either negated value after
            printing - or on wi itself.
            (print_decu): Don't call print_hex, instead print even large numbers
            decimally.
            (pp_wide_int_large): Assume len from print_dec_buf_size is big enough
            even if it returns false.
            * pretty-print.h (pp_wide_int): Use print_dec_buf_size to check if
            pp_wide_int_large should be used.
            * tree-pretty-print.cc (dump_generic_node): Use print_hex_buf_size
            to compute needed buffer size.

Diff:
---
 gcc/pretty-print.h       |  5 +++--
 gcc/tree-pretty-print.cc |  7 +++---
 gcc/wide-int-print.cc    | 55 ++++++++++++++++++++++++++++++++++++------------
 gcc/wide-int-print.h     |  2 +-
 4 files changed, 49 insertions(+), 20 deletions(-)

diff --git a/gcc/pretty-print.h b/gcc/pretty-print.h
index ad6d659175dd..02658c8afad9 100644
--- a/gcc/pretty-print.h
+++ b/gcc/pretty-print.h
@@ -448,8 +448,9 @@ pp_wide_integer (pretty_printer *pp, HOST_WIDE_INT i)
 inline void
 pp_wide_int (pretty_printer *pp, const wide_int_ref &w, signop sgn)
 {
-  unsigned int prec = w.get_precision ();
-  if (UNLIKELY ((prec + 3) / 4 > sizeof (pp_buffer (pp)->digit_buffer) - 3))
+  unsigned int len;
+  print_dec_buf_size (w, sgn, &len);
+  if (UNLIKELY (len > sizeof (pp_buffer (pp)->digit_buffer)))
     pp_wide_int_large (pp, w, sgn);
   else
     {
diff --git a/gcc/tree-pretty-print.cc b/gcc/tree-pretty-print.cc
index 12c57c14dd4a..58705c57ad53 100644
--- a/gcc/tree-pretty-print.cc
+++ b/gcc/tree-pretty-print.cc
@@ -2248,10 +2248,11 @@ dump_generic_node (pretty_printer *pp, tree node, int spc, dump_flags_t flags,
 	      pp_minus (pp);
 	      val = -val;
 	    }
-	  unsigned int prec = val.get_precision ();
-	  if ((prec + 3) / 4 > sizeof (pp_buffer (pp)->digit_buffer) - 3)
+	  unsigned int len;
+	  print_hex_buf_size (val, &len);
+	  if (UNLIKELY (len > sizeof (pp_buffer (pp)->digit_buffer)))
 	    {
-	      char *buf = XALLOCAVEC (char, (prec + 3) / 4 + 3);
+	      char *buf = XALLOCAVEC (char, len);
 	      print_hex (val, buf);
 	      pp_string (pp, buf);
 	    }
diff --git a/gcc/wide-int-print.cc b/gcc/wide-int-print.cc
index 5179525f8495..07f23cc67625 100644
--- a/gcc/wide-int-print.cc
+++ b/gcc/wide-int-print.cc
@@ -49,14 +49,12 @@ print_dec (const wide_int_ref &wi, FILE *file, signop sgn)
 }
 
 
-/* Try to print the signed self in decimal to BUF if the number fits
-   in a HWI.  Other print in hex.  */
+/* Try to print the signed self in decimal to BUF.  */
 
 void
 print_decs (const wide_int_ref &wi, char *buf)
 {
-  if ((wi.get_precision () <= HOST_BITS_PER_WIDE_INT)
-      || (wi.get_len () == 1))
+  if (wi.get_precision () <= HOST_BITS_PER_WIDE_INT || wi.get_len () == 1)
     {
       if (wi::neg_p (wi))
       	sprintf (buf, "-" HOST_WIDE_INT_PRINT_UNSIGNED,
@@ -64,12 +62,17 @@ print_decs (const wide_int_ref &wi, char *buf)
       else
 	sprintf (buf, HOST_WIDE_INT_PRINT_DEC, wi.to_shwi ());
     }
+  else if (wi::neg_p (wi))
+    {
+      widest2_int w = widest2_int::from (wi, SIGNED);
+      *buf = '-';
+      print_decu (-w, buf + 1);
+    }
   else
-    print_hex (wi, buf);
+    print_decu (wi, buf);
 }
 
-/* Try to print the signed self in decimal to FILE if the number fits
-   in a HWI.  Other print in hex.  */
+/* Try to print the signed self in decimal to FILE.  */
 
 void
 print_decs (const wide_int_ref &wi, FILE *file)
@@ -82,8 +85,7 @@ print_decs (const wide_int_ref &wi, FILE *file)
   fputs (p, file);
 }
 
-/* Try to print the unsigned self in decimal to BUF if the number fits
-   in a HWI.  Other print in hex.  */
+/* Try to print the unsigned self in decimal to BUF.  */
 
 void
 print_decu (const wide_int_ref &wi, char *buf)
@@ -92,11 +94,37 @@ print_decu (const wide_int_ref &wi, char *buf)
       || (wi.get_len () == 1 && !wi::neg_p (wi)))
     sprintf (buf, HOST_WIDE_INT_PRINT_UNSIGNED, wi.to_uhwi ());
   else
-    print_hex (wi, buf);
+    {
+      widest2_int w = widest2_int::from (wi, UNSIGNED), r;
+      widest2_int ten19 = HOST_WIDE_INT_UC (10000000000000000000);
+      char buf2[20], next1[19], next2[19];
+      size_t l, c = 0, i;
+      /* In order to avoid dividing this twice, print the 19 decimal
+	 digit chunks in reverse order into buffer and then reorder
+	 them in-place.  */
+      while (wi::gtu_p (w, ten19))
+	{
+	  w = wi::divmod_trunc (w, ten19, UNSIGNED, &r);
+	  sprintf (buf + c * 19, "%019" PRIu64, r.to_uhwi ());
+	  ++c;
+	}
+      l = sprintf (buf2, HOST_WIDE_INT_PRINT_UNSIGNED, w.to_uhwi ());
+      buf[c * 19 + l] = '\0';
+      memcpy (next1, buf, 19);
+      memcpy (buf, buf2, l);
+      for (i = 0; i < c / 2; ++i)
+	{
+	  memcpy (next2, buf + (c - i - 1) * 19, 19);
+	  memcpy (buf + l + (c - i - 1) * 19, next1, 19);
+	  memcpy (next1, buf + (i + 1) * 19, 19);
+	  memcpy (buf + l + i * 19, next2, 19);
+	}
+      if (c & 1)
+	memcpy (buf + l + i * 19, next1, 19);
+    }
 }
 
-/* Try to print the signed self in decimal to FILE if the number fits
-   in a HWI.  Other print in hex.  */
+/* Try to print the signed self in decimal to FILE.  */
 
 void
 print_decu (const wide_int_ref &wi, FILE *file)
@@ -155,8 +183,7 @@ void
 pp_wide_int_large (pretty_printer *pp, const wide_int_ref &w, signop sgn)
 {
   unsigned int len;
-  if (!print_dec_buf_size (w, sgn, &len))
-    len = WIDE_INT_PRINT_BUFFER_SIZE;
+  print_dec_buf_size (w, sgn, &len);
   char *buf = XALLOCAVEC (char, len);
   print_dec (w, buf, sgn);
   pp_string (pp, buf);
diff --git a/gcc/wide-int-print.h b/gcc/wide-int-print.h
index 8dbfe24aba48..191c7f7d8ed3 100644
--- a/gcc/wide-int-print.h
+++ b/gcc/wide-int-print.h
@@ -42,7 +42,7 @@ print_dec_buf_size (const wide_int_ref &wi, signop sgn, unsigned int *len)
   unsigned int l = wi.get_len ();
   if ((l != 1 || sgn == UNSIGNED) && wi::neg_p (wi))
     l = WIDE_INT_MAX_HWIS (wi.get_precision ());
-  l = l * HOST_BITS_PER_WIDE_INT / 4 + 4;
+  l = l * HOST_BITS_PER_WIDE_INT / 3 + 3;
   *len = l;
   return UNLIKELY (l > WIDE_INT_PRINT_BUFFER_SIZE);
 }