[ThinLTO] Make inline assembly handling more efficient in summary

[tejohnson]

Summary

The change in r285513 to prevent exporting of locals used in
inline asm added all locals in the llvm.used set to the reference
set of functions containing inline asm. Since these locals were marked
NoRename, this automatically prevented importing of the function.

Unfortunately, this caused an explosion in the summary reference lists
in some cases. In my particular example, it happened for a large protocol
buffer generated C++ file, where many of the generated functions
contained an inline asm call. It was exacerbated when doing a ThinLTO
PGO instrumentation build, where the PGO instrumentation included
thousands of private __profd_* values that were added to llvm.used.

We really only need to include a single llvm.used local (NoRename) value
in the reference list of a function containing inline asm to block it
being imported. However, it seems cleaner to add a flag to the summary
that explicitly describes this situation, which is what this patch does.

[mehdi_amini]

I have to think about what it means in terms of invariants during the ThinLink (missing edges)

[tejohnson]

In D26402#589941, @mehdi_amini wrote:

I have to think about what it means in terms of invariants during the ThinLink (missing edges)

Remember we are currently only adding edges to locals in llvm.used/llvm.compiler.used sets anyway, for the purposes of limiting importing of the inline asm calling function, not even to all of the GVs listed in llvm.used/llvm.compiler.used. Also, all values in those sets are already referenced from the globalvar summary for the llvm.used or llvm.compiler.used, so they don't look dead.

[tejohnson]

Rebase after r286297.

[mehdi_amini]

Current thought: do we still need the NoRename flag or could this totally replace it?

[tejohnson]

In D26402#589970, @mehdi_amini wrote:

Current thought: do we still need the NoRename flag or could this totally replace it?

Possibly, e.g. we shouldn't have any existing external references to anything that is NoRename (since only locals matter, and they can't already have external references), so we could just mark the things that reference such values. with e.g. the new flag and prevent their importing. When building a summary, we could presumably walk through all references/calls from that and check whether any is a local that either has a section or is in a llvm(*).used set, and mark the referencing summary with this flag if so.

However, the NoRename flag is also used to prevent promotion of any of those values in the exporting module (the main module being compiled in the backend). Without this flag, we could presumably compute the set of NoRename values in the module on the fly the same way the ModuleSummary builder does though.

Not having the extra flag costs a bit more compile time but saves a bit in the flags (although in the common case where these flags are not set it is essentially free in the vbr encoded flag operand). I'm not sure which approach is better.

[mehdi_amini]

I'm not concerned about saving a bit of spending a little more compile time, but more about not maintaining redundant information, which can make things harder to understand in general (and invariant harder to maintain/enforce).

We shouldn't have to spend compile time in the promotion phase, and I don't expect this flag to be used here anyway, because we promote only what is exported and such "NoRename" symbol shouldn't be exported in the first place.

[tejohnson]

In D26402#590060, @mehdi_amini wrote:

I'm not concerned about saving a bit of spending a little more compile time, but more about not maintaining redundant information, which can make things harder to understand in general (and invariant harder to maintain/enforce).

We shouldn't have to spend compile time in the promotion phase, and I don't expect this flag to be used here anyway, because we promote only what is exported and such "NoRename" symbol shouldn't be exported in the first place.

Sort of - we will look at the export lists (actually the linkage as marked in the index) when we decide what to internalize, but not what to promote in renameModuleForThinLTO. This means that we first aggressively promote/rename what we can, then we internalize anything that didn't need to be promoted. It has been on my list of things to fix (see the FIXME in llvm::thinLTOInternalizeModule MustPromoteGV for example). I guess this is a good time to fix it. I think there is a quick fix since we are now getting the summary entry already in doPromoteLocalToGlobal in order to check the NoRename flag, it can just check the linkage type in the entry instead. Will try that out.

[tejohnson]

