+inline raw_ostream &operator<<(raw_ostream &OS, BranchProbability Prob) {
+ return Prob.print(OS);
+}
+
+template <class ProbabilityIter>
+void BranchProbability::normalizeProbabilities(ProbabilityIter Begin,
+ ProbabilityIter End) {
+ if (Begin == End)
+ return;
+
+ 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);
+ return;
+ }
+
+ for (auto I = Begin; I != End; ++I)
+ I->N = (I->N * uint64_t(D) + Sum / 2) / Sum;
+}
+
+template <class WeightListIter>
+void BranchProbability::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 > 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 {
+ // We are converting zeros into ones, and here we need to make sure that
+ // after this the sum won't exceed UINT32_MAX.
+ if (Sum + ZeroWeightNum > UINT32_MAX) {
+ for (auto I = Begin; I != End; ++I)
+ *I /= 2;
+ ZeroWeightNum = std::count(Begin, End, 0u);
+ Sum = std::accumulate(Begin, End, uint64_t(0));
+ }
+ // Scale up non-zero weights and turn zero weights into ones.
+ uint64_t ScalingFactor = (UINT32_MAX - ZeroWeightNum) / Sum;
+ assert(ScalingFactor >= 1);
+ if (ScalingFactor > 1)
+ for (auto I = Begin; I != End; ++I)
+ *I *= ScalingFactor;
+ std::replace(Begin, End, 0u, 1u);
+ }
+ }
+}