[SCCP] Reduce the number of times ResolvedUndefsIn is called for large modules.
authorEli Friedman <efriedma@quicinc.com>
Thu, 8 Oct 2020 23:04:28 +0000 (16:04 -0700)
committerEli Friedman <efriedma@quicinc.com>
Fri, 9 Oct 2020 22:24:16 +0000 (15:24 -0700)
commit278299b0f0b0e47df95d526c95b42fa69667295c
treeb1a594b596f56c36fe0b9912247794b3059aca41
parent360f275cb7895205d7debab7a7d7bdceea42fb0c
[SCCP] Reduce the number of times ResolvedUndefsIn is called for large modules.

If a module has many values that need to be resolved by
ResolvedUndefsIn, compilation takes quadratic time overall. Solve should
do a small amount of work, since not much is added to the worklists each
time markOverdefined is called. But ResolvedUndefsIn is linear over the
length of the function/module, so resolving one undef at a time is
quadratic in general.

To solve this, make ResolvedUndefsIn resolve every undef value at once,
instead of resolving them one at a time. This loses a little
optimization power, but can be a lot faster.

We still need a loop around ResolvedUndefsIn because markOverdefined
could change the set of blocks that are live. That should be uncommon,
hopefully. We could optimize it by tracking which blocks transition from
dead to live, instead of iterating over the whole module to find them.
But I'll leave that for later. (The whole function will become a lot
simpler once we start pruning branches on undef.)

The regression test changes seem minor. The specific cases in question
could probably be optimized with a bit more work, but they seem like
edge cases that don't really matter.

Fixes an "infinite" compile issue my team found on an internal workoad.

Differential Revision: https://reviews.llvm.org/D89080
llvm/lib/Transforms/Scalar/SCCP.cpp
llvm/test/Transforms/SCCP/2004-12-10-UndefBranchBug.ll
llvm/test/Transforms/SCCP/resolvedundefsin-tracked-fn.ll