## Coverage Report

#### Created: 2019-07-24 05:18

`/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Support/BranchProbability.h`
`Line`
`Count`
`Source`
`1`
`//===- BranchProbability.h - Branch Probability Wrapper ---------*- C++ -*-===//`
`2`
`//`
`3`
`// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.`
`4`
`// See https://llvm.org/LICENSE.txt for license information.`
`5`
`// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception`
`6`
`//`
`7`
`//===----------------------------------------------------------------------===//`
`8`
`//`
`9`
`// Definition of BranchProbability shared by IR and Machine Instructions.`
`10`
`//`
`11`
`//===----------------------------------------------------------------------===//`
`12`
`13`
`#ifndef LLVM_SUPPORT_BRANCHPROBABILITY_H`
`14`
`#define LLVM_SUPPORT_BRANCHPROBABILITY_H`
`15`
`16`
`#include "llvm/Support/DataTypes.h"`
`17`
`#include <algorithm>`
`18`
`#include <cassert>`
`19`
`#include <climits>`
`20`
`#include <numeric>`
`21`
`22`
`namespace llvm {`
`23`
`24`
`class raw_ostream;`
`25`
`26`
`// This class represents Branch Probability as a non-negative fraction that is`
`27`
`// no greater than 1. It uses a fixed-point-like implementation, in which the`
`28`
`// denominator is always a constant value (here we use 1<<31 for maximum`
`29`
`// precision).`
`30`
`class BranchProbability {`
`31`
`  // Numerator`
`32`
`  uint32_t N;`
`33`
`34`
`  // Denominator, which is a constant value.`
`35`
`  static const uint32_t D = 1u << 31;`
`36`
`  static const uint32_t UnknownN = UINT32_MAX;`
`37`
`38`
`  // Construct a BranchProbability with only numerator assuming the denominator`
`39`
`  // is 1<<31. For internal use only.`
`40`
`47.6M`
`  explicit BranchProbability(uint32_t n) : N(n) {}`
`41`
`42`
`public:`
`43`
`14.5M`
`  BranchProbability() : N(UnknownN) {}`
`44`
`  BranchProbability(uint32_t Numerator, uint32_t Denominator);`
`45`
`46`
`18`
`  bool isZero() const { return N == 0; }`
`47`
`49.5M`
`  bool isUnknown() const { return N == UnknownN; }`
`48`
`49`
`19.1M`
`  static BranchProbability getZero() { return BranchProbability(0); }`
`50`
`4.37M`
`  static BranchProbability getOne() { return BranchProbability(D); }`
`51`
`4.57M`
`  static BranchProbability getUnknown() { return BranchProbability(UnknownN); }`
`52`
`  // Create a BranchProbability object with the given numerator and 1<<31`
`53`
`  // as denominator.`
`54`
`115k`
`  static BranchProbability getRaw(uint32_t N) { return BranchProbability(N); }`
`55`
`  // Create a BranchProbability object from 64-bit integers.`
`56`
`  static BranchProbability getBranchProbability(uint64_t Numerator,`
`57`
`                                                uint64_t Denominator);`
`58`
`59`
`  // Normalize given probabilties so that the sum of them becomes approximate`
`60`
`  // one.`
`61`
`  template <class ProbabilityIter>`
`62`
`  static void normalizeProbabilities(ProbabilityIter Begin,`
`63`
`                                     ProbabilityIter End);`
`64`
`65`
`40.8M`
`  uint32_t getNumerator() const { return N; }`
`66`
`59.7k`
`  static uint32_t getDenominator() { return D; }`
`67`
`68`
`  // Return (1 - Probability).`
`69`
`19.4M`
`  BranchProbability getCompl() const { return BranchProbability(D - N); }`
`70`
`71`
`  raw_ostream &print(raw_ostream &OS) const;`
`72`
`73`
`  void dump() const;`
`74`
`75`
`  /// Scale a large integer.`
`76`
`  ///`
`77`
`  /// Scales \c Num.  Guarantees full precision.  Returns the floor of the`
`78`
`  /// result.`
`79`
`  ///`
`80`
`  /// \return \c Num times \c this.`
`81`
`  uint64_t scale(uint64_t Num) const;`
`82`
`83`
`  /// Scale a large integer by the inverse.`
`84`
`  ///`
`85`
`  /// Scales \c Num by the inverse of \c this.  Guarantees full precision.`
`86`
`  /// Returns the floor of the result.`
`87`
`  ///`
`88`
`  /// \return \c Num divided by \c this.`
`89`
`  uint64_t scaleByInverse(uint64_t Num) const;`
`90`
`91`
`1.21M`
`  BranchProbability &operator+=(BranchProbability RHS) {`
`92`
`1.21M`
`    assert(N != UnknownN && RHS.N != UnknownN &&`
`93`
`1.21M`
`           "Unknown probability cannot participate in arithmetics.");`
`94`
`1.21M`
`    // Saturate the result in case of overflow.`
`95`
`1.21M`
`    N = (uint64_t(N) + RHS.N > D) ? D17.7k : N + RHS.N1.19M;`
`96`
`1.21M`
`    return *this;`
`97`
`1.21M`
`  }`
`98`
`99`
`1.36M`
`  BranchProbability &operator-=(BranchProbability RHS) {`
`100`
`1.36M`
`    assert(N != UnknownN && RHS.N != UnknownN &&`
`101`
`1.36M`
`           "Unknown probability cannot participate in arithmetics.");`
`102`
`1.36M`
`    // Saturate the result in case of underflow.`
`103`
`1.36M`
`    N = N < RHS.N ? 018 : N - RHS.N1.36M;`
`104`
`1.36M`
`    return *this;`
`105`
`1.36M`
`  }`
`106`
`107`
`7.36k`
`  BranchProbability &operator*=(BranchProbability RHS) {`
`108`
`7.36k`
`    assert(N != UnknownN && RHS.N != UnknownN &&`
`109`
`7.36k`
`           "Unknown probability cannot participate in arithmetics.");`
`110`
`7.36k`
`    N = (static_cast<uint64_t>(N) * RHS.N + D / 2) / D;`
`111`
`7.36k`
`    return *this;`
`112`
`7.36k`
`  }`
`113`
`114`
`80.9k`
`  BranchProbability &operator*=(uint32_t RHS) {`
`115`
`80.9k`
`    assert(N != UnknownN &&`
`116`
`80.9k`
`           "Unknown probability cannot participate in arithmetics.");`
`117`
`80.9k`
`    N = (uint64_t(N) * RHS > D) ? D6 : N * RHS80.9k;`
`118`
`80.9k`
`    return *this;`
`119`
`80.9k`
`  }`
`120`
`121`
`117`
`  BranchProbability &operator/=(BranchProbability RHS) {`
`122`
`117`
`    assert(N != UnknownN && RHS.N != UnknownN &&`
`123`
`117`
`           "Unknown probability cannot participate in arithmetics.");`
`124`
`117`
`    N = (static_cast<uint64_t>(N) * D + RHS.N / 2) / RHS.N;`
`125`
`117`
`    return *this;`
`126`
`117`
`  }`
`127`
`128`
`18.0M`
`  BranchProbability &operator/=(uint32_t RHS) {`
`129`
`18.0M`
`    assert(N != UnknownN &&`
`130`
`18.0M`
`           "Unknown probability cannot participate in arithmetics.");`
`131`
`18.0M`
`    assert(RHS > 0 && "The divider cannot be zero.");`
`132`
`18.0M`
`    N /= RHS;`
`133`
`18.0M`
`    return *this;`
`134`
`18.0M`
`  }`
`135`
`136`
`38.8k`
`  BranchProbability operator+(BranchProbability RHS) const {`
`137`
`38.8k`
`    BranchProbability Prob(*this);`
`138`
`38.8k`
`    Prob += RHS;`
`139`
`38.8k`
`    return Prob;`
`140`
`38.8k`
`  }`
`141`
`142`
`270k`
`  BranchProbability operator-(BranchProbability RHS) const {`
`143`
`270k`
`    BranchProbability Prob(*this);`
`144`
`270k`
`    Prob -= RHS;`
`145`
`270k`
`    return Prob;`
`146`
`270k`
`  }`
`147`
`148`
`7.31k`
`  BranchProbability operator*(BranchProbability RHS) const {`
`149`
`7.31k`
`    BranchProbability Prob(*this);`
`150`
`7.31k`
`    Prob *= RHS;`
`151`
`7.31k`
`    return Prob;`
`152`
`7.31k`
`  }`
`153`
`154`
`80.9k`
`  BranchProbability operator*(uint32_t RHS) const {`
`155`
`80.9k`
`    BranchProbability Prob(*this);`
`156`
`80.9k`
`    Prob *= RHS;`
`157`
`80.9k`
`    return Prob;`
`158`
`80.9k`
`  }`
`159`
`160`
`117`
`  BranchProbability operator/(BranchProbability RHS) const {`
`161`
`117`
`    BranchProbability Prob(*this);`
`162`
`117`
`    Prob /= RHS;`
`163`
`117`
`    return Prob;`
`164`
`117`
`  }`
`165`
`166`
`18.0M`
`  BranchProbability operator/(uint32_t RHS) const {`
`167`
`18.0M`
`    BranchProbability Prob(*this);`
`168`
`18.0M`
`    Prob /= RHS;`
`169`
`18.0M`
`    return Prob;`
`170`
`18.0M`
`  }`
`171`
`172`
`33.4k`
`  bool operator==(BranchProbability RHS) const { return N == RHS.N; }`
`173`
`29.7k`
`  bool operator!=(BranchProbability RHS) const { return !(*this == RHS); }`
`174`
`175`
`2.15M`
`  bool operator<(BranchProbability RHS) const {`
`176`
`2.15M`
`    assert(N != UnknownN && RHS.N != UnknownN &&`
`177`
`2.15M`
`           "Unknown probability cannot participate in comparisons.");`
`178`
`2.15M`
`    return N < RHS.N;`
`179`
`2.15M`
`  }`
`180`
`181`
`494k`
`  bool operator>(BranchProbability RHS) const {`
`182`
`494k`
`    assert(N != UnknownN && RHS.N != UnknownN &&`
`183`
`494k`
`           "Unknown probability cannot participate in comparisons.");`
`184`
`494k`
`    return RHS < *this;`
`185`
`494k`
`  }`
`186`
`187`
`185k`
`  bool operator<=(BranchProbability RHS) const {`
`188`
`185k`
`    assert(N != UnknownN && RHS.N != UnknownN &&`
`189`
`185k`
`           "Unknown probability cannot participate in comparisons.");`
`190`
`185k`
`    return !(RHS < *this);`
`191`
`185k`
`  }`
`192`
`193`
`470k`
`  bool operator>=(BranchProbability RHS) const {`
`194`
`470k`
`    assert(N != UnknownN && RHS.N != UnknownN &&`
`195`
`470k`
`           "Unknown probability cannot participate in comparisons.");`
`196`
`470k`
`    return !(*this < RHS);`
`197`
`470k`
`  }`
`198`
`};`
`199`
`200`
`939`
`inline raw_ostream &operator<<(raw_ostream &OS, BranchProbability Prob) {`
`201`
`939`
`  return Prob.print(OS);`
`202`
`939`
`}`
`203`
`204`
`template <class ProbabilityIter>`
`205`
`void BranchProbability::normalizeProbabilities(ProbabilityIter Begin,`
`206`
`699k`
`                                               ProbabilityIter End) {`
`207`
`699k`
`  if (Begin == End)`
`208`
`62.8k`
`    return;`
`209`
`636k`
`210`
`636k`
`  unsigned UnknownProbCount = 0;`
`211`
`636k`
`  uint64_t Sum = std::accumulate(Begin, End, uint64_t(0),`
`212`
`1.27M`
`                                 [&](uint64_t S, const BranchProbability &BP) {`
`213`
`1.27M`
`                                   if (!BP.isUnknown())`
`214`
`1.26M`
`                                     return S + BP.N;`
`215`
`8.97k`
`                                   UnknownProbCount++;`
`216`
`8.97k`
`                                   return S;`
`217`
`8.97k`
`                                 });`
`void llvm::BranchProbability::normalizeProbabilities<std::__1::__wrap_iter<llvm::BranchProbability*> >(std::__1::__wrap_iter<llvm::BranchProbability*>, std::__1::__wrap_iter<llvm::BranchProbability*>)::'lambda'(unsigned long long, llvm::BranchProbability const&)::operator()(unsigned long long, llvm::BranchProbability const&) const`
 `Line` `Count` `Source` `212` `1.19M` ` [&](uint64_t S, const BranchProbability &BP) {` `213` `1.19M` ` if (!BP.isUnknown())` `214` `1.19M` ` return S + BP.N;` `215` `6.09k` ` UnknownProbCount++;` `216` `6.09k` ` return S;` `217` `6.09k` ` });`
