[ThinLTO] Refine reachability check to fix compile time increase

[tejohnson]

Summary

A recent fix to the ThinLTO whole program dead code elimination (D56117)
increased the thin link time on a large MSAN'ed binary by 2x.
It's likely that the time increased elsewhere, but was more noticeable
here since it was already large and ended up timing out.

That change made it so we would repeatedly scan all copies of linkonce
symbols for liveness every time they were encountered during the graph
traversal. This was needed since we only mark one copy of an aliasee as
live when we encounter a live alias. This patch fixes the issue in a
more efficient manner by simply proactively visiting the aliasee (thus
marking all copies live) when we encounter a live alias.

Two notes: One, this requires a hash table lookup (finding the aliasee
summary in the index based on aliasee GUID). However, the impact of this
seems to be small compared to the original pre-D56117 thin link time. It
could be addressed if we keep the aliasee ValueInfo in the alias summary
instead of the aliasee GUID, which I am exploring in a separate patch.

Second, we only populate the aliasee GUID field when reading summaries
from bitcode (whether we are reading individual summaries and merging on
the fly to form the compiled index, or reading in a serialized combined
index). Thankfully, that's currently the only way we can get to this
code as we don't yet support reading summaries from LLVM assembly
directly into a tool that performs the thin link (they must be converted
to bitcode first). I added a FIXME, however I have the fix under test
already. The easiest fix is to simply populate this field always, which
isn't hard, but more likely the change I am exploring to store the
ValueInfo instead as described above will subsume this. I don't want to
hold up the regression fix for this though.

[mehdi_amini]

lib/Transforms/IPO/FunctionImport.cpp

785

Just a drive-by nit: you can just turn the all_of to any_of I believe

[tejohnson]

lib/Transforms/IPO/FunctionImport.cpp

785

Sure I could do that. Note the above was the code here before the commit of D56117. Will change to any_of.

[tejohnson]

Use any_of as suggested in comments.

[mehdi_amini]

lib/Transforms/IPO/FunctionImport.cpp

830

I'm wondering about the continue here, the alias itself won't go through Summary->setLive(true); a few lines below, does it matter?
(I don't know if aliases can't have refs() as well, but it'll also skip the loop)

[trentxintong]

lib/Transforms/IPO/FunctionImport.cpp

830

My understanding is that the alias has already been set alive when it reaches here, i.e. only live GVs are pushed into the Worklist.

Thank you for improving this @tejohnson.

[trentxintong]

LGTM

[mehdi_amini]

lib/Transforms/IPO/FunctionImport.cpp

830

Then what is Summary->setLive(true); line for? It only applies to Summary coming from the worklist as well? It just seems strange that this is specific to aliases.

[trentxintong]

lib/Transforms/IPO/FunctionImport.cpp

830

@mehdi_amini Good question !. AFAIK, we need this setLive(true) in case of an alias (before this patch), because if we do not, we could make the alias alive but not the aliasee. And the thinlto backend will drop dead symbols. However, it does not seem this Summary->setLive(true) is necessary here because aliasee would have been set alive in the visit() function.

[tejohnson]

lib/Transforms/IPO/FunctionImport.cpp

830

We don't need to do the refs and calls iterations for an Alias, since it doesn't have any. The call to visit() that I added will ensure that the aliasee is marked live and added to the worklist if it is not already live, so the aliasee will come through this code eventually and have its refs/calls.

In terms of why I left in the setLive for non-aliases, I am not completely sure it is needed but didn't want to modify the non-alias handling in this patch. Also I had a slight concern that the code at line 760 which adds the initial live values to the worklist does not result in all copies being marked live (if say one was marked live in the per-module index during the summary analysis phase), and without marking all copies live here we would run into the same issue that motivated the patch I'm revising here (since visit() will return if any copy marked live). We can consider modifying this in a future patch but I just wanted to modify the alias handling here to be more efficient and not touch the other handling.

lib/Transforms/IPO/FunctionImport.cpp

auto visit = [&](ValueInfo VI) {
     // and ultimately promoting calls to functions not linked into this
     // binary, which increases the binary size unnecessarily. Note that
     // if this code changes, the importer needs to change so that edges
     // to functions marked dead are skipped.
     VI = updateValueInfoForIndirectCalls(Index, VI);
     if (!VI)
       return;
 
-    // We need to make sure all variants of the symbol are scanned, alias can
-    // make one (but not all) alive.
-    if (llvm::all_of(VI.getSummaryList(),
+    if (llvm::any_of(VI.getSummaryList(),
                      [](const std::unique_ptr<llvm::GlobalValueSummary> &S) {
                        return S->isLive();
                      }))
       return;
 
     // We only keep live symbols that are known to be non-prevailing if any are
     // available_externally, linkonceodr, weakodr. Those symbols are discarded
     // later in the EliminateAvailableExternally pass and setting them to
     // not-live could break downstreams users of liveness information (PR36483)
     // or limit optimization opportunities.
     if (isPrevailing(VI.getGUID()) == PrevailingType::No) {
       bool KeepAliveLinkage = false;
       bool Interposable = false;
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()) {
-      GlobalValueSummary *Base = Summary->getBaseObject();
-      // Set base value live in case it is an alias.
-      Base->setLive(true);
-      for (auto Ref : Base->refs())
+      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.
+        // FIXME: The aliasee GUID is only populated in the summary when we
+        // read them from bitcode, which is currently the only way we can
+        // get here (we don't yet support reading the summary index directly
+        // from LLVM assembly code in tools that can perform a thin link).
+        // If that ever changes, the below call to getAliaseGUID will assert.
+        visit(Index.getValueInfo(AS->getAliaseeGUID()));
+        continue;
+      }
+
+      Summary->setLive(true);
+      for (auto Ref : Summary->refs())
         visit(Ref);
-      if (auto *FS = dyn_cast<FunctionSummary>(Base))
+      if (auto *FS = dyn_cast<FunctionSummary>(Summary.get()))
         for (auto Call : FS->calls())
           visit(Call.first);
     }
   }
   Index.setWithGlobalValueDeadStripping();
 
   unsigned DeadSymbols = Index.size() - LiveSymbols;
   LLVM_DEBUG(dbgs() << LiveSymbols << " symbols Live, and " << DeadSymbols