[Bug tree-optimization/102943] [12 Regression] Jump threader compile-time hog with 521.wrf_r

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102943

--- Comment #37 from Richard Biener <rguenth at gcc dot gnu.org> ---
I'm looking at range_def_chain::m_def_chain, it's use is well obfuscated by
inheritance but comments suggest that we have one such structure either for
each edge in the CFG or for each basic-block.  In particular this
m_def_chain vector looks very sparse and fat, replacing that with a

  hash_map<int, rdc *>

and allocating rdcs from another obstack (in principle re-using
m_bitmap.obstack would be possible but somewhat ugly) should make this
more cache and memory friendly (whether SSA name version or pointer is
used as key would remain to be determined).

The ssa1 and ssa2 members are also quite odd, we always record into the
bitmap so those seem to be a waste of time?  Changing allocation the
above way would also enable embedding bitmap_head, removing one pointer
indirection.  Unfortunately we use bitmap_ior_into so using the more
efficient tree form for bitmap queries isn't possible until somebody
implements (efficient!) bitmap_ior_into on tree form.

It wouldnt't fix the appearant algorithmic issues of course, so just food
for thought.  Complexity wise it would reduce O (n-edges * n-ssa-names)
to O (n-edges * n-deps/imports-on-edge).