GCC Bugzilla Bug 2391

	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.