MetadataLoader: replace the tracking of ForwardReferences and UnresolvedNodes with a set-based solution (NFC)

[mehdi_amini]

Summary

This makes it explicit what is the exact list to handle, and it
looks much more easy to manipulate and understand that the
previous custom tracking of min/max to express the range where
to look for.

llvm/lib/Bitcode/Reader/MetadataLoader.cpp

 #include <cstdint>
 #include <deque>
 #include <limits>
 #include <map>
 #include <memory>
 #include <string>
 #include <system_error>
 #include <tuple>
+#include <unordered_set>
 #include <utility>
 #include <vector>
 
 using namespace llvm;
 
 /// Flag whether we need to import full type definitions for ThinLTO.
 /// Currently needed for Darwin and LLDB.
 static cl::opt<bool> ImportFullTypeDefinitions(
     "import-full-type-definitions", cl::init(false), cl::Hidden,
     cl::desc("Import full type definitions for ThinLTO."));
 
 namespace {
 
 static int64_t unrotateSign(uint64_t U) { return U & 1 ? ~(U >> 1) : U >> 1; }
 
 class BitcodeReaderMetadataList {
-  /// Keep track of the current number of ForwardReference in the list.
-  unsigned NumFwdRefs = 0;
-  /// Maintain the range [min-max] that needs to be inspected to resolve cycles.
-  /// This is the range of Metadata that have involved forward reference during
-  /// loading and that needs to be inspected to resolve cycles. It is purely an
-  /// optimization to avoid spending time resolving cycles outside of this
-  /// range, i.e. where there hasn't been any forward reference.
-  unsigned MinFwdRef = 0;
-  unsigned MaxFwdRef = 0;
-  /// Set to true if there was any FwdRef encountered. This is used to track if
-  /// we need to resolve cycles after loading metadatas.
-  bool AnyFwdRefs = false;
-
   /// Array of metadata references.
   ///
   /// Don't use std::vector here.  Some versions of libc++ copy (instead of
   /// move) on resize, and TrackingMDRef is very expensive to copy.
   SmallVector<TrackingMDRef, 1> MetadataPtrs;
 
+  /// The set of indices in MetadataPtrs above of forward references that were
+  /// generated.
+  std::unordered_set<unsigned> ForwardReference;
+
+  /// The set of indices in MetadataPtrs above of Metadata that need to be
+  /// resolved.
+  std::unordered_set<unsigned> UnresolvedNodes;
+
   /// Structures for resolving old type refs.
   struct {
     SmallDenseMap<MDString *, TempMDTuple, 1> Unknown;
     SmallDenseMap<MDString *, DICompositeType *, 1> Final;
     SmallVector<std::pair<TrackingMDRef, TempMDTuple>, 1> Arrays;
   } OldTypeRefs;
 
   LLVMContext &Context;
public:
   Metadata *lookup(unsigned I) const {
     if (I < MetadataPtrs.size())
       return MetadataPtrs[I];
     return nullptr;
   }
 
   void shrinkTo(unsigned N) {
     assert(N <= size() && "Invalid shrinkTo request!");
-    assert(!AnyFwdRefs && "Unexpected forward refs");
+    assert(ForwardReference.empty() && "Unexpected forward refs");
+    assert(UnresolvedNodes.empty() && "Unexpected unresolved node");
     MetadataPtrs.resize(N);
   }
 
   /// Return the given metadata, creating a replaceable forward reference if
   /// necessary.
   Metadata *getMetadataFwdRef(unsigned Idx);
 
   /// Return the the given metadata only if it is fully resolved.
   ///
   /// Gives the same result as \a lookup(), unless \a MDNode::isResolved()
   /// would give \c false.
   Metadata *getMetadataIfResolved(unsigned Idx);
 
   MDNode *getMDNodeFwdRefOrNull(unsigned Idx);
   void assignValue(Metadata *MD, unsigned Idx);
   void tryToResolveCycles();
-  bool hasFwdRefs() const { return AnyFwdRefs; }
+  bool hasFwdRefs() const { return !ForwardReference.empty(); }
 
   /// Upgrade a type that had an MDString reference.
   void addTypeRef(MDString &UUID, DICompositeType &CT);
 
   /// Upgrade a type that had an MDString reference.
   Metadata *upgradeTypeRef(Metadata *MaybeUUID);
 
   /// Upgrade a type ref array that may have MDString references.
   Metadata *upgradeTypeRefArray(Metadata *MaybeTuple);
 
 private:
   Metadata *resolveTypeRefArray(Metadata *MaybeTuple);
 };
 
 void BitcodeReaderMetadataList::assignValue(Metadata *MD, unsigned Idx) {
+  if (auto *MDN = dyn_cast<MDNode>(MD))
+    if (!MDN->isResolved())
+      UnresolvedNodes.insert(Idx);
+
   if (Idx == size()) {
     push_back(MD);
     return;
   }
 
   if (Idx >= size())
     resize(Idx + 1);
 
   TrackingMDRef &OldMD = MetadataPtrs[Idx];
   if (!OldMD) {
     OldMD.reset(MD);
     return;
   }
 
   // If there was a forward reference to this value, replace it.
   TempMDTuple PrevMD(cast<MDTuple>(OldMD.get()));
   PrevMD->replaceAllUsesWith(MD);
-  --NumFwdRefs;
+  ForwardReference.erase(Idx);
 }
 
 Metadata *BitcodeReaderMetadataList::getMetadataFwdRef(unsigned Idx) {
   if (Idx >= size())
     resize(Idx + 1);
 
   if (Metadata *MD = MetadataPtrs[Idx])
     return MD;
 
   // Track forward refs to be resolved later.
-  if (AnyFwdRefs) {
-    MinFwdRef = std::min(MinFwdRef, Idx);
-    MaxFwdRef = std::max(MaxFwdRef, Idx);
-  } else {
-    AnyFwdRefs = true;
-    MinFwdRef = MaxFwdRef = Idx;
-  }
-  ++NumFwdRefs;
+  ForwardReference.insert(Idx);
 
   // Create and return a placeholder, which will later be RAUW'd.
   Metadata *MD = MDNode::getTemporary(Context, None).release();
   MetadataPtrs[Idx].reset(MD);
   return MD;
 }
 
 Metadata *BitcodeReaderMetadataList::getMetadataIfResolved(unsigned Idx) {
   Metadata *MD = lookup(Idx);
   if (auto *N = dyn_cast_or_null<MDNode>(MD))
     if (!N->isResolved())
       return nullptr;
   return MD;
 }
 
 MDNode *BitcodeReaderMetadataList::getMDNodeFwdRefOrNull(unsigned Idx) {
   return dyn_cast_or_null<MDNode>(getMetadataFwdRef(Idx));
 }
 
 void BitcodeReaderMetadataList::tryToResolveCycles() {
-  if (NumFwdRefs)
+  if (!ForwardReference.empty())
     // Still forward references... can't resolve cycles.
     return;
 
-  bool DidReplaceTypeRefs = false;
-
   // Upgrade from old type ref arrays.  In strange cases, this could add to
   // OldTypeRefs.Unknown.
-  for (const auto &Array : OldTypeRefs.Arrays) {
-    DidReplaceTypeRefs = true;
+  for (const auto &Array : OldTypeRefs.Arrays)
     Array.second->replaceAllUsesWith(resolveTypeRefArray(Array.first.get()));
-  }
   OldTypeRefs.Arrays.clear();
 
   // Replace old string-based type refs with the resolved node, if possible.
   // If we haven't seen the node, leave it to the verifier to complain about
   // the invalid string reference.
   for (const auto &Ref : OldTypeRefs.Unknown) {
-    DidReplaceTypeRefs = true;
     if (DICompositeType *CT = OldTypeRefs.Final.lookup(Ref.first))
       Ref.second->replaceAllUsesWith(CT);
     else
       Ref.second->replaceAllUsesWith(Ref.first);
   }
   OldTypeRefs.Unknown.clear();
 
-  // Make sure all the upgraded types are resolved.
-  if (DidReplaceTypeRefs) {
-    AnyFwdRefs = true;
-    MinFwdRef = 0;
-    MaxFwdRef = MetadataPtrs.size() - 1;
-  }
-
-  if (!AnyFwdRefs)
+  if (UnresolvedNodes.empty())
     // Nothing to do.
     return;
 
   // Resolve any cycles.
-  for (unsigned I = MinFwdRef, E = MaxFwdRef + 1; I != E; ++I) {
+  for (unsigned I : UnresolvedNodes) {
     auto &MD = MetadataPtrs[I];
     auto *N = dyn_cast_or_null<MDNode>(MD);
     if (!N)
       continue;
 
     assert(!N->isTemporary() && "Unexpected forward reference");
     N->resolveCycles();
   }
 
-  // Make sure we return early again until there's another forward ref.
-  AnyFwdRefs = false;
-  MinFwdRef = 0;
-  MaxFwdRef = 0;
+  // Make sure we return early again until there's another unresolved ref.
+  UnresolvedNodes.clear();
 }
 
 void BitcodeReaderMetadataList::addTypeRef(MDString &UUID,
                                            DICompositeType &CT) {
   assert(CT.getRawIdentifier() == &UUID && "Mismatched UUID");
   OldTypeRefs.Final.insert(std::make_pair(&UUID, &CT));
 }