BranchProbabilityInfo.h Source File (original) (raw)

13#ifndef LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H

14#define LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H

26#include

27#include

28#include

29#include

31namespace llvm {

100

101

102

103

104

105

106

107

108

109

110

111

112

114public:

116

123

125 : Handles(std::move(Arg.Handles)), Probs(std::move(Arg.Probs)),

126 LastF(Arg.LastF),

127 EstimatedBlockWeight(std::move(Arg.EstimatedBlockWeight)) {

128 for (auto &Handle : Handles)

129 Handle.setBPI(this);

130 }

131

134

137 Handles = std::move(RHS.Handles);

138 Probs = std::move(RHS.Probs);

139 EstimatedBlockWeight = std::move(RHS.EstimatedBlockWeight);

140 for (auto &Handle : Handles)

141 Handle.setBPI(this);

142 return *this;

143 }

144

146 FunctionAnalysisManager::Invalidator &);

147

149

151

152

153

154

155

156

157

160

161

162

163

166

169

170

171

172

173

175

176

177

178

179

180

184

185public:

186

187

188

189

190

194

195

196

197

198

200

201

203

205 static const BranchProbability LikelyProb((1u << 20) - 1, 1u << 20);

206 return IsLikely ? LikelyProb : LikelyProb.getCompl();

207 }

208

212

213

215

216

218

219

220

221 enum SccBlockType {

222 Inner = 0x0,

223 Header = 0x1,

224 Exiting = 0x2,

225 };

226

227

229

230

231

232

233

235

236

237 using SccBlockTypeMaps = std::vector;

238

239 SccMap SccNums;

240 SccBlockTypeMaps SccBlocks;

241

242 public:

244

245

246

247

249

250

252 return getSccBlockType(BB, SccNum) & Header;

253 }

254

255

257 return getSccBlockType(BB, SccNum) & Exiting;

258 }

259

260

261

264

265

266

269

270 private:

271

272

274

275

276 void calculateSccBlockType(const BasicBlock *BB, int SccNum);

277 };

278

279private:

280

281

282 class BasicBlockCallbackVH final : public CallbackVH {

284

285 void deleted() override {

286 assert(BPI != nullptr);

288 }

289

290 public:

292

295 };

296

297

298

299 using LoopData = std::pair<Loop *, int>;

300

301 class LoopBlock {

302 public:

303 LLVM_ABI explicit LoopBlock(const BasicBlock *BB, const LoopInfo &LI,

304 const SccInfo &SccI);

305

306 const BasicBlock *getBlock() const { return BB; }

308 LoopData getLoopData() const { return LD; }

309 Loop *getLoop() const { return LD.first; }

310 int getSccNum() const { return LD.second; }

311

312 bool belongsToLoop() const { return getLoop() || getSccNum() != -1; }

313 bool belongsToSameLoop(const LoopBlock &LB) const {

314 return (LB.getLoop() && getLoop() == LB.getLoop()) ||

315 (LB.getSccNum() != -1 && getSccNum() == LB.getSccNum());

316 }

317

318 private:

319 const BasicBlock *const BB = nullptr;

320 LoopData LD = {nullptr, -1};

321 };

322

323

324 using LoopEdge = std::pair<const LoopBlock &, const LoopBlock &>;

325

326 DenseSet<BasicBlockCallbackVH, DenseMapInfo<Value*>> Handles;

327

328

329

330 using Edge = std::pair<const BasicBlock *, unsigned>;

331

332 DenseMap<Edge, BranchProbability> Probs;

333

334

335 const Function *LastF = nullptr;

336

337 const LoopInfo *LI = nullptr;

338

339

340 std::unique_ptr SccI;

341

342

343 SmallDenseMap<const BasicBlock *, uint32_t> EstimatedBlockWeight;

344

345

346 SmallDenseMap<LoopData, uint32_t> EstimatedLoopWeight;

347

348

349 LoopBlock getLoopBlock(const BasicBlock *BB) const {

350 return LoopBlock(BB, *LI, *SccI);

351 }

352

353

354

355

356 bool isLoopEnteringEdge(const LoopEdge &Edge) const;

357

358

359

360 bool isLoopExitingEdge(const LoopEdge &Edge) const;

361

362

363 bool isLoopEnteringExitingEdge(const LoopEdge &Edge) const;

364

365

366 bool isLoopBackEdge(const LoopEdge &Edge) const;

367

368 void getLoopEnterBlocks(const LoopBlock &LB,

369 SmallVectorImpl<BasicBlock *> &Enters) const;

370

371 void getLoopExitBlocks(const LoopBlock &LB,

372 SmallVectorImpl<BasicBlock *> &Exits) const;

373

374

375

376 std::optional<uint32_t> getEstimatedBlockWeight(const BasicBlock *BB) const;

377

378

379

380

381 std::optional<uint32_t> getEstimatedLoopWeight(const LoopData &L) const;

382

383

384

385 std::optional<uint32_t> getEstimatedEdgeWeight(const LoopEdge &Edge) const;

386

387

388

389

390 template

391 std::optional<uint32_t>