`void llvm::BranchProbability::normalizeProbabilities<llvm::BranchProbability*>(llvm::BranchProbability*, llvm::BranchProbability*)::'lambda'(unsigned long long, llvm::BranchProbability const&)::operator()(unsigned long long, llvm::BranchProbability const&) const`
 `Line` `Count` `Source` `212` `75.0k` ` [&](uint64_t S, const BranchProbability &BP) {` `213` `75.0k` ` if (!BP.isUnknown())` `214` `72.1k` ` return S + BP.N;` `215` `2.88k` ` UnknownProbCount++;` `216` `2.88k` ` return S;` `217` `2.88k` ` });`
`218`
`636k`
`219`
`636k`
`  if (UnknownProbCount > 0) {`
`220`
`6.26k`
`    BranchProbability ProbForUnknown = BranchProbability::getZero();`
`221`
`6.26k`
`    // If the sum of all known probabilities is less than one, evenly distribute`
`222`
`6.26k`
`    // the complement of sum to unknown probabilities. Otherwise, set unknown`
`223`
`6.26k`
`    // probabilities to zeros and continue to normalize known probabilities.`
`224`
`6.26k`
`    if (Sum < BranchProbability::getDenominator())`
`225`
`6.26k`
`      ProbForUnknown = BranchProbability::getRaw(`
`226`
`6.26k`
`          (BranchProbability::getDenominator() - Sum) / UnknownProbCount);`
`227`
`6.26k`
`228`
`6.26k`
`    std::replace_if(Begin, End,`
`229`
`8.99k`
`                    [](const BranchProbability &BP) { return BP.isUnknown(); },`
`void llvm::BranchProbability::normalizeProbabilities<std::__1::__wrap_iter<llvm::BranchProbability*> >(std::__1::__wrap_iter<llvm::BranchProbability*>, std::__1::__wrap_iter<llvm::BranchProbability*>)::'lambda'(llvm::BranchProbability const&)::operator()(llvm::BranchProbability const&) const`
 `Line` `Count` `Source` `229` `6.10k` ` [](const BranchProbability &BP) { return BP.isUnknown(); },`
