LoopRotate compile-time regression due to MemorySSA

[nikic]

Bugzilla Link	44889
Resolution	FIXED
Resolved on	Mar 04, 2020 12:55
Version	10.0
OS	Linux
Blocks	#43900
Attachments	Large bitcode test case
CC	@alinas,@zmodem,@RKSimon

Extended Description

Running the given test-case through opt -O3 gives the following timings for loop rotation passes:

0.4672 ( 5.1%) 0.0079 ( 1.4%) 0.4751 ( 4.9%) 0.4750 ( 4.9%) Rotate Loops #​2
0.1104 ( 1.2%) 0.0052 ( 0.9%) 0.1156 ( 1.2%) 0.1155 ( 1.2%) Rotate Loops

With with opt -O3 -enable-mssa-loop-dependency=0 we get:

0.0944 ( 0.9%) 0.0037 ( 0.7%) 0.0981 ( 0.9%) 0.0980 ( 0.9%) Rotate Loops #​2
0.0394 ( 0.4%) 0.0017 ( 0.3%) 0.0411 ( 0.4%) 0.0409 ( 0.4%) Rotate Loops

That is, loop rotation has become 5x more expensive with MemorySSA enabled. Presumably updating MemorySSA during loop rotation is very expensive.

This is one of the large compile-time regressions we've observed when trying to upgrade to LLVM 10 in rust. You can see the full impact of enabling MemorySSA (all else being equal) on end-to-end compile times at https://perf.rust-lang.org/compare.html?start=9993408439c871c1bc0c0bac3b3008b24039443c&end=52e999afd3be3341463f3b87be02f2bcfb381c17.

[alinas]

Just to clarify, this is due to verifications, so for a build with assertions enabled and not a release-noasserts build. This is what I'm seeing as far as timings, and the patch in https://reviews.llvm.org/D74505 seems to confirm this, but please let me know if this is not the case.

[nikic]

Sorry for being unclear on this point: This is for a release build with assertions disabled.

[zmodem]

Is there any progress here?

[alinas]

I believe patch D74574 should have fixed this.

I updated #43753 , but missed also updating this. The last timings I ran are the ones in #43753 .
time bin/opt -O3 -enable-mssa-loop-dependency=true ~/extracted.bc
real 0m5.774s
time bin/opt -O3 -enable-mssa-loop-dependency=false ~/extracted.bc
real 0m5.701s

Nikita, could you please confirm this is resolved for you?

[nikic]

As mentioned on the other bug report, while there is still a bit of regression due to MemorySSA, the largest part of it is mitigated now, so I'll mark this as resolved.