[ThinLTO] Compile time improvement to propagateAttributes

[tejohnson]

Summary

I found that propagateAttributes was ~23% of a thin link's run time
(almost 4x higher than the second hottest function). The main reason is
that it re-examines a global var each time it is referenced. This
becomes unnecessary once it is marked both non read only and non write
only. I added a set to avoid doing redundant work, which dropped the
runtime of that thin link by almost 15%.

I made a smaller efficiency improvement (no measurable impact) to skip
all summaries for a VI if the first copy is dead. I added an assert to
ensure that all copies are dead if any is. The code in
computeDeadSymbols marks all summaries for a VI as live. There is one
corner case where it was skipping marking an alias as live, that I
fixed. However, since the code earlier marked all copies of a preserved
GUID's VI as live, and each 'visit' marks all copies live, the only case
where this could make a difference is summaries that were marked live
when they were built initially, and that is only a few special compiler
generated symbols and inline assembly symbols, so it likely is never
provoked in practice.

[evgeny777]

I made a smaller efficiency improvement (no measurable impact) to skip all summaries for a VI if the first copy is dead. I added an assert to ensure that all copies are dead if any is....

Will this work correctly in case of GUID collision? (see https://reviews.llvm.org/D67322)
BTW, what's the maximum performance improvement you got in absolute values?

llvm/lib/IR/ModuleSummaryIndex.cpp

179

nit: you can check for !VI.getAccessSpecifier() here and probably refactor the assertion above

[tejohnson]

In D84985#2187270, @evgeny777 wrote:

I made a smaller efficiency improvement (no measurable impact) to skip all summaries for a VI if the first copy is dead. I added an assert to ensure that all copies are dead if any is....

Will this work correctly in case of GUID collision? (see https://reviews.llvm.org/D67322)

The code in computeDeadSymbols will conservatively mark all copies live if any is. See not only the worklist iteration I modified here, but also the code in visit at lines 878-879, and the preserved GUID handling at lines 814-815. So if there is a collision, the colliding values may conservatively be marked live, so the loop in propagateAttributes will handle them. I.e they are either all dead or all live (especially after my fix here which will make the behavior more conservative in the chance case of any alias values that collide with a value marked live during module summary building). Other than the corner case I'm fixing here, this should be a no-op in behavior for that loop in propagateAttributes, which was already skipping all dead values, and which does check if it is a GlobalVarSummary already.

BTW, what's the maximum performance improvement you got in absolute values?

In a large binary build I saw this shave off ~10-11s in a ~71s thin link.

llvm/lib/IR/ModuleSummaryIndex.cpp

179

Will change the check here. Not sure what you want me to do with the assert though? There's not a convenient else below to put an assertion that just checks the isa<> when the access specifier is null, since it is an else if.

[tejohnson]

Address comment

[evgeny777]

The code in computeDeadSymbols will conservatively mark all copies live if any is. See not only the worklist iteration I modified here, but also the code in visit at lines 878-879, and the preserved GUID handling at lines 814-815. So if there is a collision, the colliding values may conservatively be marked live, so the loop in propagateAttributes will handle them. I.e they are either all dead or all live (especially after my fix here which will make the behavior more conservative in the chance case of any alias values that collide with a value marked live during module summary building). Other than the corner case I'm fixing here, this should be a no-op in behavior for that loop in propagateAttributes, which was already skipping all dead values, and which does check if it is a GlobalVarSummary already.

Ok, got it. My understanding is that collision still may happen between internal module asm symbol (because those have Live = true after analysis) and some other internal symbol with the same name (and module name) which is computed dead. This is rather unlikely to happen in reality, but please leave a comment about this before assertion. That said LGTM.

llvm/lib/IR/ModuleSummaryIndex.cpp

179

Ah, ok. Let's leave assert where it is.

[tejohnson]

In D84985#2187681, @evgeny777 wrote:

The code in computeDeadSymbols will conservatively mark all copies live if any is. See not only the worklist iteration I modified here, but also the code in visit at lines 878-879, and the preserved GUID handling at lines 814-815. So if there is a collision, the colliding values may conservatively be marked live, so the loop in propagateAttributes will handle them. I.e they are either all dead or all live (especially after my fix here which will make the behavior more conservative in the chance case of any alias values that collide with a value marked live during module summary building). Other than the corner case I'm fixing here, this should be a no-op in behavior for that loop in propagateAttributes, which was already skipping all dead values, and which does check if it is a GlobalVarSummary already.

Ok, got it. My understanding is that collision still may happen between internal module asm symbol (because those have Live = true after analysis) and some other internal symbol with the same name (and module name) which is computed dead. This is rather unlikely to happen in reality, but please leave a comment about this before assertion. That said LGTM.

I'll add a comment. The collision may still happen, but the in reality dead symbol will conservatively have been marked live by computeDeadSymbols.

[tejohnson]

Improve comment

llvm/lib/IR/ModuleSummaryIndex.cpp

bool ModuleSummaryIndex::isGUIDLive(GlobalValue::GUID GUID) const {
   if (SummaryList.empty())
     return true;
   for (auto &I : SummaryList)
     if (isGlobalValueLive(I.get()))
       return true;
   return false;
 }
 
-static void propagateAttributesToRefs(GlobalValueSummary *S) {
+static void
+propagateAttributesToRefs(GlobalValueSummary *S,
+                          DenseSet<ValueInfo> &MarkedNonReadWriteOnly) {
   // If reference is not readonly or writeonly then referenced summary is not
   // read/writeonly either. Note that:
   // - All references from GlobalVarSummary are conservatively considered as
   //   not readonly or writeonly. Tracking them properly requires more complex
   //   analysis then we have now.
   //
   // - AliasSummary objects have no refs at all so this function is a no-op
   //   for them.
   for (auto &VI : S->refs()) {
     assert(VI.getAccessSpecifier() == 0 || isa<FunctionSummary>(S));
+    if (!VI.getAccessSpecifier()) {
+      if (!MarkedNonReadWriteOnly.insert(VI).second)
+        continue;
+    } else if (MarkedNonReadWriteOnly.find(VI) != MarkedNonReadWriteOnly.end())
+      continue;
     for (auto &Ref : VI.getSummaryList())
       // If references to alias is not read/writeonly then aliasee
       // is not read/writeonly
       if (auto *GVS = dyn_cast<GlobalVarSummary>(Ref->getBaseObject())) {
         if (!VI.isReadOnly())
           GVS->setReadOnly(false);
         if (!VI.isWriteOnly())
           GVS->setWriteOnly(false);

 //   and modified by function B.
 //
 // Internalization itself happens in the backend after import is finished
 // See internalizeGVsAfterImport.
 void ModuleSummaryIndex::propagateAttributes(
     const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) {
   if (!PropagateAttrs)
     return;
+  DenseSet<ValueInfo> MarkedNonReadWriteOnly;
   for (auto &P : *this)
     for (auto &S : P.second.SummaryList) {
-      if (!isGlobalValueLive(S.get()))
+      if (!isGlobalValueLive(S.get())) {
+        // computeDeadSymbols should have marked all copies live. Note that
+        // it is possible that there is a GUID collision between internal
+        // symbols with the same name in different files of the same name but
+        // not enough distinguishing path. Because computeDeadSymbols should
+        // conservatively mark all copies live we can assert here that all are
+        // dead if any copy is dead.
+        assert(llvm::none_of(
+            P.second.SummaryList,
+            [&](const std::unique_ptr<GlobalValueSummary> &Summary) {
+              return isGlobalValueLive(Summary.get());
+            }));
         // We don't examine references from dead objects
-        continue;
+        break;
+      }
 
       // Global variable can't be marked read/writeonly if it is not eligible
       // to import since we need to ensure that all external references get
       // a local (imported) copy. It also can't be marked read/writeonly if
       // it or any alias (since alias points to the same memory) are preserved
       // or notEligibleToImport, since either of those means there could be
       // writes (or reads in case of writeonly) that are not visible (because
       // preserved means it could have external to DSO writes or reads, and
       // notEligibleToImport means it could have writes or reads via inline
       // assembly leading it to be in the @llvm.*used).
       if (auto *GVS = dyn_cast<GlobalVarSummary>(S->getBaseObject()))
         // Here we intentionally pass S.get() not GVS, because S could be
         // an alias. We don't analyze references here, because we have to
         // know exactly if GV is readonly to do so.
         if (!canImportGlobalVar(S.get(), /* AnalyzeRefs */ false) ||
             GUIDPreservedSymbols.count(P.first)) {
           GVS->setReadOnly(false);
           GVS->setWriteOnly(false);
         }
-      propagateAttributesToRefs(S.get());
+      propagateAttributesToRefs(S.get(), MarkedNonReadWriteOnly);
     }
   setWithAttributePropagation();
   if (llvm::AreStatisticsEnabled())
     for (auto &P : *this)
       if (P.second.SummaryList.size())
         if (auto *GVS = dyn_cast<GlobalVarSummary>(
                 P.second.SummaryList[0]->getBaseObject()))
           if (isGlobalValueLive(GVS)) {

llvm/lib/Transforms/IPO/FunctionImport.cpp

for (auto &S : VI.getSummaryList())
       S->setLive(true);
     ++LiveSymbols;
     Worklist.push_back(VI);
   };
 
   while (!Worklist.empty()) {
     auto VI = Worklist.pop_back_val();
     for (auto &Summary : VI.getSummaryList()) {
+      Summary->setLive(true);
       if (auto *AS = dyn_cast<AliasSummary>(Summary.get())) {
         // If this is an alias, visit the aliasee VI to ensure that all copies
         // are marked live and it is added to the worklist for further
         // processing of its references.
         visit(AS->getAliaseeVI(), true);
         continue;
       }
-
-      Summary->setLive(true);
       for (auto Ref : Summary->refs())
         visit(Ref, false);
       if (auto *FS = dyn_cast<FunctionSummary>(Summary.get()))
         for (auto Call : FS->calls())
           visit(Call.first, false);
     }
   }
   Index.setWithGlobalValueDeadStripping();