* [PATCH] wide-int-print: Don't print large numbers hexadecimally for print_dec{,s,u}
@ 2023-10-17 8:12 Jakub Jelinek
2023-10-17 12:19 ` Richard Biener
0 siblings, 1 reply; 2+ messages in thread
From: Jakub Jelinek @ 2023-10-17 8:12 UTC (permalink / raw)
To: Richard Biener, Richard Sandiford; +Cc: gcc-patches
Hi!
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...
Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
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.
--- gcc/wide-int-print.h.jj 2023-10-15 23:04:06.195422820 +0200
+++ gcc/wide-int-print.h 2023-10-16 10:14:41.327401697 +0200
@@ -42,7 +42,7 @@ print_dec_buf_size (const wide_int_ref &
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);
}
--- gcc/wide-int-print.cc.jj 2023-10-15 23:04:06.195422820 +0200
+++ gcc/wide-int-print.cc 2023-10-16 11:20:30.662174735 +0200
@@ -49,14 +49,12 @@ print_dec (const wide_int_ref &wi, FILE
}
-/* 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
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
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
|| (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);
--- gcc/pretty-print.h.jj 2023-10-15 23:04:06.095422965 +0200
+++ gcc/pretty-print.h 2023-10-16 10:51:56.053529117 +0200
@@ -448,8 +448,9 @@ pp_wide_integer (pretty_printer *pp, HOS
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
{
--- gcc/tree-pretty-print.cc.jj 2023-09-21 20:02:53.467522151 +0200
+++ gcc/tree-pretty-print.cc 2023-10-16 11:05:51.131997367 +0200
@@ -2248,10 +2248,11 @@ dump_generic_node (pretty_printer *pp, t
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);
}
Jakub
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: [PATCH] wide-int-print: Don't print large numbers hexadecimally for print_dec{,s,u}
2023-10-17 8:12 [PATCH] wide-int-print: Don't print large numbers hexadecimally for print_dec{,s,u} Jakub Jelinek
@ 2023-10-17 12:19 ` Richard Biener
0 siblings, 0 replies; 2+ messages in thread
From: Richard Biener @ 2023-10-17 12:19 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: Richard Sandiford, gcc-patches
On Tue, 17 Oct 2023, Jakub Jelinek wrote:
> Hi!
>
> 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...
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
OK.
Thanks,
Richard.
> 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.
>
> --- gcc/wide-int-print.h.jj 2023-10-15 23:04:06.195422820 +0200
> +++ gcc/wide-int-print.h 2023-10-16 10:14:41.327401697 +0200
> @@ -42,7 +42,7 @@ print_dec_buf_size (const wide_int_ref &
> 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);
> }
> --- gcc/wide-int-print.cc.jj 2023-10-15 23:04:06.195422820 +0200
> +++ gcc/wide-int-print.cc 2023-10-16 11:20:30.662174735 +0200
> @@ -49,14 +49,12 @@ print_dec (const wide_int_ref &wi, FILE
> }
>
>
> -/* 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
> 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
> 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
> || (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);
> --- gcc/pretty-print.h.jj 2023-10-15 23:04:06.095422965 +0200
> +++ gcc/pretty-print.h 2023-10-16 10:51:56.053529117 +0200
> @@ -448,8 +448,9 @@ pp_wide_integer (pretty_printer *pp, HOS
> 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
> {
> --- gcc/tree-pretty-print.cc.jj 2023-09-21 20:02:53.467522151 +0200
> +++ gcc/tree-pretty-print.cc 2023-10-16 11:05:51.131997367 +0200
> @@ -2248,10 +2248,11 @@ dump_generic_node (pretty_printer *pp, t
> 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);
> }
>
> Jakub
>
>
--
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Ivo Totev, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2023-10-17 12:19 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-10-17 8:12 [PATCH] wide-int-print: Don't print large numbers hexadecimally for print_dec{,s,u} Jakub Jelinek
2023-10-17 12:19 ` Richard Biener
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).