Index: ELF/CallGraphSort.cpp
===================================================================
--- ELF/CallGraphSort.cpp
+++ ELF/CallGraphSort.cpp
@@ -51,6 +51,11 @@
 using namespace lld::elf;
 
 namespace {
+struct Edge {
+  int From;
+  uint64_t Weight;
+};
+
 struct Cluster {
   Cluster(int Sec, size_t S) {
     Sections.push_back(Sec);
@@ -67,31 +72,7 @@
   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 {
@@ -101,9 +82,7 @@
   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();
@@ -121,8 +100,8 @@
 // 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 {
@@ -136,26 +115,10 @@
 
   // 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
@@ -173,16 +136,8 @@
     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)
@@ -228,10 +183,9 @@
     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;
       }
     }
Index: ELF/Config.h
===================================================================
--- ELF/Config.h
+++ ELF/Config.h
@@ -24,7 +24,7 @@
 namespace elf {
 
 class InputFile;
-class Symbol;
+class InputSectionBase;
 
 enum ELFKind {
   ELFNoneKind,
@@ -105,7 +105,8 @@
   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;
Index: ELF/Driver.cpp
===================================================================
--- ELF/Driver.cpp
+++ ELF/Driver.cpp
@@ -595,9 +595,19 @@
       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;
   }
 }
 
@@ -1216,10 +1226,6 @@
   // 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.
@@ -1270,6 +1276,11 @@
   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>();
 }
Index: test/ELF/cgprofile-warn.s
===================================================================
--- test/ELF/cgprofile-warn.s
+++ test/ELF/cgprofile-warn.s
@@ -24,6 +24,6 @@
     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