This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: fix opt/8634
Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz> 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.
--
- Geoffrey Keating <geoffk at geoffk dot org>