[MemDep] Reduce block limit
authorNikita Popov <npopov@redhat.com>
Thu, 15 Dec 2022 13:05:00 +0000 (14:05 +0100)
committerNikita Popov <npopov@redhat.com>
Fri, 13 Jan 2023 09:40:30 +0000 (10:40 +0100)
commitd734edfe7c13d1b8e32d75a5df897ef0d9b69302
tree1002559678cb5360e238cd8900d949ee6880e895
parentb39a9a94f420a25a239ae03097c255900cbd660e
[MemDep] Reduce block limit

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 very 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 200, which is probably still too
large, but at least mitigates some of the more catastrophic cases.
(For comparison, MSSA clobber walks consider up to 100
MemoryDefs/MemoryPhis, rather than 200 blocks * 100 instructions,
but these limits aren't directly comparable.)

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).

Differential Revision: https://reviews.llvm.org/D140097
llvm/lib/Analysis/MemoryDependenceAnalysis.cpp