complexity of "mem2reg"?

Does anyone know what is the complexity of the “mem2erg” optimization on llvm ir?

Is it linear or quadratic?


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.


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 :slight_smile:

If you have cases where it is slow, that would be interesting to see.

[ 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?


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.