Movatterモバイル変換

Go to the documentation of this file.

1//===- BranchProbabilityInfo.cpp - Branch Probability Analysis ------------===//

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// Loops should be simplified before this analysis.

10//

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

13#include "llvm/Analysis/BranchProbabilityInfo.h"

14#include "llvm/ADT/PostOrderIterator.h"

15#include "llvm/ADT/SCCIterator.h"

16#include "llvm/ADT/STLExtras.h"

17#include "llvm/ADT/SmallVector.h"

18#include "llvm/Analysis/ConstantFolding.h"

19#include "llvm/Analysis/LoopInfo.h"

20#include "llvm/Analysis/PostDominators.h"

21#include "llvm/Analysis/TargetLibraryInfo.h"

22#include "llvm/IR/Attributes.h"

23#include "llvm/IR/BasicBlock.h"

24#include "llvm/IR/CFG.h"

25#include "llvm/IR/Constants.h"

26#include "llvm/IR/Dominators.h"

27#include "llvm/IR/Function.h"

28#include "llvm/IR/InstrTypes.h"

29#include "llvm/IR/Instruction.h"

30#include "llvm/IR/Instructions.h"

31#include "llvm/IR/LLVMContext.h"

32#include "llvm/IR/Metadata.h"

33#include "llvm/IR/PassManager.h"

34#include "llvm/IR/ProfDataUtils.h"

35#include "llvm/IR/Type.h"

36#include "llvm/IR/Value.h"

37#include "llvm/InitializePasses.h"

38#include "llvm/Pass.h"

39#include "llvm/Support/BranchProbability.h"

40#include "llvm/Support/Casting.h"

41#include "llvm/Support/CommandLine.h"

42#include "llvm/Support/Debug.h"

43#include "llvm/Support/raw_ostream.h"

44#include <cassert>

45#include <cstdint>

46#include <map>

47#include <utility>

49using namespacellvm;

51#define DEBUG_TYPE "branch-prob"

53staticcl::opt<bool>PrintBranchProb(

54"print-bpi",cl::init(false),cl::Hidden,

55cl::desc("Print the branch probability info."));

57cl::opt<std::string>PrintBranchProbFuncName(

58"print-bpi-func-name",cl::Hidden,

59cl::desc("The option to specify the name of the function "

60"whose branch probability info is printed."));

62INITIALIZE_PASS_BEGIN(BranchProbabilityInfoWrapperPass,"branch-prob",

63"Branch Probability Analysis",false,true)

64INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)

65INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)

66INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)

67INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)

68INITIALIZE_PASS_END(BranchProbabilityInfoWrapperPass, "branch-prob",

69 "Branch ProbabilityAnalysis",false,true)

71BranchProbabilityInfoWrapperPass::BranchProbabilityInfoWrapperPass()

72 :FunctionPass(ID) {

73initializeBranchProbabilityInfoWrapperPassPass(

74 *PassRegistry::getPassRegistry());

75}

77charBranchProbabilityInfoWrapperPass::ID = 0;

79// Weights are for internal use only. They are used by heuristics to help to

80// estimate edges' probability. Example:

81//

82// Using "Loop Branch Heuristics" we predict weights of edges for the

83// block BB2.

84// ...

85// |

86// V

87// BB1<-+

88// | |

89// | | (Weight = 124)

90// V |

91// BB2--+

92// |

93// | (Weight = 4)

94// V

95// BB3

96//

97// Probability of the edge BB2->BB1 = 124 / (124 + 4) = 0.96875

98// Probability of the edge BB2->BB3 = 4 / (124 + 4) = 0.03125

99staticconstuint32_t LBH_TAKEN_WEIGHT = 124;

100staticconstuint32_t LBH_NONTAKEN_WEIGHT = 4;

101

102/// Unreachable-terminating branch taken probability.

103///

104/// This is the probability for a branch being taken to a block that terminates

105/// (eventually) in unreachable. These are predicted as unlikely as possible.

106/// All reachable probability will proportionally share the remaining part.

107staticconstBranchProbability UR_TAKEN_PROB =BranchProbability::getRaw(1);

108

109/// Heuristics and lookup tables for non-loop branches:

110/// Pointer Heuristics (PH)

111staticconstuint32_t PH_TAKEN_WEIGHT = 20;

112staticconstuint32_t PH_NONTAKEN_WEIGHT = 12;

113staticconstBranchProbability

114PtrTakenProb(PH_TAKEN_WEIGHT,PH_TAKEN_WEIGHT +PH_NONTAKEN_WEIGHT);

115staticconstBranchProbability

116PtrUntakenProb(PH_NONTAKEN_WEIGHT,PH_TAKEN_WEIGHT +PH_NONTAKEN_WEIGHT);

117

118usingProbabilityList =SmallVector<BranchProbability>;

119usingProbabilityTable = std::map<CmpInst::Predicate, ProbabilityList>;

120

121/// Pointer comparisons:

122staticconstProbabilityTable PointerTable{

123 {ICmpInst::ICMP_NE, {PtrTakenProb,PtrUntakenProb}},/// p != q -> Likely

124 {ICmpInst::ICMP_EQ, {PtrUntakenProb,PtrTakenProb}},/// p == q -> Unlikely

125};

126

127/// Zero Heuristics (ZH)

128staticconstuint32_t ZH_TAKEN_WEIGHT = 20;

129staticconstuint32_t ZH_NONTAKEN_WEIGHT = 12;

130staticconstBranchProbability

131ZeroTakenProb(ZH_TAKEN_WEIGHT,ZH_TAKEN_WEIGHT +ZH_NONTAKEN_WEIGHT);

132staticconstBranchProbability

133ZeroUntakenProb(ZH_NONTAKEN_WEIGHT,ZH_TAKEN_WEIGHT +ZH_NONTAKEN_WEIGHT);

134

135/// Integer compares with 0:

136staticconstProbabilityTable ICmpWithZeroTable{

137 {CmpInst::ICMP_EQ, {ZeroUntakenProb,ZeroTakenProb}},/// X == 0 -> Unlikely

138 {CmpInst::ICMP_NE, {ZeroTakenProb,ZeroUntakenProb}},/// X != 0 -> Likely

139 {CmpInst::ICMP_SLT, {ZeroUntakenProb,ZeroTakenProb}},/// X < 0 -> Unlikely

140 {CmpInst::ICMP_SGT, {ZeroTakenProb,ZeroUntakenProb}},/// X > 0 -> Likely

141};

142

143/// Integer compares with -1:

144staticconstProbabilityTable ICmpWithMinusOneTable{

145 {CmpInst::ICMP_EQ, {ZeroUntakenProb,ZeroTakenProb}},/// X == -1 -> Unlikely

146 {CmpInst::ICMP_NE, {ZeroTakenProb,ZeroUntakenProb}},/// X != -1 -> Likely

147// InstCombine canonicalizes X >= 0 into X > -1

148 {CmpInst::ICMP_SGT, {ZeroTakenProb,ZeroUntakenProb}},/// X >= 0 -> Likely

149};

150

151/// Integer compares with 1:

152staticconstProbabilityTable ICmpWithOneTable{

153// InstCombine canonicalizes X <= 0 into X < 1

154 {CmpInst::ICMP_SLT, {ZeroUntakenProb,ZeroTakenProb}},/// X <= 0 -> Unlikely

155};

156

157/// strcmp and similar functions return zero, negative, or positive, if the

158/// first string is equal, less, or greater than the second. We consider it

159/// likely that the strings are not equal, so a comparison with zero is

160/// probably false, but also a comparison with any other number is also

161/// probably false given that what exactly is returned for nonzero values is

162/// not specified. Any kind of comparison other than equality we know

163/// nothing about.

164staticconstProbabilityTable ICmpWithLibCallTable{

165 {CmpInst::ICMP_EQ, {ZeroUntakenProb,ZeroTakenProb}},

166 {CmpInst::ICMP_NE, {ZeroTakenProb,ZeroUntakenProb}},

167};

168

169// Floating-Point Heuristics (FPH)

170staticconstuint32_t FPH_TAKEN_WEIGHT = 20;

171staticconstuint32_t FPH_NONTAKEN_WEIGHT = 12;

172

173/// This is the probability for an ordered floating point comparison.

174staticconstuint32_t FPH_ORD_WEIGHT = 1024 * 1024 - 1;

175/// This is the probability for an unordered floating point comparison, it means

176/// one or two of the operands are NaN. Usually it is used to test for an

177/// exceptional case, so the result is unlikely.

178staticconstuint32_t FPH_UNO_WEIGHT = 1;

179

180staticconstBranchProbability FPOrdTakenProb(FPH_ORD_WEIGHT,

181FPH_ORD_WEIGHT +FPH_UNO_WEIGHT);

182staticconstBranchProbability

183FPOrdUntakenProb(FPH_UNO_WEIGHT,FPH_ORD_WEIGHT +FPH_UNO_WEIGHT);

184staticconstBranchProbability

185FPTakenProb(FPH_TAKEN_WEIGHT,FPH_TAKEN_WEIGHT +FPH_NONTAKEN_WEIGHT);

186staticconstBranchProbability

187FPUntakenProb(FPH_NONTAKEN_WEIGHT,FPH_TAKEN_WEIGHT +FPH_NONTAKEN_WEIGHT);

188

189/// Floating-Point compares:

190staticconstProbabilityTable FCmpTable{

191 {FCmpInst::FCMP_ORD, {FPOrdTakenProb,FPOrdUntakenProb}},/// !isnan -> Likely

192 {FCmpInst::FCMP_UNO, {FPOrdUntakenProb,FPOrdTakenProb}},/// isnan -> Unlikely

193};

194

195/// Set of dedicated "absolute" execution weights for a block. These weights are

196/// meaningful relative to each other and their derivatives only.

197enum classBlockExecWeight : std::uint32_t {

198 /// Special weight used for cases with exact zero probability.

199ZERO = 0x0,

200 /// Minimal possible non zero weight.

201LOWEST_NON_ZERO = 0x1,

202 /// Weight to an 'unreachable' block.

203UNREACHABLE =ZERO,

204 /// Weight to a block containing non returning call.

205NORETURN =LOWEST_NON_ZERO,

206 /// Weight to 'unwind' block of an invoke instruction.

207UNWIND =LOWEST_NON_ZERO,

208 /// Weight to a 'cold' block. Cold blocks are the ones containing calls marked

209 /// with attribute 'cold'.

210COLD = 0xffff,

211 /// Default weight is used in cases when there is no dedicated execution

212 /// weight set. It is not propagated through the domination line either.

213DEFAULT = 0xfffff

214};

215

