[llvm-dev] complexity of "mem2reg"?
Peng Cheng via llvm-dev
llvm-dev at lists.llvm.org
Mon Aug 17 12:56:52 PDT 2015
[ My original reply was on hold because the attached ir is too big. Here
is the pure content without attachment. ]
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
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the llvm-dev