This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: fix opt/8634
Hello,
> > > 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.
> >
> > Why do you think purge_adressof does linear work per insn?
>
> I don't. I don't think anyone does. Richard was saying that if
> purge_addressof is linear in the number of insns, and you then call it
> a number of times that's proportional to the number of insns, that
> makes it quadratic.
but as it is called exacly once per each function, it is linear.
Zdenek