Movatterモバイル変換

Go to the documentation of this file.

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//===----------------------------------------------------------------------===//

13#ifndef LLVM_SUPPORT_BRANCHPROBABILITY_H

14#define LLVM_SUPPORT_BRANCHPROBABILITY_H

16#include "llvm/Support/DataTypes.h"

17#include <algorithm>

18#include <cassert>

19#include <iterator>

20#include <numeric>

22namespacellvm {

24classraw_ostream;

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).

30classBranchProbability {

31// Numerator

32uint32_t N;

34// Denominator, which is a constant value.

35staticconstexpruint32_t D = 1u << 31;

36staticconstexpruint32_t UnknownN = UINT32_MAX;

38// Construct a BranchProbability with only numerator assuming the denominator

39// is 1<<31. For internal use only.

40explicitBranchProbability(uint32_t n) :N(n) {}

42public:

43BranchProbability() :N(UnknownN) {}

44BranchProbability(uint32_t Numerator,uint32_t Denominator);

46boolisZero() const{returnN == 0; }

47boolisUnknown() const{returnN == UnknownN; }

49staticBranchProbability getZero() {returnBranchProbability(0); }

50staticBranchProbability getOne() {returnBranchProbability(D); }

51staticBranchProbability getUnknown() {returnBranchProbability(UnknownN); }

52// Create a BranchProbability object with the given numerator and 1<<31

53// as denominator.

54staticBranchProbability getRaw(uint32_t N) {returnBranchProbability(N); }

55// Create a BranchProbability object from 64-bit integers.

56staticBranchProbability getBranchProbability(uint64_t Numerator,

57uint64_t Denominator);

59// Normalize given probabilties so that the sum of them becomes approximate

60// one.

61template <class ProbabilityIter>

62staticvoidnormalizeProbabilities(ProbabilityIter Begin,

63 ProbabilityIterEnd);

65uint32_t getNumerator() const{returnN; }

66staticuint32_t getDenominator() {return D; }

68// Return (1 - Probability).

69BranchProbability getCompl() const{returnBranchProbability(D -N); }

71raw_ostream &print(raw_ostream &OS)const;

73voiddump()const;

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.

81uint64_t scale(uint64_t Num)const;

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.

89uint64_t scaleByInverse(uint64_t Num)const;

91BranchProbability &operator+=(BranchProbability RHS) {

92assert(N != UnknownN &&RHS.N != UnknownN &&

93"Unknown probability cannot participate in arithmetics.");

94// Saturate the result in case of overflow.

95N = (uint64_t(N) +RHS.N > D) ? D :N +RHS.N;

96return *this;

97 }

99BranchProbability &operator-=(BranchProbability RHS) {

100assert(N != UnknownN &&RHS.N != UnknownN &&

101"Unknown probability cannot participate in arithmetics.");

102// Saturate the result in case of underflow.

103N =N <RHS.N ? 0 :N -RHS.N;

104return *this;

105 }

106

107BranchProbability &operator*=(BranchProbability RHS) {

108assert(N != UnknownN &&RHS.N != UnknownN &&

109"Unknown probability cannot participate in arithmetics.");

110N = (static_cast<uint64_t>(N) *RHS.N + D / 2) / D;

111return *this;

112 }

113

114BranchProbability &operator*=(uint32_t RHS) {

115assert(N != UnknownN &&

116"Unknown probability cannot participate in arithmetics.");

117N = (uint64_t(N) *RHS > D) ? D :N *RHS;

118return *this;

119 }

120

121BranchProbability &operator/=(BranchProbability RHS) {

122assert(N != UnknownN &&RHS.N != UnknownN &&

123"Unknown probability cannot participate in arithmetics.");

124N = (static_cast<uint64_t>(N) * D +RHS.N / 2) /RHS.N;

125return *this;

126 }

127

128BranchProbability &operator/=(uint32_t RHS) {

129assert(N != UnknownN &&

130"Unknown probability cannot participate in arithmetics.");

131assert(RHS > 0 &&"The divider cannot be zero.");

132N /=RHS;

133return *this;

134 }

135

136BranchProbability operator+(BranchProbability RHS) const{

137BranchProbability Prob(*this);

138 Prob +=RHS;

139return Prob;

140 }

141

142BranchProbability operator-(BranchProbability RHS) const{

143BranchProbability Prob(*this);

144 Prob -=RHS;

145return Prob;

146 }

147

148BranchProbability operator*(BranchProbability RHS) const{

149BranchProbability Prob(*this);

150 Prob *=RHS;

151return Prob;

152 }

153

154BranchProbability operator*(uint32_t RHS) const{

155BranchProbability Prob(*this);

156 Prob *=RHS;

157return Prob;

158 }

159

160BranchProbability operator/(BranchProbability RHS) const{

161BranchProbability Prob(*this);

162 Prob /=RHS;

163return Prob;

164 }

165

166BranchProbability operator/(uint32_t RHS) const{

167BranchProbability Prob(*this);

168 Prob /=RHS;

169return Prob;

170 }

171

172booloperator==(BranchProbability RHS) const{returnN ==RHS.N; }

173booloperator!=(BranchProbability RHS) const{return !(*this ==RHS); }

174

175booloperator<(BranchProbability RHS) const{

176assert(N != UnknownN &&RHS.N != UnknownN &&

177"Unknown probability cannot participate in comparisons.");

178returnN <RHS.N;

179 }

180

181booloperator>(BranchProbability RHS) const{

182assert(N != UnknownN &&RHS.N != UnknownN &&

183"Unknown probability cannot participate in comparisons.");

184returnRHS < *this;

185 }

186

187booloperator<=(BranchProbability RHS) const{

188assert(N != UnknownN &&RHS.N != UnknownN &&

189"Unknown probability cannot participate in comparisons.");

190return !(RHS < *this);

191 }

192

193booloperator>=(BranchProbability RHS) const{

194assert(N != UnknownN &&RHS.N != UnknownN &&

195"Unknown probability cannot participate in comparisons.");

196return !(*this <RHS);

197 }

198};

