Store initial cluster weight instead of normalized edge weights

ELF/CallGraphSort.cpp

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;
   std::vector<int> Succs;
 };
 
 struct Edge {
   int From;
   int To;
   uint64_t Weight;
-  double NormalizedWeight;
 };
 
 struct EdgeDenseMapInfo {
   static Edge getEmptyKey() {
     return {DenseMapInfo<int>::getEmptyKey(), DenseMapInfo<int>::getEmptyKey(),
-            0, 0};
+            0};
   }
   static Edge getTombstoneKey() {
     return {DenseMapInfo<int>::getTombstoneKey(),
-            DenseMapInfo<int>::getTombstoneKey(), 0, 0};
+            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;
   }
 };
 
 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 normalizeEdgeWeights();
   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;
-
-// Minimum edge probability to consider merging.
-constexpr double MIN_EDGE_PROBABILITY = 0.1;
 } // 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;
for (const auto &C : Profile) {
     int From = GetOrCreateNode(FromSB);
     int To = GetOrCreateNode(ToSB);
 
     Clusters[To].Weight += Weight;
 
     if (From == To)
       continue;
 
-    Edge E{From, To, Weight, 0};
+    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[From].Succs.push_back(To);
       Clusters[To].Preds.push_back(From);
     } else
       Edges[EI].Weight += Weight;
   }
-  normalizeEdgeWeights();
-}
 
-// Normalize the edge weights so that we can reject edges which have a low
-// probibility.
-void CallGraphSort::normalizeEdgeWeights() {
-  for (int SI = 0, SE = Sections.size(); SI != SE; ++SI) {
-    Cluster &C = Clusters[SI];
-    for (int PI : C.Preds) {
-      Edge &E = Edges[EdgeMap[{PI, SI, 0, 0}]];
-      if (C.Weight == 0)
-        continue;
-      E.NormalizedWeight = double(E.Weight) / double(C.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);
   if (NewDensity < A.getDensity() / MAX_DENSITY_DEGRADATION)
     return true;
   return false;
void CallGraphSort::groupClusters() {
   std::stable_sort(SortedSecs.begin(), SortedSecs.end(), [&](int A, int B) {
     return Clusters[B].getDensity() < Clusters[A].getDensity();
   });
 
   for (int SI : SortedSecs) {
     Cluster &C = *SecToCluster[SI];
 
     int BestPred = -1;
-    double BestWeight = 0;
+    uint64_t BestWeight = 0;
 
     for (int PI : Clusters[SI].Preds) {
-      Edge &E = Edges[EdgeMap[{PI, SI, 0, 0}]];
-      if (BestPred == -1 || E.NormalizedWeight > BestWeight) {
+      Edge &E = Edges[EdgeMap[{PI, SI, 0}]];
+      if (BestPred == -1 || E.Weight > BestWeight) {
         BestPred = PI;
-        BestWeight = E.NormalizedWeight;
+        BestWeight = E.Weight;
       }
     }
 
-    if (BestWeight < MIN_EDGE_PROBABILITY)
+    // don't consider merging if the edge is unlikely.
+    if (BestWeight * 10 <= C.InitialWeight)
       continue;
 
     Cluster *PredC = SecToCluster[BestPred];
     if (PredC == nullptr || PredC == &C)
       continue;
 
     if (C.Size + PredC->Size > MAX_CLUSTER_SIZE)
       continue;