[ADCE][NFC] Batch DT updates together
authorQuentin Colombet <qcolombet@apple.com>
Wed, 5 Jan 2022 21:48:50 +0000 (13:48 -0800)
committerQuentin Colombet <qcolombet@apple.com>
Wed, 5 Jan 2022 22:05:20 +0000 (14:05 -0800)
commitcdbad62c526c5b7e13f634b9d6bc54f2a01aabc0
treea115a07fc150835e725a83e6230c0ee1dcced6e5
parentcfcd7af8deb8a02c3832e211905dcb30dd04dc1d
[ADCE][NFC] Batch DT updates together

This patch delayed the updates of the dominator tree to the very end of
the pass instead of doing that in small increments after each basic
block.

This improves the runtime of the pass in particular in pathological
cases because now the updater sees the full extend of the updates and
can decide whether it is faster to apply the changes incrementally or
just recompute the full tree from scratch.

Put differently, thanks to this patch, we can take advantage of the
improvements that Chijun Sima <simachijun@gmail.com> made in the
dominator tree updater a while ago with commit 32fd196cbf4d: "Teach the
DominatorTree fallback to recalculation when applying updates to speedup
JT (PR37929)".

This change is NFC but can improve the runtime of the compiler
dramatically in some pathological cases (where the pass was pushing a
lot (several thousands) of small updates (less than 6)).

For instance on the motivating example we went from 300+ sec to less
than a second.

Differential Revision: https://reviews.llvm.org/D116610
llvm/lib/Transforms/Scalar/ADCE.cpp