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

[Joerg Sonnenberger via llvm-dev]

On Thu, Jan 14, 2016 at 08:38:10AM -0800, Daniel Berlin wrote:
> > 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).

Well, yes, talking about big-O notation is fine, the question is what
the N stands for :)

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

Right, that's what I mean. I think the lattice height can degenerate to
the number of BBs in a function easily. When looking at the size of the
IR, it effectively becomes O(n^2) where n is the size of the IR as worst
case. That would justify finding some cut-off point, even when it is
quite large and depending on the optimizer level (-O2 vs -O3?).

Joerg