[ThinLTO] Add a recursive step in Metadata lazy-loading

[mehdi_amini]

Summary

Without this, we're stressing the RAUW of unique nodes,
which is a costly operation. This is intended to limit
the number of RAUW, and is very effective on the total
link-time of opt with ThinLTO, before:

real 4m4.587s  user 15m3.401s  sys 0m23.616s

after:

real 3m25.261s user 12m22.132s sys 0m24.152s

[mehdi_amini]

Add a comment, and handles correctly uniquing cycles (even if I didn't encounter any when bootstrapping clang)

[mehdi_amini]

Note that I gave the timing for the *full* link, if I focus on the time spent in "materializeMetadata()" is goes from 215s to 37s, almost a 6x improvement.

[tejohnson]

Nice improvement - is this related to the regression you saw in your measurements on the effectiveness of lazy loading metadata? A few comments/suggestions below.

In D28751#646918, @mehdi_amini wrote:

Add a comment, and handles correctly uniquing cycles (even if I didn't encounter any when bootstrapping clang)

Do we have a test case that exposes this issue? If not, it would be good to add

llvm/lib/Bitcode/Reader/MetadataLoader.cpp

836

The comment is a little confusing, since we are in fact creating a temporary just above. Maybe change to something like "instead of keeping the temporary which requires a later RAUW".

[mehdi_amini]

In D28751#648142, @tejohnson wrote:

Nice improvement - is this related to the regression you saw in your measurements on the effectiveness of lazy loading metadata? A few comments/suggestions below.

Yes, it recovers this and goes beyond.

Do we have a test case that exposes this issue? If not, it would be good to add

Added! Thanks it was a good idea as it shown that the patch was wrong (I was creating a temp for the operand about to be lazy-loaded instead of the parent).

llvm/lib/Bitcode/Reader/MetadataLoader.cpp

MDString *MetadataLoader::MetadataLoaderImpl::lazyLoadOneMDString(unsigned ID) {
   MetadataList.assignValue(MDS, ID);
   return MDS;
 }
 
 void MetadataLoader::MetadataLoaderImpl::lazyLoadOneMetadata(
     unsigned ID, PlaceholderQueue &Placeholders) {
   assert(ID < (MDStringRef.size()) + GlobalMetadataBitPosIndex.size());
   assert(ID >= MDStringRef.size() && "Unexpected lazy-loading of MDString");
-#ifndef NDEBUG
   // Lookup first if the metadata hasn't already been loaded.
   if (auto *MD = MetadataList.lookup(ID)) {
     auto *N = dyn_cast_or_null<MDNode>(MD);
-    assert(N && N->isTemporary() && "Lazy loading an already loaded metadata");
+    if (!N->isTemporary())
+      return;
   }
-#endif
   SmallVector<uint64_t, 64> Record;
   StringRef Blob;
   IndexCursor.JumpToBit(GlobalMetadataBitPosIndex[ID - MDStringRef.size()]);
   auto Entry = IndexCursor.advanceSkippingSubblocks();
   ++NumMDRecordLoaded;
   unsigned Code = IndexCursor.readRecord(Entry.ID, Record, &Blob);
   if (Error Err = parseOneMetadata(Record, Code, Placeholders, Blob, ID))
     report_fatal_error("Can't lazyload MD");

 Error MetadataLoader::MetadataLoaderImpl::parseOneMetadata(
     SmallVectorImpl<uint64_t> &Record, unsigned Code,
     PlaceholderQueue &Placeholders, StringRef Blob, unsigned &NextMetadataNo) {
 
   bool IsDistinct = false;
   auto getMD = [&](unsigned ID) -> Metadata * {
     if (ID < MDStringRef.size())
       return lazyLoadOneMDString(ID);
-    if (!IsDistinct)
-      return MetadataList.getMetadataFwdRef(ID);
+    if (!IsDistinct) {
+      if (auto *MD = MetadataList.lookup(ID))
+        return MD;
+      // Create a temporary, it is needed before recursing in case there are
+      // uniquing cycles.
+      auto *TempMD = MetadataList.getMetadataFwdRef(ID);
+      // If lazy-loading is enabled, we try recursively to load the operand
+      // instead of creating a temporary.
+      if (ID < (MDStringRef.size() + GlobalMetadataBitPosIndex.size())) {
+        lazyLoadOneMetadata(ID, Placeholders);
+        return MetadataList.lookup(ID);
+      }
+      return TempMD;
+    }
     if (auto *MD = MetadataList.getMetadataIfResolved(ID))
       return MD;
     return &Placeholders.getPlaceholderOp(ID);
   };
   auto getMDOrNull = [&](unsigned ID) -> Metadata * {
     if (ID)
       return getMD(ID - 1);
     return nullptr;