llvm dev - Jan 2016 - High memory use and LVI/Correlated Value Propagation

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.

Joerg

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160113/7f69fdc3/attachment.html>

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? The instances I have
seen are all very large functions with many branches. Consider it from
this perspective: there is currently only one hammer for controlling the
amount of memory/CPU time CVP will use from clang -- -O0 vs -O2. I
believe that -O2 should provide a result in a reasonable amount of time
and with a reasonable amount of memory. The 2GB clamp (and 1h of CPU
time) for a 64bit clang are similar to the limits for a native build on
a 32bit architecture, so they are not arbitrary constraints.

Joerg

On 01/13/2016 04:28 PM, Daniel Berlin via llvm-dev
wrote:
>
>
> On Wed, Jan 13, 2016 at 4:23 PM, Joerg Sonnenberger via llvm-dev 
> <llvm-dev at lists.llvm.org <mailto: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.
(Deliberately replying up thread to skip detailed discussion of the 
lattice.)

We have had bugs in the past which causes us to move back up the 
lattice.  The most likely cause of long running time(*) is an accidental 
reversal in the lattice.  Note that we move up the lattice intentionally 
in some cases (specifically around assumes) when intersecting facts from 
different sources.

(*) Assuming we're talking about an algorithmic issue and not simply 
poor implementation quality.  We're definitely more wasteful about 
memory than we need to be for instance.  Depending on the caching 
behavior of the algorithm, this could appear super linear in running time.

If you have found a case that involves many steps for each variable in 
the lattice, one principled fix would be to bound the number of constant 
range refinements allowed.  e.g. If you updated the constant range 5 
times, drop to overdefined.

Philip

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160114/38ec9878/attachment.html>