[MemDep] Reduce block limit

[nikic]

Summary

The non-local MemDep analysis has a limit on the number of blocks it will scan trying to find dependencies. The current limit of 1000 is ridiculously high, especially when we consider that each block scan can also visit up to 100 instructions. In degenerate cases (where we actually scan that many blocks) MemDep/GVN dominate overall compile-time, for little benefit.

This patch reduces the limit to 100, which is probably still too large, but at least avoids some of the more catastrophic cases. (For comparison, MSSA clobber walks consider up to 100 MemoryDefs/MemoryPhis, rather than 100 blocks * 100 instructions, but these limits aren't directly comparable.)

The impact on relevant GVN statistics from llvm-test-suite is as follows:

                   |   Old |   New |  Diff
gvn.NumGVNLoad     | 19298 | 19246 | -0.27%
gvn.NumPRELoad     | 13983 | 13963 | -0.14%
gvn.NumPRELoopLoad |   703 |   702 | -0.14%

The impact on compile-time is as follows: http://llvm-compile-time-tracker.com/compare.php?from=92619956eb27ef08dd24045307593fc3d7f78db0&to=675a7cdab6ef84b994b00b2d0e2f146634056c9d&stat=instructions:u

        | geomean
O3      |  -0.30%
ThinLTO |  -0.52%
LTO-g   |  -0.95%

In addition to the average improvement, this also fixes some degenerate cases. For example, libclamav_htmlnorm.c improves by 13-23%, depending on build configuration.

I know that we were kind of hoping that this issue would resolve itself in time, either by a switch to NewGVN or use of MSSA in GVN. But I think we should still address this in the meantime. Additionally, a switch to an MSSA-based implementation will effectively be doing this as well, in a roundabout way (by dint of MSSA having lower cutoffs than MDA).

[asbirlea]

Reducing this limit is certainly the right thing to do. To what value so as to not cause large regressions is a question I'd like to answer with some experimental data.
I'll start some experiments and come back to this.

[nikic]

In D140097#3998241, @asbirlea wrote:

Reducing this limit is certainly the right thing to do. To what value so as to not cause large regressions is a question I'd like to answer with some experimental data.
I'll start some experiments and come back to this.

Thanks!

[asbirlea]

I'm seeing one instance of increase in compile-time with the 100 limit and a couple of small run time regressions. The results look somewhat cleaner with a cap of 300. Could we use 300 as an intermediate step?

[nikic]

Default to 300 blocks.

Compile-time results for this are a bit underwhelming, but I guess it doesn't hurt to start conservatively: http://llvm-compile-time-tracker.com/compare.php?from=cc845e9de8c87c74d494f4e90e8fcf4fca264989&to=1b691111c3e80929268c8b749470d2b5bfad6f9d&stat=instructions:u

Did you happen to also try 200 blocks?

[asbirlea]

I did now and it also looks clean. Commit with 200?

llvm/lib/Analysis/MemoryDependenceAnalysis.cpp

 // Limit for the number of instructions to scan in a block.
 
 static cl::opt<unsigned> BlockScanLimit(
     "memdep-block-scan-limit", cl::Hidden, cl::init(100),
     cl::desc("The number of instructions to scan in a block in memory "
              "dependency analysis (default = 100)"));
 
 static cl::opt<unsigned>
-    BlockNumberLimit("memdep-block-number-limit", cl::Hidden, cl::init(1000),
+    BlockNumberLimit("memdep-block-number-limit", cl::Hidden, cl::init(200),
                      cl::desc("The number of blocks to scan during memory "
-                              "dependency analysis (default = 1000)"));
+                              "dependency analysis (default = 200)"));
 
 // Limit on the number of memdep results to process.
 static const unsigned int NumResultsLimit = 100;
 
 /// This is a helper function that removes Val from 'Inst's set in ReverseMap.
 ///
 /// If the set becomes empty, remove Inst's entry.
 template <typename KeyTy>