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

[Daniel Berlin via llvm-dev]

The lattice height will never be based on the size of the BB's because the
bb's are irrelevant to the lattice value of a given variable (which is
usually a range).

IE the value a variable takes on is not related to it's bb, but only the
range of things representable by that value type, plus a few different
types of things we may want to represent symbolically (IE value A is > 5).

in simple lattices, "range of things representable by that value type" is
each a different transition, so it's a very *wide* lattice, but not a very
tall one.

So, for example, constant propagation is usually a 3 height lattice, even
if the width of the middle lattice value  is "every constant value a given
variable could take on".  This is because a single variable can only take
on *one* of those values in SSA.


On Thu, Jan 14, 2016 at 12:59 PM, Joerg Sonnenberger via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

> 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
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160114/505501fa/attachment.html>