216BranchProbabilityInfo::SccInfo::SccInfo(constFunction &F) {

217// Record SCC numbers of blocks in the CFG to identify irreducible loops.

218// FIXME: We could only calculate this if the CFG is known to be irreducible

219// (perhaps cache this info in LoopInfo if we can easily calculate it there?).

220int SccNum = 0;

221for (scc_iterator<const Function *> It =scc_begin(&F); !It.isAtEnd();

222 ++It, ++SccNum) {

223// Ignore single-block SCCs since they either aren't loops or LoopInfo will

224// catch them.

225const std::vector<const BasicBlock *> &Scc = *It;

226if (Scc.size() == 1)

227continue;

228

229LLVM_DEBUG(dbgs() <<"BPI: SCC " << SccNum <<":");

230for (constauto *BB : Scc) {

231LLVM_DEBUG(dbgs() <<" " << BB->getName());

232 SccNums[BB] = SccNum;

233 calculateSccBlockType(BB, SccNum);

234 }

235LLVM_DEBUG(dbgs() <<"\n");

236 }

237}

238

239intBranchProbabilityInfo::SccInfo::getSCCNum(constBasicBlock *BB) const{

240auto SccIt = SccNums.find(BB);

241if (SccIt == SccNums.end())

242return -1;

243return SccIt->second;

244}

245

246voidBranchProbabilityInfo::SccInfo::getSccEnterBlocks(

247int SccNum,SmallVectorImpl<BasicBlock *> &Enters) const{

248

249for (auto MapIt : SccBlocks[SccNum]) {

250constauto *BB = MapIt.first;

251if (isSCCHeader(BB, SccNum))

252for (constauto *Pred :predecessors(BB))

253if (getSCCNum(Pred) != SccNum)

254 Enters.push_back(const_cast<BasicBlock *>(BB));

255 }

256}

257

258voidBranchProbabilityInfo::SccInfo::getSccExitBlocks(

259int SccNum,SmallVectorImpl<BasicBlock *> &Exits) const{

260for (auto MapIt : SccBlocks[SccNum]) {

261constauto *BB = MapIt.first;

262if (isSCCExitingBlock(BB, SccNum))

263for (constauto *Succ :successors(BB))

264if (getSCCNum(Succ) != SccNum)

265 Exits.push_back(const_cast<BasicBlock *>(Succ));

266 }

267}

268

269uint32_t BranchProbabilityInfo::SccInfo::getSccBlockType(constBasicBlock *BB,

270int SccNum) const{

271assert(getSCCNum(BB) == SccNum);

272

273assert(SccBlocks.size() >static_cast<unsigned>(SccNum) &&"Unknown SCC");

274constauto &SccBlockTypes = SccBlocks[SccNum];

275

276auto It = SccBlockTypes.find(BB);

277if (It != SccBlockTypes.end()) {

278return It->second;

279 }

280return Inner;

281}

282

283void BranchProbabilityInfo::SccInfo::calculateSccBlockType(constBasicBlock *BB,

284int SccNum) {

285assert(getSCCNum(BB) == SccNum);

286uint32_t BlockType = Inner;

287

288if (llvm::any_of(predecessors(BB), [&](constBasicBlock *Pred) {

289// Consider any block that is an entry point to the SCC as

290// a header.

291return getSCCNum(Pred) != SccNum;

292 }))

293BlockType |= Header;

294

295if (llvm::any_of(successors(BB), [&](constBasicBlock *Succ) {

296return getSCCNum(Succ) != SccNum;

297 }))

298BlockType |= Exiting;

299

300// Lazily compute the set of headers for a given SCC and cache the results

301// in the SccHeaderMap.

302if (SccBlocks.size() <=static_cast<unsigned>(SccNum))

303 SccBlocks.resize(SccNum + 1);

304auto &SccBlockTypes = SccBlocks[SccNum];

305

306if (BlockType != Inner) {

307bool IsInserted;

308 std::tie(std::ignore, IsInserted) =

309 SccBlockTypes.insert(std::make_pair(BB, BlockType));

310assert(IsInserted &&"Duplicated block in SCC");

311 }

312}

313

314BranchProbabilityInfo::LoopBlock::LoopBlock(constBasicBlock *BB,

315constLoopInfo &LI,

316const SccInfo &SccI)

317 : BB(BB) {

318LD.first = LI.getLoopFor(BB);

319if (!LD.first) {

320LD.second = SccI.getSCCNum(BB);

321 }

322}

323

324bool BranchProbabilityInfo::isLoopEnteringEdge(const LoopEdge &Edge) const{

325constauto &SrcBlock = Edge.first;

326constauto &DstBlock = Edge.second;

327return (DstBlock.getLoop() &&

328 !DstBlock.getLoop()->contains(SrcBlock.getLoop())) ||

329// Assume that SCCs can't be nested.

330 (DstBlock.getSccNum() != -1 &&

331 SrcBlock.getSccNum() != DstBlock.getSccNum());

332}

333

334bool BranchProbabilityInfo::isLoopExitingEdge(const LoopEdge &Edge) const{

335return isLoopEnteringEdge({Edge.second, Edge.first});

336}

337

338bool BranchProbabilityInfo::isLoopEnteringExitingEdge(

339const LoopEdge &Edge) const{

340return isLoopEnteringEdge(Edge) || isLoopExitingEdge(Edge);

341}

342

343bool BranchProbabilityInfo::isLoopBackEdge(const LoopEdge &Edge) const{

344constauto &SrcBlock = Edge.first;

345constauto &DstBlock = Edge.second;

346return SrcBlock.belongsToSameLoop(DstBlock) &&

347 ((DstBlock.getLoop() &&

348 DstBlock.getLoop()->getHeader() == DstBlock.getBlock()) ||

349 (DstBlock.getSccNum() != -1 &&

350 SccI->isSCCHeader(DstBlock.getBlock(), DstBlock.getSccNum())));

351}

352

353void BranchProbabilityInfo::getLoopEnterBlocks(

354const LoopBlock &LB,SmallVectorImpl<BasicBlock *> &Enters) const{

355if (LB.getLoop()) {

356auto *Header = LB.getLoop()->getHeader();

357 Enters.append(pred_begin(Header),pred_end(Header));

358 }else {

359assert(LB.getSccNum() != -1 &&"LB doesn't belong to any loop?");

360 SccI->getSccEnterBlocks(LB.getSccNum(), Enters);

361 }

362}

363

364void BranchProbabilityInfo::getLoopExitBlocks(

365const LoopBlock &LB,SmallVectorImpl<BasicBlock *> &Exits) const{

366if (LB.getLoop()) {

367 LB.getLoop()->getExitBlocks(Exits);

368 }else {

369assert(LB.getSccNum() != -1 &&"LB doesn't belong to any loop?");

370 SccI->getSccExitBlocks(LB.getSccNum(), Exits);

371 }

372}

373

374// Propagate existing explicit probabilities from either profile data or

375// 'expect' intrinsic processing. Examine metadata against unreachable

376// heuristic. The probability of the edge coming to unreachable block is

377// set to min of metadata and unreachable heuristic.

378bool BranchProbabilityInfo::calcMetadataWeights(constBasicBlock *BB) {

379constInstruction *TI = BB->getTerminator();

380assert(TI->getNumSuccessors() > 1 &&"expected more than one successor!");

381if (!(isa<BranchInst>(TI) || isa<SwitchInst>(TI) || isa<IndirectBrInst>(TI) ||

382 isa<InvokeInst>(TI) || isa<CallBrInst>(TI)))

383returnfalse;

384

385MDNode *WeightsNode =getValidBranchWeightMDNode(*TI);

386if (!WeightsNode)

387returnfalse;

388

389// Check that the number of successors is manageable.

390assert(TI->getNumSuccessors() < UINT32_MAX &&"Too many successors");

391

392// Build up the final weights that will be used in a temporary buffer.

393// Compute the sum of all weights to later decide whether they need to

394// be scaled to fit in 32 bits.

395uint64_t WeightSum = 0;

396SmallVector<uint32_t, 2> Weights;

397SmallVector<unsigned, 2> UnreachableIdxs;

398SmallVector<unsigned, 2> ReachableIdxs;

399

400extractBranchWeights(WeightsNode, Weights);

401for (unsignedI = 0, E = Weights.size();I != E; ++I) {

402 WeightSum += Weights[I];

403const LoopBlock SrcLoopBB = getLoopBlock(BB);

404const LoopBlock DstLoopBB = getLoopBlock(TI->getSuccessor(I));

405auto EstimatedWeight = getEstimatedEdgeWeight({SrcLoopBB, DstLoopBB});

406if (EstimatedWeight &&

407 *EstimatedWeight <=static_cast<uint32_t>(BlockExecWeight::UNREACHABLE))

408 UnreachableIdxs.push_back(I);

409else

410 ReachableIdxs.push_back(I);

411 }

412assert(Weights.size() == TI->getNumSuccessors() &&"Checked above");

413

414// If the sum of weights does not fit in 32 bits, scale every weight down

415// accordingly.

416uint64_t ScalingFactor =

417 (WeightSum > UINT32_MAX) ? WeightSum / UINT32_MAX + 1 : 1;

418

419if (ScalingFactor > 1) {

420 WeightSum = 0;

421for (unsignedI = 0, E = TI->getNumSuccessors();I != E; ++I) {

422 Weights[I] /= ScalingFactor;

423 WeightSum += Weights[I];

424 }

425 }

426assert(WeightSum <= UINT32_MAX &&

427"Expected weights to scale down to 32 bits");

428

429if (WeightSum == 0 || ReachableIdxs.size() == 0) {

430for (unsignedI = 0, E = TI->getNumSuccessors();I != E; ++I)

431 Weights[I] = 1;

432 WeightSum = TI->getNumSuccessors();

433 }

434

435// Set the probability.

436SmallVector<BranchProbability, 2> BP;

437for (unsignedI = 0, E = TI->getNumSuccessors();I != E; ++I)

438 BP.push_back({ Weights[I],static_cast<uint32_t>(WeightSum) });

439

440// Examine the metadata against unreachable heuristic.

441// If the unreachable heuristic is more strong then we use it for this edge.

442if (UnreachableIdxs.size() == 0 || ReachableIdxs.size() == 0) {

443setEdgeProbability(BB, BP);

444returntrue;

445 }

446

447auto UnreachableProb =UR_TAKEN_PROB;

448for (autoI : UnreachableIdxs)

449if (UnreachableProb < BP[I]) {

450 BP[I] = UnreachableProb;

451 }

452

453// Sum of all edge probabilities must be 1.0. If we modified the probability

454// of some edges then we must distribute the introduced difference over the

455// reachable blocks.

456//

457// Proportional distribution: the relation between probabilities of the

458// reachable edges is kept unchanged. That is for any reachable edges i and j:

459// newBP[i] / newBP[j] == oldBP[i] / oldBP[j] =>

460// newBP[i] / oldBP[i] == newBP[j] / oldBP[j] == K

461// Where K is independent of i,j.

462// newBP[i] == oldBP[i] * K

463// We need to find K.

464// Make sum of all reachables of the left and right parts:

465// sum_of_reachable(newBP) == K * sum_of_reachable(oldBP)

466// Sum of newBP must be equal to 1.0:

467// sum_of_reachable(newBP) + sum_of_unreachable(newBP) == 1.0 =>

468// sum_of_reachable(newBP) = 1.0 - sum_of_unreachable(newBP)

469// Where sum_of_unreachable(newBP) is what has been just changed.

470// Finally:

471// K == sum_of_reachable(newBP) / sum_of_reachable(oldBP) =>

472// K == (1.0 - sum_of_unreachable(newBP)) / sum_of_reachable(oldBP)

473BranchProbability NewUnreachableSum =BranchProbability::getZero();

474for (autoI : UnreachableIdxs)

475 NewUnreachableSum += BP[I];

476

477BranchProbability NewReachableSum =

478BranchProbability::getOne() - NewUnreachableSum;

479

480BranchProbability OldReachableSum =BranchProbability::getZero();

481for (autoI : ReachableIdxs)

482 OldReachableSum += BP[I];

483

484if (OldReachableSum != NewReachableSum) {// Anything to dsitribute?

485if (OldReachableSum.isZero()) {

486// If all oldBP[i] are zeroes then the proportional distribution results

487// in all zero probabilities and the error stays big. In this case we

488// evenly spread NewReachableSum over the reachable edges.

489BranchProbability PerEdge = NewReachableSum / ReachableIdxs.size();

490for (autoI : ReachableIdxs)

491 BP[I] = PerEdge;

492 }else {

493for (autoI : ReachableIdxs) {

494// We use uint64_t to avoid double rounding error of the following

495// calculation: BP[i] = BP[i] * NewReachableSum / OldReachableSum

496// The formula is taken from the private constructor

497// BranchProbability(uint32_t Numerator, uint32_t Denominator)

498uint64_t Mul =static_cast<uint64_t>(NewReachableSum.getNumerator()) *

499 BP[I].getNumerator();

500uint32_t Div =static_cast<uint32_t>(

501divideNearest(Mul, OldReachableSum.getNumerator()));

502 BP[I] =BranchProbability::getRaw(Div);

503 }

504 }

505 }

506

507setEdgeProbability(BB, BP);

508

509returntrue;

510}

