[llvm-dev] complexity of "mem2reg"?
Daniel Berlin via llvm-dev
llvm-dev at lists.llvm.org
Mon Aug 17 12:57:21 PDT 2015
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
> 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
More information about the llvm-dev