<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jan 14, 2016 at 10:32 AM, Hal Finkel <span dir="ltr"><<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">----- Original Message -----<br>
<br>
> From: "Daniel Berlin via llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>><br>
> To: "Joerg Sonnenberger" <<a href="mailto:joerg@britannica.bec.de" target="_blank">joerg@britannica.bec.de</a>>, "llvm-dev"<br>
> <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>><br>
> Sent: Thursday, January 14, 2016 10:38:10 AM<br>
> Subject: Re: [llvm-dev] High memory use and LVI/Correlated Value<br>
> Propagation<br>
<div><div><br>
> On Thu, Jan 14, 2016 at 5:57 AM, Joerg Sonnenberger via llvm-dev <<br>
> <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a> > wrote:<br>
<br>
> > On Wed, Jan 13, 2016 at 04:28:03PM -0800, Daniel Berlin wrote:<br>
><br>
> > > On Wed, Jan 13, 2016 at 4:23 PM, Joerg Sonnenberger via llvm-dev<br>
> > > <<br>
><br>
> > > <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a> > wrote:<br>
><br>
> > ><br>
><br>
> > > > On Wed, Jan 13, 2016 at 03:38:24PM -0800, Philip Reames wrote:<br>
><br>
> > > > > I don't think that arbitrary limiting the complexity of the<br>
> > > > > search is the<br>
><br>
> > > > > right approach. There are numerous ways the LVI<br>
> > > > > infrastructure<br>
> > > > > could be<br>
><br>
> > > > > made more memory efficient. Fixing the existing code to be<br>
> > > > > memory<br>
><br>
> > > > efficient<br>
><br>
> > > > > is the right approach. Only once there's no more low hanging<br>
> > > > > fruit<br>
><br>
> > > > should<br>
><br>
> > > > > we even consider clamping the search.<br>
><br>
> > > ><br>
><br>
> > > > Memory efficiency is only half of the problem. I.e. groonga's<br>
> > > > expr.c<br>
><br>
> > > > needs 4m to build on my laptop, a 2.7GHz i7. That doesn't sound<br>
><br>
> > > > reasonable for a -O2. Unlike the GVN issue, the cases I have<br>
> > > > run<br>
> > > > into do<br>
><br>
> > > > finish after a(n unreasonable) while, so at least it is not<br>
> > > > trivially<br>
><br>
> > > > superlinear.<br>
><br>
> > > ><br>
><br>
> > ><br>
><br>
> > ><br>
><br>
> > > Okay, so rather than artificially limit stuff, we should see if<br>
> > > we<br>
> > > can fix<br>
><br>
> > > the efficiency of the algorithms.<br>
><br>
> > ><br>
><br>
> > > CVP is an O(N*lattice height) pass problem. It sounds like it is<br>
> > > being more<br>
><br>
> > > than that for you.<br>
><br>
<br>
> > I assume you mean something like #BB * #variables?<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>
> What CVP does is doable in linear time on number of variables *<br>
> lattice height. It has some memory cost to do this.<br>
<br>
> Assume for a second the lattice height is fixed (IE we do not have<br>
> completely symbolic ranges).<br>
<br>
> It is possible, in linear time, to build an SSA-like form for the<br>
> ranges it is computing.<br>
> It is then possible, in linear time, to propagate those ranges to all<br>
> affected variables.<br>
<br>
> This is O(N) + O(N).<br>
<br>
> Doing so may change the ranges (they only get *better*, however).<br>
> So you may need to do this until they fall all the way down the<br>
> lattice.<br>
<br>
> This means you may repeat this lattice height number of times.<br>
<br>
</div></div>What is the height of the lattice here?</blockquote><div><br></div><div>The current LVI is a bit hard to analyze, i'm not sure it's really as fixed height as one would think.</div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"> I understand that it goes from top -> defined -> overdefined, and that's three, but defined is not itself one state. Because it is tracking integer ranges, those ranges could undergo 2^#bits refinements in the worst case (thus making the lattice height quite large), no?<br></blockquote><div><br></div><div>If it tracks ranges on a per-bit basis, the max refinements for a given range is is O(bits * 3), assuming things do not go the wrong way on the lattice.</div><div><br></div><div>IE either they are underdefined, or they are 1, or they are 0, or they are overdefined.</div><div><br></div><div>The lattice is</div><div><br></div><div>underdefined</div><div> / \</div><div>0 1</div><div> \ /</div><div>overdefined</div><div><br></div><div>The only way to end up with 2**n refinements is if things can go the other direction on the lattice.</div><div><br></div><div>Note: This is the standard fixpoint algorithm (and what LVI is emulating, AFAIK). There are range constraint based solvers that are significantly more complicated, but that's not what LVI does.</div><div><br></div><div>(see <a href="https://www.cs.berkeley.edu/~daw/papers/range-tacas04.pdf">https://www.cs.berkeley.edu/~daw/papers/range-tacas04.pdf</a>, and the paper i cite below, which does a variant of that on llvm in pretty much linear time) </div><div><br></div><div>Also, the worst case here is one where every variable is affected by a single range.</div><div><br></div><div>(it's also possible to lazily construct the ssa form, and only update changed variables, in the same time bound. It's probably complicated enough to implement that it may not be worth it).</div><div><br></div><div>In practice, you can do even complicated ranges very fast.</div><div><br></div><div><a href="http://homepages.dcc.ufmg.br/~fernando/publications/papers/CGO13_raphael.pdf" target="_blank">http://homepages.dcc.ufmg.br/~fernando/publications/papers/CGO13_raphael.pdf</a></div><div><br>(the time is basically linear in practice, even for large programs, code is on github)</div><div><br></div><div>Ignore the part where they use it in the end for something else that we don't care about, etc.</div><div><br></div><div>They are also solving for a much more complex set of ranges than we are talking about for CVP, and for all the variables, so they use a real range constraint solver in the end instead of a fixpoint with a fixed height lattice.</div><div><br></div><div><br></div><div> </div><div><br></div></div></div></div>