ArgList: cache index ranges containing arguments with each ID

Improve performance of argument list parsing with large numbers of IDs and
large numbers of arguments, by tracking a conservative range of indexes within
the argument list that might contain an argument with each ID. In the worst
case (when the first and last argument with a given ID are at the opposite ends
of the argument list), this still results in a linear-time walk of the list,
but it helps substantially in the common case where each ID occurs only once,
or a few times close together in the list.

This gives a ~10x speedup to clang's `test/Driver/response-file.c`, which
constructs a very large set of command line arguments and feeds them to the
clang driver.

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


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@300135 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 33 insertions, 193 deletions

diff --git a/lib/Option/ArgList.cpp b/lib/Option/ArgList.cpp
index 7ff358a57e0..39dbce87f9a 100644
--- a/lib/Option/ArgList.cpp
+++ b/lib/Option/ArgList.cpp
@@ -19,203 +19,44 @@
 using namespace llvm;
 using namespace llvm::opt;
 
-void arg_iterator::SkipToNextArg() {
-  for (; Current != Args.end(); ++Current) {
-    // Done if there are no filters.
-    if (!Id0.isValid())
-      break;
-
-    // Otherwise require a match.
-    const Option &O = (*Current)->getOption();
-    if (O.matches(Id0) ||
-        (Id1.isValid() && O.matches(Id1)) ||
-        (Id2.isValid() && O.matches(Id2)))
-      break;
-  }
-}
-
 void ArgList::append(Arg *A) {
   Args.push_back(A);
-}
-
-void ArgList::eraseArg(OptSpecifier Id) {
-  Args.erase(
-      remove_if(*this, [=](Arg *A) { return A->getOption().matches(Id); }),
-      end());
-}
-
-Arg *ArgList::getLastArgNoClaim(OptSpecifier Id) const {
-  // FIXME: Make search efficient?
-  for (const_reverse_iterator it = rbegin(), ie = rend(); it != ie; ++it)
-    if ((*it)->getOption().matches(Id))
-      return *it;
-  return nullptr;
-}
-
-Arg *ArgList::getLastArgNoClaim(OptSpecifier Id0, OptSpecifier Id1) const {
-  // FIXME: Make search efficient?
-  for (const_reverse_iterator it = rbegin(), ie = rend(); it != ie; ++it)
-    if ((*it)->getOption().matches(Id0) ||
-        (*it)->getOption().matches(Id1))
-      return *it;
-  return nullptr;
-}
-
-Arg *ArgList::getLastArgNoClaim(OptSpecifier Id0, OptSpecifier Id1,
-                                OptSpecifier Id2) const {
-  // FIXME: Make search efficient?
-  for (const_reverse_iterator it = rbegin(), ie = rend(); it != ie; ++it)
-    if ((*it)->getOption().matches(Id0) || (*it)->getOption().matches(Id1) ||
-        (*it)->getOption().matches(Id2))
-      return *it;
-  return nullptr;
-}
-
-Arg *ArgList::getLastArgNoClaim(OptSpecifier Id0, OptSpecifier Id1,
-                                OptSpecifier Id2, OptSpecifier Id3) const {
-  // FIXME: Make search efficient?
-  for (const_reverse_iterator it = rbegin(), ie = rend(); it != ie; ++it)
-    if ((*it)->getOption().matches(Id0) || (*it)->getOption().matches(Id1) ||
-        (*it)->getOption().matches(Id2) || (*it)->getOption().matches(Id3))
-      return *it;
-  return nullptr;
-}
-
-Arg *ArgList::getLastArg(OptSpecifier Id) const {
-  Arg *Res = nullptr;
-  for (const_iterator it = begin(), ie = end(); it != ie; ++it) {
-    if ((*it)->getOption().matches(Id)) {
-      Res = *it;
-      Res->claim();
-    }
-  }
 
-  return Res;
-}
-
-Arg *ArgList::getLastArg(OptSpecifier Id0, OptSpecifier Id1) const {
-  Arg *Res = nullptr;
-  for (const_iterator it = begin(), ie = end(); it != ie; ++it) {
-    if ((*it)->getOption().matches(Id0) ||
-        (*it)->getOption().matches(Id1)) {
-      Res = *it;
-      Res->claim();
-
-    }
+  // Update ranges for the option and all of its groups.
+  for (Option O = A->getOption().getUnaliasedOption(); O.isValid();
+       O = O.getGroup()) {
+    auto &R =
+        OptRanges.insert(std::make_pair(O.getID(), emptyRange())).first->second;
+    R.first = std::min<unsigned>(R.first, Args.size() - 1);
+    R.second = Args.size();
   }
-
-  return Res;
 }
 
-Arg *ArgList::getLastArg(OptSpecifier Id0, OptSpecifier Id1,
-                         OptSpecifier Id2) const {
-  Arg *Res = nullptr;
-  for (const_iterator it = begin(), ie = end(); it != ie; ++it) {
-    if ((*it)->getOption().matches(Id0) ||
-        (*it)->getOption().matches(Id1) ||
-        (*it)->getOption().matches(Id2)) {
-      Res = *it;
-      Res->claim();
-    }
-  }
-
-  return Res;
-}
-
-Arg *ArgList::getLastArg(OptSpecifier Id0, OptSpecifier Id1,
-                         OptSpecifier Id2, OptSpecifier Id3) const {
-  Arg *Res = nullptr;
-  for (const_iterator it = begin(), ie = end(); it != ie; ++it) {
-    if ((*it)->getOption().matches(Id0) ||
-        (*it)->getOption().matches(Id1) ||
-        (*it)->getOption().matches(Id2) ||
-        (*it)->getOption().matches(Id3)) {
-      Res = *it;
-      Res->claim();
-    }
-  }
-
-  return Res;
-}
-
-Arg *ArgList::getLastArg(OptSpecifier Id0, OptSpecifier Id1,
-                         OptSpecifier Id2, OptSpecifier Id3,
-                         OptSpecifier Id4) const {
-  Arg *Res = nullptr;
-  for (const_iterator it = begin(), ie = end(); it != ie; ++it) {
-    if ((*it)->getOption().matches(Id0) ||
-        (*it)->getOption().matches(Id1) ||
-        (*it)->getOption().matches(Id2) ||
-        (*it)->getOption().matches(Id3) ||
-        (*it)->getOption().matches(Id4)) {
-      Res = *it;
-      Res->claim();
-    }
-  }
-
-  return Res;
-}
-
-Arg *ArgList::getLastArg(OptSpecifier Id0, OptSpecifier Id1,
-                         OptSpecifier Id2, OptSpecifier Id3,
-                         OptSpecifier Id4, OptSpecifier Id5) const {
-  Arg *Res = nullptr;
-  for (const_iterator it = begin(), ie = end(); it != ie; ++it) {
-    if ((*it)->getOption().matches(Id0) ||
-        (*it)->getOption().matches(Id1) ||
-        (*it)->getOption().matches(Id2) ||
-        (*it)->getOption().matches(Id3) ||
-        (*it)->getOption().matches(Id4) ||
-        (*it)->getOption().matches(Id5)) {
-      Res = *it;
-      Res->claim();
-    }
-  }
-
-  return Res;
-}
-
-Arg *ArgList::getLastArg(OptSpecifier Id0, OptSpecifier Id1,
-                         OptSpecifier Id2, OptSpecifier Id3,
-                         OptSpecifier Id4, OptSpecifier Id5,
-                         OptSpecifier Id6) const {
-  Arg *Res = nullptr;
-  for (const_iterator it = begin(), ie = end(); it != ie; ++it) {
-    if ((*it)->getOption().matches(Id0) ||
-        (*it)->getOption().matches(Id1) ||
-        (*it)->getOption().matches(Id2) ||
-        (*it)->getOption().matches(Id3) ||
-        (*it)->getOption().matches(Id4) ||
-        (*it)->getOption().matches(Id5) ||
-        (*it)->getOption().matches(Id6)) {
-      Res = *it;
-      Res->claim();
-    }
+void ArgList::eraseArg(OptSpecifier Id) {
+  // Zero out the removed entries but keep them around so that we don't
+  // need to invalidate OptRanges.
+  for (Arg *const &A : filtered(Id)) {
+    // Avoid the need for a non-const filtered iterator variant.
+    Arg **ArgsBegin = Args.data();
+    ArgsBegin[&A - ArgsBegin] = nullptr;
   }
-
-  return Res;
+  OptRanges.erase(Id.getID());
 }
 
-Arg *ArgList::getLastArg(OptSpecifier Id0, OptSpecifier Id1,
-                         OptSpecifier Id2, OptSpecifier Id3,
-                         OptSpecifier Id4, OptSpecifier Id5,
-                         OptSpecifier Id6, OptSpecifier Id7) const {
-  Arg *Res = nullptr;
-  for (const_iterator it = begin(), ie = end(); it != ie; ++it) {
-    if ((*it)->getOption().matches(Id0) ||
-        (*it)->getOption().matches(Id1) ||
-        (*it)->getOption().matches(Id2) ||
-        (*it)->getOption().matches(Id3) ||
-        (*it)->getOption().matches(Id4) ||
-        (*it)->getOption().matches(Id5) ||
-        (*it)->getOption().matches(Id6) ||
-        (*it)->getOption().matches(Id7)) {
-      Res = *it;
-      Res->claim();
+ArgList::OptRange
+ArgList::getRange(std::initializer_list<OptSpecifier> Ids) const {
+  OptRange R = emptyRange();
+  for (auto Id : Ids) {
+    auto I = OptRanges.find(Id.getID());
+    if (I != OptRanges.end()) {
+      R.first = std::min(R.first, I->second.first);
+      R.second = std::max(R.second, I->second.second);
     }
   }
-
-  return Res;
+  // Map an empty {-1, 0} range to {0, 0} so it can be used to form iterators.
+  if (R.first == -1u)
+    R.first = 0;
+  return R;
 }
 
 bool ArgList::hasFlag(OptSpecifier Pos, OptSpecifier Neg, bool Default) const {
@@ -231,8 +72,7 @@ bool ArgList::hasFlag(OptSpecifier Pos, OptSpecifier PosAlias, OptSpecifier Neg,
   return Default;
 }
 
-StringRef ArgList::getLastArgValue(OptSpecifier Id,
-                                         StringRef Default) const {
+StringRef ArgList::getLastArgValue(OptSpecifier Id, StringRef Default) const {
   if (Arg *A = getLastArg(Id))
     return A->getValue();
   return Default;
@@ -262,7 +102,7 @@ void ArgList::AddLastArg(ArgStringList &Output, OptSpecifier Id0,
 void ArgList::AddAllArgsExcept(ArgStringList &Output,
                                ArrayRef<OptSpecifier> Ids,
                                ArrayRef<OptSpecifier> ExcludeIds) const {
-  for (const Arg *Arg : Args) {
+  for (const Arg *Arg : *this) {
     bool Excluded = false;
     for (OptSpecifier Id : ExcludeIds) {
       if (Arg->getOption().matches(Id)) {
@@ -325,14 +165,14 @@ void ArgList::AddAllArgsTranslated(ArgStringList &Output, OptSpecifier Id0,
 }
 
 void ArgList::ClaimAllArgs(OptSpecifier Id0) const {
-  for (auto Arg : filtered(Id0))
+  for (auto *Arg : filtered(Id0))
     Arg->claim();
 }
 
 void ArgList::ClaimAllArgs() const {
-  for (const_iterator it = begin(), ie = end(); it != ie; ++it)
-    if (!(*it)->isClaimed())
-      (*it)->claim();
+  for (auto *Arg : *this)
+    if (!Arg->isClaimed())
+      Arg->claim();
 }
 
 const char *ArgList::GetOrMakeJoinedArgString(unsigned Index,