[Bug rtl-optimization/19097] [3.4/4.0/4.1 regression] Quadratic behavior with many sets for the same register in gcse CPROP

["amacleod at redhat dot com" <gcc-bugzilla at gcc dot gnu dot org>]

------- Comment #19 from amacleod at redhat dot com  2005-10-18 12:25 -------
Created an attachment (id=10017)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=10017&action=view)
patch for operand scan

Now that correct_use_link is *only* used for real uses, it is no longer
profitable to try to "shortcut" the search for the owner of a use list. The
shortcut use to look at each previous node as the list was traversed, and check
to see if the stmt was modified. If it wasn't, we knew that node was in the
correct list and wouldnt have to scan all the way back to the owner.

well, this testcase was spending almost all its time checking for
stmt_modified_p....  something like 250,000,000 checks on 50,000 calls.

I've removed the no longer useful shortcut, and the results are as follows:

bootstrapped and no new regressions on i686-pc-linux-gnu.

Andrew


                    x86-64:
-O1 on testcase:
before patch     tree operand scan     :   8.00 (36%)
                 TOTAL                 :  22.18

after patch:     tree operand scan     :   1.41 ( 9%)
                 TOTAL                 :  15.62

-O2 on testcase:
before patch     tree operand scan     :   7.88 (15%)
                 TOTAL                 :  53.08

after patch:     tree operand scan     :   1.42 ( 3%)
                 TOTAL                 :  46.94


                    x86:
-O1 on testcase:
before patch     tree operand scan     :   2.54 (17%)
                 TOTAL                 :  14.60


after patch:     tree operand scan     :   1.01 ( 8%)
                 TOTAL                 :  12.51

-O2 on testcase:
before patch     tree operand scan     :   2.95 ( 8%)
                 TOTAL                 :  39.20

after patch:     tree operand scan     :   1.06 ( 3%)
                 TOTAL                 :  38.03


pretty much a wash on cc1-i and cpgram.cc testcases on both targets.


-- 


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