[Bug debug/41371] [4.5 Regression] var-tracking is slow and memory hungry

["rguenth at gcc dot gnu dot org" <gcc-bugzilla at gcc dot gnu dot org>]

------- 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