[llvm-dev] High memory use and LVI/Correlated Value Propagation

[Daniel Berlin via llvm-dev]

On Thu, Jan 14, 2016 at 5:57 AM, Joerg Sonnenberger via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

> On Wed, Jan 13, 2016 at 04:28:03PM -0800, Daniel Berlin wrote:
> > On Wed, Jan 13, 2016 at 4:23 PM, Joerg Sonnenberger via llvm-dev <
> > llvm-dev at lists.llvm.org> wrote:
> >
> > > On Wed, Jan 13, 2016 at 03:38:24PM -0800, Philip Reames wrote:
> > > > I don't think that arbitrary limiting the complexity of the search
> is the
> > > > right approach.  There are numerous ways the LVI infrastructure
> could be
> > > > made more memory efficient.  Fixing the existing code to be memory
> > > efficient
> > > > is the right approach.  Only once there's no more low hanging fruit
> > > should
> > > > we even consider clamping the search.
> > >
> > > Memory efficiency is only half of the problem. I.e. groonga's expr.c
> > > needs 4m to build on my laptop, a 2.7GHz i7. That doesn't sound
> > > reasonable for a -O2. Unlike the GVN issue, the cases I have run into
> do
> > > finish after a(n unreasonable) while, so at least it is not trivially
> > > superlinear.
> > >
> >
> >
> > Okay, so rather than artificially limit stuff, we should see if we can
> fix
> > the efficiency of the algorithms.
> >
> > CVP is an O(N*lattice height) pass problem. It sounds like it is being
> more
> > than that for you.
>
> I assume you mean something like #BB * #variables?


No.
 ;)
I mean the theoretical complexity of performing the optimization CVP
performs (regardless of how it is currently implemented).

What CVP does is doable in linear time on number of variables * lattice
height.  It has some memory cost to do this.

Assume for a second the lattice height is fixed (IE we do not have
completely symbolic ranges).

It is possible, in linear time, to build an SSA-like form for the ranges it
is computing.
It is then possible, in linear time, to propagate those ranges to all
affected variables.

This is O(N) + O(N).

Doing so may change the ranges (they only get *better*, however).
So you may need to do this until they fall all the way down the lattice.

This means you may repeat this lattice height number of times.

CVP as currently implemented tries to be very lazy. The cost of being very
lazy is that it has a worse theoretical complexity in the worst case, but
is faster in cases there is not a lot to do.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160114/ad6d0660/attachment-0001.html>