This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Speedup of new-ra


On Mon, 27 Oct 2003, Denis Chertykov wrote:

> Few months ago I have profiled new-ra and found that mostly critical
> function is `alias ()' (so many function ;).

It never was at the top position for me, but it surely is called very
often, yes.

> May be better to have additional field in web for quick alias
> calculation. (ie: head_alias) head_alias will poin to `alias (web)'. For
> noncoalesced webs it will point to web himself. (ie: web->head_alias =
> web).

Beware that the updating of such a member is a bit nontrivial.  For
instance given this:
  alias(a) == c
  alias(b) == c
  alias(c) == c  (i.e. c has no alias)
and now one changes c's alias to be d, then with a function all would
simply work, with a member you would also have to update the aliases of a
and b.  Classical union-find structure, hence from 'c' you don't know all
webs aliased to it.

Another problem is the undoing of coalescing.  For this we have to avoid
path compression.  Probably it's the best to precompute all aliases around
points which often ask this information (the function in ra-rewrite do
this), but don't change the alias forest itself.  That's would be much
safer, and probably still be a benefit.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]