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)
commit32fd196cbf4d510aace7e42cf492b4dc2f3cd7e2
tree7b6e4462a79351a90468e8b61df97d194d05bba2
parent27e9fdb2ff4bf5a500bb75644247db2209b69dc0
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

llvm-svn: 345353
llvm/include/llvm/Support/GenericDomTreeConstruction.h