ArgList: cache index ranges containing arguments with each ID

[rsmith]

Summary

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.

In passing I also converted the interface to use variadic templates. I can split those changes into a separate patch if you'd prefer.

[rnk]

I agree with your analysis on the mailing list, let's go with this change as is. Keeping maps of range is super simple. Keeping a map of lists that need to be merged on demand makes temporary data structures, which might be slow, and isn't a clear win.

llvm/trunk/include/llvm/Option/ArgList.h

 //===--- ArgList.h - Argument List Management -------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_OPTION_ARGLIST_H
 #define LLVM_OPTION_ARGLIST_H
 
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Option/Arg.h"
 #include "llvm/Option/OptSpecifier.h"
 #include "llvm/Option/Option.h"
 #include <list>
 #include <memory>
 #include <string>
 #include <vector>
 
 namespace llvm {
 namespace opt {
 class ArgList;
 class Option;
 
 /// arg_iterator - Iterates through arguments stored inside an ArgList.
+template<typename BaseIter, unsigned NumOptSpecifiers = 0>
 class arg_iterator {
-  /// The current argument.
-  SmallVectorImpl<Arg*>::const_iterator Current;
+  /// The current argument and the end of the sequence we're iterating.
+  BaseIter Current, End;
 
-  /// The argument list we are iterating over.
-  const ArgList &Args;
+  /// Optional filters on the arguments which will be match. To avoid a
+  /// zero-sized array, we store one specifier even if we're asked for none.
+  OptSpecifier Ids[NumOptSpecifiers ? NumOptSpecifiers : 1];
 
-  /// Optional filters on the arguments which will be match. Most clients
-  /// should never want to iterate over arguments without filters, so we won't
-  /// bother to factor this into two separate iterator implementations.
-  //
-  // FIXME: Make efficient; the idea is to provide efficient iteration over
-  // all arguments which match a particular id and then just provide an
-  // iterator combinator which takes multiple iterators which can be
-  // efficiently compared and returns them in order.
-  OptSpecifier Id0, Id1, Id2;
+  void SkipToNextArg() {
+    for (; Current != End; ++Current) {
+      // Skip erased elements.
+      if (!*Current)
+        continue;
+
+      // Done if there are no filters.
+      if (!NumOptSpecifiers)
+        return;
+
+      // Otherwise require a match.
+      const Option &O = (*Current)->getOption();
+      for (auto Id : Ids) {
+        if (!Id.isValid())
+          break;
+        if (O.matches(Id))
+          return;
+      }
+    }
+  }
 
-  void SkipToNextArg();
+  typedef std::iterator_traits<BaseIter> Traits;
 
 public:
-  typedef Arg * const *                 value_type;
-  typedef Arg * const &                 reference;
-  typedef Arg * const *                 pointer;
-  typedef std::forward_iterator_tag   iterator_category;
-  typedef std::ptrdiff_t              difference_type;
+  typedef typename Traits::value_type  value_type;
+  typedef typename Traits::reference   reference;
+  typedef typename Traits::pointer     pointer;
+  typedef std::forward_iterator_tag    iterator_category;
+  typedef std::ptrdiff_t               difference_type;
 
-  arg_iterator(SmallVectorImpl<Arg *>::const_iterator it, const ArgList &Args,
-               OptSpecifier Id0 = 0U, OptSpecifier Id1 = 0U,
-               OptSpecifier Id2 = 0U)
-      : Current(it), Args(Args), Id0(Id0), Id1(Id1), Id2(Id2) {
+  arg_iterator(
+      BaseIter Current, BaseIter End,
+      const OptSpecifier (&Ids)[NumOptSpecifiers ? NumOptSpecifiers : 1] = {})
+      : Current(Current), End(End) {
+    for (unsigned I = 0; I != NumOptSpecifiers; ++I)
+      this->Ids[I] = Ids[I];
     SkipToNextArg();
   }
 
+  // FIXME: This conversion function makes no sense.
   operator const Arg*() { return *Current; }
+
   reference operator*() const { return *Current; }
   pointer operator->() const { return Current; }
 
   arg_iterator &operator++() {
     ++Current;
     SkipToNextArg();
     return *this;
   }

 ///
 /// The ArgList class manages a list of Arg instances as well as
 /// auxiliary data and convenience methods to allow Tools to quickly
 /// check for the presence of Arg instances for a particular Option
 /// and to iterate over groups of arguments.
 class ArgList {
 public:
   typedef SmallVector<Arg*, 16> arglist_type;
-  typedef arglist_type::iterator iterator;
-  typedef arglist_type::const_iterator const_iterator;
-  typedef arglist_type::reverse_iterator reverse_iterator;
-  typedef arglist_type::const_reverse_iterator const_reverse_iterator;
+  typedef arg_iterator<arglist_type::iterator> iterator;
+  typedef arg_iterator<arglist_type::const_iterator> const_iterator;
+  typedef arg_iterator<arglist_type::reverse_iterator> reverse_iterator;
+  typedef arg_iterator<arglist_type::const_reverse_iterator>
+      const_reverse_iterator;
+
+  template<unsigned N> using filtered_iterator =
+      arg_iterator<arglist_type::const_iterator, N>;
+  template<unsigned N> using filtered_reverse_iterator =
+      arg_iterator<arglist_type::const_reverse_iterator, N>;
 
 private:
   /// The internal list of arguments.
   arglist_type Args;
 
+  typedef std::pair<unsigned, unsigned> OptRange;
+  static OptRange emptyRange() { return {-1u, 0u}; }
+
+  /// The first and last index of each different OptSpecifier ID.
+  DenseMap<unsigned, OptRange> OptRanges;
+
+  /// Get the range of indexes in which options with the specified IDs might
+  /// reside, or (0, 0) if there are no such options.
+  OptRange getRange(std::initializer_list<OptSpecifier> Ids) const;
+
 protected:
   // Make the default special members protected so they won't be used to slice
   // derived objects, but can still be used by derived objects to implement
   // their own special members.
   ArgList() = default;
   // Explicit move operations to ensure the container is cleared post-move
   // otherwise it could lead to a double-delete in the case of moving of an
   // InputArgList which deletes the contents of the container. If we could fix
   // up the ownership here (delegate storage/ownership to the derived class so
   // it can be a container of unique_ptr) this would be simpler.
-  ArgList(ArgList &&RHS) : Args(std::move(RHS.Args)) { RHS.Args.clear(); }
+  ArgList(ArgList &&RHS)
+      : Args(std::move(RHS.Args)), OptRanges(std::move(RHS.OptRanges)) {
+    RHS.Args.clear();
+    RHS.OptRanges.clear();
+  }
   ArgList &operator=(ArgList &&RHS) {
     Args = std::move(RHS.Args);
     RHS.Args.clear();
+    OptRanges = std::move(RHS.OptRanges);
+    RHS.OptRanges.clear();
     return *this;
   }
   // Protect the dtor to ensure this type is never destroyed polymorphically.
   ~ArgList() = default;
 
 public:
-
   /// @name Arg Access
   /// @{
 
   /// append - Append \p A to the arg list.
   void append(Arg *A);
 
-  arglist_type &getArgs() { return Args; }
   const arglist_type &getArgs() const { return Args; }
 
   unsigned size() const { return Args.size(); }
 
   /// @}
   /// @name Arg Iteration
   /// @{
 
-  iterator begin() { return Args.begin(); }
-  iterator end() { return Args.end(); }
-
-  reverse_iterator rbegin() { return Args.rbegin(); }
-  reverse_iterator rend() { return Args.rend(); }
-
-  const_iterator begin() const { return Args.begin(); }
-  const_iterator end() const { return Args.end(); }
+  iterator begin() { return {Args.begin(), Args.end()}; }
+  iterator end() { return {Args.end(), Args.end()}; }
 
-  const_reverse_iterator rbegin() const { return Args.rbegin(); }
-  const_reverse_iterator rend() const { return Args.rend(); }
+  reverse_iterator rbegin() { return {Args.rbegin(), Args.rend()}; }
+  reverse_iterator rend() { return {Args.rend(), Args.rend()}; }
 
-  arg_iterator filtered_begin(OptSpecifier Id0 = 0U, OptSpecifier Id1 = 0U,
-                              OptSpecifier Id2 = 0U) const {
-    return arg_iterator(Args.begin(), *this, Id0, Id1, Id2);
-  }
-  arg_iterator filtered_end() const {
-    return arg_iterator(Args.end(), *this);
-  }
+  const_iterator begin() const { return {Args.begin(), Args.end()}; }
+  const_iterator end() const { return {Args.end(), Args.end()}; }
 
-  iterator_range<arg_iterator> filtered(OptSpecifier Id0 = 0U,
-                                        OptSpecifier Id1 = 0U,
-                                        OptSpecifier Id2 = 0U) const {
-    return make_range(filtered_begin(Id0, Id1, Id2), filtered_end());
+  const_reverse_iterator rbegin() const { return {Args.rbegin(), Args.rend()}; }
+  const_reverse_iterator rend() const { return {Args.rend(), Args.rend()}; }
+
+  template<typename ...OptSpecifiers>
+  iterator_range<filtered_iterator<sizeof...(OptSpecifiers)>>
+  filtered(OptSpecifiers ...Ids) const {
+    OptRange Range = getRange({Ids...});
+    auto B = Args.begin() + Range.first;
+    auto E = Args.begin() + Range.second;
+    using Iterator = filtered_iterator<sizeof...(OptSpecifiers)>;
+    return make_range(Iterator(B, E, {Ids...}), Iterator(E, E, {Ids...}));
+  }
+
+  template<typename ...OptSpecifiers>
+  iterator_range<filtered_reverse_iterator<sizeof...(OptSpecifiers)>>
+  filtered_reverse(OptSpecifiers ...Ids) const {
+    OptRange Range = getRange({Ids...});
+    auto B = Args.rend() - Range.second;
+    auto E = Args.rend() - Range.first;
+    using Iterator = filtered_reverse_iterator<sizeof...(OptSpecifiers)>;
+    return make_range(Iterator(B, E, {Ids...}), Iterator(E, E, {Ids...}));
   }
 
   /// @}
   /// @name Arg Removal
   /// @{
 
   /// eraseArg - Remove any option matching \p Id.
   void eraseArg(OptSpecifier Id);
 
   /// @}
   /// @name Arg Access
   /// @{
 
   /// hasArg - Does the arg list contain any option matching \p Id.
   ///
   /// \p Claim Whether the argument should be claimed, if it exists.
-  bool hasArgNoClaim(OptSpecifier Id) const {
-    return getLastArgNoClaim(Id) != nullptr;
-  }
-  bool hasArg(OptSpecifier Id) const {
-    return getLastArg(Id) != nullptr;
+  template<typename ...OptSpecifiers>
+  bool hasArgNoClaim(OptSpecifiers ...Ids) const {
+    return getLastArgNoClaim(Ids...) != nullptr;
+  }
+  template<typename ...OptSpecifiers>
+  bool hasArg(OptSpecifiers ...Ids) const {
+    return getLastArg(Ids...) != nullptr;
+  }
+
+  /// Return the last argument matching \p Id, or null.
+  template<typename ...OptSpecifiers>
+  Arg *getLastArg(OptSpecifiers ...Ids) const {
+    Arg *Res = nullptr;
+    for (Arg *A : filtered(Ids...)) {
+      Res = A;
+      Res->claim();
+    }
+    return Res;
+  }
+
+  /// Return the last argument matching \p Id, or null. Do not "claim" the
+  /// option (don't mark it as having been used).
+  template<typename ...OptSpecifiers>
+  Arg *getLastArgNoClaim(OptSpecifiers ...Ids) const {
+    for (Arg *A : filtered_reverse(Ids...))
+      return A;
+    return nullptr;
   }
-  bool hasArg(OptSpecifier Id0, OptSpecifier Id1) const {
-    return getLastArg(Id0, Id1) != nullptr;
-  }
-  bool hasArg(OptSpecifier Id0, OptSpecifier Id1, OptSpecifier Id2) const {
-    return getLastArg(Id0, Id1, Id2) != nullptr;
-  }
-
-  /// getLastArg - Return the last argument matching \p Id, or null.
-  ///
-  /// \p Claim Whether the argument should be claimed, if it exists.
-  Arg *getLastArgNoClaim(OptSpecifier Id) const;
-  Arg *getLastArgNoClaim(OptSpecifier Id0, OptSpecifier Id1) const;
-  Arg *getLastArgNoClaim(OptSpecifier Id0, OptSpecifier Id1,
-                         OptSpecifier Id2) const;
-  Arg *getLastArgNoClaim(OptSpecifier Id0, OptSpecifier Id1, OptSpecifier Id2,
-                         OptSpecifier Id3) const;
-  Arg *getLastArg(OptSpecifier Id) const;
-  Arg *getLastArg(OptSpecifier Id0, OptSpecifier Id1) const;
-  Arg *getLastArg(OptSpecifier Id0, OptSpecifier Id1, OptSpecifier Id2) const;
-  Arg *getLastArg(OptSpecifier Id0, OptSpecifier Id1, OptSpecifier Id2,
-                  OptSpecifier Id3) const;
-  Arg *getLastArg(OptSpecifier Id0, OptSpecifier Id1, OptSpecifier Id2,
-                  OptSpecifier Id3, OptSpecifier Id4) const;
-  Arg *getLastArg(OptSpecifier Id0, OptSpecifier Id1, OptSpecifier Id2,
-                  OptSpecifier Id3, OptSpecifier Id4, OptSpecifier Id5) const;
-  Arg *getLastArg(OptSpecifier Id0, OptSpecifier Id1, OptSpecifier Id2,
-                  OptSpecifier Id3, OptSpecifier Id4, OptSpecifier Id5,
-                  OptSpecifier Id6) const;
-  Arg *getLastArg(OptSpecifier Id0, OptSpecifier Id1, OptSpecifier Id2,
-                  OptSpecifier Id3, OptSpecifier Id4, OptSpecifier Id5,
-                  OptSpecifier Id6, OptSpecifier Id7) const;
 
   /// getArgString - Return the input argument string at \p Index.
   virtual const char *getArgString(unsigned Index) const = 0;
 
   /// getNumInputArgStrings - Return the number of original argument strings,
   /// which are guaranteed to be the first strings in the argument string
   /// list.
   virtual unsigned getNumInputArgStrings() const = 0;
 
   /// @}
   /// @name Argument Lookup Utilities
   /// @{
 
   /// getLastArgValue - Return the value of the last argument, or a default.
-  StringRef getLastArgValue(OptSpecifier Id,
-                                  StringRef Default = "") const;
+  StringRef getLastArgValue(OptSpecifier Id, StringRef Default = "") const;
 
   /// getAllArgValues - Get the values of all instances of the given argument
   /// as strings.
   std::vector<std::string> getAllArgValues(OptSpecifier Id) const;
 
   /// @}
   /// @name Translation Utilities
   /// @{
public:
 
   /// AddAllArgs - Render all arguments matching the given ids.
   void AddAllArgs(ArgStringList &Output, OptSpecifier Id0,
                   OptSpecifier Id1 = 0U, OptSpecifier Id2 = 0U) const;
 
   /// AddAllArgValues - Render the argument values of all arguments
   /// matching the given ids.
   void AddAllArgValues(ArgStringList &Output, OptSpecifier Id0,
-                        OptSpecifier Id1 = 0U, OptSpecifier Id2 = 0U) const;
 
   /// AddAllArgsTranslated - Render all the arguments matching the
   /// given ids, but forced to separate args and using the provided
   /// name instead of the first option value.
   ///
   /// \param Joined - If true, render the argument as joined with
   /// the option specifier.
   void AddAllArgsTranslated(ArgStringList &Output, OptSpecifier Id0,

llvm/trunk/lib/Option/ArgList.cpp

 #include "llvm/Option/Arg.h"
 #include "llvm/Option/Option.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 
 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();
-
-    }
-  }
-
-  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();
-    }
-  }
+  // 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, 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();
-    }
-  }
-
-  return Res;
+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;
+  }
+  OptRanges.erase(Id.getID());
+}
+
+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);
+    }
+  }
+  // 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 {
   if (Arg *A = getLastArg(Pos, Neg))
     return A->getOption().matches(Pos);
   return Default;
 }
 
 bool ArgList::hasFlag(OptSpecifier Pos, OptSpecifier PosAlias, OptSpecifier Neg,
                       bool Default) const {
   if (Arg *A = getLastArg(Pos, PosAlias, Neg))
     return A->getOption().matches(Pos) || A->getOption().matches(PosAlias);
   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;
 }
 
 std::vector<std::string> ArgList::getAllArgValues(OptSpecifier Id) const {
   SmallVector<const char *, 16> Values;
   AddAllArgValues(Values, Id);
if (Arg *A = getLastArg(Id0, Id1)) {
     A->claim();
     A->render(*this, Output);
   }
 }
 
 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)) {
         Excluded = true;
         break;
       }
     }
     if (!Excluded) {
for (auto Arg: filtered(Id0)) {
     } else {
       Output.push_back(Translation);
       Output.push_back(Arg->getValue(0));
     }
   }
 }
 
 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,
                                               StringRef LHS,
                                               StringRef RHS) const {
   StringRef Cur = getArgString(Index);
   if (Cur.size() == LHS.size() + RHS.size() &&
       Cur.startswith(LHS) && Cur.endswith(RHS))