+++ This bug was initially created as a clone of Bug #684895 +++

Description of problem:

<neb> I think I have a reproducer for another problem that seems to make it go into an infinite loop on new compilers
<neb> Almost half of the time is spent in:
<neb>                :      /* Skip the clobbers. We delete the active insn if this insn
<neb>                :         shadows the set.  To have been put on the active list, it
<neb>                :         has exactly on set. */
<neb> 267397 46.0425 :      while (!s_info->is_set)
<neb>                :        s_info = s_info->next;
<neb> in gcc/dse.c
<neb> static int record_store (rtx body, bb_info_t bb_info) is the hot function.
<neb> record_store total: 535076 92.1336 */
<fche> not an infinite loop, just a poor-complexity algorithm, no ?
<neb> fche heh maybe I'm just not patient enough. 4.1.2 seems to compile it in 13 min on a Power6. It has been going for >15hrs on my laptop.
<fche> so hey, sic a debugger onto that line, try 'next' or a cont with a breakpoint on the next line, to see if that loop ever exits for a particular linked-list
<fche> btw still trying -O1 with that test case vs. -O0 ?
<neb> yes
<neb> It has been chugging along since yesterday. ;-)
<neb> yes it gets out of the loop and out of the function
<neb> leading evidence to your "poor-complexity algorithm" vs. my "infinite loop" hypothesis
<neb> I'll try O0
<fche> and try it with a smaller level of cartesian 'fanout'
<neb> with -O0 c++: Internal error: Killed (program cc1plus)
<neb> nice 
<fche> ship it
<fche> or rather, report it if that's all the compiler gives you
<fche> have you tried with a shrunken test case (smaller fanout )?
<neb> fche, no haven't tried with a smaller testcase yet.
<neb> I'm reporting it right now.
<fche> thanks
<neb> NP I take great pleasure in doing it.
<fche> I don't doubt it!
<neb> I'll do the smaller fanout in a bit.

Trying to compile with -O1 seems to get caught in a poor complexity algorithm. 

 * Total samples for file : "/usr/src/debug/gcc-4.4.4-20100726/obj-x86_64-redhat-linux/gcc/../../gcc/dse.c"
 * 
 * 535156 92.1474
...

               :/* BODY is an instruction pattern that belongs to INSN.  Return 1 if
               :   there is a candidate store, after adding it to the appropriate
               :   local store group if so.  */
               :
               :static int
               :record_store (rtx body, bb_info_t bb_info)
     6  0.0010 :{ /* record_store total: 535076 92.1336 */
...
               :      /* Skip the clobbers. We delete the active insn if this insn
               :         shadows the set.  To have been put on the active list, it
               :         has exactly on set. */
267397 46.0425 :      while (!s_info->is_set)
               :        s_info = s_info->next;
...

Version-Release number of selected component (if applicable):

gcc (GCC) 4.5.1 20100924 (Red Hat 4.5.1-4) 

How reproducible:

[ben@vfed bgp_large_exe]$ make
c++ -c -fPIC -O0 -DINDEX=0 crossN.cc -o cross0_g++.o
c++: Internal error: Killed (program cc1plus)
Please submit a full bug report.
See <http://bugzilla.redhat.com/bugzilla> for instructions.
make: *** [cross0_g++.o] Error 1 

Actual results:

Compile never completes.

Expected results:

Compile completes.

Additional info:

--- Additional comment from tgummels on 2011-03-14 14:20:05 EDT ---

Created attachment 484275 [details]
oprofile annotate

--- Additional comment from tgummels on 2011-03-14 14:22:06 EDT ---

Created attachment 484276 [details]
Reproducer Source