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

348–360

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.

353

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

495

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;
 
+  // ImportedEntities - A list of imported entities. Does not own.
+  SmallVector<const DIImportedEntity*, 10> 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.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)) {
     unsigned ChildScopeCount;
 
     // 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()) {
+      SmallVector<const DIImportedEntity*, 8> Entities;
       // There is no need to emit empty lexical block DIE.
-      for (const auto &E : DD->findImportedEntitiesForScope(DS))
+      for (const auto &E : DD->findImportedEntitiesForScope(DS)) {
         Children.push_back(
             constructImportedEntityDIE(cast<DIImportedEntity>(E.second)));
+        Entities.push_back(cast<DIImportedEntity>(E.second));
+      }
+
+      uint i = 0;
+      for (const auto *IE : ImportedEntities) {
+        if (IE->getScope() == DS) {
+          assert(i < Entities.size());
+          assert(Entities[i] == IE);
+          i++;
+        }
+      }
+      assert(i == Entities.size());
     }
 
     // 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()));

lib/CodeGen/AsmPrinter/DwarfDebug.h

class DwarfDebug : public AsmPrinterHandler {
 
   /// 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;
+  bool IsScopesWithImportedEntitiesSorted;
 
   /// 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 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()));
-  }
+  findImportedEntitiesForScope(const MDNode *Scope);
 
   /// 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);
 

lib/CodeGen/AsmPrinter/DwarfDebug.cpp

if (!CU_Nodes)
     return;
   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())
+    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);
+    }
+    IsScopesWithImportedEntitiesSorted = false;
+
     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 (const auto &Var : ConcreteVariables) {
     if (AbsVar && AbsVar->getDIE()) {
       Unit->addDIEEntry(*VariableDie, dwarf::DW_AT_abstract_origin,
                         *AbsVar->getDIE());
     } else
       Unit->applyVariableAttributes(*Var, *VariableDie);
   }
 }
 
+iterator_range<DwarfDebug::ImportedEntityMap::const_iterator>
+DwarfDebug::findImportedEntitiesForScope(const MDNode *Scope) {
+    // 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; }
+    if (!IsScopesWithImportedEntitiesSorted) {
+      std::stable_sort(ScopesWithImportedEntities.begin(),
+                       ScopesWithImportedEntities.end(), less_first());
+      IsScopesWithImportedEntitiesSorted = true;
+    }
+
+    return make_range(std::equal_range(
+        ScopesWithImportedEntities.begin(), ScopesWithImportedEntities.end(),
+        std::pair<const MDNode *, const MDNode *>(Scope, nullptr),
+        less_first()));
+}
+
 void DwarfDebug::finishSubprogramDefinitions() {
   for (const auto &P : SPMap)
     forBothCUs(*P.second, [&](DwarfCompileUnit &CU) {
       CU.finishSubprogramDefinition(cast<DISubprogram>(P.first));
     });
 }