`void llvm::BranchProbability::normalizeProbabilities<llvm::BranchProbability*>(llvm::BranchProbability*, llvm::BranchProbability*)::'lambda'(llvm::BranchProbability const&)::operator()(llvm::BranchProbability const&) const`
 `Line` `Count` `Source` `229` `2.89k` ` [](const BranchProbability &BP) { return BP.isUnknown(); },`
`230`
`6.26k`
`                    ProbForUnknown);`
`231`
`6.26k`
`232`
`6.26k`
`    if (Sum <= BranchProbability::getDenominator())`
`233`
`6.26k`
`      return;`
`234`
`630k`
`  }`
`235`
`630k`
`236`
`630k`
`  if (Sum == 0) {`
`237`
`834`
`    BranchProbability BP(1, std::distance(Begin, End));`
`238`
`834`
`    std::fill(Begin, End, BP);`
`239`
`834`
`    return;`
`240`
`834`
`  }`
`241`
`629k`
`242`
`1.89M`
`  for (auto I = Begin; 629kI != End; ++I1.26M)`
`243`
`1.26M`
`    I->N = (I->N * uint64_t(D) + Sum / 2) / Sum;`
`244`
`629k`
`}`
`void llvm::BranchProbability::normalizeProbabilities<std::__1::__wrap_iter<llvm::BranchProbability*> >(std::__1::__wrap_iter<llvm::BranchProbability*>, std::__1::__wrap_iter<llvm::BranchProbability*>)`
 `Line` `Count` `Source` `206` `661k` ` ProbabilityIter End) {` `207` `661k` ` if (Begin == End)` `208` `62.8k` ` return;` `209` `598k` `210` `598k` ` unsigned UnknownProbCount = 0;` `211` `598k` ` uint64_t Sum = std::accumulate(Begin, End, uint64_t(0),` `212` `598k` ` [&](uint64_t S, const BranchProbability &BP) {` `213` `598k` ` if (!BP.isUnknown())` `214` `598k` ` return S + BP.N;` `215` `598k` ` UnknownProbCount++;` `216` `598k` ` return S;` `217` `598k` ` });` `218` `598k` `219` `598k` ` if (UnknownProbCount > 0) {` `220` `4.84k` ` BranchProbability ProbForUnknown = BranchProbability::getZero();` `221` `4.84k` ` // If the sum of all known probabilities is less than one, evenly distribute` `222` `4.84k` ` // the complement of sum to unknown probabilities. Otherwise, set unknown` `223` `4.84k` ` // probabilities to zeros and continue to normalize known probabilities.` `224` `4.84k` ` if (Sum < BranchProbability::getDenominator())` `225` `4.84k` ` ProbForUnknown = BranchProbability::getRaw(` `226` `4.84k` ` (BranchProbability::getDenominator() - Sum) / UnknownProbCount);` `227` `4.84k` `228` `4.84k` ` std::replace_if(Begin, End,` `229` `4.84k` ` [](const BranchProbability &BP) { return BP.isUnknown(); },` `230` `4.84k` ` ProbForUnknown);` `231` `4.84k` `232` `4.84k` ` if (Sum <= BranchProbability::getDenominator())` `233` `4.84k` ` return;` `234` `593k` ` }` `235` `593k` `236` `593k` ` if (Sum == 0) {` `237` `833` ` BranchProbability BP(1, std::distance(Begin, End));` `238` `833` ` std::fill(Begin, End, BP);` `239` `833` ` return;` `240` `833` ` }` `241` `593k` `242` `1.78M` ` for (auto I = Begin; 593kI != End; ++I1.19M)` `243` `1.19M` ` I->N = (I->N * uint64_t(D) + Sum / 2) / Sum;` `244` `593k` `}`