392 getMaxEstimatedEdgeWeight(const LoopBlock &SrcBB,

394

395

396

397

398

399 bool updateEstimatedBlockWeight(LoopBlock &LoopBB, uint32_t BBWeight,

400 SmallVectorImpl<BasicBlock *> &BlockWorkList,

401 SmallVectorImpl &LoopWorkList);

402

403

404

405 void propagateEstimatedBlockWeight(const LoopBlock &LoopBB, DominatorTree *DT,

406 PostDominatorTree *PDT, uint32_t BBWeight,

407 SmallVectorImpl<BasicBlock *> &WorkList,

408 SmallVectorImpl &LoopWorkList);

409

410

411 std::optional<uint32_t> getInitialEstimatedBlockWeight(const BasicBlock *BB);

412

413

414 void estimateBlockWeights(const Function &F, DominatorTree *DT,

415 PostDominatorTree *PDT);

416

417

418

419 bool calcEstimatedHeuristics(const BasicBlock *BB);

420 bool calcMetadataWeights(const BasicBlock *BB);

421 bool calcPointerHeuristics(const BasicBlock *BB);

422 bool calcZeroHeuristics(const BasicBlock *BB, const TargetLibraryInfo *TLI);

423 bool calcFloatingPointHeuristics(const BasicBlock *BB);

424};

425

426

430

432

433public:

434

436

437

439};

440

441

443 : public PassInfoMixin {

445

446public:

448

450

452};

453

454

457

458public:

460

462

465

466 void getAnalysisUsage(AnalysisUsage &AU) const override;

468 void releaseMemory() override;

470};

471

472}

473

474#endif

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)

This file defines DenseMapInfo traits for DenseMap.

This file defines the DenseMap class.

This file defines the DenseSet and SmallDenseSet classes.

static bool runOnFunction(Function &F, bool PostInlining)

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

This header defines various interfaces for pass management in LLVM.

Represent the analysis usage information of a pass.

LLVM Basic Block Representation.

Analysis pass which computes BranchProbabilityInfo.

Definition BranchProbabilityInfo.h:428

LLVM_ABI BranchProbabilityInfo run(Function &F, FunctionAnalysisManager &AM)

Run the analysis pass over a function and produce BPI.

BranchProbabilityInfo Result

Provide the result type for this analysis pass.

Definition BranchProbabilityInfo.h:435

static char ID

Definition BranchProbabilityInfo.h:459

const BranchProbabilityInfo & getBPI() const

Definition BranchProbabilityInfo.h:464

BranchProbabilityInfoWrapperPass()

BranchProbabilityInfo & getBPI()

Definition BranchProbabilityInfo.h:463

bool isSCCHeader(const BasicBlock *BB, int SccNum) const

Returns true if BB is a 'header' block in SCC with SccNum ID, false otherwise.

Definition BranchProbabilityInfo.h:251

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

bool isSCCExitingBlock(const BasicBlock *BB, int SccNum) const

Returns true if BB is an 'exiting' block in SCC with SccNum ID, false otherwise.

Definition BranchProbabilityInfo.h:256

LLVM_ABI SccInfo(const Function &F)

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

LLVM_ABI int getSCCNum(const BasicBlock *BB) const

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

Analysis providing branch probability information.

Definition BranchProbabilityInfo.h:113

LLVM_ABI void eraseBlock(const BasicBlock *BB)

Forget analysis results for the given basic block.

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

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

BranchProbabilityInfo(const BranchProbabilityInfo &)=delete

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

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

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

static BranchProbability getBranchProbStackProtector(bool IsLikely)

Definition BranchProbabilityInfo.h:204

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

BranchProbabilityInfo & operator=(BranchProbabilityInfo &&RHS)

Definition BranchProbabilityInfo.h:135

BranchProbabilityInfo()=default

LLVM_ABI void releaseMemory()

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

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

LLVM_ABI void swapSuccEdgesProbabilities(const BasicBlock *Src)

Swap outgoing edges probabilities for Src with branch terminator.

BranchProbabilityInfo(BranchProbabilityInfo &&Arg)

Definition BranchProbabilityInfo.h:124

LLVM_ABI void print(raw_ostream &OS) const

BranchProbabilityInfo(const Function &F, const LoopInfo &LI, const TargetLibraryInfo *TLI=nullptr, DominatorTree *DT=nullptr, PostDominatorTree *PDT=nullptr)

Definition BranchProbabilityInfo.h:117

BranchProbabilityInfo & operator=(const BranchProbabilityInfo &)=delete

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

Print an edge's probability.

LLVM_ABI void copyEdgeProbabilities(BasicBlock *Src, BasicBlock *Dst)

Copy outgoing edge probabilities from Src to Dst.

BranchProbabilityPrinterPass(raw_ostream &OS)

Definition BranchProbabilityInfo.h:447

static bool isRequired()

Definition BranchProbabilityInfo.h:451

LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

BranchProbability getCompl() const

Value handle with callbacks on RAUW and destruction.

CallbackVH(const CallbackVH &)=default

virtual void deleted()

Callback for Value destruction.

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

Represents a single loop in the control flow graph.

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

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

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

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

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

Value * getValPtr() const

LLVM Value Representation.

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

@ BasicBlock

Various leaf nodes.

This is an optimization pass for GlobalISel generic memory operations.

iterator_range(Container &&) -> iterator_range< llvm::detail::IterOfRange< Container > >

OutputIt move(R &&Range, OutputIt Out)

Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

SuccIterator< const Instruction, const BasicBlock > const_succ_iterator

Implement std::hash so that hash_code can be used in STL containers.

A CRTP mix-in that provides informational APIs needed for analysis passes.

A special type used by analysis passes to provide an address that identifies that particular analysis...

A CRTP mix-in to automatically provide informational APIs needed for passes.