From 4c241849363d510a5d63c1c78989ef1fa15c1565 Mon Sep 17 00:00:00 2001 From: Cong Hou Date: Thu, 17 Dec 2015 22:27:07 +0000 Subject: [PATCH 1/1] [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 --- include/llvm/Support/BranchProbability.h | 37 +++++++++++++++------ unittests/Support/BranchProbabilityTest.cpp | 31 +++++++++++++++++ 2 files changed, 57 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); diff --git a/unittests/Support/BranchProbabilityTest.cpp b/unittests/Support/BranchProbabilityTest.cpp index 847661d21b3..e90e7f8ff11 100644 --- a/unittests/Support/BranchProbabilityTest.cpp +++ b/unittests/Support/BranchProbabilityTest.cpp @@ -288,6 +288,7 @@ TEST(BranchProbabilityTest, scaleBruteForce) { } TEST(BranchProbabilityTest, NormalizeProbabilities) { + const auto UnknownProb = BranchProbability::getUnknown(); { SmallVector Probs{{0, 1}, {0, 1}}; BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end()); @@ -322,6 +323,36 @@ TEST(BranchProbabilityTest, NormalizeProbabilities) { EXPECT_EQ(BranchProbability::getDenominator() / 3 + 1, Probs[2].getNumerator()); } + { + SmallVector Probs{{0, 1}, UnknownProb}; + BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end()); + EXPECT_EQ(0, Probs[0].getNumerator()); + EXPECT_EQ(BranchProbability::getDenominator(), Probs[1].getNumerator()); + } + { + SmallVector Probs{{1, 1}, UnknownProb}; + BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end()); + EXPECT_EQ(BranchProbability::getDenominator(), Probs[0].getNumerator()); + EXPECT_EQ(0, Probs[1].getNumerator()); + } + { + SmallVector Probs{{1, 2}, UnknownProb}; + BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end()); + EXPECT_EQ(BranchProbability::getDenominator() / 2, Probs[0].getNumerator()); + EXPECT_EQ(BranchProbability::getDenominator() / 2, Probs[1].getNumerator()); + } + { + SmallVector Probs{ + {1, 2}, {1, 2}, {1, 2}, UnknownProb}; + BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end()); + EXPECT_EQ(BranchProbability::getDenominator() / 3 + 1, + Probs[0].getNumerator()); + EXPECT_EQ(BranchProbability::getDenominator() / 3 + 1, + Probs[1].getNumerator()); + EXPECT_EQ(BranchProbability::getDenominator() / 3 + 1, + Probs[2].getNumerator()); + EXPECT_EQ(0, Probs[3].getNumerator()); + } } } -- 2.34.1