Movatterモバイル変換

Go to the documentation of this file.

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-exception

6//

7//===----------------------------------------------------------------------===//

8//

9// This file implements Branch Probability class.

10//

11//===----------------------------------------------------------------------===//

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>

21using namespacellvm;

23constexpruint32_t BranchProbability::D;

25raw_ostream &BranchProbability::print(raw_ostream &OS) const{

26if (isUnknown())

27returnOS <<"?%";

29// Get a percentage rounded to two decimal digits. This avoids

30// implementation-defined rounding inside printf.

31doublePercent = rint(((double)N / D) * 100.0 * 100.0) / 100.0;

32returnOS <<format("0x%08" PRIx32" / 0x%08" PRIx32" = %.2f%%", N, D,

33Percent);

34}

36#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

37LLVM_DUMP_METHODvoidBranchProbability::dump() const{print(dbgs()) <<'\n'; }

38#endif

40BranchProbability::BranchProbability(uint32_t Numerator,uint32_t Denominator) {

41assert(Denominator > 0 &&"Denominator cannot be 0!");

42assert(Numerator <= Denominator &&"Probability cannot be bigger than 1!");

43if (Denominator == D)

44 N = Numerator;

45else {

46uint64_t Prob64 =

47 (Numerator *static_cast<uint64_t>(D) + Denominator / 2) / Denominator;

48 N =static_cast<uint32_t>(Prob64);

49 }

50}

52BranchProbability

53BranchProbability::getBranchProbability(uint64_t Numerator,

54uint64_t Denominator) {

55assert(Numerator <= Denominator &&"Probability cannot be bigger than 1!");

56// Scale down Denominator to fit in a 32-bit integer.

57int Scale = 0;

58while (Denominator > UINT32_MAX) {

59 Denominator >>= 1;

60 Scale++;

61 }

62returnBranchProbability(Numerator >> Scale, Denominator);

63}

65// If ConstD is not zero, then replace D by ConstD so that division and modulo

66// operations by D can be optimized, in case this function is not inlined by the

67// compiler.

68template <uint32_t ConstD>

69staticuint64_t scale(uint64_t Num,uint32_t N,uint32_t D) {

70if (ConstD > 0)

71D = ConstD;

73assert(D &&"divide by 0");

75// Fast path for multiplying by 1.0.

76if (!Num ||D ==N)

77return Num;

79// Split Num into upper and lower parts to multiply, then recombine.

80uint64_t ProductHigh = (Num >> 32) *N;

81uint64_t ProductLow = (Num & UINT32_MAX) *N;

83// Split into 32-bit digits.

84uint32_t Upper32 = ProductHigh >> 32;

85uint32_t Lower32 = ProductLow & UINT32_MAX;

86uint32_t Mid32Partial = ProductHigh & UINT32_MAX;

87uint32_t Mid32 = Mid32Partial + (ProductLow >> 32);

89// Carry.

90 Upper32 += Mid32 < Mid32Partial;

92uint64_t Rem = (uint64_t(Upper32) << 32) | Mid32;

93uint64_t UpperQ = Rem /D;

95// Check for overflow.

96if (UpperQ > UINT32_MAX)

97returnUINT64_MAX;

99 Rem = ((Rem %D) << 32) | Lower32;

100uint64_t LowerQ = Rem /D;

101uint64_t Q = (UpperQ << 32) + LowerQ;

102

103// Check for overflow.

104return Q < LowerQ ?UINT64_MAX : Q;

105}

106

107uint64_t BranchProbability::scale(uint64_t Num) const{

108 return ::scale<D>(Num, N, D);

109}

110

111uint64_t BranchProbability::scaleByInverse(uint64_t Num) const{

112 return ::scale<0>(Num, D, N);

113}

scale

static uint64_t scale(uint64_t Num, uint32_t N, uint32_t D)

Definition:BranchProbability.cpp:69

BranchProbability.h

static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")

LLVM_DUMP_METHOD

#define LLVM_DUMP_METHOD

Mark debug helper function definitions like dump() that should not be stripped from debug builds.

Definition:Compiler.h:622

Debug.h

Format.h

assert

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

raw_pwrite_stream & OS

Definition:SampleProfWriter.cpp:51

llvm::BranchProbability

Definition:BranchProbability.h:30

llvm::BranchProbability::dump

void dump() const

Definition:BranchProbability.cpp:37

llvm::BranchProbability::getBranchProbability

static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)

Definition:BranchProbability.cpp:53

llvm::BranchProbability::print

raw_ostream & print(raw_ostream &OS) const

Definition:BranchProbability.cpp:25

llvm::BranchProbability::scaleByInverse

uint64_t scaleByInverse(uint64_t Num) const

Scale a large integer by the inverse.

Definition:BranchProbability.cpp:111

llvm::BranchProbability::isUnknown

bool isUnknown() const

Definition:BranchProbability.h:47

llvm::BranchProbability::scale

uint64_t scale(uint64_t Num) const

Scale a large integer.

Definition:BranchProbability.cpp:107

llvm::BranchProbability::BranchProbability

BranchProbability()

Definition:BranchProbability.h:43

llvm::raw_ostream

This class implements an extremely fast bulk output stream that can only output to a stream.

Definition:raw_ostream.h:52

uint32_t

uint64_t

UINT64_MAX

#define UINT64_MAX

Definition:DataTypes.h:77

llvm

This is an optimization pass for GlobalISel generic memory operations.

Definition:AddressRanges.h:18

llvm::FloatStyle::Percent

@ Percent

llvm::dbgs

raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

Definition:Debug.cpp:163

llvm::format

format_object< Ts... > format(const char *Fmt, const Ts &... Vals)

These are helper functions used to produce formatted output.

Definition:Format.h:125

raw_ostream.h

#define N