[MC] Merge MC[Sub,Super]RegIterator with mc_[sub,super]_reg_iterator

[barannikov88]

Summary

Turn MC*RegIterator into fully qualified iterators by deriving them from
iterator_adaptor_base. This makes mc_*_reg iterators redundant.

[barannikov88]

Bugfix

[barannikov88]

Pull in post-increment operator++

[barannikov88]

Move inline from declaration to definition

[barannikov88]

Drop an unrelated change

[barannikov88]

Comment default constructors, remove isValid

[barannikov88]

This is an NFC to make D152098 simpler.

There is a bit of boilerplate in the form of overridden operator++ because forward iterators
require operator* to return by reference ( C++ <= 17 AFAIK). concat_range relies on this.
operator++ caches the value so that operator* can return a reference.

[barannikov88]

Add const so that operator-> can be used

[dblaikie]

llvm/include/llvm/MC/MCRegisterInfo.h

542

You could still expose isValid through MCSubRegIterator & avoid needing to add the second iterator here? No big deal either way, I guess.

[barannikov88]

llvm/include/llvm/MC/MCRegisterInfo.h

542

I tried to make them look like the usual iterators, that don't usually provide such kind of methods. But I guess having this method here won't hurt, will add.

It would be nice if we had an adaptation of default_sentinel_t from C++20, then this method could be rutned into operator==.

[barannikov88]

llvm/include/llvm/MC/MCRegisterInfo.h

513

@dblaikie Could you comment on this?
This requires type type to be default constructible. In D152098 I add MCRegUnit that does not have a good default value. Maybe I should instead return a proxy object from operator* that will hold the value? Would that be correct w.r.t. iterator requirements? Probably factor the proxy out into a common (templated) base class, too.

[barannikov88]

Add isValid method

[barannikov88]

llvm/include/llvm/MC/MCRegisterInfo.h

513

Ah I guess this won't change a thing, I would still need to be able to construct the proxy from some value, which I don't have in case of the end iterator.

[foad]

Sounds good to me but I don't have enough C++ expertise to review it properly.

[dblaikie]

llvm/include/llvm/MC/MCRegisterInfo.h

513

If you need something that isn't default constructible/can't just have an instance hanging around as a member like this, the next best thing would be std::optional<T> so it can be non-constructed. If the overhead of the extra bool/padding in std::optional is significant, you could maybe use a raw aligned buffer and /maybe/ conditionalize on the validity of the underlying iterator to decide whether there's an object in that buffer or not. But ensuring the code doesn't leak/fail to construct/destroy properly would be subtle.

