The following code, when compiled with optimization on gcc/arm (any configuration), demonstrates an exponential time behaviour in combine. Each additional statement doubles the length of the compilation. This is a long-standing problem that dates back to at least gcc-2.8 Release: 3.1 20010323 (experimental) Environment: System: SunOS sun18 5.7 Generic_106541-11 sun4u sparc SUNW,Ultra-5_10 Architecture: sun4 host: sparc-sun-solaris2.5.1 build: sparc-sun-solaris2.5.1 target: arm-unknown-elf configured with: /home/rearnsha/gnusrc/egcs-cross/configure --target=arm-elf --with-headers=/home/rearnsha/gnusrc/utils/newlib/libc/include --prefix=/home/rearnsha/gnu/egcs/install/SunOS5 How-To-Repeat: Compile the following test case on arm-elf (or any other ARM target): arm-elf-gcc -O test.c unsigned mhz_2(register long n, unsigned a) { for (; n > 0; --n) { a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; a^=a+a; } return a; }
Fix: Fixed by: 2003-02-13 Adam Nemet <anemet@lnxw.com> PR opt/2391 * combine.c: Fix spelling in comment. (cached_nonzero_bits): New function. (cached_num_sign_bit_copies): New function. (nonzero_bits_with_known): New macro. (num_sign_bit_copies_with_known): New macro. (nonzero_bits1): Rename from nonzero_bits. Add three new arguments. Change calls from nonzero_bits to nonzero_bits_with_known. (num_sign_bit_copies1): Rename from num_sign_bit_copies. Add three new arguments. Change calls from num_sign_bit_copies to num_sign_bit_copies_with_known. (nonzero_bits): New macro. (num_sign_bit_copies): New macro. (update_table_tick): Don't traverse identical subexpression more than once. (get_last_value_validate): Likewise. Mainline: http://gcc.gnu.org/ml/gcc-cvs/2003-02/msg00691.html 3.3 brach: http://gcc.gnu.org/ml/gcc-cvs/2003-02/msg00758.html
From: Craig Rodrigues <rodrigc@mediaone.net> To: rearnsha@arm.com, gcc-gnats@gcc.gnu.org, gcc-prs@gcc.gnu.org, bjh21@netbsd.org, gcc-bugs@gcc.gnu.org, nobody@gcc.gnu.org Cc: Subject: Re: optimization/2391: Exponential compilation time explosion in combine Date: Sat, 12 Jan 2002 15:13:04 -0500 http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&pr=2391 PR 5333 was marked as a duplicate of this bug. Attachment from PR 5333 added to this PR, with the following instructions: =============================================================== When compiling the attached code with -O, GCC (configured as above) seems to run forever, eating CPU but not leaking memory. The command line (run from within the GCC source tree) was: ./xgcc -da -B. -O -v ~/mhz.i The -da produces dumps up to mhz.i.30.mach. A workaround is to compile without -O. This bug has been present since at least egcs 1.1.2.
Responsible-Changed-From-To: unassigned->nemet Responsible-Changed-Why: .
State-Changed-From-To: open->closed State-Changed-Why: Fixed.