This is the mail archive of the gcc-patches@gcc.gnu.org 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: 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 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).

Zdenek


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