Sort of - we will look at the export lists (actually the linkage as marked in the index) when we decide what to internalize, but not what to promote in renameModuleForThinLTO. This means that we first aggressively promote/rename what we can, then we internalize anything that didn't need to be promoted. It has been on my list of things to fix (see the FIXME in llvm::thinLTOInternalizeModule MustPromoteGV for example). I guess this is a good time to fix it. I think there is a quick fix since we are now getting the summary entry already in doPromoteLocalToGlobal in order to check the NoRename flag, it can just check the linkage type in the entry instead. Will try that out.

See https://reviews.llvm.org/D26467 for the work to get the promotion logic to be selective based on the index for the exporting module.

[tejohnson]

In D26402#590932, @tejohnson wrote:

Sort of - we will look at the export lists (actually the linkage as marked in the index) when we decide what to internalize, but not what to promote in renameModuleForThinLTO. This means that we first aggressively promote/rename what we can, then we internalize anything that didn't need to be promoted. It has been on my list of things to fix (see the FIXME in llvm::thinLTOInternalizeModule MustPromoteGV for example). I guess this is a good time to fix it. I think there is a quick fix since we are now getting the summary entry already in doPromoteLocalToGlobal in order to check the NoRename flag, it can just check the linkage type in the entry instead. Will try that out.

See https://reviews.llvm.org/D26467 for the work to get the promotion logic to be selective based on the index for the exporting module.

I started to rebase this patch on top of D26467, but after adjusting the logic in the function importer, I think there is a good reason to keep the separate flags. We have a FIXME in the importer where we check if the current summary is eligible for importing:

// Can't import a global that needs renaming if has a section for instance.
// FIXME: we may be able to import it by copying it without promotion.

If we drop the NoRename flag, then we have no idea at thin link time which summaries must be copied in order to be imported. And if we have a single MayReferenceNoRename flag, it will then necessarily require being set in both the case where we have *possible* opaque references to non-renamable values, and where we know for sure it is referencing non-renamable values. We won't be able to distinguish when it is safe to import it unless we copy *all* local values referenced in the module (because we don't know which local values are non-renamable, and we don't know if the MayReferenceNoRename function call/reference set even contains all the necessary edges to those non-renamable locals vs a possible reference from opaque inline assembly).

I.e. let's say we have these three situations:

1. Non-opaque reference to a local variable that has a section

int X attribute ((section ("MYSECTION")));
foo() {

... = X;

}

2. Opaque use of local variable in inline asm call

static int Y;
bar() {

asm("...Y...");

}

3. Non-opaque use of a local defined in module level asm

module asm "Z: ..." // i.e. module level asm def of a local Z
baz() {

... = Z;

}

In cases 1 and 3 we could import the functions (foo and baz, respectively) if we did a copy without promotion/rename of the referenced non-renamable local.

In case 2 we cannot import bar, due to the opaque reference in the inline asm call (well, we could only if we copied in *all local values defined and referenced in the module* - we could potentially refine that set once we load the module during the backend import and see which are referenced from llvm.used/llvm.compiler.used, but we don't know this during the Thin Link).

With the current version of this patch, we can detect this because the foo and baz* summaries have a direct reference to the summaries of those locals, which are flagged as NoRename (and wouldn't have the MayReferenceNoRename flag set). And bar will simply have the MayReferenceNoRename flag set, preventing its import. (*baz will once r286297 is resubmitted)

If I change this to use a single MayReferenceNoRename flag, then when we are in the Thin Link these 3 cases are indistinguishable.

Note that D26467 (selective promotion) is still good and should go in independently.

[tejohnson]

On Sat, Nov 12, 2016 at 10:04 PM, Mehdi Amini <[e-mail]> wrote:

Not sure about 1: you can’t assume of whatever specific meaning is attached to a section in general.

Meaning we wouldn't necessarily be able to import as a copy? I was basing this suggestion on the discussion we had for the patch that initially limited importing of global values with sections (D18298), which is when the FIXME about importing these as copies was added.

In case 3, it is difficult because you don’t know what Z is referencing. And you would have to import the full module ASM block, which can contains another global, and then you’d define the global in two modules.

True, that is going to be difficult, we'd have to split out the module asm part defining the local Z and append that in the importing module. And ensure the module asm analysis looks for references of locals (it will already report uses of globals). Maybe not worth the trouble.

Also, if you still want to keep the separated flag, then MayReferenceNoRename isn’t great: it should be targeting the case 2 you mentioned exclusively, so it should be something like HasInlineASMReferencingInternal or something like that.

Ok, will update the name. Although we don't know for sure whether the inline asm references a local, so perhaps HasInlineASMMaybeReferencingInternal.
A mouthful, but more descriptive.

[tejohnson]

Rename new flag as per review.

[mehdi_amini]

LGTM.

In D26402#594367, @tejohnson wrote:

On Sat, Nov 12, 2016 at 10:04 PM, Mehdi Amini <[e-mail]> wrote:

Not sure about 1: you can’t assume of whatever specific meaning is attached to a section in general.

Meaning we wouldn't necessarily be able to import as a copy? I was basing this suggestion on the discussion we had for the patch that initially limited importing of global values with sections (D18298), which is when the FIXME about importing these as copies was added.

Yes, I'm not sure it is always legal to copy. LangRef is fairly vague with sections at the IR level though. We can always try and see what breaks in practice :)

Also, if you still want to keep the separated flag, then MayReferenceNoRename isn’t great: it should be targeting the case 2 you mentioned exclusively, so it should be something like HasInlineASMReferencingInternal or something like that.

Ok, will update the name. Although we don't know for sure whether the inline asm references a local, so perhaps HasInlineASMMaybeReferencingInternal.
A mouthful, but more descriptive.

Right, I was already finding my original suggestion long, apparently you can do better :)

include/llvm/IR/ModuleSummaryIndex.h

struct GVFlags {
     /// In the future this will be used to update and optimize linkage
     /// types based on global summary-based analysis.
     unsigned Linkage : 4;
 
     /// Indicate if the global value cannot be renamed (in a specific section,
     /// possibly referenced from inline assembly, etc).
     unsigned NoRename : 1;
 
+    /// Indicate if a function contains inline assembly (which is opaque),
+    /// that may reference a local value. This is used to prevent importing
+    /// of this function, since we can't promote and rename the uses of the
+    /// local in the inline assembly. Use a flag rather than bloating the
+    /// summary with references to every possible local value in the
+    /// llvm.used set.
+    unsigned HasInlineAsmMaybeReferencingInternal : 1;
+
     /// Indicate if the function is not viable to inline.
     unsigned IsNotViableToInline : 1;
 
     /// Convenience Constructors
     explicit GVFlags(GlobalValue::LinkageTypes Linkage, bool NoRename,
+                     bool HasInlineAsmMaybeReferencingInternal,
                      bool IsNotViableToInline)
         : Linkage(Linkage), NoRename(NoRename),
+          HasInlineAsmMaybeReferencingInternal(
+              HasInlineAsmMaybeReferencingInternal),
           IsNotViableToInline(IsNotViableToInline) {}
 
     GVFlags(const GlobalValue &GV)
-        : Linkage(GV.getLinkage()), NoRename(GV.hasSection()) {
+        : Linkage(GV.getLinkage()), NoRename(GV.hasSection()),
+          HasInlineAsmMaybeReferencingInternal(false) {
       IsNotViableToInline = false;
       if (const auto *F = dyn_cast<Function>(&GV))
         // Inliner doesn't handle variadic functions.
         // FIXME: refactor this to use the same code that inliner is using.
         IsNotViableToInline = F->isVarArg();
     }
   };
 
public:
   /// Return true if this global value cannot be renamed (in a specific section,
   /// possibly referenced from inline assembly, etc).
   bool noRename() const { return Flags.NoRename; }
 
   /// Flag that this global value cannot be renamed (in a specific section,
   /// possibly referenced from inline assembly, etc).
   void setNoRename() { Flags.NoRename = true; }
 
+  /// Return true if this global value possibly references another value
+  /// that can't be renamed.
+  bool hasInlineAsmMaybeReferencingInternal() const {
+    return Flags.HasInlineAsmMaybeReferencingInternal;
+  }
+
+  /// Flag that this global value possibly references another value that
+  /// can't be renamed.
+  void setHasInlineAsmMaybeReferencingInternal() {
+    Flags.HasInlineAsmMaybeReferencingInternal = true;
+  }
+
   /// Record a reference from this global value to the global value identified
   /// by \p RefGUID.
   void addRefEdge(GlobalValue::GUID RefGUID) { RefEdgeList.push_back(RefGUID); }
 
   /// Record a reference from this global value to the global value identified
   /// by \p RefV.
   void addRefEdge(const Value *RefV) { RefEdgeList.push_back(RefV); }
 

lib/Analysis/ModuleSummaryAnalysis.cpp

static CalleeInfo::HotnessType getHotness(uint64_t ProfileCount,
   if (PSI->isColdCount(ProfileCount))
     return CalleeInfo::HotnessType::Cold;
   return CalleeInfo::HotnessType::None;
 }
 
 static void computeFunctionSummary(ModuleSummaryIndex &Index, const Module &M,
                                    const Function &F, BlockFrequencyInfo *BFI,
                                    ProfileSummaryInfo *PSI,
-                                   SmallPtrSetImpl<GlobalValue *> &LocalsUsed) {
+                                   bool HasLocalsInUsed) {
   // Summary not currently supported for anonymous functions, they should
   // have been named.
   assert(F.hasName());
 
   unsigned NumInsts = 0;
   // Map from callee ValueId to profile count. Used to accumulate profile
   // counts for all static calls to a given callee.
   DenseMap<const Value *, CalleeInfo> CallGraphEdges;
   DenseMap<GlobalValue::GUID, CalleeInfo> IndirectCallEdges;
   DenseSet<const Value *> RefEdges;
   ICallPromotionAnalysis ICallAnalysis;
-  bool HasLocalsInUsed = !LocalsUsed.empty();
 
+  bool HasInlineAsmMaybeReferencingInternal = false;
   SmallPtrSet<const User *, 8> Visited;
   for (const BasicBlock &BB : F)
     for (const Instruction &I : BB) {
       if (isa<DbgInfoIntrinsic>(I))
         continue;
       ++NumInsts;
       findRefEdges(&I, RefEdges, Visited);
       auto CS = ImmutableCallSite(&I);
       if (!CS)
         continue;
 
       const auto *CI = dyn_cast<CallInst>(&I);
       // Since we don't know exactly which local values are referenced in inline
-      // assembly, conservatively reference all of them from this function, to
-      // ensure we don't export a reference (which would require renaming and
-      // promotion).
+      // assembly, conservatively mark the function as possibly referencing
+      // a local value from inline assembly to ensure we don't export a
+      // reference (which would require renaming and promotion of the
+      // referenced value).
       if (HasLocalsInUsed && CI && CI->isInlineAsm())
-        RefEdges.insert(LocalsUsed.begin(), LocalsUsed.end());
+        HasInlineAsmMaybeReferencingInternal = true;
 
       auto *CalledValue = CS.getCalledValue();
       auto *CalledFunction = CS.getCalledFunction();
       // Check if this is an alias to a function. If so, get the
       // called aliasee for the checks below.
       if (auto *GA = dyn_cast<GlobalAlias>(CalledValue)) {
         assert(!CalledFunction && "Expected null called function in callsite for alias");
         CalledFunction = dyn_cast<Function>(GA->getBaseObject());
for (const BasicBlock &BB : F)
     }
 
   GlobalValueSummary::GVFlags Flags(F);
   std::unique_ptr<FunctionSummary> FuncSummary =
       llvm::make_unique<FunctionSummary>(Flags, NumInsts);
   FuncSummary->addCallGraphEdges(CallGraphEdges);
   FuncSummary->addCallGraphEdges(IndirectCallEdges);
   FuncSummary->addRefEdges(RefEdges);
+  if (HasInlineAsmMaybeReferencingInternal)
+    FuncSummary->setHasInlineAsmMaybeReferencingInternal();
   Index.addGlobalValueSummary(F.getName(), std::move(FuncSummary));
 }
 
 static void computeVariableSummary(ModuleSummaryIndex &Index,
                                    const GlobalVariable &V) {
   DenseSet<const Value *> RefEdges;
   SmallPtrSet<const User *, 8> Visited;
   findRefEdges(&V, RefEdges, Visited);
if (GetBFICallback)
       BFI = GetBFICallback(F);
     else if (F.getEntryCount().hasValue()) {
       LoopInfo LI{DominatorTree(const_cast<Function &>(F))};
       BranchProbabilityInfo BPI{F, LI};
       BFIPtr = llvm::make_unique<BlockFrequencyInfo>(F, BPI, LI);
       BFI = BFIPtr.get();
     }
 
-    computeFunctionSummary(Index, M, F, BFI, PSI, LocalsUsed);
+    computeFunctionSummary(Index, M, F, BFI, PSI, !LocalsUsed.empty());
   }
 
   // Compute summaries for all variables defined in module, and save in the
   // index.
   for (const GlobalVariable &G : M.globals()) {
     if (G.isDeclaration())
       continue;
     computeVariableSummary(Index, G);

lib/Bitcode/Reader/BitcodeReader.cpp

static GlobalValueSummary::GVFlags getDecodedGVSummaryFlags(uint64_t RawFlags,
                                                             uint64_t Version) {
   // Summary were not emitted before LLVM 3.9, we don't need to upgrade Linkage
   // like getDecodedLinkage() above. Any future change to the linkage enum and
   // to getDecodedLinkage() will need to be taken into account here as above.
   auto Linkage = GlobalValue::LinkageTypes(RawFlags & 0xF); // 4 bits
   RawFlags = RawFlags >> 4;
   bool NoRename = RawFlags & 0x1;
   bool IsNotViableToInline = RawFlags & 0x2;
-  return GlobalValueSummary::GVFlags(Linkage, NoRename, IsNotViableToInline);
+  bool HasInlineAsmMaybeReferencingInternal = RawFlags & 0x4;
+  return GlobalValueSummary::GVFlags(Linkage, NoRename,
+                                     HasInlineAsmMaybeReferencingInternal,
+                                     IsNotViableToInline);
 }
 
 static GlobalValue::VisibilityTypes getDecodedVisibility(unsigned Val) {
   switch (Val) {
   default: // Map unknown visibilities to default.
   case 0: return GlobalValue::DefaultVisibility;
   case 1: return GlobalValue::HiddenVisibility;
   case 2: return GlobalValue::ProtectedVisibility;

lib/Bitcode/Writer/BitcodeWriter.cpp

 }
 
 // Decode the flags for GlobalValue in the summary
 static uint64_t getEncodedGVSummaryFlags(GlobalValueSummary::GVFlags Flags) {
   uint64_t RawFlags = 0;
 
   RawFlags |= Flags.NoRename; // bool
   RawFlags |= (Flags.IsNotViableToInline << 1);
+  RawFlags |= (Flags.HasInlineAsmMaybeReferencingInternal << 2);
   // Linkage don't need to be remapped at that time for the summary. Any future
   // change to the getEncodedLinkage() function will need to be taken into
   // account here as well.
   RawFlags = (RawFlags << 4) | Flags.Linkage; // 4 bits
 
   return RawFlags;
 }
 

lib/Transforms/IPO/FunctionImport.cpp

if (!canBeExternallyReferenced(Summary))
     return false;
 
   // Don't import functions that are not viable to inline.
   if (Summary.isNotViableToInline())
     return false;
 
   // Check references (and potential calls) in the same module. If the current
   // value references a global that can't be externally referenced it is not
-  // eligible for import.
+  // eligible for import. First check the flag set when we have possible
+  // opaque references (e.g. inline asm calls), then check the call and
+  // reference sets.
+  if (Summary.hasInlineAsmMaybeReferencingInternal())
+    return false;
   bool AllRefsCanBeExternallyReferenced =
       llvm::all_of(Summary.refs(), [&](const ValueInfo &VI) {
         return canBeExternallyReferenced(Index, VI.getGUID());
       });
   if (!AllRefsCanBeExternallyReferenced)
     return false;
 
   if (auto *FuncSummary = dyn_cast<FunctionSummary>(&Summary)) {