199

200inlineraw_ostream &operator<<(raw_ostream &OS,BranchProbability Prob) {

201return Prob.print(OS);

202}

203

204template <class ProbabilityIter>

205voidBranchProbability::normalizeProbabilities(ProbabilityIter Begin,

206 ProbabilityIterEnd) {

207if (Begin ==End)

208return;

209

210unsigned UnknownProbCount = 0;

211uint64_t Sum = std::accumulate(Begin,End,uint64_t(0),

212 [&](uint64_t S,constBranchProbability &BP) {

213if (!BP.isUnknown())

214return S + BP.N;

215 UnknownProbCount++;

216return S;

217 });

218

219if (UnknownProbCount > 0) {

220BranchProbability ProbForUnknown =BranchProbability::getZero();

221// If the sum of all known probabilities is less than one, evenly distribute

222// the complement of sum to unknown probabilities. Otherwise, set unknown

223// probabilities to zeros and continue to normalize known probabilities.

224if (Sum <BranchProbability::getDenominator())

225 ProbForUnknown =BranchProbability::getRaw(

226 (BranchProbability::getDenominator() - Sum) / UnknownProbCount);

227

228 std::replace_if(Begin,End,

229 [](constBranchProbability &BP) {return BP.isUnknown(); },

230 ProbForUnknown);

231

232if (Sum <=BranchProbability::getDenominator())

233return;

234 }

235

236if (Sum == 0) {

237BranchProbability BP(1, std::distance(Begin,End));

238 std::fill(Begin,End, BP);

239return;

240 }

241

242for (autoI = Begin;I !=End; ++I)

243I->N = (I->N *uint64_t(D) + Sum / 2) / Sum;

244}

245

246}

247

248#endif

End

bool End

Definition:ELF_riscv.cpp:480

#define I(x, y, z)

Definition:MD5.cpp:58

assert

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

raw_pwrite_stream & OS

Definition:SampleProfWriter.cpp:51

