Update MachineBranchProbabilityInfo::normalizeEdgeWeights to make sure there is no...

[oota-llvm.git] / include / llvm / CodeGen / MachineBranchProbabilityInfo.h

diff --git a/include/llvm/CodeGen/MachineBranchProbabilityInfo.h b/include/llvm/CodeGen/MachineBranchProbabilityInfo.h
index 26f0d99373871e0ec791934c68535379f6289c5b..21e2dbb5722f1c6ebe86f00d110e8e339fce489b 100644 (file)
--- a/include/llvm/CodeGen/MachineBranchProbabilityInfo.h
+++ b/include/llvm/CodeGen/MachineBranchProbabilityInfo.h
@@ -86,35 +86,43 @@ public:
                                     const MachineBasicBlock *Dst) const;
 
   // Normalize a list of weights by scaling them down so that the sum of them
-  // doesn't exceed UINT32_MAX. Return the scale.
+  // doesn't exceed UINT32_MAX.
   template <class WeightListIter>
-  static uint32_t normalizeEdgeWeights(WeightListIter Begin,
-                                       WeightListIter End);
+  static void normalizeEdgeWeights(WeightListIter Begin, WeightListIter End);
 };
 
 template <class WeightListIter>
-uint32_t
-MachineBranchProbabilityInfo::normalizeEdgeWeights(WeightListIter Begin,
-                                                   WeightListIter End) {
+void MachineBranchProbabilityInfo::normalizeEdgeWeights(WeightListIter Begin,
+                                                        WeightListIter End) {
   // First we compute the sum with 64-bits of precision.
   uint64_t Sum = std::accumulate(Begin, End, uint64_t(0));
 
-  // If Sum is zero, set all weights to 1.
-  if (Sum == 0)
-    std::fill(Begin, End, uint64_t(1));
-
-  // If the computed sum fits in 32-bits, we're done.
-  if (Sum <= UINT32_MAX)
-    return 1;
-
-  // Otherwise, compute the scale necessary to cause the weights to fit, and
-  // re-sum with that scale applied.
-  assert((Sum / UINT32_MAX) < UINT32_MAX &&
-         "The sum of weights exceeds UINT32_MAX^2!");
-  uint32_t Scale = (Sum / UINT32_MAX) + 1;
-  for (auto I = Begin; I != End; ++I)
-    *I /= Scale;
-  return Scale;
+  if (Sum > UINT32_MAX) {
+    // Compute the scale necessary to cause the weights to fit, and re-sum with
+    // that scale applied.
+    assert(Sum / UINT32_MAX < UINT32_MAX &&
+           "The sum of weights exceeds UINT32_MAX^2!");
+    uint32_t Scale = Sum / UINT32_MAX + 1;
+    for (auto I = Begin; I != End; ++I)
+      *I /= Scale;
+    Sum = std::accumulate(Begin, End, uint64_t(0));
+  }
+
+  // Eliminate zero weights.
+  auto ZeroWeightNum = std::count(Begin, End, 0u);
+  if (ZeroWeightNum > 0) {
+    // If all weights are zeros, replace them by 1.
+    if (Sum == 0)
+      std::fill(Begin, End, 1u);
+    else {
+      // Scale up non-zero weights and turn zero weights into ones.
+      uint64_t ScalingFactor = (UINT32_MAX - ZeroWeightNum) / Sum;
+      if (ScalingFactor > 1)
+        for (auto I = Begin; I != End; ++I)
+          *I *= ScalingFactor;
+      std::replace(Begin, End, 0u, 1u);
+    }
+  }
 }
 
 }