[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 ↗

(On Diff #84508)

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/trunk/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)
+    if (!IsDistinct) {
+      if (auto *MD = MetadataList.lookup(ID))
+        return MD;
+      // If lazy-loading is enabled, we try recursively to load the operand
+      // instead of creating a temporary.
+      if (ID < (MDStringRef.size() + GlobalMetadataBitPosIndex.size())) {
+        // Create a temporary for the node that is referencing the operand we
+        // will lazy-load. It is needed before recursing in case there are
+        // uniquing cycles.
+        MetadataList.getMetadataFwdRef(NextMetadataNo);
+        lazyLoadOneMetadata(ID, Placeholders);
+        return MetadataList.lookup(ID);
+      }
+      // Return a temporary.
       return MetadataList.getMetadataFwdRef(ID);
+    }
     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;

llvm/trunk/test/ThinLTO/X86/lazyload_metadata.ll

 ; RUN:  2>&1 | FileCheck %s -check-prefix=LAZY
 ; LAZY: 49 bitcode-reader  - Number of Metadata records loaded
 ; LAZY: 1 bitcode-reader  - Number of MDStrings loaded
 
 ; RUN: llvm-lto -thinlto-action=import %t2.bc -thinlto-index=%t3.bc \
 ; RUN:          -o /dev/null -disable-ondemand-mds-loading -stats \
 ; RUN:  2>&1 | FileCheck %s -check-prefix=NOTLAZY
 ; NOTLAZY: 58 bitcode-reader  - Number of Metadata records loaded
-; NOTLAZY: 8 bitcode-reader  - Number of MDStrings loaded
+; NOTLAZY: 6 bitcode-reader  - Number of MDStrings loaded
 
 
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.11.0"
 
 define void @globalfunc1(i32 %arg) {
   %tmp = add i32 %arg, 0, !metadata !2
   ret void
define void @globalfunc3(i32 %arg) {
   ret void
 }
 
 !1 = !{!2, !3, !4, !5, !6, !7, !8, !9}
 !2 = !{!"Hello World"}
 !3 = !{!"3"}
 !4 = !{!"4"}
 !5 = !{!"5"}
-!6 = !{!"6"}
+!6 = !{!9}
 !7 = !{!"7"}
 !8 = !{!"8"}
-!9 = !{!"9"}
+!9 = !{!6}