llvm dev - Aug 2015 - complexity of "mem2reg"?

Does anyone know what is the complexity of the "mem2erg" optimization
on
llvm ir?

Is it linear or quadratic?

Regards,
-Peng
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150817/c3b210f1/attachment.html>

The reason I asked this is that I observed some data which shows the
complexity of "mem2reg" is more than linear.  So, I would like to
confirm
whether that is expected behavior.

Thanks!
-Peng

On Mon, Aug 17, 2015 at 3:13 PM, Peng Cheng <gm4cheng at gmail.com> wrote:
> Does anyone know what is the complexity of the "mem2erg"
optimization on
> llvm ir?
>
> Is it linear or quadratic?
>
> Regards,
> -Peng
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150817/bd5de014/attachment.html>

It should be linear per-alloca, which will make it quadtraic overall.

It could be made linear overall by reusing info or not pruning (but
we'd have to do bitvector dataflow for computing live-in blocks, etc),
but it's trickier.

There was also a recent bug discovered in the linear time IDF
computation used to place phi nodes that made it quadratic in some
cases. This has been made linear again, and testcases added to show it
is linear :)

If you have cases where it is slow, that would be interesting to see.


On Mon, Aug 17, 2015 at 12:14 PM, Peng Cheng via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> The reason I asked this is that I observed some data which shows the
> complexity of "mem2reg" is more than linear.  So, I would like to
confirm
> whether that is expected behavior.
>
> Thanks!
> -Peng
>
> On Mon, Aug 17, 2015 at 3:13 PM, Peng Cheng <gm4cheng at gmail.com>
wrote:
>>
>> Does anyone know what is the complexity of the "mem2erg"
optimization on
>> llvm ir?
>>
>> Is it linear or quadratic?
>>
>> Regards,
>> -Peng
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org         http://llvm.cs.uiuc.edu
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>

April 10th, look for message from Cameron Zwarich titled "[PATCH]
Improvements to SSA construction"

I later also added a python program to generate ladder graphs (the
worst case for the iterated dominance frontiers algorithm) to test it.



On Mon, Aug 17, 2015 at 12:53 PM, Peng Cheng <gm4cheng at gmail.com>
wrote:
> Thanks for the help!
>
> 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.
>
> Could you point to me the link to the recent bug fix on the linear time IDF
> computation?
>
> Regards,
> -Peng
>
>
> On Mon, Aug 17, 2015 at 3:24 PM, Daniel Berlin <dberlin at
dberlin.org> wrote:
>>
>> It should be linear per-alloca, which will make it quadtraic overall.
>>
>> It could be made linear overall by reusing info or not pruning (but
>> we'd have to do bitvector dataflow for computing live-in blocks,
etc),
>> but it's trickier.
>>
>> There was also a recent bug discovered in the linear time IDF
>> computation used to place phi nodes that made it quadratic in some
>> cases. This has been made linear again, and testcases added to show it
>> is linear :)
>>
>> If you have cases where it is slow, that would be interesting to see.
>>
>>
>> On Mon, Aug 17, 2015 at 12:14 PM, Peng Cheng via llvm-dev
>> <llvm-dev at lists.llvm.org> wrote:
>> > The reason I asked this is that I observed some data which shows
the
>> > complexity of "mem2reg" is more than linear.  So, I
would like to
>> > confirm
>> > whether that is expected behavior.
>> >
>> > Thanks!
>> > -Peng
>> >
>> > On Mon, Aug 17, 2015 at 3:13 PM, Peng Cheng <gm4cheng at
gmail.com> wrote:
>> >>
>> >> Does anyone know what is the complexity of the
"mem2erg" optimization
>> >> on
>> >> llvm ir?
>> >>
>> >> Is it linear or quadratic?
>> >>
>> >> Regards,
>> >> -Peng
>> >
>> >
>> >
>> > _______________________________________________
>> > LLVM Developers mailing list
>> > llvm-dev at lists.llvm.org         http://llvm.cs.uiuc.edu
>> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>> >
>
>