Avoid having a map for edges

ELF/CallGraphSort.cpp

 #include "SymbolTable.h"
 #include "Symbols.h"
 
 using namespace llvm;
 using namespace lld;
 using namespace lld::elf;
 
 namespace {
+struct Edge {
+  int From;
+  uint64_t Weight;
+};
+
 struct Cluster {
   Cluster(int Sec, size_t S) {
     Sections.push_back(Sec);
     Size = S;
   }
 
   double getDensity() const {
     if (Size == 0)
       return 0;
     return double(Weight) / double(Size);
   }
 
   std::vector<int> Sections;
   size_t Size = 0;
   uint64_t Weight = 0;
   uint64_t InitialWeight = 0;
-  std::vector<int> Preds;
-};
-
-struct Edge {
-  int From;
-  int To;
-  uint64_t Weight;
-};
-
-struct EdgeDenseMapInfo {
-  static Edge getEmptyKey() {
-    return {DenseMapInfo<int>::getEmptyKey(), DenseMapInfo<int>::getEmptyKey(),
-            0};
-  }
-  static Edge getTombstoneKey() {
-    return {DenseMapInfo<int>::getTombstoneKey(),
-            DenseMapInfo<int>::getTombstoneKey(), 0};
-  }
-  static unsigned getHashValue(const Edge &Val) {
-    return hash_combine(DenseMapInfo<int>::getHashValue(Val.From),
-                        DenseMapInfo<int>::getHashValue(Val.To));
-  }
-  static bool isEqual(const Edge &LHS, const Edge &RHS) {
-    return LHS.From == RHS.From && LHS.To == RHS.To;
-  }
+  std::vector<Edge> Preds;
 };
 
 class CallGraphSort {
 public:
   CallGraphSort();
 
   DenseMap<const InputSectionBase *, int> run();
 
 private:
-  DenseMap<Edge, int, EdgeDenseMapInfo> EdgeMap;
   std::vector<Cluster> Clusters;
-  std::vector<Edge> Edges;
   std::vector<const InputSectionBase *> Sections;
 
   void groupClusters();
 };
 
 // Maximum ammount the combined cluster density can be worse than the original
 // cluster to consider merging.
 constexpr int MAX_DENSITY_DEGRADATION = 8;
 
 // Maximum cluster size in bytes.
 constexpr uint64_t MAX_CLUSTER_SIZE = 1024 * 1024;
 } // end anonymous namespace
 
 // Take the edge list in Config->CallGraphProfile, resolve symbol names to
 // Symbols, and generate a graph between InputSections with the provided
 // weights.
 CallGraphSort::CallGraphSort() {
-  llvm::MapVector<std::pair<const Symbol *, const Symbol *>, uint64_t>
-      &Profile = Config->CallGraphProfile;
+  llvm::MapVector<std::pair<const InputSectionBase *, const InputSectionBase *>,
+                  uint64_t> &Profile = Config->CallGraphProfile;
   DenseMap<const InputSectionBase *, int> SecToCluster;
 
   auto GetOrCreateNode = [&](const InputSectionBase *IS) -> int {
     auto Res = SecToCluster.insert(std::make_pair(IS, Clusters.size()));
     if (Res.second) {
       Sections.push_back(IS);
       Clusters.emplace_back(Clusters.size(), IS->getSize());
     }
     return Res.first->second;
   };
 
   // Create the graph.
   for (const auto &C : Profile) {
-    warnUnorderableSymbol(C.first.first);
-    warnUnorderableSymbol(C.first.second);
-    const Defined *FromSym = dyn_cast<Defined>(C.first.first);
-    const Defined *ToSym = dyn_cast<Defined>(C.first.second);
-
-    if (!FromSym || !ToSym)
-      continue;
-
-    const InputSectionBase *FromSB =
-        dyn_cast_or_null<InputSectionBase>(FromSym->Section);
-    const InputSectionBase *ToSB =
-        dyn_cast_or_null<InputSectionBase>(ToSym->Section);
+    const auto *FromSB = cast<InputSectionBase>(C.first.first->Repl);
+    const auto *ToSB = cast<InputSectionBase>(C.first.second->Repl);
     uint64_t Weight = C.second;
 
-    if (!FromSB || !ToSB || Weight == 0)
-      continue;
-
-    FromSB = cast<InputSectionBase>(FromSB->Repl);
-    ToSB = cast<InputSectionBase>(ToSB->Repl);
-
     // Ignore edges between input sections belonging to different output
     // sections.  This is done because otherwise we would end up with clusters
     // containing input sections that can't actually be placed adjacently in the
     // output.  This messes with the cluster size and density calculations.  We
     // would also end up moving input sections in other output sections without
     // moving them closer to what calls them.
     if (FromSB->getOutputSection() != ToSB->getOutputSection())
       continue;
 
     int From = GetOrCreateNode(FromSB);
     int To = GetOrCreateNode(ToSB);
 
     Clusters[To].Weight += Weight;
 
     if (From == To)
       continue;
 
-    Edge E{From, To, Weight};
-
-    // Add or increment an edge
-    auto Res = EdgeMap.insert(std::make_pair(E, Edges.size()));
-    int EI = Res.first->second;
-    if (Res.second) {
-      Edges.push_back(E);
-      Clusters[To].Preds.push_back(From);
-    } else
-      Edges[EI].Weight += Weight;
+    // Add an edge
+    Clusters[To].Preds.push_back({From, Weight});
   }
 
   for (Cluster &C : Clusters)
     C.InitialWeight = C.Weight;
 }
 
 // It's bad to merge clusters which would degrade the density too much.
 static bool isNewDensityBad(Cluster &A, Cluster &B) {
void CallGraphSort::groupClusters() {
   });
 
   for (int SI : SortedSecs) {
     Cluster &C = *SecToCluster[SI];
 
     int BestPred = -1;
     uint64_t BestWeight = 0;
 
-    for (int PI : Clusters[SI].Preds) {
-      Edge &E = Edges[EdgeMap[{PI, SI, 0}]];
+    for (Edge &E : Clusters[SI].Preds) {
       if (BestPred == -1 || E.Weight > BestWeight) {
-        BestPred = PI;
+        BestPred = E.From;
         BestWeight = E.Weight;
       }
     }
 
     // don't consider merging if the edge is unlikely.
     if (BestWeight * 10 <= C.InitialWeight)
       continue;
 

ELF/Config.h

 #include "llvm/Support/CodeGen.h"
 #include "llvm/Support/Endian.h"
 #include <vector>
 
 namespace lld {
 namespace elf {
 
 class InputFile;
-class Symbol;
+class InputSectionBase;
 
 enum ELFKind {
   ELFNoneKind,
   ELF32LEKind,
   ELF32BEKind,
   ELF64LEKind,
   ELF64BEKind
 };
struct Configuration {
   std::vector<llvm::StringRef> FilterList;
   std::vector<llvm::StringRef> SearchPaths;
   std::vector<llvm::StringRef> SymbolOrderingFile;
   std::vector<llvm::StringRef> Undefined;
   std::vector<SymbolVersion> DynamicList;
   std::vector<SymbolVersion> VersionScriptGlobals;
   std::vector<SymbolVersion> VersionScriptLocals;
   std::vector<uint8_t> BuildIdVector;
-  llvm::MapVector<std::pair<const Symbol *, const Symbol *>, uint64_t>
+  llvm::MapVector<std::pair<const InputSectionBase *, const InputSectionBase *>,
+                  uint64_t>
       CallGraphProfile;
   bool AllowMultipleDefinition;
   bool AndroidPackDynRelocs = false;
   bool ARMHasBlx = false;
   bool ARMHasMovtMovw = false;
   bool ARMJ1J2BranchEncoding = false;
   bool AsNeeded = false;
   bool Bsymbolic;

ELF/Driver.cpp

for (StringRef L : args::getLines(MB)) {
     const Symbol *FromSym = SymbolNameToSymbol.lookup(Fields[0]);
     const Symbol *ToSym = SymbolNameToSymbol.lookup(Fields[1]);
     if (Config->WarnSymbolOrdering) {
       if (!FromSym)
         warn("call graph file: no such symbol: " + Fields[0]);
       if (!ToSym)
         warn("call graph file: no such symbol: " + Fields[1]);
     }
-    if (!FromSym || !ToSym)
+    if (!FromSym || !ToSym || Count == 0)
       continue;
-    Config->CallGraphProfile[std::make_pair(FromSym, ToSym)] += Count;
+    warnUnorderableSymbol(FromSym);
+    warnUnorderableSymbol(ToSym);
+    const Defined *FromSymD = dyn_cast<Defined>(FromSym);
+    const Defined *ToSymD = dyn_cast<Defined>(ToSym);
+    if (!FromSymD || !ToSymD)
+      continue;
+    const auto *FromSB = dyn_cast_or_null<InputSectionBase>(FromSymD->Section);
+    const auto *ToSB = dyn_cast_or_null<InputSectionBase>(ToSymD->Section);
+    if (!FromSB || !ToSB)
+      continue;
+    Config->CallGraphProfile[std::make_pair(FromSB, ToSB)] += Count;
   }
 }
 
 static bool getCompressDebugSections(opt::InputArgList &Args) {
   StringRef S = Args.getLastArgValue(OPT_compress_debug_sections, "none");
   if (S == "none")
     return false;
   if (S != "zlib")
template <class ELFT> void LinkerDriver::link(opt::InputArgList &Args) {
 
   Symtab->addCombinedLTOObject<ELFT>();
   if (errorCount())
     return;
 
   // Apply symbol renames for -wrap.
   Symtab->applySymbolWrap();
 
-  if (auto *Arg = Args.getLastArg(OPT_call_graph_ordering_file))
-    if (Optional<MemoryBufferRef> Buffer = readFile(Arg->getValue()))
-      readCallGraph(*Buffer);
-
   // Now that we have a complete list of input files.
   // Beyond this point, no new files are added.
   // Aggregate all input sections into one place.
   for (InputFile *F : ObjectFiles)
     for (InputSectionBase *S : F->getSections())
       if (S && S != &InputSection::Discarded)
         InputSections.push_back(S);
   for (BinaryFile *F : BinaryFiles)
template <class ELFT> void LinkerDriver::link(opt::InputArgList &Args) {
   // and identical code folding.
   markLive<ELFT>();
   demoteSharedSymbols<ELFT>();
   decompressSections();
   mergeSections();
   if (Config->ICF)
     doIcf<ELFT>();
 
+  // Read the callgraph now that we know what was gced or icfed
+  if (auto *Arg = Args.getLastArg(OPT_call_graph_ordering_file))
+    if (Optional<MemoryBufferRef> Buffer = readFile(Arg->getValue()))
+      readCallGraph(*Buffer);
+
   // Write the result to the file.
   writeResult<ELFT>();
 }

test/ELF/cgprofile-warn.s

 B = 0x1234
 
     .section    .text.A,"ax",@progbits
     .globl  A
 A:
     mov poppy, %rax
     retq
 
-# CHECK: call graph file: no such symbol: adena
 # CHECK: unable to order absolute symbol: B
+# CHECK: call graph file: no such symbol: adena
 # CHECK: unable to order undefined symbol: poppy