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

[Philip Reames via llvm-dev]

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>