llvm/include/llvm/MC/MCRegisterInfo.h

 #include "llvm/MC/MCRegister.h"
 #include <cassert>
 #include <cstdint>
 #include <iterator>
 #include <utility>
 
 namespace llvm {
 
+class MCSubRegIterator;
+class MCSuperRegIterator;
+
 /// MCRegisterClass - Base class of TargetRegisterClass.
 class MCRegisterClass {
 public:
   using iterator = const MCPhysReg*;
   using const_iterator = const MCPhysReg*;
 
   const iterator RegsBegin;
   const uint8_t *const RegSet;
private:
   unsigned EHDwarf2LRegsSize;
   const DwarfLLVMRegPair *L2DwarfRegs;        // LLVM to Dwarf regs mapping
   const DwarfLLVMRegPair *EHL2DwarfRegs;      // LLVM to Dwarf regs mapping EH
   const DwarfLLVMRegPair *Dwarf2LRegs;        // Dwarf to LLVM regs mapping
   const DwarfLLVMRegPair *EHDwarf2LRegs;      // Dwarf to LLVM regs mapping EH
   DenseMap<MCRegister, int> L2SEHRegs;        // LLVM to SEH regs mapping
   DenseMap<MCRegister, int> L2CVRegs;         // LLVM to CV regs mapping
 
-public:
-  // Forward declaration to become a friend class of DiffListIterator.
-  template <class SubT> class mc_difflist_iterator;
-
-  /// DiffListIterator - Base iterator class that can traverse the
-  /// differentially encoded register and regunit lists in DiffLists.
-  /// Don't use this class directly, use one of the specialized sub-classes
-  /// defined below.
-  class DiffListIterator {
+  /// Iterator class that can traverse the differentially encoded values in
+  /// DiffLists. Don't use this class directly, use one of the adaptors below.
+  class DiffListIterator
+      : public iterator_facade_base<DiffListIterator, std::forward_iterator_tag,
+                                    unsigned> {
     unsigned Val = 0;
     const int16_t *List = nullptr;
 
-  protected:
-    /// Create an invalid iterator. Call init() to point to something useful.
+  public:
+    /// Constructs an invalid iterator, which is also the end iterator.
+    /// Call init() to point to something useful.
     DiffListIterator() = default;
 
     /// Point the iterator to InitVal, decoding subsequent values from DiffList.
     void init(unsigned InitVal, const int16_t *DiffList) {
       Val = InitVal;
       List = DiffList;
     }
 
-  public:
-    /// isValid - returns true if this iterator is not yet at the end.
+    /// Returns true if this iterator is not yet at the end.
     bool isValid() const { return List; }
 
     /// Dereference the iterator to get the value at the current position.
-    MCRegister operator*() const { return Val; }
+    const unsigned &operator*() const { return Val; }
 
+    using DiffListIterator::iterator_facade_base::operator++;
     /// Pre-increment to move to the next position.
-    void operator++() {
+    DiffListIterator &operator++() {
       assert(isValid() && "Cannot move off the end of the list.");
       int16_t D = *List++;
       Val += D;
       // The end of the list is encoded as a 0 differential.
       if (!D)
         List = nullptr;
+      return *this;
     }
 
-    template <class SubT> friend class MCRegisterInfo::mc_difflist_iterator;
-  };
-
-  /// Forward iterator using DiffListIterator.
-  template <class SubT>
-  class mc_difflist_iterator
-      : public iterator_facade_base<mc_difflist_iterator<SubT>,
-                                    std::forward_iterator_tag, MCPhysReg> {
-    MCRegisterInfo::DiffListIterator Iter;
-    /// Current value as MCPhysReg, so we can return a reference to it.
-    MCPhysReg Val = 0;
-
-  protected:
-    /// Point the iterator to InitVal, decoding subsequent values from DiffList.
-    void init(unsigned InitVal, const int16_t *DiffList) {
-      Iter.init(InitVal, DiffList);
-      Val = *Iter;
-    }
-
-  public:
-    // Allow default construction to build variables, but this doesn't build
-    // a useful iterator.
-    mc_difflist_iterator() = default;
-
-    /// Return an iterator past the last element.
-    static SubT end() {
-      SubT End;
-      End.Iter.List = nullptr;
-      return End;
-    }
-
-    bool operator==(const mc_difflist_iterator &Arg) const {
-      return Iter.List == Arg.Iter.List;
-    }
-
-    const MCPhysReg &operator*() const { return Val; }
-
-    using mc_difflist_iterator::iterator_facade_base::operator++;
-    void operator++() {
-      assert(Iter.List && "Cannot increment the end iterator!");
-      ++Iter;
-      Val = *Iter;
+    bool operator==(const DiffListIterator &Other) const {
+      return List == Other.List;
     }
   };
 
-  /// Forward iterator over all sub-registers.
-  /// TODO: Replace remaining uses of MCSubRegIterator.
-  class mc_subreg_iterator : public mc_difflist_iterator<mc_subreg_iterator> {
-  public:
-    mc_subreg_iterator() = default;
-
-    mc_subreg_iterator(MCRegister Reg, const MCRegisterInfo *MCRI) {
-      assert(MCRegister::isPhysicalRegister(Reg.id()));
-      init(Reg.id(), MCRI->DiffLists + MCRI->get(Reg).SubRegs);
-    }
-  };
-
-  /// Forward iterator over all super-registers.
-  /// TODO: Replace remaining uses of MCSuperRegIterator.
-  class mc_superreg_iterator
-      : public mc_difflist_iterator<mc_superreg_iterator> {
-  public:
-    mc_superreg_iterator() = default;
-
-    mc_superreg_iterator(MCRegister Reg, const MCRegisterInfo *MCRI) {
-      assert(MCRegister::isPhysicalRegister(Reg.id()));
-      init(Reg.id(), MCRI->DiffLists + MCRI->get(Reg).SuperRegs);
-    }
-  };
-
   /// Return an iterator range over all sub-registers of \p Reg, excluding \p
   /// Reg.
-  iterator_range<mc_subreg_iterator> subregs(MCRegister Reg) const {
-    return make_range(std::next(mc_subreg_iterator(Reg, this)),
-                      mc_subreg_iterator::end());
-  }
+  inline iterator_range<MCSubRegIterator> subregs(MCRegister Reg) const;
 
   /// Return an iterator range over all sub-registers of \p Reg, including \p
   /// Reg.
-  iterator_range<mc_subreg_iterator> subregs_inclusive(MCRegister Reg) const {
-    return make_range({Reg, this}, mc_subreg_iterator::end());
-  }
+  inline iterator_range<MCSubRegIterator>
+  subregs_inclusive(MCRegister Reg) const;
 
   /// Return an iterator range over all super-registers of \p Reg, excluding \p
   /// Reg.
-  iterator_range<mc_superreg_iterator> superregs(MCRegister Reg) const {
-    return make_range(std::next(mc_superreg_iterator(Reg, this)),
-                      mc_superreg_iterator::end());
-  }
+  inline iterator_range<MCSuperRegIterator> superregs(MCRegister Reg) const;
 
   /// Return an iterator range over all super-registers of \p Reg, including \p
   /// Reg.
-  iterator_range<mc_superreg_iterator>
-  superregs_inclusive(MCRegister Reg) const {
-    return make_range({Reg, this}, mc_superreg_iterator::end());
-  }
+  inline iterator_range<MCSuperRegIterator>
+  superregs_inclusive(MCRegister Reg) const;
 
   /// Return an iterator range over all sub- and super-registers of \p Reg,
   /// including \p Reg.
-  detail::concat_range<const MCPhysReg, iterator_range<mc_subreg_iterator>,
-                       iterator_range<mc_superreg_iterator>>
-  sub_and_superregs_inclusive(MCRegister Reg) const {
-    return concat<const MCPhysReg>(subregs_inclusive(Reg), superregs(Reg));
-  }
+  inline detail::concat_range<const MCPhysReg, iterator_range<MCSubRegIterator>,
+                              iterator_range<MCSuperRegIterator>>
+  sub_and_superregs_inclusive(MCRegister Reg) const;
 
   // These iterators are allowed to sub-class DiffListIterator and access
   // internal list pointers.
   friend class MCSubRegIterator;
   friend class MCSubRegIndexIterator;
   friend class MCSuperRegIterator;
   friend class MCRegUnitIterator;
   friend class MCRegUnitMaskIterator;

 //                          Register List Iterators
 //===----------------------------------------------------------------------===//
 
 // MCRegisterInfo provides lists of super-registers, sub-registers, and
 // aliasing registers. Use these iterator classes to traverse the lists.
 
 /// MCSubRegIterator enumerates all sub-registers of Reg.
 /// If IncludeSelf is set, Reg itself is included in the list.
-class MCSubRegIterator : public MCRegisterInfo::DiffListIterator {
+class MCSubRegIterator
+    : public iterator_adaptor_base<MCSubRegIterator,
+                                   MCRegisterInfo::DiffListIterator,
+                                   std::forward_iterator_tag, MCPhysReg> {
+  // Cache the current value, so that we can return a reference to it.
+  MCPhysReg Val;
+
 public:
+  MCSubRegIterator() = default;
+
   MCSubRegIterator(MCRegister Reg, const MCRegisterInfo *MCRI,
                    bool IncludeSelf = false) {
     assert(MCRegister::isPhysicalRegister(Reg.id()));
-    init(Reg.id(), MCRI->DiffLists + MCRI->get(Reg).SubRegs);
+    I.init(Reg.id(), MCRI->DiffLists + MCRI->get(Reg).SubRegs);
     // Initially, the iterator points to Reg itself.
+    Val = MCPhysReg(*I);
     if (!IncludeSelf)
       ++*this;
   }
+
+  const MCPhysReg &operator*() const { return Val; }
+
+  using iterator_adaptor_base::operator++;
+  MCSubRegIterator &operator++() {
+    Val = MCPhysReg(*++I);
+    return *this;
+  }
+
+  bool isValid() const { return I.isValid(); }
 };
 
 /// Iterator that enumerates the sub-registers of a Reg and the associated
 /// sub-register indices.
 class MCSubRegIndexIterator {
   MCSubRegIterator SRIter;
   const uint16_t *SRIndex;
 
 public:
   /// Constructs an iterator that traverses subregisters and their
   /// associated subregister indices.
   MCSubRegIndexIterator(MCRegister Reg, const MCRegisterInfo *MCRI)
-    : SRIter(Reg, MCRI) {
+      : SRIter(Reg, MCRI, /*IncludeSelf=*/false) {
     SRIndex = MCRI->SubRegIndices + MCRI->get(Reg).SubRegIndices;
   }
 
   /// Returns current sub-register.
   MCRegister getSubReg() const {
     return *SRIter;
   }
 
public:
   void operator++() {
     ++SRIter;
     ++SRIndex;
   }
 };
 
 /// MCSuperRegIterator enumerates all super-registers of Reg.
 /// If IncludeSelf is set, Reg itself is included in the list.
-class MCSuperRegIterator : public MCRegisterInfo::DiffListIterator {
+class MCSuperRegIterator
+    : public iterator_adaptor_base<MCSuperRegIterator,
+                                   MCRegisterInfo::DiffListIterator,
+                                   std::forward_iterator_tag, MCPhysReg> {
+  // Cache the current value, so that we can return a reference to it.
+  MCPhysReg Val;
+
 public:
   MCSuperRegIterator() = default;
 
   MCSuperRegIterator(MCRegister Reg, const MCRegisterInfo *MCRI,
                      bool IncludeSelf = false) {
     assert(MCRegister::isPhysicalRegister(Reg.id()));
-    init(Reg.id(), MCRI->DiffLists + MCRI->get(Reg).SuperRegs);
+    I.init(Reg.id(), MCRI->DiffLists + MCRI->get(Reg).SuperRegs);
     // Initially, the iterator points to Reg itself.
+    Val = MCPhysReg(*I);
     if (!IncludeSelf)
       ++*this;
   }
+
+  const MCPhysReg &operator*() const { return Val; }
+
+  using iterator_adaptor_base::operator++;
+  MCSuperRegIterator &operator++() {
+    Val = MCPhysReg(*++I);
+    return *this;
+  }
+
+  bool isValid() const { return I.isValid(); }
 };
 
 // Definition for isSuperRegister. Put it down here since it needs the
 // iterator defined above in addition to the MCRegisterInfo class itself.
 inline bool MCRegisterInfo::isSuperRegister(MCRegister RegA, MCRegister RegB) const{
   return is_contained(superregs(RegA), RegB);
 }
 
public:
 
   void operator++() {
     assert(isValid() && "Cannot move off the end of the list.");
     do advance();
     while (!IncludeSelf && isValid() && *SI == Reg);
   }
 };
 
+iterator_range<MCSubRegIterator> MCRegisterInfo::subregs(MCRegister Reg) const {
+  return make_range({Reg, this, /*IncludeSelf=*/false}, MCSubRegIterator());
+}
+
+iterator_range<MCSubRegIterator>
+MCRegisterInfo::subregs_inclusive(MCRegister Reg) const {
+  return make_range({Reg, this, /*IncludeSelf=*/true}, MCSubRegIterator());
+}
+
+iterator_range<MCSuperRegIterator>
+MCRegisterInfo::superregs(MCRegister Reg) const {
+  return make_range({Reg, this, /*IncludeSelf=*/false}, MCSuperRegIterator());
+}
+
+iterator_range<MCSuperRegIterator>
+MCRegisterInfo::superregs_inclusive(MCRegister Reg) const {
+  return make_range({Reg, this, /*IncludeSelf=*/true}, MCSuperRegIterator());
+}
+
+detail::concat_range<const MCPhysReg, iterator_range<MCSubRegIterator>,
+                     iterator_range<MCSuperRegIterator>>
+MCRegisterInfo::sub_and_superregs_inclusive(MCRegister Reg) const {
+  return concat<const MCPhysReg>(subregs_inclusive(Reg), superregs(Reg));
+}
+
 } // end namespace llvm
 
 #endif // LLVM_MC_MCREGISTERINFO_H