511

512// Calculate Edge Weights using "Pointer Heuristics". Predict a comparison

513// between two pointer or pointer and NULL will fail.

514bool BranchProbabilityInfo::calcPointerHeuristics(constBasicBlock *BB) {

515constBranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());

516if (!BI || !BI->isConditional())

517returnfalse;

518

519Value *Cond = BI->getCondition();

520ICmpInst *CI = dyn_cast<ICmpInst>(Cond);

521if (!CI || !CI->isEquality())

522returnfalse;

523

524Value *LHS = CI->getOperand(0);

525

526if (!LHS->getType()->isPointerTy())

527returnfalse;

528

529assert(CI->getOperand(1)->getType()->isPointerTy());

530

531auto Search =PointerTable.find(CI->getPredicate());

532if (Search ==PointerTable.end())

533returnfalse;

534setEdgeProbability(BB, Search->second);

535returntrue;

536}

537

538// Compute the unlikely successors to the block BB in the loop L, specifically

539// those that are unlikely because this is a loop, and add them to the

540// UnlikelyBlocks set.

541staticvoid

542computeUnlikelySuccessors(constBasicBlock *BB,Loop *L,

543SmallPtrSetImpl<const BasicBlock*> &UnlikelyBlocks) {

544// Sometimes in a loop we have a branch whose condition is made false by

545// taking it. This is typically something like

546// int n = 0;

547// while (...) {

548// if (++n >= MAX) {

549// n = 0;

550// }

551// }

552// In this sort of situation taking the branch means that at the very least it

553// won't be taken again in the next iteration of the loop, so we should

554// consider it less likely than a typical branch.

555//

556// We detect this by looking back through the graph of PHI nodes that sets the

557// value that the condition depends on, and seeing if we can reach a successor

558// block which can be determined to make the condition false.

559//

560// FIXME: We currently consider unlikely blocks to be half as likely as other

561// blocks, but if we consider the example above the likelyhood is actually

562// 1/MAX. We could therefore be more precise in how unlikely we consider

563// blocks to be, but it would require more careful examination of the form

564// of the comparison expression.

565constBranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());

566if (!BI || !BI->isConditional())

567return;

568

569// Check if the branch is based on an instruction compared with a constant

570CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition());

571if (!CI || !isa<Instruction>(CI->getOperand(0)) ||

572 !isa<Constant>(CI->getOperand(1)))

573return;

574

575// Either the instruction must be a PHI, or a chain of operations involving

576// constants that ends in a PHI which we can then collapse into a single value

577// if the PHI value is known.

578Instruction *CmpLHS = dyn_cast<Instruction>(CI->getOperand(0));

579PHINode *CmpPHI = dyn_cast<PHINode>(CmpLHS);

580Constant *CmpConst = dyn_cast<Constant>(CI->getOperand(1));

581// Collect the instructions until we hit a PHI

582SmallVector<BinaryOperator *, 1> InstChain;

583while (!CmpPHI && CmpLHS && isa<BinaryOperator>(CmpLHS) &&

584 isa<Constant>(CmpLHS->getOperand(1))) {

585// Stop if the chain extends outside of the loop

586if (!L->contains(CmpLHS))

587return;

588 InstChain.push_back(cast<BinaryOperator>(CmpLHS));

589 CmpLHS = dyn_cast<Instruction>(CmpLHS->getOperand(0));

590if (CmpLHS)

591 CmpPHI = dyn_cast<PHINode>(CmpLHS);

592 }

593if (!CmpPHI || !L->contains(CmpPHI))

594return;

595

596// Trace the phi node to find all values that come from successors of BB

597SmallPtrSet<PHINode*, 8> VisitedInsts;

598SmallVector<PHINode*, 8> WorkList;

599 WorkList.push_back(CmpPHI);

600 VisitedInsts.insert(CmpPHI);

601while (!WorkList.empty()) {

602PHINode *P = WorkList.pop_back_val();

603for (BasicBlock *B :P->blocks()) {

604// Skip blocks that aren't part of the loop

605if (!L->contains(B))

606continue;

607Value *V =P->getIncomingValueForBlock(B);

608// If the source is a PHI add it to the work list if we haven't

609// already visited it.

610if (PHINode *PN = dyn_cast<PHINode>(V)) {

611if (VisitedInsts.insert(PN).second)

612 WorkList.push_back(PN);

613continue;

614 }

615// If this incoming value is a constant and B is a successor of BB, then

616// we can constant-evaluate the compare to see if it makes the branch be

617// taken or not.

618Constant *CmpLHSConst = dyn_cast<Constant>(V);

619if (!CmpLHSConst || !llvm::is_contained(successors(BB),B))

620continue;

621// First collapse InstChain

622constDataLayout &DL = BB->getDataLayout();

623for (Instruction *I :llvm::reverse(InstChain)) {

624 CmpLHSConst =ConstantFoldBinaryOpOperands(

625I->getOpcode(), CmpLHSConst, cast<Constant>(I->getOperand(1)),DL);

626if (!CmpLHSConst)

627break;

628 }

629if (!CmpLHSConst)

630continue;

631// Now constant-evaluate the compare

632Constant *Result =ConstantFoldCompareInstOperands(

633 CI->getPredicate(), CmpLHSConst, CmpConst,DL);

634// If the result means we don't branch to the block then that block is

635// unlikely.

636if (Result &&

637 ((Result->isZeroValue() &&B == BI->getSuccessor(0)) ||

638 (Result->isOneValue() &&B == BI->getSuccessor(1))))

639 UnlikelyBlocks.insert(B);

640 }

641 }

642}

643

644std::optional<uint32_t>

645BranchProbabilityInfo::getEstimatedBlockWeight(constBasicBlock *BB) const{

646auto WeightIt = EstimatedBlockWeight.find(BB);

647if (WeightIt == EstimatedBlockWeight.end())

648return std::nullopt;

649return WeightIt->second;

650}

651

652std::optional<uint32_t>

653BranchProbabilityInfo::getEstimatedLoopWeight(const LoopData &L) const{

654auto WeightIt = EstimatedLoopWeight.find(L);

655if (WeightIt == EstimatedLoopWeight.end())

656return std::nullopt;

657return WeightIt->second;

658}

659

660std::optional<uint32_t>

661BranchProbabilityInfo::getEstimatedEdgeWeight(const LoopEdge &Edge) const{

662// For edges entering a loop take weight of a loop rather than an individual

663// block in the loop.

664return isLoopEnteringEdge(Edge)

665 ? getEstimatedLoopWeight(Edge.second.getLoopData())

666 : getEstimatedBlockWeight(Edge.second.getBlock());

667}

668

669template <class IterT>

670std::optional<uint32_t> BranchProbabilityInfo::getMaxEstimatedEdgeWeight(

671const LoopBlock &SrcLoopBB,iterator_range<IterT> Successors) const{

672SmallVector<uint32_t, 4> Weights;

673 std::optional<uint32_t> MaxWeight;

674for (constBasicBlock *DstBB : Successors) {

675const LoopBlock DstLoopBB = getLoopBlock(DstBB);

676auto Weight = getEstimatedEdgeWeight({SrcLoopBB, DstLoopBB});

677

678if (!Weight)

679return std::nullopt;

680

681if (!MaxWeight || *MaxWeight < *Weight)

682 MaxWeight = Weight;

683 }

684

685return MaxWeight;

686}

687

688// Updates \p LoopBB's weight and returns true. If \p LoopBB has already

689// an associated weight it is unchanged and false is returned.

690//

691// Please note by the algorithm the weight is not expected to change once set

692// thus 'false' status is used to track visited blocks.

693bool BranchProbabilityInfo::updateEstimatedBlockWeight(

694 LoopBlock &LoopBB,uint32_t BBWeight,

695SmallVectorImpl<BasicBlock *> &BlockWorkList,

696SmallVectorImpl<LoopBlock> &LoopWorkList) {

697BasicBlock *BB = LoopBB.getBlock();

698

699// In general, weight is assigned to a block when it has final value and

700// can't/shouldn't be changed. However, there are cases when a block

701// inherently has several (possibly "contradicting") weights. For example,

702// "unwind" block may also contain "cold" call. In that case the first

703// set weight is favored and all consequent weights are ignored.

704if (!EstimatedBlockWeight.insert({BB, BBWeight}).second)

705returnfalse;

706

707for (BasicBlock *PredBlock :predecessors(BB)) {

708 LoopBlock PredLoop = getLoopBlock(PredBlock);

709// Add affected block/loop to a working list.

710if (isLoopExitingEdge({PredLoop, LoopBB})) {

711if (!EstimatedLoopWeight.count(PredLoop.getLoopData()))

712 LoopWorkList.push_back(PredLoop);

713 }elseif (!EstimatedBlockWeight.count(PredBlock))

714 BlockWorkList.push_back(PredBlock);

715 }

716returntrue;

717}

718

719// Starting from \p BB traverse through dominator blocks and assign \p BBWeight

720// to all such blocks that are post dominated by \BB. In other words to all

721// blocks that the one is executed if and only if another one is executed.

722// Importantly, we skip loops here for two reasons. First weights of blocks in

723// a loop should be scaled by trip count (yet possibly unknown). Second there is

