<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jan 14, 2016 at 5:57 AM, 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><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="HOEnZb"><div class="h5">On Wed, Jan 13, 2016 at 04:28:03PM -0800, Daniel Berlin wrote:<br>
> On Wed, Jan 13, 2016 at 4:23 PM, Joerg Sonnenberger via llvm-dev <<br>
> <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<br>
><br>
> > On Wed, Jan 13, 2016 at 03:38:24PM -0800, Philip Reames wrote:<br>
> > > I don't think that arbitrary limiting the complexity of the search is the<br>
> > > right approach.  There are numerous ways the LVI infrastructure could be<br>
> > > made more memory efficient.  Fixing the existing code to be memory<br>
> > efficient<br>
> > > is the right approach.  Only once there's no more low hanging fruit<br>
> > should<br>
> > > we even consider clamping the search.<br>
> ><br>
> > Memory efficiency is only half of the problem. I.e. groonga's expr.c<br>
> > needs 4m to build on my laptop, a 2.7GHz i7. That doesn't sound<br>
> > reasonable for a -O2. Unlike the GVN issue, the cases I have run into do<br>
> > finish after a(n unreasonable) while, so at least it is not trivially<br>
> > superlinear.<br>
> ><br>
><br>
><br>
> Okay, so rather than artificially limit stuff, we should see if we can fix<br>
> the efficiency of the algorithms.<br>
><br>
> CVP is an O(N*lattice height) pass problem. It sounds like it is being more<br>
> than that for you.<br>
<br>
</div></div>I assume you mean something like #BB * #variables? </blockquote><div><br></div><div>No.</div><div> ;)</div><div>I mean the theoretical complexity of performing the optimization CVP performs (regardless of how it is currently implemented).</div><div><br></div><div>What CVP does is doable in linear time on number of variables * lattice height.  It has some memory cost to do this.</div><div><br></div><div>Assume for a second the lattice height is fixed (IE we do not have completely symbolic ranges).</div><div><br></div><div>It is possible, in linear time, to build an SSA-like form for the ranges it is computing. </div><div>It is then possible, in linear time, to propagate those ranges to all affected variables.</div><div><br></div><div>This is O(N) + O(N).</div><div><br></div><div>Doing so may change the ranges (they only get *better*, however).</div><div>So you may need to do this until they fall all the way down the lattice.</div><div><br></div><div>This means you may repeat this lattice height number of times.</div><div><br></div><div>CVP as currently implemented tries to be very lazy. The cost of being very lazy is that it has a worse theoretical complexity in the worst case, but is faster in cases there is not a lot to do.</div><div><br></div><div><br></div><div><br></div></div></div></div>