<div dir="ltr">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).<div><div><br></div><div>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).</div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div><br></div><div>On Thu, Jan 14, 2016 at 12:59 PM, Joerg Sonnenberger via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br></div><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span>On Thu, Jan 14, 2016 at 08:38:10AM -0800, Daniel Berlin wrote:<br>
> > I assume you mean something like #BB * #variables?<br>
><br>
><br>
> No.<br>
>  ;)<br>
> I mean the theoretical complexity of performing the optimization CVP<br>
> performs (regardless of how it is currently implemented).<br>
<br>
</span>Well, yes, talking about big-O notation is fine, the question is what<br>
the N stands for :)<br>
<span><br>
> What CVP does is doable in linear time on number of variables * lattice<br>
> height.  It has some memory cost to do this.<br>
<br>
</span>Right, that's what I mean. I think the lattice height can degenerate to<br>
the number of BBs in a function easily. When looking at the size of the<br>
IR, it effectively becomes O(n^2) where n is the size of the IR as worst<br>
case. That would justify finding some cut-off point, even when it is<br>
quite large and depending on the optimizer level (-O2 vs -O3?).<br>
<div><div><br>
Joerg<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</div></div></blockquote></div><br></div></div></div>