[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

diff --git a/lib/Transforms/IPO/GlobalOpt.cpp b/lib/Transforms/IPO/GlobalOpt.cpp
index ddfc52273ca02346d78b88934898ac1a1ac3d247..812ee243738a239e4bb3cff52fa7b292f9119754 100644 (file)
--- 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<const Comdat *, 8> NotDiscardableComdats;
   };
@@ -1770,6 +1771,19 @@ bool GlobalOpt::isPointerValueDeadOnEntryToFunction(const Function *F, GlobalVal
   auto &DT = getAnalysis<DominatorTreeWrapperPass>(*const_cast<Function *>(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) {