------- Comment #10 from jakub at gcc dot gnu dot org 2010-01-11 18:23 ------- 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. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41371