724// no any value in doing that because that doesn't give any additional

725// information regarding distribution of probabilities inside the loop.

726// Exception is loop 'enter' and 'exit' edges that are handled in a special way

727// at calcEstimatedHeuristics.

728//

729// In addition, \p WorkList is populated with basic blocks if at leas one

730// successor has updated estimated weight.

731void BranchProbabilityInfo::propagateEstimatedBlockWeight(

732const LoopBlock &LoopBB,DominatorTree *DT,PostDominatorTree *PDT,

733uint32_t BBWeight,SmallVectorImpl<BasicBlock *> &BlockWorkList,

734SmallVectorImpl<LoopBlock> &LoopWorkList) {

735constBasicBlock *BB = LoopBB.getBlock();

736constauto *DTStartNode = DT->getNode(BB);

737constauto *PDTStartNode = PDT->getNode(BB);

738

739// TODO: Consider propagating weight down the domination line as well.

740for (constauto *DTNode = DTStartNode; DTNode !=nullptr;

741 DTNode = DTNode->getIDom()) {

742auto *DomBB = DTNode->getBlock();

743// Consider blocks which lie on one 'line'.

744if (!PDT->dominates(PDTStartNode, PDT->getNode(DomBB)))

745// If BB doesn't post dominate DomBB it will not post dominate dominators

746// of DomBB as well.

747break;

748

749 LoopBlock DomLoopBB = getLoopBlock(DomBB);

750const LoopEdge Edge{DomLoopBB, LoopBB};

751// Don't propagate weight to blocks belonging to different loops.

752if (!isLoopEnteringExitingEdge(Edge)) {

753if (!updateEstimatedBlockWeight(DomLoopBB, BBWeight, BlockWorkList,

754 LoopWorkList))

755// If DomBB has weight set then all it's predecessors are already

756// processed (since we propagate weight up to the top of IR each time).

757break;

758 }elseif (isLoopExitingEdge(Edge)) {

759 LoopWorkList.push_back(DomLoopBB);

760 }

761 }

762}

763

764std::optional<uint32_t>

765BranchProbabilityInfo::getInitialEstimatedBlockWeight(constBasicBlock *BB) {

766// Returns true if \p BB has call marked with "NoReturn" attribute.

767auto hasNoReturn = [&](constBasicBlock *BB) {

768for (constauto &I :reverse(*BB))

769if (constCallInst *CI = dyn_cast<CallInst>(&I))

770if (CI->hasFnAttr(Attribute::NoReturn))

771returntrue;

772

773returnfalse;

774 };

775

776// Important note regarding the order of checks. They are ordered by weight

777// from lowest to highest. Doing that allows to avoid "unstable" results

778// when several conditions heuristics can be applied simultaneously.

779if (isa<UnreachableInst>(BB->getTerminator()) ||

780// If this block is terminated by a call to

781// @llvm.experimental.deoptimize then treat it like an unreachable

782// since it is expected to practically never execute.

783// TODO: Should we actually treat as never returning call?

784 BB->getTerminatingDeoptimizeCall())

785return hasNoReturn(BB)

786 ?static_cast<uint32_t>(BlockExecWeight::NORETURN)

787 :static_cast<uint32_t>(BlockExecWeight::UNREACHABLE);

788

789// Check if the block is an exception handling block.

790if (BB->isEHPad())

791returnstatic_cast<uint32_t>(BlockExecWeight::UNWIND);

792

793// Check if the block contains 'cold' call.

794for (constauto &I : *BB)

795if (constCallInst *CI = dyn_cast<CallInst>(&I))

796if (CI->hasFnAttr(Attribute::Cold))

797returnstatic_cast<uint32_t>(BlockExecWeight::COLD);

798

799return std::nullopt;

800}

801

802// Does RPO traversal over all blocks in \p F and assigns weights to

803// 'unreachable', 'noreturn', 'cold', 'unwind' blocks. In addition it does its

804// best to propagate the weight to up/down the IR.

805void BranchProbabilityInfo::computeEestimateBlockWeight(

806constFunction &F,DominatorTree *DT,PostDominatorTree *PDT) {

807SmallVector<BasicBlock *, 8> BlockWorkList;

808SmallVector<LoopBlock, 8> LoopWorkList;

809SmallDenseMap<LoopData, SmallVector<BasicBlock *, 4>> LoopExitBlocks;

810

811// By doing RPO we make sure that all predecessors already have weights

812// calculated before visiting theirs successors.

813ReversePostOrderTraversal<const Function *> RPOT(&F);

814for (constauto *BB : RPOT)

815if (auto BBWeight = getInitialEstimatedBlockWeight(BB))

816// If we were able to find estimated weight for the block set it to this

817// block and propagate up the IR.

818 propagateEstimatedBlockWeight(getLoopBlock(BB), DT, PDT, *BBWeight,

819 BlockWorkList, LoopWorkList);

820

821// BlockWorklist/LoopWorkList contains blocks/loops with at least one

822// successor/exit having estimated weight. Try to propagate weight to such

823// blocks/loops from successors/exits.

824// Process loops and blocks. Order is not important.

825do {

826while (!LoopWorkList.empty()) {

827const LoopBlock LoopBB = LoopWorkList.pop_back_val();

828const LoopDataLD = LoopBB.getLoopData();

829if (EstimatedLoopWeight.count(LD))

830continue;

831

832auto Res = LoopExitBlocks.try_emplace(LD);

833SmallVectorImpl<BasicBlock *> &Exits = Res.first->second;

834if (Res.second)

835 getLoopExitBlocks(LoopBB, Exits);

836auto LoopWeight = getMaxEstimatedEdgeWeight(

837 LoopBB,make_range(Exits.begin(), Exits.end()));

838

839if (LoopWeight) {

840// If we never exit the loop then we can enter it once at maximum.

841if (LoopWeight <=static_cast<uint32_t>(BlockExecWeight::UNREACHABLE))

842 LoopWeight =static_cast<uint32_t>(BlockExecWeight::LOWEST_NON_ZERO);

843

844 EstimatedLoopWeight.insert({LD, *LoopWeight});

845// Add all blocks entering the loop into working list.

846 getLoopEnterBlocks(LoopBB, BlockWorkList);

847 }

848 }

849

850while (!BlockWorkList.empty()) {

851// We can reach here only if BlockWorkList is not empty.

852constBasicBlock *BB = BlockWorkList.pop_back_val();

853if (EstimatedBlockWeight.count(BB))

854continue;

855

856// We take maximum over all weights of successors. In other words we take

857// weight of "hot" path. In theory we can probably find a better function

858// which gives higher accuracy results (comparing to "maximum") but I

859// can't

860// think of any right now. And I doubt it will make any difference in

861// practice.

862const LoopBlock LoopBB = getLoopBlock(BB);

863auto MaxWeight = getMaxEstimatedEdgeWeight(LoopBB,successors(BB));

864

865if (MaxWeight)

866 propagateEstimatedBlockWeight(LoopBB, DT, PDT, *MaxWeight,

867 BlockWorkList, LoopWorkList);

868 }

869 }while (!BlockWorkList.empty() || !LoopWorkList.empty());

870}

871

872// Calculate edge probabilities based on block's estimated weight.

873// Note that gathered weights were not scaled for loops. Thus edges entering

874// and exiting loops requires special processing.

875bool BranchProbabilityInfo::calcEstimatedHeuristics(constBasicBlock *BB) {

876assert(BB->getTerminator()->getNumSuccessors() > 1 &&

877"expected more than one successor!");

878

879const LoopBlock LoopBB = getLoopBlock(BB);

880

881SmallPtrSet<const BasicBlock *, 8> UnlikelyBlocks;

882uint32_t TC =LBH_TAKEN_WEIGHT /LBH_NONTAKEN_WEIGHT;

883if (LoopBB.getLoop())

884computeUnlikelySuccessors(BB, LoopBB.getLoop(), UnlikelyBlocks);

885

886// Changed to 'true' if at least one successor has estimated weight.

887bool FoundEstimatedWeight =false;

888SmallVector<uint32_t, 4> SuccWeights;

889uint64_t TotalWeight = 0;

890// Go over all successors of BB and put their weights into SuccWeights.

891for (constBasicBlock *SuccBB :successors(BB)) {

892 std::optional<uint32_t> Weight;

893const LoopBlock SuccLoopBB = getLoopBlock(SuccBB);

894const LoopEdge Edge{LoopBB, SuccLoopBB};

895

896 Weight = getEstimatedEdgeWeight(Edge);

897

898if (isLoopExitingEdge(Edge) &&

899// Avoid adjustment of ZERO weight since it should remain unchanged.

900 Weight !=static_cast<uint32_t>(BlockExecWeight::ZERO)) {

901// Scale down loop exiting weight by trip count.

902 Weight = std::max(

903static_cast<uint32_t>(BlockExecWeight::LOWEST_NON_ZERO),

904 Weight.value_or(static_cast<uint32_t>(BlockExecWeight::DEFAULT)) /

905 TC);

906 }

907bool IsUnlikelyEdge = LoopBB.getLoop() && UnlikelyBlocks.contains(SuccBB);

908if (IsUnlikelyEdge &&

909// Avoid adjustment of ZERO weight since it should remain unchanged.

910 Weight !=static_cast<uint32_t>(BlockExecWeight::ZERO)) {

911// 'Unlikely' blocks have twice lower weight.

912 Weight = std::max(

913static_cast<uint32_t>(BlockExecWeight::LOWEST_NON_ZERO),

914 Weight.value_or(static_cast<uint32_t>(BlockExecWeight::DEFAULT)) / 2);

915 }

916

917if (Weight)

918 FoundEstimatedWeight =true;

919

920auto WeightVal =

921 Weight.value_or(static_cast<uint32_t>(BlockExecWeight::DEFAULT));

922 TotalWeight += WeightVal;

923 SuccWeights.push_back(WeightVal);

924 }

925

926// If non of blocks have estimated weight bail out.

927// If TotalWeight is 0 that means weight of each successor is 0 as well and

928// equally likely. Bail out early to not deal with devision by zero.

929if (!FoundEstimatedWeight || TotalWeight == 0)

930returnfalse;

931

932assert(SuccWeights.size() ==succ_size(BB) &&"Missed successor?");

933constunsigned SuccCount = SuccWeights.size();

934

935// If the sum of weights does not fit in 32 bits, scale every weight down

936// accordingly.

937if (TotalWeight > UINT32_MAX) {

938uint64_t ScalingFactor = TotalWeight / UINT32_MAX + 1;

939 TotalWeight = 0;

940for (unsignedIdx = 0;Idx < SuccCount; ++Idx) {

941 SuccWeights[Idx] /= ScalingFactor;

942if (SuccWeights[Idx] ==static_cast<uint32_t>(BlockExecWeight::ZERO))

943 SuccWeights[Idx] =

944static_cast<uint32_t>(BlockExecWeight::LOWEST_NON_ZERO);

945 TotalWeight += SuccWeights[Idx];

946 }

947assert(TotalWeight <= UINT32_MAX &&"Total weight overflows");

948 }

949

950// Finally set probabilities to edges according to estimated block weights.

951SmallVector<BranchProbability, 4> EdgeProbabilities(

952 SuccCount,BranchProbability::getUnknown());

953

954for (unsignedIdx = 0;Idx < SuccCount; ++Idx) {

955 EdgeProbabilities[Idx] =

956BranchProbability(SuccWeights[Idx], (uint32_t)TotalWeight);

957 }

958setEdgeProbability(BB, EdgeProbabilities);

959returntrue;

960}

