From 8b4675ffaa2ed4ea5dbb1add12e9f580409ebb61 Mon Sep 17 00:00:00 2001 From: James Molloy Date: Mon, 16 Nov 2015 10:16:22 +0000 Subject: [PATCH] [GlobalOpt] Address post-commit review comments on r253168 Address Duncan Exon Smith's comments on D14148, which was added after the patch had been LGTM'd and committed: * clang-format one area where whitespace diffs occurred. * Add a threshold to limit the store/load dominance checks as they are quadratic. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@253192 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/IPO/GlobalOpt.cpp | 20 +++++++++++++++++--- 1 file changed, 17 insertions(+), 3 deletions(-) diff --git a/lib/Transforms/IPO/GlobalOpt.cpp b/lib/Transforms/IPO/GlobalOpt.cpp index ddfc52273ca..812ee243738 100644 --- a/lib/Transforms/IPO/GlobalOpt.cpp +++ b/lib/Transforms/IPO/GlobalOpt.cpp @@ -87,9 +87,10 @@ namespace { bool ProcessInternalGlobal(GlobalVariable *GV,Module::global_iterator &GVI, const GlobalStatus &GS); bool OptimizeEmptyGlobalCXXDtors(Function *CXAAtExitFn); - - bool isPointerValueDeadOnEntryToFunction(const Function *F, GlobalValue *GV); - + + bool isPointerValueDeadOnEntryToFunction(const Function *F, + GlobalValue *GV); + TargetLibraryInfo *TLI; SmallSet NotDiscardableComdats; }; @@ -1770,6 +1771,19 @@ bool GlobalOpt::isPointerValueDeadOnEntryToFunction(const Function *F, GlobalVal auto &DT = getAnalysis(*const_cast(F)) .getDomTree(); + // The below check is quadratic. Check we're not going to do too many tests. + // FIXME: Even though this will always have worst-case quadratic time, we + // could put effort into minimizing the average time by putting stores that + // have been shown to dominate at least one load at the beginning of the + // Stores array, making subsequent dominance checks more likely to succeed + // early. + // + // The threshold here is fairly large because global->local demotion is a + // very powerful optimization should it fire. + const unsigned Threshold = 100; + if (Loads.size() * Stores.size() > Threshold) + return false; + for (auto *L : Loads) { auto *LTy = L->getType(); if (!std::any_of(Stores.begin(), Stores.end(), [&](StoreInst *S) { -- 2.34.1