summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTom Stellard <tstellar@redhat.com>2018-11-20 03:42:43 +0000
committerTom Stellard <tstellar@redhat.com>2018-11-20 03:42:43 +0000
commite4023f8c634cb857649ef80786adf1dcc9f2005a (patch)
tree718ecd900444a0f1a51970a01843be73be46bc6d
parente3cd69e00b5c8c9c91fe640e7538f4e85436da7d (diff)
downloadbcm5719-llvm-e4023f8c634cb857649ef80786adf1dcc9f2005a.tar.gz
bcm5719-llvm-e4023f8c634cb857649ef80786adf1dcc9f2005a.zip
Merging r345353:
------------------------------------------------------------------------ r345353 | sima | 2018-10-25 18:28:36 -0700 (Thu, 25 Oct 2018) | 21 lines 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: 347285
-rw-r--r--llvm/include/llvm/Support/GenericDomTreeConstruction.h14
1 files changed, 14 insertions, 0 deletions
diff --git a/llvm/include/llvm/Support/GenericDomTreeConstruction.h b/llvm/include/llvm/Support/GenericDomTreeConstruction.h
index 103ff8ca476..977f209f92b 100644
--- a/llvm/include/llvm/Support/GenericDomTreeConstruction.h
+++ b/llvm/include/llvm/Support/GenericDomTreeConstruction.h
@@ -1186,6 +1186,20 @@ struct SemiNCAInfo {
<< '\t' << U << "\n");
LLVM_DEBUG(dbgs() << "\n");
+ // Recalculate the DominatorTree when the number of updates
+ // exceeds a threshold, which usually makes direct updating slower than
+ // recalculation. We select this threshold proportional to the
+ // size of the DominatorTree. The constant is selected
+ // by choosing the one with an acceptable performance on some real-world
+ // inputs.
+
+ // Make unittests of the incremental algorithm work
+ if (DT.DomTreeNodes.size() <= 100) {
+ if (NumLegalized > DT.DomTreeNodes.size())
+ CalculateFromScratch(DT, &BUI);
+ } else if (NumLegalized > DT.DomTreeNodes.size() / 40)
+ CalculateFromScratch(DT, &BUI);
+
// If the DominatorTree was recalculated at some point, stop the batch
// updates. Full recalculations ignore batch updates and look at the actual
// CFG.
OpenPOWER on IntegriCloud