`void llvm::BranchProbability::normalizeProbabilities<llvm::BranchProbability*>(llvm::BranchProbability*, llvm::BranchProbability*)`
 `Line` `Count` `Source` `206` `37.4k` ` ProbabilityIter End) {` `207` `37.4k` ` if (Begin == End)` `208` `0` ` return;` `209` `37.4k` `210` `37.4k` ` unsigned UnknownProbCount = 0;` `211` `37.4k` ` uint64_t Sum = std::accumulate(Begin, End, uint64_t(0),` `212` `37.4k` ` [&](uint64_t S, const BranchProbability &BP) {` `213` `37.4k` ` if (!BP.isUnknown())` `214` `37.4k` ` return S + BP.N;` `215` `37.4k` ` UnknownProbCount++;` `216` `37.4k` ` return S;` `217` `37.4k` ` });` `218` `37.4k` `219` `37.4k` ` if (UnknownProbCount > 0) {` `220` `1.42k` ` BranchProbability ProbForUnknown = BranchProbability::getZero();` `221` `1.42k` ` // If the sum of all known probabilities is less than one, evenly distribute` `222` `1.42k` ` // the complement of sum to unknown probabilities. Otherwise, set unknown` `223` `1.42k` ` // probabilities to zeros and continue to normalize known probabilities.` `224` `1.42k` ` if (Sum < BranchProbability::getDenominator())` `225` `1.41k` ` ProbForUnknown = BranchProbability::getRaw(` `226` `1.41k` ` (BranchProbability::getDenominator() - Sum) / UnknownProbCount);` `227` `1.42k` `228` `1.42k` ` std::replace_if(Begin, End,` `229` `1.42k` ` [](const BranchProbability &BP) { return BP.isUnknown(); },` `230` `1.42k` ` ProbForUnknown);` `231` `1.42k` `232` `1.42k` ` if (Sum <= BranchProbability::getDenominator())` `233` `1.42k` ` return;` `234` `36.0k` ` }` `235` `36.0k` `236` `36.0k` ` if (Sum == 0) {` `237` `1` ` BranchProbability BP(1, std::distance(Begin, End));` `238` `1` ` std::fill(Begin, End, BP);` `239` `1` ` return;` `240` `1` ` }` `241` `36.0k` `242` `108k` ` for (auto I = Begin; 36.0kI != End; ++I72.1k)` `243` `72.1k` ` I->N = (I->N * uint64_t(D) + Sum / 2) / Sum;` `244` `36.0k` `}`
`245`
`246`
`}`
`247`
`248`
`#endif`