OSDN Git Service

Teach the DominatorTree fallback to recalculation when applying updates to speedup...
authorChijun Sima <simachijun@gmail.com>
Fri, 26 Oct 2018 01:28:36 +0000 (01:28 +0000)
committerChijun Sima <simachijun@gmail.com>
Fri, 26 Oct 2018 01:28:36 +0000 (01:28 +0000)
commit8b17cc87ef70db6c823318e35cb5a72f25f1e2aa
tree2c9a300ac018b558f7f925ece9276e16470a75af
parent23962bb2765b60e0aee02123dcd6faeaab0e0c5c
Teach the DominatorTree fallback to recalculation when applying updates to speedup JT (PR37929)

Summary:
This patch makes the dominatortree recalculate when applying updates with the size of the update vector larger than a threshold. Directly applying updates is usually slower than recalculating the whole domtree in this case. This patch fixes an issue which causes JT running slowly on some inputs.

In bug 37929, the dominator tree is trying to apply 19,000+ updates several times, which takes several minutes.

After this patch, the time used by DT.applyUpdates:

| Input | Before (s) | After (s) | Speedup |
| the 2nd Reproducer in 37929 | 297 | 0.15 | 1980x |
| clang-5.0.0.0.bc | 9.7 | 4.3 | 2.26x |
| clang-5.0.0.4.bc | 11.6 | 2.6 | 4.46x |

Reviewers: kuhar, brzycki, trentxintong, davide, dmgreen, grosser

Reviewed By: kuhar, brzycki

Subscribers: kristina, llvm-commits

Differential Revision: https://reviews.llvm.org/D53245

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@345353 91177308-0d34-0410-b5e6-96231b3b80d8
include/llvm/Support/GenericDomTreeConstruction.h