[Bug optimization/13931] New: combiner much slower on big functions

[bonzini at gnu dot org]

The combiner jumped up from 3.3.2's 8% to 3.4/3.5's 56% in the attached function. 
 
No. of lines in block            Run time 
600                                      0.36 
1200				    2.33 
1800                                    5.77 
2400                                   10.56 
 
There seems to be a quadratic bottleneck in combine.  distribute_notes has a loop that 
goes over all previous instructions.  distribute_notes calls reg_set_p, which calls set_of, 
which calls note_stores, which calls set_of_1, which calls reg_overlap_mentioned_p, 
which calls refers_to_regno_p... and all these show up quite at the top of the profile. 
 
# of instructions       function 
224,203,200  rtlanal.c:refers_to_regno_p 
150,433,200  rtlanal.c:reg_overlap_mentioned_p 
 75,561,636  rtlanal.c:note_stores 
 56,985,600  rtlanal.c:reg_referenced_p 
 49,576,316  regrename.c:validate_value_data 
 40,026,779  rtl.c:rtx_equal_p 
 28,740,658  flow.c:mark_set_1 
 27,562,800  combine.c:distribute_notes 
 25,928,400  rtlanal.c:set_of_1 
 15,840,000  rtlanal.c:reg_set_p 
 
This might be a duplicate of PR13775.

-- 
           Summary: combiner much slower on big functions
           Product: gcc
           Version: 3.4.0
            Status: UNCONFIRMED
          Severity: critical
          Priority: P2
         Component: optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: bonzini at gnu dot org
                CC: gcc-bugs at gcc dot gnu dot org
 GCC build triplet: i686-pc-linux-gnu
  GCC host triplet: i686-pc-linux-gnu
GCC target triplet: i686-pc-linux-gnu


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13931