961

962bool BranchProbabilityInfo::calcZeroHeuristics(constBasicBlock *BB,

963constTargetLibraryInfo *TLI) {

964constBranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());

965if (!BI || !BI->isConditional())

966returnfalse;

967

968Value *Cond = BI->getCondition();

969ICmpInst *CI = dyn_cast<ICmpInst>(Cond);

970if (!CI)

971returnfalse;

972

973auto GetConstantInt = [](Value *V) {

974if (auto *I = dyn_cast<BitCastInst>(V))

975return dyn_cast<ConstantInt>(I->getOperand(0));

976return dyn_cast<ConstantInt>(V);

977 };

978

979Value *RHS = CI->getOperand(1);

980ConstantInt *CV = GetConstantInt(RHS);

981if (!CV)

982returnfalse;

983

984// If the LHS is the result of AND'ing a value with a single bit bitmask,

985// we don't have information about probabilities.

986if (Instruction *LHS = dyn_cast<Instruction>(CI->getOperand(0)))

987if (LHS->getOpcode() == Instruction::And)

988if (ConstantInt *AndRHS = GetConstantInt(LHS->getOperand(1)))

989if (AndRHS->getValue().isPowerOf2())

990returnfalse;

991

992// Check if the LHS is the return value of a library function

993LibFunc Func =NumLibFuncs;

994if (TLI)

995if (CallInst *Call = dyn_cast<CallInst>(CI->getOperand(0)))

996if (Function *CalledFn =Call->getCalledFunction())

997 TLI->getLibFunc(*CalledFn, Func);

998

999 ProbabilityTable::const_iterator Search;

1000if (Func == LibFunc_strcasecmp ||

1001 Func == LibFunc_strcmp ||

1002 Func == LibFunc_strncasecmp ||

1003 Func == LibFunc_strncmp ||

1004 Func == LibFunc_memcmp ||

1005 Func == LibFunc_bcmp) {

1006 Search =ICmpWithLibCallTable.find(CI->getPredicate());

1007if (Search ==ICmpWithLibCallTable.end())

1008returnfalse;

1009 }elseif (CV->isZero()) {

1010 Search =ICmpWithZeroTable.find(CI->getPredicate());

1011if (Search ==ICmpWithZeroTable.end())

1012returnfalse;

1013 }elseif (CV->isOne()) {

1014 Search =ICmpWithOneTable.find(CI->getPredicate());

1015if (Search ==ICmpWithOneTable.end())

1016returnfalse;

1017 }elseif (CV->isMinusOne()) {

1018 Search =ICmpWithMinusOneTable.find(CI->getPredicate());

1019if (Search ==ICmpWithMinusOneTable.end())

1020returnfalse;

1021 }else {

1022returnfalse;

1023 }

1024

1025setEdgeProbability(BB, Search->second);

1026returntrue;

1027}

1028

1029bool BranchProbabilityInfo::calcFloatingPointHeuristics(constBasicBlock *BB) {

1030constBranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());

1031if (!BI || !BI->isConditional())

1032returnfalse;

1033

1034Value *Cond = BI->getCondition();

1035FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond);

1036if (!FCmp)

1037returnfalse;

1038

1039ProbabilityList ProbList;

1040if (FCmp->isEquality()) {

1041 ProbList = !FCmp->isTrueWhenEqual() ?

1042// f1 == f2 -> Unlikely

1043ProbabilityList({FPTakenProb,FPUntakenProb}) :

1044// f1 != f2 -> Likely

1045ProbabilityList({FPUntakenProb,FPTakenProb});

1046 }else {

1047auto Search =FCmpTable.find(FCmp->getPredicate());

1048if (Search ==FCmpTable.end())

1049returnfalse;

1050 ProbList = Search->second;

1051 }

1052

1053setEdgeProbability(BB, ProbList);

1054returntrue;

1055}

1056

1057voidBranchProbabilityInfo::releaseMemory() {

1058 Probs.clear();

1059 Handles.clear();

1060}

1061

1062boolBranchProbabilityInfo::invalidate(Function &,constPreservedAnalyses &PA,

1063FunctionAnalysisManager::Invalidator &) {

1064// Check whether the analysis, all analyses on functions, or the function's

1065// CFG have been preserved.

1066auto PAC = PA.getChecker<BranchProbabilityAnalysis>();

1067return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||

1068 PAC.preservedSet<CFGAnalyses>());

1069}

1070

1071voidBranchProbabilityInfo::print(raw_ostream &OS) const{

1072OS <<"---- Branch Probabilities ----\n";

1073// We print the probabilities from the last function the analysis ran over,

1074// or the function it is currently running over.

1075assert(LastF &&"Cannot print prior to running over a function");

1076for (constauto &BI : *LastF) {

1077for (constBasicBlock *Succ :successors(&BI))

1078printEdgeProbability(OS <<" ", &BI, Succ);

1079 }

1080}

1081

1082boolBranchProbabilityInfo::

1083isEdgeHot(constBasicBlock *Src,constBasicBlock *Dst) const{

1084// Hot probability is at least 4/5 = 80%

1085// FIXME: Compare against a static "hot" BranchProbability.

1086returngetEdgeProbability(Src, Dst) >BranchProbability(4, 5);

1087}

1088

1089/// Get the raw edge probability for the edge. If can't find it, return a

1090/// default probability 1/N where N is the number of successors. Here an edge is

1091/// specified using PredBlock and an

1092/// index to the successors.

1093BranchProbability

1094BranchProbabilityInfo::getEdgeProbability(constBasicBlock *Src,

1095unsigned IndexInSuccessors) const{

1096autoI = Probs.find(std::make_pair(Src, IndexInSuccessors));

1097assert((Probs.end() == Probs.find(std::make_pair(Src, 0))) ==

1098 (Probs.end() ==I) &&

1099"Probability for I-th successor must always be defined along with the "

1100"probability for the first successor");

1101

1102if (I != Probs.end())

1103returnI->second;

1104

1105return {1,static_cast<uint32_t>(succ_size(Src))};

1106}

1107

1108BranchProbability

1109BranchProbabilityInfo::getEdgeProbability(constBasicBlock *Src,

1110const_succ_iterator Dst) const{

1111returngetEdgeProbability(Src, Dst.getSuccessorIndex());

1112}

1113

1114/// Get the raw edge probability calculated for the block pair. This returns the

1115/// sum of all raw edge probabilities from Src to Dst.

1116BranchProbability

1117BranchProbabilityInfo::getEdgeProbability(constBasicBlock *Src,

1118constBasicBlock *Dst) const{

1119if (!Probs.count(std::make_pair(Src, 0)))

1120returnBranchProbability(llvm::count(successors(Src), Dst),succ_size(Src));

1121

1122auto Prob =BranchProbability::getZero();

1123for (const_succ_iterator I =succ_begin(Src), E =succ_end(Src);I != E; ++I)

1124if (*I == Dst)

1125 Prob += Probs.find(std::make_pair(Src,I.getSuccessorIndex()))->second;

1126

1127return Prob;

1128}

1129

1130/// Set the edge probability for all edges at once.

1131voidBranchProbabilityInfo::setEdgeProbability(

1132constBasicBlock *Src,constSmallVectorImpl<BranchProbability> &Probs) {

1133assert(Src->getTerminator()->getNumSuccessors() == Probs.size());

1134eraseBlock(Src);// Erase stale data if any.

1135if (Probs.size() == 0)

1136return;// Nothing to set.

1137

1138 Handles.insert(BasicBlockCallbackVH(Src,this));

1139uint64_t TotalNumerator = 0;

1140for (unsigned SuccIdx = 0; SuccIdx < Probs.size(); ++SuccIdx) {

1141 this->Probs[std::make_pair(Src, SuccIdx)] = Probs[SuccIdx];

1142LLVM_DEBUG(dbgs() <<"set edge " << Src->getName() <<" -> " << SuccIdx

1143 <<" successor probability to " << Probs[SuccIdx]

1144 <<"\n");

1145 TotalNumerator += Probs[SuccIdx].getNumerator();

1146 }

1147

1148// Because of rounding errors the total probability cannot be checked to be

1149// 1.0 exactly. That is TotalNumerator == BranchProbability::getDenominator.

1150// Instead, every single probability in Probs must be as accurate as possible.

1151// This results in error 1/denominator at most, thus the total absolute error

1152// should be within Probs.size / BranchProbability::getDenominator.

1153assert(TotalNumerator <=BranchProbability::getDenominator() + Probs.size());

1154assert(TotalNumerator >=BranchProbability::getDenominator() - Probs.size());

1155 (void)TotalNumerator;

1156}

1157

1158voidBranchProbabilityInfo::copyEdgeProbabilities(BasicBlock *Src,

1159BasicBlock *Dst) {

1160eraseBlock(Dst);// Erase stale data if any.

1161unsigned NumSuccessors = Src->getTerminator()->getNumSuccessors();

1162assert(NumSuccessors == Dst->getTerminator()->getNumSuccessors());

1163if (NumSuccessors == 0)

1164return;// Nothing to set.

1165if (!this->Probs.contains(std::make_pair(Src, 0)))

1166return;// No probability is set for edges from Src. Keep the same for Dst.

1167

1168 Handles.insert(BasicBlockCallbackVH(Dst,this));

1169for (unsigned SuccIdx = 0; SuccIdx < NumSuccessors; ++SuccIdx) {

1170auto Prob = this->Probs[std::make_pair(Src, SuccIdx)];

1171 this->Probs[std::make_pair(Dst, SuccIdx)] = Prob;

1172LLVM_DEBUG(dbgs() <<"set edge " << Dst->getName() <<" -> " << SuccIdx

1173 <<" successor probability to " << Prob <<"\n");

1174 }

1175}

1176

1177voidBranchProbabilityInfo::swapSuccEdgesProbabilities(constBasicBlock *Src) {

1178assert(Src->getTerminator()->getNumSuccessors() == 2);

1179auto It0 = Probs.find(std::make_pair(Src, 0));

1180if (It0 == Probs.end())

1181return;// No probability is set for edges from Src

1182auto It1 = Probs.find(std::make_pair(Src, 1));

1183assert(It1 != Probs.end());

1184std::swap(It0->second, It1->second);

1185}

1186

1187raw_ostream &

1188BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS,

1189constBasicBlock *Src,

