[llvm-dev] complexity of "mem2reg"?

[Daniel Berlin via 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
>> >
>
>