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

joker-eph · joker-eph · commit 690952d15e6e · 2016-12-25T04:22:54.000Z
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. Differential Revision: https://reviews.llvm.org/D28089 llvm-svn: 290507
diff --git a/llvm/lib/Bitcode/Reader/MetadataLoader.cpp b/llvm/lib/Bitcode/Reader/MetadataLoader.cpp
@@ -97,25 +97,20 @@ 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.
+  SmallDenseSet<unsigned, 1> ForwardReference;
+
+  /// The set of indices in MetadataPtrs above of Metadata that need to be
+  /// resolved.
+  SmallDenseSet<unsigned, 1> UnresolvedNodes;
+
   /// Structures for resolving old type refs.
   struct {
     SmallDenseMap<MDString *, TempMDTuple, 1> Unknown;
@@ -151,7 +146,8 @@ class BitcodeReaderMetadataList {
 
   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);
   }
 
@@ -168,7 +164,7 @@ class BitcodeReaderMetadataList {
   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);
@@ -184,6 +180,10 @@ class BitcodeReaderMetadataList {
 };
 
 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;
@@ -201,7 +201,7 @@ void BitcodeReaderMetadataList::assignValue(Metadata *MD, unsigned Idx) {
   // 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) {
@@ -212,14 +212,7 @@ Metadata *BitcodeReaderMetadataList::getMetadataFwdRef(unsigned 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();
@@ -240,50 +233,38 @@ MDNode *BitcodeReaderMetadataList::getMDNodeFwdRefOrNull(unsigned Idx) {
 }
 
 void BitcodeReaderMetadataList::tryToResolveCycles() {
-  if (NumFwdRefs)
+  if (!ForwardReference.empty())
     // Still forward references... can't resolve cycles.
     return;
 
-  bool DidReplaceTypeRefs = false;
-
   // Give up on finding a full definition for any forward decls that remain.
   for (const auto &Ref : OldTypeRefs.FwdDecls)
     OldTypeRefs.Final.insert(Ref);
   OldTypeRefs.FwdDecls.clear();
 
   // 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)
@@ -293,10 +274,8 @@ void BitcodeReaderMetadataList::tryToResolveCycles() {
     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,