1190constBasicBlock *Dst) const{

1191constBranchProbability Prob =getEdgeProbability(Src, Dst);

1192OS <<"edge ";

1193 Src->printAsOperand(OS,false, Src->getModule());

1194OS <<" -> ";

1195 Dst->printAsOperand(OS,false, Dst->getModule());

1196OS <<" probability is " << Prob

1197 << (isEdgeHot(Src, Dst) ?" [HOT edge]\n" :"\n");

1198

1199returnOS;

1200}

1201

1202voidBranchProbabilityInfo::eraseBlock(constBasicBlock *BB) {

1203LLVM_DEBUG(dbgs() <<"eraseBlock " << BB->getName() <<"\n");

1204

1205// Note that we cannot use successors of BB because the terminator of BB may

1206// have changed when eraseBlock is called as a BasicBlockCallbackVH callback.

1207// Instead we remove prob data for the block by iterating successors by their

1208// indices from 0 till the last which exists. There could not be prob data for

1209// a pair (BB, N) if there is no data for (BB, N-1) because the data is always

1210// set for all successors from 0 to M at once by the method

1211// setEdgeProbability().

1212 Handles.erase(BasicBlockCallbackVH(BB,this));

1213for (unsignedI = 0;; ++I) {

1214auto MapI = Probs.find(std::make_pair(BB,I));

1215if (MapI == Probs.end()) {

1216assert(Probs.count(std::make_pair(BB,I + 1)) == 0 &&

1217"Must be no more successors");

1218return;

1219 }

1220 Probs.erase(MapI);

1221 }

1222}

1223

1224voidBranchProbabilityInfo::calculate(constFunction &F,constLoopInfo &LoopI,

1225constTargetLibraryInfo *TLI,

1226DominatorTree *DT,

1227PostDominatorTree *PDT) {

1228LLVM_DEBUG(dbgs() <<"---- Branch Probability Info : " <<F.getName()

1229 <<" ----\n\n");

1230 LastF = &F;// Store the last function we ran on for printing.

1231 LI = &LoopI;

1232

1233 SccI = std::make_unique<SccInfo>(F);

1234

1235assert(EstimatedBlockWeight.empty());

1236assert(EstimatedLoopWeight.empty());

1237

1238 std::unique_ptr<DominatorTree> DTPtr;

1239 std::unique_ptr<PostDominatorTree> PDTPtr;

1240

1241if (!DT) {

1242 DTPtr = std::make_unique<DominatorTree>(const_cast<Function &>(F));

1243 DT = DTPtr.get();

1244 }

1245

1246if (!PDT) {

1247 PDTPtr = std::make_unique<PostDominatorTree>(const_cast<Function &>(F));

1248 PDT = PDTPtr.get();

1249 }

1250

1251 computeEestimateBlockWeight(F, DT, PDT);

1252

1253// Walk the basic blocks in post-order so that we can build up state about

1254// the successors of a block iteratively.

1255for (constauto *BB :post_order(&F.getEntryBlock())) {

1256LLVM_DEBUG(dbgs() <<"Computing probabilities for " << BB->getName()

1257 <<"\n");

1258// If there is no at least two successors, no sense to set probability.

1259if (BB->getTerminator()->getNumSuccessors() < 2)

1260continue;

1261if (calcMetadataWeights(BB))

1262continue;

1263if (calcEstimatedHeuristics(BB))

1264continue;

1265if (calcPointerHeuristics(BB))

1266continue;

1267if (calcZeroHeuristics(BB, TLI))

1268continue;

1269if (calcFloatingPointHeuristics(BB))

1270continue;

1271 }

1272

1273 EstimatedLoopWeight.clear();

1274 EstimatedBlockWeight.clear();

1275 SccI.reset();

1276

1277if (PrintBranchProb && (PrintBranchProbFuncName.empty() ||

1278F.getName() ==PrintBranchProbFuncName)) {

1279print(dbgs());

1280 }

1281}

1282

1283voidBranchProbabilityInfoWrapperPass::getAnalysisUsage(

1284AnalysisUsage &AU) const{

1285// We require DT so it's available when LI is available. The LI updating code

1286// asserts that DT is also present so if we don't make sure that we have DT

1287// here, that assert will trigger.

1288 AU.addRequired<DominatorTreeWrapperPass>();

1289 AU.addRequired<LoopInfoWrapperPass>();

1290 AU.addRequired<TargetLibraryInfoWrapperPass>();

1291 AU.addRequired<DominatorTreeWrapperPass>();

1292 AU.addRequired<PostDominatorTreeWrapperPass>();

1293 AU.setPreservesAll();

1294}

1295

1296boolBranchProbabilityInfoWrapperPass::runOnFunction(Function &F) {

1297constLoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();

1298constTargetLibraryInfo &TLI =

1299 getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);

1300DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();

1301PostDominatorTree &PDT =

1302 getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();

1303 BPI.calculate(F, LI, &TLI, &DT, &PDT);

1304returnfalse;

1305}

1306

1307voidBranchProbabilityInfoWrapperPass::releaseMemory() { BPI.releaseMemory(); }

1308

1309voidBranchProbabilityInfoWrapperPass::print(raw_ostream &OS,

1310constModule *) const{

1311 BPI.print(OS);

1312}

1313

1314AnalysisKey BranchProbabilityAnalysis::Key;

1315BranchProbabilityInfo

1316BranchProbabilityAnalysis::run(Function &F,FunctionAnalysisManager &AM) {

1317auto &LI = AM.getResult<LoopAnalysis>(F);

1318auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);

1319auto &DT = AM.getResult<DominatorTreeAnalysis>(F);

1320auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);

1321BranchProbabilityInfo BPI;

1322 BPI.calculate(F, LI, &TLI, &DT, &PDT);

1323return BPI;

1324}

1325

1326PreservedAnalyses

1327BranchProbabilityPrinterPass::run(Function &F,FunctionAnalysisManager &AM) {

1328OS <<"Printing analysis 'Branch Probability Analysis' for function '"

1329 <<F.getName() <<"':\n";

1330 AM.getResult<BranchProbabilityAnalysis>(F).print(OS);

1331returnPreservedAnalyses::all();

1332}

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

Definition:ARMSLSHardening.cpp:73

Attributes.h

This file contains the simple types necessary to represent the attributes associated with functions a...

true

basic Basic Alias true

Definition:BasicAliasAnalysis.cpp:1981

BlockExecWeight

Set of dedicated "absolute" execution weights for a block.

Definition:BranchProbabilityInfo.cpp:197

BlockExecWeight::NORETURN

@ NORETURN

Weight to a block containing non returning call.

BlockExecWeight::UNWIND

@ UNWIND

Weight to 'unwind' block of an invoke instruction.

BlockExecWeight::COLD

@ COLD

Weight to a 'cold' block.

BlockExecWeight::ZERO

@ ZERO

Special weight used for cases with exact zero probability.

BlockExecWeight::UNREACHABLE

@ UNREACHABLE

Weight to an 'unreachable' block.

BlockExecWeight::DEFAULT

@ DEFAULT

Default weight is used in cases when there is no dedicated execution weight set.

BlockExecWeight::LOWEST_NON_ZERO

@ LOWEST_NON_ZERO

Minimal possible non zero weight.

FPH_TAKEN_WEIGHT

static const uint32_t FPH_TAKEN_WEIGHT

Definition:BranchProbabilityInfo.cpp:170

FPUntakenProb

static const BranchProbability FPUntakenProb(FPH_NONTAKEN_WEIGHT, FPH_TAKEN_WEIGHT+FPH_NONTAKEN_WEIGHT)

ZeroUntakenProb

static const BranchProbability ZeroUntakenProb(ZH_NONTAKEN_WEIGHT, ZH_TAKEN_WEIGHT+ZH_NONTAKEN_WEIGHT)

LBH_TAKEN_WEIGHT

static const uint32_t LBH_TAKEN_WEIGHT

Definition:BranchProbabilityInfo.cpp:99

ZH_NONTAKEN_WEIGHT

static const uint32_t ZH_NONTAKEN_WEIGHT

Definition:BranchProbabilityInfo.cpp:129

ICmpWithLibCallTable

static const ProbabilityTable ICmpWithLibCallTable

strcmp and similar functions return zero, negative, or positive, if the first string is equal,...

Definition:BranchProbabilityInfo.cpp:164

ICmpWithMinusOneTable

static const ProbabilityTable ICmpWithMinusOneTable

Integer compares with -1:

Definition:BranchProbabilityInfo.cpp:144

prob

branch prob

Definition:BranchProbabilityInfo.cpp:68

FPOrdTakenProb

static const BranchProbability FPOrdTakenProb(FPH_ORD_WEIGHT, FPH_ORD_WEIGHT+FPH_UNO_WEIGHT)

ICmpWithZeroTable

static const ProbabilityTable ICmpWithZeroTable

Integer compares with 0:

Definition:BranchProbabilityInfo.cpp:136

PH_NONTAKEN_WEIGHT

static const uint32_t PH_NONTAKEN_WEIGHT

Definition:BranchProbabilityInfo.cpp:112

ProbabilityTable

std::map< CmpInst::Predicate, ProbabilityList > ProbabilityTable

Definition:BranchProbabilityInfo.cpp:119

PtrTakenProb

static const BranchProbability PtrTakenProb(PH_TAKEN_WEIGHT, PH_TAKEN_WEIGHT+PH_NONTAKEN_WEIGHT)

ZeroTakenProb

static const BranchProbability ZeroTakenProb(ZH_TAKEN_WEIGHT, ZH_TAKEN_WEIGHT+ZH_NONTAKEN_WEIGHT)

FPOrdUntakenProb

static const BranchProbability FPOrdUntakenProb(FPH_UNO_WEIGHT, FPH_ORD_WEIGHT+FPH_UNO_WEIGHT)

PH_TAKEN_WEIGHT

static const uint32_t PH_TAKEN_WEIGHT

Heuristics and lookup tables for non-loop branches: Pointer Heuristics (PH)

Definition:BranchProbabilityInfo.cpp:111

FPTakenProb

static const BranchProbability FPTakenProb(FPH_TAKEN_WEIGHT, FPH_TAKEN_WEIGHT+FPH_NONTAKEN_WEIGHT)

Analysis

branch Branch Probability Analysis

Definition:BranchProbabilityInfo.cpp:69

PtrUntakenProb

static const BranchProbability PtrUntakenProb(PH_NONTAKEN_WEIGHT, PH_TAKEN_WEIGHT+PH_NONTAKEN_WEIGHT)

ProbabilityList

SmallVector< BranchProbability > ProbabilityList

Definition:BranchProbabilityInfo.cpp:118

ICmpWithOneTable

static const ProbabilityTable ICmpWithOneTable

Integer compares with 1:

Definition:BranchProbabilityInfo.cpp:152

ZH_TAKEN_WEIGHT

static const uint32_t ZH_TAKEN_WEIGHT

Zero Heuristics (ZH)

Definition:BranchProbabilityInfo.cpp:128

FPH_NONTAKEN_WEIGHT

static const uint32_t FPH_NONTAKEN_WEIGHT

Definition:BranchProbabilityInfo.cpp:171

UR_TAKEN_PROB

static const BranchProbability UR_TAKEN_PROB

