From mboxrd@z Thu Jan  1 00:00:00 1970
From: Richard Earnshaw <rearnsha@arm.com>
To: gcc-gnats@gcc.gnu.org
Subject: optimization/2391: Exponential compilation time explosion in combine
Date: Mon, 26 Mar 2001 02:36:00 -0000
Message-id: <200103261026.LAA29078@sun18.cambridge.arm.com>
X-SW-Source: 2001-03/msg00272.html
List-Id: <gcc-prs.sourceware.org>

>Number:         2391
>Category:       optimization
>Synopsis:       Exponential compilation time explosion in combine
>Confidential:   no
>Severity:       serious
>Priority:       medium
>Responsible:    unassigned
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Mon Mar 26 02:36:00 PST 2001
>Closed-Date:
>Last-Modified:
>Originator:     Richard Earnshaw
>Release:        3.1 20010323 (experimental)
>Organization:
ARM 
>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
>Description:
	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

>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:
	Unknown.
>Release-Note:
>Audit-Trail:
>Unformatted: