Move imported entities into DwarfCompilationUnit to speed up LTO linking.

[krasin]

Summary

In particular, this CL speeds up the official Chrome linking with LTO by
1.8x.

See more details in https://crbug.com/542426

[krasin]

.

[krasin]

• Remove leftovers

[krasin]

NOT FOR SUBMIT: verification code with old and new approaches.

[krasin]

Reduce the diff

[krasin]

Diff is even smaller

[krasin]

Now, it's only new code. Correct, but not fully optimized for speed yet.

[krasin]

Use DenseMap.

[dblaikie]

Looks great - thanks for your patience/perseverance on this. I think the net result is a better design & better performance.

Please commit whenever you're ready (couple of optional brace issues, but nothing else to worry about).

lib/CodeGen/AsmPrinter/DwarfCompileUnit.cpp

345–347

You could drop the braces on the single-statement loop (as with the original code) - some people prefer to have them for multiline blocks, even if it's a single statement.

350

This verification code looks good to me - so if that's passing when running over a large project like Chrome, I'm happy enough that this is doing the right thing.

lib/CodeGen/AsmPrinter/DwarfDebug.cpp

494

drop the braces on a single-line block (matches the code that follows)

[krasin]

sync

[krasin]

• Remove unnecessary braces

[krasin]

I am running last checks and will submit after that.
This variant is actually slower than the initial one. I have measured 65 minutes for linking the official Chrome with LTO and CFI versus 55 minutes originally.
I have a feeling that there's something could be done about that. Moving the logic into DwarfCompilationUnit is unlikely to be the reason for the slowdown.

[krasin]

svn

lib/CodeGen/AsmPrinter/DwarfCompileUnit.h

class DwarfCompileUnit : public DwarfUnit {
   DIE::value_iterator StmtListValue;
 
   /// Skeleton unit associated with this unit.
   DwarfCompileUnit *Skeleton;
 
   /// The start of the unit within its section.
   MCSymbol *LabelBegin;
 
+  typedef llvm::SmallVector<const MDNode *, 8> ImportedEntityList;
+  typedef llvm::DenseMap<const MDNode *, ImportedEntityList>
+  ImportedEntityMap;
+
+  ImportedEntityMap ImportedEntities;
+
   /// GlobalNames - A map of globally visible named entities for this unit.
   StringMap<const DIE *> GlobalNames;
 
   /// GlobalTypes - A map of globally visible types for this unit.
   StringMap<const DIE *> GlobalTypes;
 
   // List of range lists for a given compile unit, separate from the ranges for
   // the CU itself.
public:
   /// addSectionDelta - Add a label delta attribute data and value.
   DIE::value_iterator addSectionDelta(DIE &Die, dwarf::Attribute Attribute,
                                       const MCSymbol *Hi, const MCSymbol *Lo);
 
   DwarfCompileUnit &getCU() override { return *this; }
 
   unsigned getOrCreateSourceID(StringRef FileName, StringRef DirName) override;
 
+  void addImportedEntity(const DIImportedEntity* IE) {
+    ImportedEntities[IE->getScope()].push_back(IE);
+  }
+
   /// addRange - Add an address range to the list of ranges for this unit.
   void addRange(RangeSpan Range);
 
   void attachLowHighPC(DIE &D, const MCSymbol *Begin, const MCSymbol *End);
 
   /// addSectionLabel - Add a Dwarf section label attribute data and value.
   ///
   DIE::value_iterator addSectionLabel(DIE &Die, dwarf::Attribute Attribute,

lib/CodeGen/AsmPrinter/DwarfCompileUnit.cpp

if (Scope->getParent() && isa<DISubprogram>(DS)) {
 
     // We create children here when we know the scope DIE is not going to be
     // null and the children will be added to the scope DIE.
     createScopeChildrenDIE(Scope, Children, &ChildScopeCount);
 
     // Skip imported directives in gmlt-like data.
     if (!includeMinimalInlineScopes()) {
       // There is no need to emit empty lexical block DIE.
-      for (const auto &E : DD->findImportedEntitiesForScope(DS))
+      for (const auto *IE : ImportedEntities[DS])
           Children.push_back(
-            constructImportedEntityDIE(cast<DIImportedEntity>(E.second)));
+              constructImportedEntityDIE(cast<DIImportedEntity>(IE)));
     }
 
     // If there are only other scopes as children, put them directly in the
     // parent instead, as this scope would serve no purpose.
     if (Children.size() == ChildScopeCount) {
       FinalChildren.insert(FinalChildren.end(),
                            std::make_move_iterator(Children.begin()),
                            std::make_move_iterator(Children.end()));
       return;
     }
     ScopeDIE = constructLexicalScopeDIE(Scope);

lib/CodeGen/AsmPrinter/DwarfDebug.h

class DwarfDebug : public AsmPrinterHandler {
   StringRef CompilationDir;
 
   /// Holder for the file specific debug information.
   DwarfFile InfoHolder;
 
   /// Holders for the various debug information flags that we might need to
   /// have exposed. See accessor functions below for description.
 
-  /// Holder for imported entities.
-  typedef SmallVector<std::pair<const MDNode *, const MDNode *>, 32>
-  ImportedEntityMap;
-  ImportedEntityMap ScopesWithImportedEntities;
-
   /// Map from MDNodes for user-defined types to the type units that
   /// describe them.
   DenseMap<const MDNode *, const DwarfTypeUnit *> DwarfTypeUnits;
 
   SmallVector<
       std::pair<std::unique_ptr<DwarfTypeUnit>, const DICompositeType *>, 1>
       TypeUnitsUnderConstruction;
 
public:
   void addAccelObjC(StringRef Name, const DIE &Die);
 
   void addAccelNamespace(StringRef Name, const DIE &Die);
 
   void addAccelType(StringRef Name, const DIE &Die, char Flags);
 
   const MachineFunction *getCurrentFunction() const { return CurFn; }
 
-  iterator_range<ImportedEntityMap::const_iterator>
-  findImportedEntitiesForScope(const MDNode *Scope) const {
-    return make_range(std::equal_range(
-        ScopesWithImportedEntities.begin(), ScopesWithImportedEntities.end(),
-        std::pair<const MDNode *, const MDNode *>(Scope, nullptr),
-        less_first()));
-  }
-
   /// A helper function to check whether the DIE for a given Scope is
   /// going to be null.
   bool isLexicalScopeDIENull(LexicalScope *Scope);
 
   /// Return Label preceding the instruction.
   MCSymbol *getLabelBeforeInsn(const MachineInstr *MI);
 
   /// Return Label immediately following the instruction.

lib/CodeGen/AsmPrinter/DwarfDebug.cpp

void DwarfDebug::beginModule() {
   TypeIdentifierMap = generateDITypeIdentifierMap(CU_Nodes);
 
   SingleCU = CU_Nodes->getNumOperands() == 1;
 
   for (MDNode *N : CU_Nodes->operands()) {
     auto *CUNode = cast<DICompileUnit>(N);
     DwarfCompileUnit &CU = constructDwarfCompileUnit(CUNode);
     for (auto *IE : CUNode->getImportedEntities())
-      ScopesWithImportedEntities.push_back(std::make_pair(IE->getScope(), IE));
-    // Stable sort to preserve the order of appearance of imported entities.
-    // This is to avoid out-of-order processing of interdependent declarations
-    // within the same scope, e.g. { namespace A = base; namespace B = A; }
-    std::stable_sort(ScopesWithImportedEntities.begin(),
-                     ScopesWithImportedEntities.end(), less_first());
+      CU.addImportedEntity(IE);
     for (auto *GV : CUNode->getGlobalVariables())
       CU.getOrCreateGlobalVariableDIE(GV);
     for (auto *SP : CUNode->getSubprograms())
       SPMap.insert(std::make_pair(SP, &CU));
     for (auto *Ty : CUNode->getEnumTypes()) {
       // The enum types array by design contains pointers to
       // MDNodes rather than DIRefs. Unique them here.
       CU.getOrCreateTypeDIE(cast<DIType>(resolve(Ty->getRef())));
     }
     for (auto *Ty : CUNode->getRetainedTypes()) {