Unreachable-terminating branch taken probability.

Definition:BranchProbabilityInfo.cpp:107

FCmpTable

static const ProbabilityTable FCmpTable

Floating-Point compares:

Definition:BranchProbabilityInfo.cpp:190

LBH_NONTAKEN_WEIGHT

static const uint32_t LBH_NONTAKEN_WEIGHT

Definition:BranchProbabilityInfo.cpp:100

PointerTable

static const ProbabilityTable PointerTable

Pointer comparisons:

Definition:BranchProbabilityInfo.cpp:122

FPH_ORD_WEIGHT

static const uint32_t FPH_ORD_WEIGHT

This is the probability for an ordered floating point comparison.

Definition:BranchProbabilityInfo.cpp:174

computeUnlikelySuccessors

static void computeUnlikelySuccessors(const BasicBlock *BB, Loop *L, SmallPtrSetImpl< const BasicBlock * > &UnlikelyBlocks)

Definition:BranchProbabilityInfo.cpp:542

FPH_UNO_WEIGHT

static const uint32_t FPH_UNO_WEIGHT

This is the probability for an unordered floating point comparison, it means one or two of the operan...

Definition:BranchProbabilityInfo.cpp:178

PrintBranchProbFuncName

cl::opt< std::string > PrintBranchProbFuncName("print-bpi-func-name", cl::Hidden, cl::desc("The option to specify the name of the function " "whose branch probability info is printed."))

PrintBranchProb

static cl::opt< bool > PrintBranchProb("print-bpi", cl::init(false), cl::Hidden, cl::desc("Print the branch probability info."))

BranchProbabilityInfo.h

BranchProbability.h

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

This file contains the declarations for the subclasses of Constant, which represent the different fla...

Idx

Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx

Definition:DeadArgumentElimination.cpp:353

Debug.h

LLVM_DEBUG

#define LLVM_DEBUG(...)

Definition:Debug.h:106

Dominators.h

BasicBlock.h

CFG.h

This file provides various utilities for inspecting and working with the control flow graph in LLVM I...

Function.h

Instruction.h

PassManager.h

This header defines various interfaces for pass management in LLVM.

#define F(x, y, z)

Definition:MD5.cpp:55

#define I(x, y, z)

Definition:MD5.cpp:58

Metadata.h

This file contains the declarations for metadata subclasses.

#define P(N)

INITIALIZE_PASS_DEPENDENCY

#define INITIALIZE_PASS_DEPENDENCY(depName)

Definition:PassSupport.h:55

INITIALIZE_PASS_END

#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)

Definition:PassSupport.h:57

INITIALIZE_PASS_BEGIN

#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)

Definition:PassSupport.h:52

Pass.h

PostDominators.h

PostOrderIterator.h

This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.

ProfDataUtils.h

This file contains the declarations for profiling metadata utility functions.

Cond

const SmallVectorImpl< MachineOperand > & Cond

Definition:RISCVRedundantCopyElimination.cpp:75

SCCIterator.h

This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected components (SCCs) of a ...

assert

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

STLExtras.h

This file contains some templates that are useful if you are working with the STL at all.

raw_pwrite_stream & OS

Definition:SampleProfWriter.cpp:51

SmallVector.h

This file defines the SmallVector class.

TargetLibraryInfo.h

RHS

Value * RHS

Definition:X86PartialReduction.cpp:74

LHS

Value * LHS

Definition:X86PartialReduction.cpp:73

llvm::AllAnalysesOn

This templated class represents "all analyses that operate over <a particular IR unit>" (e....

Definition:Analysis.h:49

llvm::AnalysisManager::Invalidator

API to communicate dependencies between analyses during invalidation.

Definition:PassManager.h:292

llvm::AnalysisManager

A container for analyses that lazily runs them and caches their results.

Definition:PassManager.h:253

llvm::AnalysisManager::getResult

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

Definition:PassManager.h:410

llvm::AnalysisUsage

Represent the analysis usage information of a pass.

Definition:PassAnalysisSupport.h:47

llvm::AnalysisUsage::addRequired

AnalysisUsage & addRequired()

Definition:PassAnalysisSupport.h:75

llvm::AnalysisUsage::setPreservesAll

void setPreservesAll()

Set by analyses that do not transform their input at all.

Definition:PassAnalysisSupport.h:130

llvm::BasicBlock

LLVM Basic Block Representation.

Definition:BasicBlock.h:61

llvm::BasicBlock::getTerminatingDeoptimizeCall

const CallInst * getTerminatingDeoptimizeCall() const

Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...

Definition:BasicBlock.cpp:331

llvm::BasicBlock::getDataLayout

const DataLayout & getDataLayout() const

Get the data layout of the module this basic block belongs to.

Definition:BasicBlock.cpp:296

llvm::BasicBlock::isEHPad

bool isEHPad() const

Return true if this basic block is an exception handling block.

Definition:BasicBlock.h:678

llvm::BasicBlock::getTerminator

const Instruction * getTerminator() const LLVM_READONLY

Returns the terminator instruction if the block is well formed or null if the block is not well forme...

Definition:BasicBlock.h:240

llvm::BranchInst

Conditional or Unconditional Branch instruction.

Definition:Instructions.h:3016

llvm::BranchInst::isConditional

bool isConditional() const

Definition:Instructions.h:3090

llvm::BranchInst::getSuccessor

BasicBlock * getSuccessor(unsigned i) const

Definition:Instructions.h:3104

llvm::BranchInst::getCondition

Value * getCondition() const

Definition:Instructions.h:3092

llvm::BranchProbabilityAnalysis

Analysis pass which computes BranchProbabilityInfo.

Definition:BranchProbabilityInfo.h:425

llvm::BranchProbabilityAnalysis::run

BranchProbabilityInfo run(Function &F, FunctionAnalysisManager &AM)

Run the analysis pass over a function and produce BPI.

Definition:BranchProbabilityInfo.cpp:1316

llvm::BranchProbabilityInfoWrapperPass

Legacy analysis pass which computes BranchProbabilityInfo.

Definition:BranchProbabilityInfo.h:452

llvm::BranchProbabilityInfoWrapperPass::releaseMemory

void releaseMemory() override

releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...

Definition:BranchProbabilityInfo.cpp:1307

llvm::BranchProbabilityInfoWrapperPass::getAnalysisUsage

void getAnalysisUsage(AnalysisUsage &AU) const override

getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...

Definition:BranchProbabilityInfo.cpp:1283

llvm::BranchProbabilityInfoWrapperPass::ID

static char ID

Definition:BranchProbabilityInfo.h:456

llvm::BranchProbabilityInfoWrapperPass::runOnFunction

bool runOnFunction(Function &F) override

runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.

Definition:BranchProbabilityInfo.cpp:1296

llvm::BranchProbabilityInfoWrapperPass::print

void print(raw_ostream &OS, const Module *M=nullptr) const override

print - Print out the internal state of the pass.

Definition:BranchProbabilityInfo.cpp:1309

llvm::BranchProbabilityInfo::SccInfo::getSccEnterBlocks

void getSccEnterBlocks(int SccNum, SmallVectorImpl< BasicBlock * > &Enters) const

Fills in Enters vector with all such blocks that don't belong to SCC with SccNum ID but there is an e...

Definition:BranchProbabilityInfo.cpp:246

llvm::BranchProbabilityInfo::SccInfo::SccInfo

SccInfo(const Function &F)

Definition:BranchProbabilityInfo.cpp:216

llvm::BranchProbabilityInfo::SccInfo::getSccExitBlocks

void getSccExitBlocks(int SccNum, SmallVectorImpl< BasicBlock * > &Exits) const

Fills in Exits vector with all such blocks that don't belong to SCC with SccNum ID but there is an ed...

Definition:BranchProbabilityInfo.cpp:258

llvm::BranchProbabilityInfo::SccInfo::getSCCNum

int getSCCNum(const BasicBlock *BB) const

If BB belongs to some SCC then ID of that SCC is returned, otherwise -1 is returned.

Definition:BranchProbabilityInfo.cpp:239

llvm::BranchProbabilityInfo

Analysis providing branch probability information.

Definition:BranchProbabilityInfo.h:112

llvm::BranchProbabilityInfo::eraseBlock

void eraseBlock(const BasicBlock *BB)

Forget analysis results for the given basic block.

Definition:BranchProbabilityInfo.cpp:1202

llvm::BranchProbabilityInfo::setEdgeProbability

void setEdgeProbability(const BasicBlock *Src, const SmallVectorImpl< BranchProbability > &Probs)

Set the raw probabilities for all edges from the given block.

Definition:BranchProbabilityInfo.cpp:1131

llvm::BranchProbabilityInfo::invalidate

bool invalidate(Function &, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)

Definition:BranchProbabilityInfo.cpp:1062

llvm::BranchProbabilityInfo::getEdgeProbability

BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const

Get an edge's probability, relative to other out-edges of the Src.

Definition:BranchProbabilityInfo.cpp:1094

llvm::BranchProbabilityInfo::calculate

void calculate(const Function &F, const LoopInfo &LI, const TargetLibraryInfo *TLI, DominatorTree *DT, PostDominatorTree *PDT)

Definition:BranchProbabilityInfo.cpp:1224

llvm::BranchProbabilityInfo::releaseMemory

void releaseMemory()

Definition:BranchProbabilityInfo.cpp:1057

llvm::BranchProbabilityInfo::isEdgeHot

bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const

Test if an edge is hot relative to other out-edges of the Src.

Definition:BranchProbabilityInfo.cpp:1083

llvm::BranchProbabilityInfo::swapSuccEdgesProbabilities

void swapSuccEdgesProbabilities(const BasicBlock *Src)

Swap outgoing edges probabilities for Src with branch terminator.

Definition:BranchProbabilityInfo.cpp:1177

llvm::BranchProbabilityInfo::print

void print(raw_ostream &OS) const

Definition:BranchProbabilityInfo.cpp:1071

llvm::BranchProbabilityInfo::printEdgeProbability

raw_ostream & printEdgeProbability(raw_ostream &OS, const BasicBlock *Src, const BasicBlock *Dst) const

Print an edge's probability.

Definition:BranchProbabilityInfo.cpp:1188

llvm::BranchProbabilityInfo::copyEdgeProbabilities

void copyEdgeProbabilities(BasicBlock *Src, BasicBlock *Dst)

Copy outgoing edge probabilities from Src to Dst.

Definition:BranchProbabilityInfo.cpp:1158

llvm::BranchProbabilityPrinterPass::run

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Definition:BranchProbabilityInfo.cpp:1327

llvm::BranchProbability

Definition:BranchProbability.h:30

llvm::BranchProbability::getDenominator

static uint32_t getDenominator()

Definition:BranchProbability.h:66

llvm::BranchProbability::getRaw

static BranchProbability getRaw(uint32_t N)

Definition:BranchProbability.h:54

llvm::BranchProbability::getOne

static BranchProbability getOne()

Definition:BranchProbability.h:50

llvm::BranchProbability::isZero

bool isZero() const

Definition:BranchProbability.h:46

llvm::BranchProbability::getUnknown

static BranchProbability getUnknown()

Definition:BranchProbability.h:51

llvm::BranchProbability::getNumerator

uint32_t getNumerator() const

Definition:BranchProbability.h:65

llvm::BranchProbability::getZero

static BranchProbability getZero()

Definition:BranchProbability.h:49

llvm::CFGAnalyses

Represents analyses that only rely on functions' control flow.

Definition:Analysis.h:72

llvm::CallInst

This class represents a function call, abstracting a target machine's calling convention.

Definition:Instructions.h:1479

llvm::CmpInst

This class is the base class for the comparison instructions.

Definition:InstrTypes.h:661

llvm::CmpInst::ICMP_SLT

@ ICMP_SLT

signed less than

Definition:InstrTypes.h:702

llvm::CmpInst::ICMP_SGT

@ ICMP_SGT

signed greater than

Definition:InstrTypes.h:700

llvm::CmpInst::ICMP_EQ

@ ICMP_EQ

equal

Definition:InstrTypes.h:694

llvm::CmpInst::ICMP_NE

@ ICMP_NE

not equal

Definition:InstrTypes.h:695

llvm::CmpInst::isTrueWhenEqual

bool isTrueWhenEqual() const

This is just a convenience.

Definition:InstrTypes.h:940

llvm::CmpInst::getPredicate

Predicate getPredicate() const

Return the predicate for this instruction.

Definition:InstrTypes.h:763

llvm::ConstantInt

This is the shared class of boolean and integer constants.

Definition:Constants.h:83

llvm::ConstantInt::isMinusOne

bool isMinusOne() const

This function will return true iff every bit in this constant is set to true.

Definition:Constants.h:220

llvm::ConstantInt::isOne

bool isOne() const

This is just a convenience method to make client code smaller for a common case.

Definition:Constants.h:214

llvm::ConstantInt::isZero

bool isZero() const

This is just a convenience method to make client code smaller for a common code.

Definition:Constants.h:208

llvm::Constant

This is an important base class in LLVM.

Definition:Constant.h:42

llvm::DataLayout

A parsed version of the target data layout string in and methods for querying it.

Definition:DataLayout.h:63

llvm::DenseMapBase::find

iterator find(const_arg_type_t< KeyT > Val)

Definition:DenseMap.h:156

llvm::DenseMapBase::try_emplace

std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)

