fix opt/8634

Geoff Keating geoffk@geoffk.org
Tue Apr 8 18:33:00 GMT 2003


> Date: Tue, 8 Apr 2003 20:10:20 +0200
> From: Zdenek Dvorak <rakdver@atrey.karlin.mff.cuni.cz>
> Cc: gcc-patches@gcc.gnu.org
> Content-Disposition: inline
> User-Agent: Mutt/1.3.28i
> X-OriginalArrivalTime: 08 Apr 2003 18:09:57.0093 (UTC) FILETIME=[0FF17950:01C2FDFA]
> 
> Hello,
> 
> > Zdenek Dvorak <rakdver@atrey.karlin.mff.cuni.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.

-- 
- Geoffrey Keating <geoffk@geoffk.org>



More information about the Gcc-patches mailing list