<div dir="ltr"><div><span style="font-size:12.8000001907349px">[ My original reply was on hold because the attached ir is too big.  Here is the pure content without attachment. ]</span></div><div><span style="font-size:12.8000001907349px"><br></span></div><span style="font-size:12.8000001907349px">Thanks for the help!</span><div style="font-size:12.8000001907349px"><br></div><div style="font-size:12.8000001907349px">I looked at my three irs, the number of whose alloca instructions increases linearly.  That explains the quadratic time increase of the mem2reg.  The smallest ir ( >6M ) is attached if you are interested.</div><div style="font-size:12.8000001907349px"><br></div><div style="font-size:12.8000001907349px">Could you point to me the link to the recent bug fix on<span style="font-size:12.8000001907349px"> </span><span style="font-size:12.8000001907349px">the linear time IDF </span><span style="font-size:12.8000001907349px">computation?</span></div><div style="font-size:12.8000001907349px"><span style="font-size:12.8000001907349px"><br></span></div><div style="font-size:12.8000001907349px"><span style="font-size:12.8000001907349px">Regards,</span></div><div style="font-size:12.8000001907349px"><span style="font-size:12.8000001907349px">-Peng</span></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Aug 17, 2015 at 3:24 PM, Daniel Berlin <span dir="ltr"><<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">It should be linear per-alloca, which will make it quadtraic overall.<br>
<br>
It could be made linear overall by reusing info or not pruning (but<br>
we'd have to do bitvector dataflow for computing live-in blocks, etc),<br>
but it's trickier.<br>
<br>
There was also a recent bug discovered in the linear time IDF<br>
computation used to place phi nodes that made it quadratic in some<br>
cases. This has been made linear again, and testcases added to show it<br>
is linear :)<br>
<br>
If you have cases where it is slow, that would be interesting to see.<br>
<div><div class="h5"><br>
<br>
On Mon, Aug 17, 2015 at 12:14 PM, Peng Cheng via llvm-dev<br>
<<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<br>
> The reason I asked this is that I observed some data which shows the<br>
> complexity of "mem2reg" is more than linear.  So, I would like to confirm<br>
> whether that is expected behavior.<br>
><br>
> Thanks!<br>
> -Peng<br>
><br>
> On Mon, Aug 17, 2015 at 3:13 PM, Peng Cheng <<a href="mailto:gm4cheng@gmail.com">gm4cheng@gmail.com</a>> wrote:<br>
>><br>
>> Does anyone know what is the complexity of the "mem2erg" optimization on<br>
>> llvm ir?<br>
>><br>
>> Is it linear or quadratic?<br>
>><br>
>> Regards,<br>
>> -Peng<br>
><br>
><br>
><br>
</div></div>> _______________________________________________<br>
> LLVM Developers mailing list<br>
> <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>         <a href="http://llvm.cs.uiuc.edu" rel="noreferrer" target="_blank">http://llvm.cs.uiuc.edu</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>
><br>
</blockquote></div><br></div>