Definition:DenseMap.h:226

llvm::DenseMapBase::empty

bool empty() const

Definition:DenseMap.h:98

llvm::DenseMapBase::count

size_type count(const_arg_type_t< KeyT > Val) const

Return 1 if the specified key is in the map, 0 otherwise.

Definition:DenseMap.h:152

llvm::DenseMapBase::end

iterator end()

Definition:DenseMap.h:84

llvm::DenseMapBase::insert

std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)

Definition:DenseMap.h:211

llvm::DenseMapBase::clear

void clear()

Definition:DenseMap.h:110

llvm::DominatorTreeAnalysis

Analysis pass which computes a DominatorTree.

Definition:Dominators.h:279

llvm::DominatorTreeBase::getNode

DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const

getNode - return the (Post)DominatorTree node for the specified basic block.

Definition:GenericDomTree.h:401

llvm::DominatorTreeWrapperPass

Legacy analysis pass which computes a DominatorTree.

Definition:Dominators.h:317

llvm::DominatorTree

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

Definition:Dominators.h:162

llvm::FCmpInst

This instruction compares its operands according to the predicate given to the constructor.

Definition:Instructions.h:1379

llvm::FCmpInst::isEquality

static bool isEquality(Predicate Pred)

Definition:Instructions.h:1422

llvm::FunctionPass

FunctionPass class - This class is used to implement most global optimizations.

Definition:Pass.h:310

llvm::Function

Definition:Function.h:63

llvm::ICmpInst

This instruction compares its operands according to the predicate given to the constructor.

Definition:Instructions.h:1158

llvm::ICmpInst::isEquality

static bool isEquality(Predicate P)

Return true if this predicate is either EQ or NE.

Definition:Instructions.h:1285

llvm::Instruction

Definition:Instruction.h:68

llvm::Instruction::getNumSuccessors

unsigned getNumSuccessors() const LLVM_READONLY

Return the number of successors that this instruction has.

Definition:Instruction.cpp:1275

llvm::Instruction::getSuccessor

BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY

Return the specified successor. This instruction must be a terminator.

Definition:Instruction.cpp:1287

llvm::LoopAnalysis

Analysis pass that exposes the LoopInfo for a function.

Definition:LoopInfo.h:566

llvm::LoopInfoBase::getLoopFor

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

Definition:GenericLoopInfo.h:606

llvm::LoopInfoWrapperPass

The legacy pass manager's analysis pass to compute loop information.

Definition:LoopInfo.h:593

llvm::LoopInfo

Definition:LoopInfo.h:407

llvm::Loop

Represents a single loop in the control flow graph.

Definition:LoopInfo.h:39

llvm::MDNode

Metadata node.

Definition:Metadata.h:1073

llvm::Module

A Module instance is used to store all the information related to an LLVM module.

Definition:Module.h:65

llvm::PHINode

Definition:Instructions.h:2600

llvm::PassRegistry::getPassRegistry

static PassRegistry * getPassRegistry()

getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...

Definition:PassRegistry.cpp:24

llvm::PostDominatorTreeAnalysis

Analysis pass which computes a PostDominatorTree.

Definition:PostDominators.h:48

llvm::PostDominatorTree

PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...

Definition:PostDominators.h:28

llvm::PostDominatorTree::dominates

bool dominates(const Instruction *I1, const Instruction *I2) const

Return true if I1 dominates I2.

Definition:PostDominators.cpp:54

llvm::PreservedAnalyses

A set of analyses that are preserved following a run of a transformation pass.

Definition:Analysis.h:111

llvm::PreservedAnalyses::all

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

Definition:Analysis.h:117

llvm::PreservedAnalyses::getChecker

PreservedAnalysisChecker getChecker() const

Build a checker for this PreservedAnalyses and the specified analysis type.

Definition:Analysis.h:264

llvm::ReversePostOrderTraversal

Definition:PostOrderIterator.h:299

llvm::SmallDenseMap

Definition:DenseMap.h:883

llvm::SmallPtrSetImpl

A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...

Definition:SmallPtrSet.h:363

llvm::SmallPtrSetImpl::insert

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

Definition:SmallPtrSet.h:384

llvm::SmallPtrSetImpl::contains

bool contains(ConstPtrType Ptr) const

Definition:SmallPtrSet.h:458

llvm::SmallPtrSet

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

Definition:SmallPtrSet.h:519

llvm::SmallVectorBase::empty

bool empty() const

Definition:SmallVector.h:81

llvm::SmallVectorBase::size

size_t size() const

Definition:SmallVector.h:78

llvm::SmallVectorImpl

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

Definition:SmallVector.h:573

llvm::SmallVectorImpl::pop_back_val

T pop_back_val()

Definition:SmallVector.h:673

llvm::SmallVectorImpl::append

void append(ItTy in_start, ItTy in_end)

Add the specified range to the end of the SmallVector.

Definition:SmallVector.h:683

llvm::SmallVectorTemplateBase::push_back

void push_back(const T &Elt)

Definition:SmallVector.h:413

llvm::SmallVectorTemplateCommon::end

iterator end()

Definition:SmallVector.h:269

llvm::SmallVectorTemplateCommon::begin

iterator begin()

Definition:SmallVector.h:267

llvm::SmallVector

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

Definition:SmallVector.h:1196

llvm::SuccIterator

Definition:CFG.h:141

llvm::TargetLibraryAnalysis

Analysis pass providing the TargetLibraryInfo.

Definition:TargetLibraryInfo.h:614

llvm::TargetLibraryInfoWrapperPass

Definition:TargetLibraryInfo.h:639

llvm::TargetLibraryInfo

Provides information about what library functions are available for the current target.

Definition:TargetLibraryInfo.h:280

llvm::TargetLibraryInfo::getLibFunc

bool getLibFunc(StringRef funcName, LibFunc &F) const

Searches for a particular function name.

Definition:TargetLibraryInfo.h:345

llvm::Type::isPointerTy

bool isPointerTy() const

True if this is an instance of PointerType.

Definition:Type.h:264

llvm::User::getOperand

Value * getOperand(unsigned i) const

Definition:User.h:228

llvm::Value

LLVM Value Representation.

Definition:Value.h:74

llvm::Value::getType

Type * getType() const

All values are typed, get the type of this value.

Definition:Value.h:255

llvm::Value::getName

StringRef getName() const

Return a constant reference to the value's name.

Definition:Value.cpp:309

llvm::cl::opt

Definition:CommandLine.h:1423

llvm::iterator_range

A range adaptor for a pair of iterators.

Definition:iterator_range.h:42

llvm::raw_ostream

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

Definition:raw_ostream.h:52

llvm::scc_iterator

Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG.

Definition:SCCIterator.h:49

Definition:StackSlotColoring.cpp:193

llvm::ARM_MB::LD

@ LD

Definition:ARMBaseInfo.h:72

llvm::M68k::MemAddrModeKind::V

@ V

llvm::MCID::Call

@ Call

Definition:MCInstrDesc.h:156

llvm::WebAssembly::BlockType

BlockType

Used as immediate MachineOperands for block signatures.

Definition:WebAssemblyMCTypeUtilities.h:25

llvm::cl::Hidden

@ Hidden

Definition:CommandLine.h:137

llvm::cl::init

initializer< Ty > init(const Ty &Val)

Definition:CommandLine.h:443

llvm::rdf::Func

NodeAddr< FuncNode * > Func

Definition:RDFGraph.h:393

llvm

This is an optimization pass for GlobalISel generic memory operations.

Definition:AddressRanges.h:18

llvm::pred_end

auto pred_end(const MachineBasicBlock *BB)

Definition:MachineBasicBlock.h:1385

llvm::LibFunc

LibFunc

Definition:TargetLibraryInfo.h:68

llvm::NumLibFuncs

@ NumLibFuncs

Definition:TargetLibraryInfo.h:72

llvm::successors

auto successors(const MachineBasicBlock *BB)

Definition:MachineBasicBlock.h:1376

llvm::make_range

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

Definition:iterator_range.h:77

llvm::scc_begin

scc_iterator< T > scc_begin(const T &G)

Construct the begin iterator for a deduced graph type T.

Definition:SCCIterator.h:233

llvm::ConstantFoldCompareInstOperands

Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)

Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.

Definition:ConstantFolding.cpp:1186

llvm::post_order

iterator_range< po_iterator< T > > post_order(const T &G)

Definition:PostOrderIterator.h:197

llvm::initializeBranchProbabilityInfoWrapperPassPass

void initializeBranchProbabilityInfoWrapperPassPass(PassRegistry &)

llvm::divideNearest

constexpr T divideNearest(U Numerator, V Denominator)

Returns (Numerator / Denominator) rounded by round-half-up.

Definition:MathExtras.h:468

llvm::any_of