124 lines · cpp
1//===-------------- lib/Support/BranchProbability.cpp -----------*- 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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements Branch Probability class.10//11//===----------------------------------------------------------------------===//12 13#include "llvm/Support/BranchProbability.h"14#include "llvm/Config/llvm-config.h"15#include "llvm/Support/Debug.h"16#include "llvm/Support/Format.h"17#include "llvm/Support/raw_ostream.h"18#include <cassert>19#include <cmath>20 21using namespace llvm;22 23raw_ostream &BranchProbability::print(raw_ostream &OS) const {24 if (isUnknown())25 return OS << "?%";26 27 // Get a percentage rounded to two decimal digits. This avoids28 // implementation-defined rounding inside printf.29 double Percent = rint(((double)N / D) * 100.0 * 100.0) / 100.0;30 return OS << format("0x%08" PRIx32 " / 0x%08" PRIx32 " = %.2f%%", N, D,31 Percent);32}33 34#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)35LLVM_DUMP_METHOD void BranchProbability::dump() const { print(dbgs()) << '\n'; }36#endif37 38BranchProbability::BranchProbability(uint32_t Numerator, uint32_t Denominator) {39 assert(Denominator > 0 && "Denominator cannot be 0!");40 assert(Numerator <= Denominator && "Probability cannot be bigger than 1!");41 if (Denominator == D)42 N = Numerator;43 else {44 uint64_t Prob64 =45 (Numerator * static_cast<uint64_t>(D) + Denominator / 2) / Denominator;46 N = static_cast<uint32_t>(Prob64);47 }48}49 50BranchProbability51BranchProbability::getBranchProbability(uint64_t Numerator,52 uint64_t Denominator) {53 assert(Numerator <= Denominator && "Probability cannot be bigger than 1!");54 // Scale down Denominator to fit in a 32-bit integer.55 int Scale = 0;56 while (Denominator > UINT32_MAX) {57 Denominator >>= 1;58 Scale++;59 }60 return BranchProbability(Numerator >> Scale, Denominator);61}62 63BranchProbability BranchProbability::getBranchProbability(double Prob) {64 assert(0 <= Prob && Prob <= 1 && "Probability must be between 0 and 1!");65 return BranchProbability(std::round(Prob * D), D);66}67 68// If ConstD is not zero, then replace D by ConstD so that division and modulo69// operations by D can be optimized, in case this function is not inlined by the70// compiler.71template <uint32_t ConstD>72static uint64_t scale(uint64_t Num, uint32_t N, uint32_t D) {73 if (ConstD > 0)74 D = ConstD;75 76 assert(D && "divide by 0");77 78 // Fast path for multiplying by 1.0.79 if (!Num || D == N)80 return Num;81 82 // Split Num into upper and lower parts to multiply, then recombine.83 uint64_t ProductHigh = (Num >> 32) * N;84 uint64_t ProductLow = (Num & UINT32_MAX) * N;85 86 // Split into 32-bit digits.87 uint32_t Upper32 = ProductHigh >> 32;88 uint32_t Lower32 = ProductLow & UINT32_MAX;89 uint32_t Mid32Partial = ProductHigh & UINT32_MAX;90 uint32_t Mid32 = Mid32Partial + (ProductLow >> 32);91 92 // Carry.93 Upper32 += Mid32 < Mid32Partial;94 95 uint64_t Rem = (uint64_t(Upper32) << 32) | Mid32;96 uint64_t UpperQ = Rem / D;97 98 // Check for overflow.99 if (UpperQ > UINT32_MAX)100 return UINT64_MAX;101 102 Rem = ((Rem % D) << 32) | Lower32;103 uint64_t LowerQ = Rem / D;104 uint64_t Q = (UpperQ << 32) + LowerQ;105 106 // Check for overflow.107 return Q < LowerQ ? UINT64_MAX : Q;108}109 110uint64_t BranchProbability::scale(uint64_t Num) const {111 return ::scale<D>(Num, N, D);112}113 114uint64_t BranchProbability::scaleByInverse(uint64_t Num) const {115 return ::scale<0>(Num, D, N);116}117 118BranchProbability BranchProbability::pow(unsigned N) const {119 BranchProbability Res = BranchProbability::getOne();120 for (unsigned I = 0; I < N; ++I)121 Res *= *this;122 return Res;123}124