[llvm-dev] complexity of "mem2reg"?

[Daniel Berlin via llvm-dev]

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
>