[LLD][ELF] - Simplify Call-Chain Clustering implementation a bit.

[grimar]

Summary

Looking at the current implementation and algorithm description,
it does not seem we need to keep vector with all edges for
each cluster and can just remember the best one.

At least with the current implementation, this is NFC change I believe.

This allows to simplify the code a bit, patch shows the change I am suggesting.

[grimar]

Ping.

[grimar]

Ping.

[ruiu]

LGTM

ELF/CallGraphSort.cpp

140 ↗

(On Diff #160256)

Format

lld/trunk/ELF/CallGraphSort.cpp

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<Edge> Preds;
+  Edge BestPred = {-1, 0};
 };
 
 class CallGraphSort {
 public:
   CallGraphSort();
 
   DenseMap<const InputSectionBase *, int> run();
 
for (const auto &C : Profile) {
     int From = GetOrCreateNode(FromSB);
     int To = GetOrCreateNode(ToSB);
 
     Clusters[To].Weight += Weight;
 
     if (From == To)
       continue;
 
-    // Add an edge
-    Clusters[To].Preds.push_back({From, Weight});
+    // Remember the best edge.
+    Cluster &ToC = Clusters[To];
+    if (ToC.BestPred.From == -1 || ToC.BestPred.Weight < Weight) {
+      ToC.BestPred.From = From;
+      ToC.BestPred.Weight = 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) {
   double NewDensity = double(A.Weight + B.Weight) / double(A.Size + B.Size);
std::stable_sort(SortedSecs.begin(), SortedSecs.end(), [&](int A, int B) {
     return Clusters[B].getDensity() < Clusters[A].getDensity();
   });
 
   for (int SI : SortedSecs) {
     // Clusters[SI] is the same as SecToClusters[SI] here because it has not
     // been merged into another cluster yet.
     Cluster &C = Clusters[SI];
 
-    int BestPred = -1;
-    uint64_t BestWeight = 0;
-
-    for (Edge &E : C.Preds) {
-      if (BestPred == -1 || E.Weight > BestWeight) {
-        BestPred = E.From;
-        BestWeight = E.Weight;
-      }
-    }
-
-    // don't consider merging if the edge is unlikely.
-    if (BestWeight * 10 <= C.InitialWeight)
+    // Don't consider merging if the edge is unlikely.
+    if (C.BestPred.From == -1 || C.BestPred.Weight * 10 <= C.InitialWeight)
       continue;
 
-    Cluster *PredC = SecToCluster[BestPred];
+    Cluster *PredC = SecToCluster[C.BestPred.From];
     if (PredC == &C)
       continue;
 
     if (C.Size + PredC->Size > MAX_CLUSTER_SIZE)
       continue;
 
     if (isNewDensityBad(*PredC, C))
       continue;