[llvm-dev] complexity of "mem2reg"?

[Peng Cheng via llvm-dev]

[ 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
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
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150817/f93582fb/attachment.html>