When MemoryDependenceAnalysis hits a CFG with many transparent blocks, the algorithm easily degrades into quadratic memory and time complexity. The easiest example is a long chain of BBs that don't otherwise use a location. The caching will add an entry for every intermediate block and limiting the number of results doesn't help as no results are produced until a definition is found.
When MemoryDependenceAnalysis hits a CFG with many transparent blocks,
the algorithm easily degrades into quadratic memory and time complexity.
The easiest example is a long chain of BBs that don't otherwise use a
location. The caching will add an entry for every intermediate block and
limiting the number of results doesn't help as no results are produced
until a definition is found.

Introduce a limit similar to the existing instructions-per-block limit.
This limit counts the total number of blocks checked. If the limit is
reached, entries are considered unknown. The initial value is 1000,
which avoids regressions for normal sized functions while still
limiting edge cases to reasnable memory consumption and execution time.

Differential Revision: http://reviews.llvm.org/D16123


git-svn-id: 0ff597fd157e6f4fc38580e8d64ab130330d2411@261430 91177308-0d34-0410-b5e6-96231b3b80d8

llvm-mirror/llvm,GPUOpen-Drivers/llvm,llvm-mirror/llvm,apple/swift-llvm,GPUOpen-Drivers/llvm,apple/swift-llvm,llvm-mirror/llvm,GPUOpen-Drivers/llvm,llvm-mirror/llvm,apple/swift-llvm,llvm-mirror/llvm,llvm-mirror/llvm,llvm-mirror/llvm,GPUOpen-Drivers/llvm,llvm-mirror/llvm,GPUOpen-Drivers/llvm,apple/swift-llvm,GPUOpen-Drivers/llvm,GPUOpen-Drivers/llvm,apple/swift-llvm,apple/swift-llvm,apple/swift-llvm,apple/swift-llvm,llvm-mirror/llvm,GPUOpen-Drivers/llvm