[BranchProbability] Remove the restriction that known and unknown probabilities cannot coexist when being normalized.

The current BranchProbability::normalizeProbabilities() forbids known and
unknown probabilities to coexist in the list. This was once used to help
capture probability exceptions but has caused some reported build
failures (https://llvm.org/bugs/show_bug.cgi?id=25838).

This patch removes this restriction by evenly distributing the complement
of the sum of all known probabilities to unknown ones. We could still
treat this as an abnormal behavior, but it is better to emit warnings in
our future profile validator.


Differential revision: http://reviews.llvm.org/D15548




git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@255934 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 26 insertions, 11 deletions

diff --git a/include/llvm/Support/BranchProbability.h b/include/llvm/Support/BranchProbability.h
index 415805ce397..1d6a7d84fbf 100644
--- a/include/llvm/Support/BranchProbability.h
+++ b/include/llvm/Support/BranchProbability.h
@@ -183,17 +183,32 @@ void BranchProbability::normalizeProbabilities(ProbabilityIter Begin,
   if (Begin == End)
     return;
 
-  auto UnknownProbCount =
-      std::count(Begin, End, BranchProbability::getUnknown());
-  assert((UnknownProbCount == 0 ||
-          UnknownProbCount == std::distance(Begin, End)) &&
-         "Cannot normalize probabilities with known and unknown ones.");
-  (void)UnknownProbCount;
-
-  uint64_t Sum = std::accumulate(
-      Begin, End, uint64_t(0),
-      [](uint64_t S, const BranchProbability &BP) { return S + BP.N; });
-
+  unsigned UnknownProbCount = 0;
+  uint64_t Sum = std::accumulate(Begin, End, uint64_t(0),
+                                 [&](uint64_t S, const BranchProbability &BP) {
+                                   if (!BP.isUnknown())
+                                     return S + BP.N;
+                                   UnknownProbCount++;
+                                   return S;
+                                 });
+
+  if (UnknownProbCount > 0) {
+    BranchProbability ProbForUnknown = BranchProbability::getZero();
+    // If the sum of all known probabilities is less than one, evenly distribute
+    // the complement of sum to unknown probabilities. Otherwise, set unknown
+    // probabilities to zeros and continue to normalize known probabilities.
+    if (Sum < BranchProbability::getDenominator())
+      ProbForUnknown = BranchProbability::getRaw(
+          (BranchProbability::getDenominator() - Sum) / UnknownProbCount);
+
+    std::replace_if(Begin, End,
+                    [](const BranchProbability &BP) { return BP.isUnknown(); },
+                    ProbForUnknown);
+
+    if (Sum <= BranchProbability::getDenominator())
+      return;
+  }
+ 
   if (Sum == 0) {
     BranchProbability BP(1, std::distance(Begin, End));
     std::fill(Begin, End, BP);