This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] PR25468 (-g makes g++ loop forever)
- From: Steven Bosscher <stevenb dot gcc at gmail dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Sun, 23 Jul 2006 19:35:15 +0200
- Subject: [patch] PR25468 (-g makes g++ loop forever)
Hi,
This is one of those bugs that makes you question Linus' "given enough
eyeballs, all bugs are shallow" hypothesis.
The bug is in many of the ASM_OUTPUT_ASCII definitions throughout
the config/* files. Below is a copy of the one from config/elfos.h:
#define ASM_OUTPUT_ASCII(FILE, STR, LENGTH) \
do \
{ \
register const unsigned char *_ascii_bytes = \
(const unsigned char *) (STR); \
register const unsigned char *limit = _ascii_bytes + (LENGTH); \
register unsigned bytes_in_chunk = 0; \
\
for (; _ascii_bytes < limit; _ascii_bytes++) \
{ \
register const unsigned char *p; \
\
if (bytes_in_chunk >= 60) \
{ \
fprintf ((FILE), "\"\n"); \
bytes_in_chunk = 0; \
} \
\
for (p = _ascii_bytes; p < limit && *p != '\0'; p++) \
continue; \
\
if (p < limit && (p - _ascii_bytes) <= (long)STRING_LIMIT) \
{ \
if (bytes_in_chunk > 0) \
{ \
fprintf ((FILE), "\"\n"); \
bytes_in_chunk = 0; \
} \
\
ASM_OUTPUT_LIMITED_STRING ((FILE), _ascii_bytes); \
_ascii_bytes = p; \
} \
else \
{ \
register int escape; \
register unsigned ch; \
\
if (bytes_in_chunk == 0) \
fprintf ((FILE), "%s\"", ASCII_DATA_ASM_OP); \
\
switch (escape = ESCAPES[ch = *_ascii_bytes]) \
{ \
case 0: \
putc (ch, (FILE)); \
bytes_in_chunk++; \
break; \
case 1: \
fprintf ((FILE), "\\%03o", ch); \
bytes_in_chunk += 4; \
break; \
default: \
putc ('\\', (FILE)); \
putc (escape, (FILE)); \
bytes_in_chunk += 2; \
break; \
} \
} \
} \
\
if (bytes_in_chunk > 0) \
fprintf ((FILE), "\"\n"); \
} \
while (0)
OK, so we're being called with some string STR of length LENGTH. As
Jim Wilson pointed out in the Bug audit trail, the putc and fprintfs
used to write out the individual characters probably don't make this
a very efficient macro. (The fact that this _is_ a macro is another
bad thing, but oh well.) In the test case from the bug, gcc will try
to push something in the order of 70 Mb through this function, mostly
very large strings for very large C++ mangled and unmanged identifier
names. In some cases, LENGTH is larger than 40,000 for the test case.
But the putc and fprintf calls are not the real problem here.
What really happens is this:
1) Look for '\0' between STR[0] and STR[LENGTH]. If there is a '\0'
and the string lenght from STR[0] to the '\0' is less than STRING_LIMIT,
write out that string in whole. otherwise, dump a single byte and
advance to the next character in STR.
2) Look for '\0' between STR[1] and STR[LENGTH]. If there is a '\0'
and the string lenght from STR[0] to the '\0' is less than STRING_LIMIT,
write out that string in whole. otherwise, dump a single byte and
advance to the next character in STR.
3) Look for '\0' between STR[1] and STR[LENGTH]. If there is a '\0'
and the string lenght from STR[0] to the '\0' is less than STRING_LIMIT,
write out that string in whole. otherwise, dump a single byte and
advance to the next character in STR.
(...)
i) Look for '\0' between STR[i] and STR[LENGTH]. If there is a '\0'
and the string lenght from STR[0] to the '\0' is less than STRING_LIMIT,
write out that string in whole. otherwise, dump a single byte and
advance to the next character in STR.
Now imagine LENGTH=40000. Searching for '\0' happens on these lines:
for (p = _ascii_bytes; p < limit && *p != '\0'; p++) \
continue; \
This is a classic example of quadratic behavior.
Now, I can see why sometimes people write their code this way. But what
has me puzzled, is that two people (Jim and myself) can stare at this
macro for obviously quite some time, and not spot the quadratic loop
instantly :-) And that the folks who have copied this kind of loop to
at least 5 other files also didn't spot this problem.
In any case, the fix is trivial: cache the last found '\0'. That is what
the attached patch does, but only in config/elfos.h, which leaves the
same bug in at least cris/aout.h, i386/ptx4-i.h, i386/i386-interix.h,
i386/sysv4.h, and i386/i386elf.h. I'm not interested in those targets,
and even if I were, I can't test on them. So sorry, but someone else
will have to fix those.
The attached patch has been bootstrapped and tested on x86_64-suse-linux-gnu
with multilib, and on i686-suse-linux-gnu. I have verified that the test
case from the bug now compiles almost as fast with -g as without, and also
that the debug output is the same for this test case, for the test case
from PR8361, and for almost all of gcc itself (i.e. my collection of cc1-i
files). Even for PR8361, this patch gives a >10% compile time speedup with
-g.
OK for mainline? Also OK for GCC 4.1 after some time on the trunk?
Thanks,
Gr.
Steven
PR debug/25468
* config/elfos.h (ASM_OUTPUT_ASCII): Remove 'register' marks.
Cache the last found '\0' marker to avoid quadratic behavior.
Index: config/elfos.h
===================================================================
--- config/elfos.h (revision 115684)
+++ config/elfos.h (working copy)
@@ -429,14 +429,15 @@ Boston, MA 02110-1301, USA. */
#define ASM_OUTPUT_ASCII(FILE, STR, LENGTH) \
do \
{ \
- register const unsigned char *_ascii_bytes = \
+ const unsigned char *_ascii_bytes = \
(const unsigned char *) (STR); \
- register const unsigned char *limit = _ascii_bytes + (LENGTH); \
- register unsigned bytes_in_chunk = 0; \
+ const unsigned char *limit = _ascii_bytes + (LENGTH); \
+ const unsigned char *last_null = NULL; \
+ unsigned bytes_in_chunk = 0; \
\
for (; _ascii_bytes < limit; _ascii_bytes++) \
{ \
- register const unsigned char *p; \
+ const unsigned char *p; \
\
if (bytes_in_chunk >= 60) \
{ \
@@ -444,8 +445,14 @@ Boston, MA 02110-1301, USA. */
bytes_in_chunk = 0; \
} \
\
- for (p = _ascii_bytes; p < limit && *p != '\0'; p++) \
- continue; \
+ if (_ascii_bytes > last_null) \
+ { \
+ for (p = _ascii_bytes; p < limit && *p != '\0'; p++) \
+ continue; \
+ last_null = p; \
+ } \
+ else \
+ p = last_null; \
\
if (p < limit && (p - _ascii_bytes) <= (long)STRING_LIMIT) \
{ \