Tue Apr 8 18:10:00 GMT 2003
> Zdenek Dvorak <email@example.com> writes:
> > Hello,
> > > I believe purge_addressof costs us almost nothing
> > >
> > > Not at all true, since it can iterate over all insns, so if you have a
> > > mechanism that calls it a fixed percentage of the time, it's actually
> > > *quadratic*.
> > can you explain this in greater detail? It is one pass over insns, so it
> > should be linear, no?
> If you take a linear operation (that is, O(n)), and then you perform
> it K*n times for some fixed constant K, then the program is O(n*n),
> which is quadratic.
Why do you think purge_adressof does linear work per insn? I haven't studied
it in detail, but I think it manages to work in time linear in the
length of insn chain (the only place that could cause problems is
backpatching of regs when we decide to really put adressof to the
stack, but I think we construct list of insns for each such register
when emitting it and there is at most constant number of addresofs per
insn, so it comes again to linear).
More information about the Gcc-patches