RHS

Value * RHS

Definition:X86PartialReduction.cpp:74

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::operator-

BranchProbability operator-(BranchProbability RHS) const

Definition:BranchProbability.h:142

llvm::BranchProbability::operator-=

BranchProbability & operator-=(BranchProbability RHS)

Definition:BranchProbability.h:99

llvm::BranchProbability::getDenominator

static uint32_t getDenominator()

Definition:BranchProbability.h:66

llvm::BranchProbability::operator<

bool operator<(BranchProbability RHS) const

Definition:BranchProbability.h:175

llvm::BranchProbability::operator!=

bool operator!=(BranchProbability RHS) const

Definition:BranchProbability.h:173

llvm::BranchProbability::getRaw

static BranchProbability getRaw(uint32_t N)

Definition:BranchProbability.h:54

llvm::BranchProbability::operator==

bool operator==(BranchProbability RHS) const

Definition:BranchProbability.h:172

llvm::BranchProbability::operator/

BranchProbability operator/(uint32_t RHS) const

Definition:BranchProbability.h:166

llvm::BranchProbability::operator/=

BranchProbability & operator/=(BranchProbability RHS)

Definition:BranchProbability.h:121

llvm::BranchProbability::operator<=

bool operator<=(BranchProbability RHS) const

Definition:BranchProbability.h:187

llvm::BranchProbability::getOne

static BranchProbability getOne()

Definition:BranchProbability.h:50

llvm::BranchProbability::print

raw_ostream & print(raw_ostream &OS) const

Definition:BranchProbability.cpp:25

llvm::BranchProbability::operator*=

BranchProbability & operator*=(BranchProbability RHS)

Definition:BranchProbability.h:107

llvm::BranchProbability::scaleByInverse

uint64_t scaleByInverse(uint64_t Num) const

Scale a large integer by the inverse.

Definition:BranchProbability.cpp:111

llvm::BranchProbability::isZero

bool isZero() const

Definition:BranchProbability.h:46

llvm::BranchProbability::operator*

BranchProbability operator*(BranchProbability RHS) const

Definition:BranchProbability.h:148

llvm::BranchProbability::getUnknown

static BranchProbability getUnknown()

Definition:BranchProbability.h:51

llvm::BranchProbability::operator/

BranchProbability operator/(BranchProbability RHS) const

Definition:BranchProbability.h:160

llvm::BranchProbability::getNumerator

uint32_t getNumerator() const

Definition:BranchProbability.h:65

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::BranchProbability::operator+

BranchProbability operator+(BranchProbability RHS) const

Definition:BranchProbability.h:136

llvm::BranchProbability::operator>=

bool operator>=(BranchProbability RHS) const

Definition:BranchProbability.h:193

llvm::BranchProbability::operator*

BranchProbability operator*(uint32_t RHS) const

Definition:BranchProbability.h:154

llvm::BranchProbability::operator*=

BranchProbability & operator*=(uint32_t RHS)

Definition:BranchProbability.h:114

llvm::BranchProbability::getCompl

BranchProbability getCompl() const

Definition:BranchProbability.h:69

llvm::BranchProbability::operator+=

BranchProbability & operator+=(BranchProbability RHS)

Definition:BranchProbability.h:91

llvm::BranchProbability::operator/=

BranchProbability & operator/=(uint32_t RHS)

Definition:BranchProbability.h:128

llvm::BranchProbability::getZero

static BranchProbability getZero()

Definition:BranchProbability.h:49

llvm::BranchProbability::operator>

bool operator>(BranchProbability RHS) const

Definition:BranchProbability.h:181

llvm::BranchProbability::normalizeProbabilities

static void normalizeProbabilities(ProbabilityIter Begin, ProbabilityIter End)

Definition:BranchProbability.h:205

llvm::raw_ostream

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

Definition:raw_ostream.h:52

This is an optimization pass for GlobalISel generic memory operations.

Definition:AddressRanges.h:18

llvm::operator<<

raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)

Definition:APFixedPoint.h:303

#define N