------- Comment #11 from rguenth at gcc dot gnu dot org 2010-01-12 09:09 ------- (In reply to comment #10) > I've looked briefly at the #c4 testcase, and the problem seems to be extremely > long loc_chains. var-tracking e.g. stops for huge amount of time (many > minutes) on one bb, EH pad with 162 incoming EH edges (and no others). Each > of > those 162 incoming EH edges has roughly 1800 vars in its out hash table, with > just one problematic one - which has around 650 items in > var->var_part[0].loc_chain chain. There are ~ 2 other vars with loc_chain > chain lengths in the 40s and the rest is with chain length below 10. The CPU > eater is intersect_loc_chains. > For each of the 650 loc_chain entries it calls find_loc_in_1pdv, which, as the > vast majority of the entries in s2var's loc_chain are VALUEs, looks stuff up > in > the hash table and recurses. > > I wonder whether for large loc_chain lengths we just couldn't use a temporary > hash table. If we see in intersect_loc_chains that chain length is beyond > certain threshold, populate a temporary hash table by doing what > find_loc_in_1pdv does (except instead of rtx_equal_p and returning early it > seeing a match it would record each loc into the hash table and continue > walking). Then intersect_loc_chains could just walk this hash table instead > of > searching through it again and again, avoiding the O(loc_chain_length^2) > complexity.
That sounds like a good idea. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41371
