1 | ////===- SampleProfileLoadBaseImpl.h - Profile loader base impl --*- 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 | /// \file |

10 | /// This file provides the interface for the sampled PGO profile loader base |

11 | /// implementation. |

12 | // |

13 | //===----------------------------------------------------------------------===// |

14 | |

15 | #ifndef LLVM_TRANSFORMS_UTILS_SAMPLEPROFILELOADERBASEIMPL_H |

16 | #define LLVM_TRANSFORMS_UTILS_SAMPLEPROFILELOADERBASEIMPL_H |

17 | |

18 | #include "llvm/ADT/ArrayRef.h" |

19 | #include "llvm/ADT/DenseMap.h" |

20 | #include "llvm/ADT/DenseSet.h" |

21 | #include "llvm/ADT/SmallPtrSet.h" |

22 | #include "llvm/ADT/SmallSet.h" |

23 | #include "llvm/ADT/SmallVector.h" |

24 | #include "llvm/Analysis/LoopInfo.h" |

25 | #include "llvm/Analysis/OptimizationRemarkEmitter.h" |

26 | #include "llvm/Analysis/PostDominators.h" |

27 | #include "llvm/IR/BasicBlock.h" |

28 | #include "llvm/IR/CFG.h" |

29 | #include "llvm/IR/DebugInfoMetadata.h" |

30 | #include "llvm/IR/DebugLoc.h" |

31 | #include "llvm/IR/Dominators.h" |

32 | #include "llvm/IR/Function.h" |

33 | #include "llvm/IR/Instruction.h" |

34 | #include "llvm/IR/Instructions.h" |

35 | #include "llvm/IR/Module.h" |

36 | #include "llvm/ProfileData/SampleProf.h" |

37 | #include "llvm/ProfileData/SampleProfReader.h" |

38 | #include "llvm/Support/CommandLine.h" |

39 | #include "llvm/Support/GenericDomTree.h" |

40 | #include "llvm/Support/raw_ostream.h" |

41 | #include "llvm/Transforms/Utils/SampleProfileLoaderBaseUtil.h" |

42 | |

43 | namespace llvm { |

44 | using namespace sampleprof; |

45 | using namespace sampleprofutil; |

46 | using ProfileCount = Function::ProfileCount; |

47 | |

48 | #define DEBUG_TYPE "sample-profile-impl" |

49 | |

50 | namespace afdo_detail { |

51 | |

52 | template <typename BlockT> struct IRTraits; |

53 | template <> struct IRTraits<BasicBlock> { |

54 | using InstructionT = Instruction; |

55 | using BasicBlockT = BasicBlock; |

56 | using FunctionT = Function; |

57 | using BlockFrequencyInfoT = BlockFrequencyInfo; |

58 | using LoopT = Loop; |

59 | using LoopInfoT = LoopInfo; |

60 | using OptRemarkEmitterT = OptimizationRemarkEmitter; |

61 | using OptRemarkAnalysisT = OptimizationRemarkAnalysis; |

62 | using DominatorTreeT = DominatorTree; |

63 | using PostDominatorTreeT = PostDominatorTree; |

64 | static Function &getFunction(Function &F) { return F; } |

65 | static const BasicBlock *getEntryBB(const Function *F) { |

66 | return &F->getEntryBlock(); |

67 | } |

68 | }; |

69 | |

70 | } // end namespace afdo_detail |

71 | |

72 | extern cl::opt<unsigned> SampleProfileMaxPropagateIterations; |

73 | extern cl::opt<unsigned> SampleProfileRecordCoverage; |

74 | extern cl::opt<unsigned> SampleProfileSampleCoverage; |

75 | extern cl::opt<bool> NoWarnSampleUnused; |

76 | |

77 | template <typename BT> class SampleProfileLoaderBaseImpl { |

78 | public: |

79 | SampleProfileLoaderBaseImpl(std::string Name) : Filename(Name) {} |

80 | void dump() { Reader->dump(); } |

81 | |

82 | using InstructionT = typename afdo_detail::IRTraits<BT>::InstructionT; |

83 | using BasicBlockT = typename afdo_detail::IRTraits<BT>::BasicBlockT; |

84 | using BlockFrequencyInfoT = |

85 | typename afdo_detail::IRTraits<BT>::BlockFrequencyInfoT; |

86 | using FunctionT = typename afdo_detail::IRTraits<BT>::FunctionT; |

87 | using LoopT = typename afdo_detail::IRTraits<BT>::LoopT; |

88 | using LoopInfoT = typename afdo_detail::IRTraits<BT>::LoopInfoT; |

89 | using OptRemarkEmitterT = |

90 | typename afdo_detail::IRTraits<BT>::OptRemarkEmitterT; |

91 | using OptRemarkAnalysisT = |

92 | typename afdo_detail::IRTraits<BT>::OptRemarkAnalysisT; |

93 | using DominatorTreeT = typename afdo_detail::IRTraits<BT>::DominatorTreeT; |

94 | using PostDominatorTreeT = |

95 | typename afdo_detail::IRTraits<BT>::PostDominatorTreeT; |

96 | |

97 | using BlockWeightMap = DenseMap<const BasicBlockT *, uint64_t>; |

98 | using EquivalenceClassMap = |

99 | DenseMap<const BasicBlockT *, const BasicBlockT *>; |

100 | using Edge = std::pair<const BasicBlockT *, const BasicBlockT *>; |

101 | using EdgeWeightMap = DenseMap<Edge, uint64_t>; |

102 | using BlockEdgeMap = |

103 | DenseMap<const BasicBlockT *, SmallVector<const BasicBlockT *, 8>>; |

104 | |

105 | protected: |

106 | ~SampleProfileLoaderBaseImpl() = default; |

107 | friend class SampleCoverageTracker; |

108 | |

109 | Function &getFunction(FunctionT &F) { |

110 | return afdo_detail::IRTraits<BT>::getFunction(F); |

111 | } |

112 | const BasicBlockT *getEntryBB(const FunctionT *F) { |

113 | return afdo_detail::IRTraits<BT>::getEntryBB(F); |

114 | } |

115 | |

116 | unsigned getFunctionLoc(FunctionT &Func); |

117 | virtual ErrorOr<uint64_t> getInstWeight(const InstructionT &Inst); |

118 | ErrorOr<uint64_t> getInstWeightImpl(const InstructionT &Inst); |

119 | ErrorOr<uint64_t> getBlockWeight(const BasicBlockT *BB); |

120 | mutable DenseMap<const DILocation *, const FunctionSamples *> |

121 | DILocation2SampleMap; |

122 | virtual const FunctionSamples * |

123 | findFunctionSamples(const InstructionT &I) const; |

124 | void printEdgeWeight(raw_ostream &OS, Edge E); |

125 | void printBlockWeight(raw_ostream &OS, const BasicBlockT *BB) const; |

126 | void printBlockEquivalence(raw_ostream &OS, const BasicBlockT *BB); |

127 | bool computeBlockWeights(FunctionT &F); |

128 | void findEquivalenceClasses(FunctionT &F); |

129 | void findEquivalencesFor(BasicBlockT *BB1, |

130 | ArrayRef<BasicBlockT *> Descendants, |

131 | PostDominatorTreeT *DomTree); |

132 | |

133 | void propagateWeights(FunctionT &F); |

134 | uint64_t visitEdge(Edge E, unsigned *NumUnknownEdges, Edge *UnknownEdge); |

135 | void buildEdges(FunctionT &F); |

136 | bool propagateThroughEdges(FunctionT &F, bool UpdateBlockCount); |

137 | void clearFunctionData(); |

138 | void computeDominanceAndLoopInfo(FunctionT &F); |

139 | bool |

140 | computeAndPropagateWeights(FunctionT &F, |

141 | const DenseSet<GlobalValue::GUID> &InlinedGUIDs); |

142 | void emitCoverageRemarks(FunctionT &F); |

143 | |

144 | /// Map basic blocks to their computed weights. |

145 | /// |

146 | /// The weight of a basic block is defined to be the maximum |

147 | /// of all the instruction weights in that block. |

148 | BlockWeightMap BlockWeights; |

149 | |

150 | /// Map edges to their computed weights. |

151 | /// |

152 | /// Edge weights are computed by propagating basic block weights in |

153 | /// SampleProfile::propagateWeights. |

154 | EdgeWeightMap EdgeWeights; |

155 | |

156 | /// Set of visited blocks during propagation. |

157 | SmallPtrSet<const BasicBlockT *, 32> VisitedBlocks; |

158 | |

159 | /// Set of visited edges during propagation. |

160 | SmallSet<Edge, 32> VisitedEdges; |

161 | |

162 | /// Equivalence classes for block weights. |

163 | /// |

164 | /// Two blocks BB1 and BB2 are in the same equivalence class if they |

165 | /// dominate and post-dominate each other, and they are in the same loop |

166 | /// nest. When this happens, the two blocks are guaranteed to execute |

167 | /// the same number of times. |

168 | EquivalenceClassMap EquivalenceClass; |

169 | |

170 | /// Dominance, post-dominance and loop information. |

171 | std::unique_ptr<DominatorTreeT> DT; |

172 | std::unique_ptr<PostDominatorTreeT> PDT; |

173 | std::unique_ptr<LoopInfoT> LI; |

174 | |

175 | /// Predecessors for each basic block in the CFG. |

176 | BlockEdgeMap Predecessors; |

177 | |

178 | /// Successors for each basic block in the CFG. |

179 | BlockEdgeMap Successors; |

180 | |

181 | /// Profile coverage tracker. |

182 | SampleCoverageTracker CoverageTracker; |

183 | |

184 | /// Profile reader object. |

185 | std::unique_ptr<SampleProfileReader> Reader; |

186 | |

187 | /// Samples collected for the body of this function. |

188 | FunctionSamples *Samples = nullptr; |

189 | |

190 | /// Name of the profile file to load. |

191 | std::string Filename; |

192 | |

193 | /// Profile Summary Info computed from sample profile. |

194 | ProfileSummaryInfo *PSI = nullptr; |

195 | |

196 | /// Optimization Remark Emitter used to emit diagnostic remarks. |

197 | OptRemarkEmitterT *ORE = nullptr; |

198 | }; |

199 | |

200 | /// Clear all the per-function data used to load samples and propagate weights. |

201 | template <typename BT> |

202 | void SampleProfileLoaderBaseImpl<BT>::clearFunctionData() { |

203 | BlockWeights.clear(); |

204 | EdgeWeights.clear(); |

205 | VisitedBlocks.clear(); |

206 | VisitedEdges.clear(); |

207 | EquivalenceClass.clear(); |

208 | DT = nullptr; |

209 | PDT = nullptr; |

210 | LI = nullptr; |

211 | Predecessors.clear(); |

212 | Successors.clear(); |

213 | CoverageTracker.clear(); |

214 | } |

215 | |

216 | #ifndef NDEBUG |

217 | /// Print the weight of edge \p E on stream \p OS. |

218 | /// |

219 | /// \param OS Stream to emit the output to. |

220 | /// \param E Edge to print. |

221 | template <typename BT> |

222 | void SampleProfileLoaderBaseImpl<BT>::printEdgeWeight(raw_ostream &OS, Edge E) { |

223 | OS << "weight["<< E.first->getName() << "->"<< E.second->getName() |

224 | << "]: "<< EdgeWeights[E] << "\n"; |

225 | } |

226 | |

227 | /// Print the equivalence class of block \p BB on stream \p OS. |

228 | /// |

229 | /// \param OS Stream to emit the output to. |

230 | /// \param BB Block to print. |

231 | template <typename BT> |

232 | void SampleProfileLoaderBaseImpl<BT>::printBlockEquivalence( |

233 | raw_ostream &OS, const BasicBlockT *BB) { |

234 | const BasicBlockT *Equiv = EquivalenceClass[BB]; |

235 | OS << "equivalence["<< BB->getName() |

236 | << "]: "<< ((Equiv) ? EquivalenceClass[BB]->getName() : "NONE") << "\n"; |

237 | } |

238 | |

239 | /// Print the weight of block \p BB on stream \p OS. |

240 | /// |

241 | /// \param OS Stream to emit the output to. |

242 | /// \param BB Block to print. |

243 | template <typename BT> |

244 | void SampleProfileLoaderBaseImpl<BT>::printBlockWeight( |

245 | raw_ostream &OS, const BasicBlockT *BB) const { |

246 | const auto &I = BlockWeights.find(BB); |

247 | uint64_t W = (I == BlockWeights.end() ? 0 : I->second); |

248 | OS << "weight["<< BB->getName() << "]: "<< W << "\n"; |

249 | } |

250 | #endif |

251 | |

252 | /// Get the weight for an instruction. |

253 | /// |

254 | /// The "weight" of an instruction \p Inst is the number of samples |

255 | /// collected on that instruction at runtime. To retrieve it, we |

256 | /// need to compute the line number of \p Inst relative to the start of its |

257 | /// function. We use HeaderLineno to compute the offset. We then |

258 | /// look up the samples collected for \p Inst using BodySamples. |

259 | /// |

260 | /// \param Inst Instruction to query. |

261 | /// |

262 | /// \returns the weight of \p Inst. |

263 | template <typename BT> |

264 | ErrorOr<uint64_t> |

265 | SampleProfileLoaderBaseImpl<BT>::getInstWeight(const InstructionT &Inst) { |

266 | return getInstWeightImpl(Inst); |

267 | } |

268 | |

269 | template <typename BT> |

270 | ErrorOr<uint64_t> |

271 | SampleProfileLoaderBaseImpl<BT>::getInstWeightImpl(const InstructionT &Inst) { |

272 | const FunctionSamples *FS = findFunctionSamples(Inst); |

273 | if (!FS) |

274 | return std::error_code(); |

275 | |

276 | const DebugLoc &DLoc = Inst.getDebugLoc(); |

277 | if (!DLoc) |

278 | return std::error_code(); |

279 | |

280 | const DILocation *DIL = DLoc; |

281 | uint32_t LineOffset = FunctionSamples::getOffset(DIL); |

282 | uint32_t Discriminator = DIL->getBaseDiscriminator(); |

283 | ErrorOr<uint64_t> R = FS->findSamplesAt(LineOffset, Discriminator); |

284 | if (R) { |

285 | bool FirstMark = |

286 | CoverageTracker.markSamplesUsed(FS, LineOffset, Discriminator, R.get()); |

287 | if (FirstMark) { |

288 | ORE->emit([&]() { |

289 | OptRemarkAnalysisT Remark(DEBUG_TYPE, "AppliedSamples", &Inst); |

290 | Remark << "Applied "<< ore::NV( "NumSamples", *R); |

291 | Remark << " samples from profile (offset: "; |

292 | Remark << ore::NV("LineOffset", LineOffset); |

293 | if (Discriminator) { |

294 | Remark << "."; |

295 | Remark << ore::NV("Discriminator", Discriminator); |

296 | } |

297 | Remark << ")"; |

298 | return Remark; |

299 | }); |

300 | } |

301 | LLVM_DEBUG(dbgs() << " "<< DLoc.getLine() << "." |

302 | << DIL->getBaseDiscriminator() << ":"<< Inst |

303 | << " (line offset: "<< LineOffset << "." |

304 | << DIL->getBaseDiscriminator() << " - weight: "<< R.get() |

305 | << ")\n"); |

306 | } |

307 | return R; |

308 | } |

309 | |

310 | /// Compute the weight of a basic block. |

311 | /// |

312 | /// The weight of basic block \p BB is the maximum weight of all the |

313 | /// instructions in BB. |

314 | /// |

315 | /// \param BB The basic block to query. |

316 | /// |

317 | /// \returns the weight for \p BB. |

318 | template <typename BT> |

319 | ErrorOr<uint64_t> |

320 | SampleProfileLoaderBaseImpl<BT>::getBlockWeight(const BasicBlockT *BB) { |

321 | uint64_t Max = 0; |

322 | bool HasWeight = false; |

323 | for (auto &I : *BB) { |

324 | const ErrorOr<uint64_t> &R = getInstWeight(I); |

325 | if (R) { |

326 | Max = std::max(Max, R.get()); |

327 | HasWeight = true; |

328 | } |

329 | } |

330 | return HasWeight ? ErrorOr<uint64_t>(Max) : std::error_code(); |

331 | } |

332 | |

333 | /// Compute and store the weights of every basic block. |

334 | /// |

335 | /// This populates the BlockWeights map by computing |

336 | /// the weights of every basic block in the CFG. |

337 | /// |

338 | /// \param F The function to query. |

339 | template <typename BT> |

340 | bool SampleProfileLoaderBaseImpl<BT>::computeBlockWeights(FunctionT &F) { |

341 | bool Changed = false; |

342 | LLVM_DEBUG(dbgs() << "Block weights\n"); |

343 | for (const auto &BB : F) { |

344 | ErrorOr<uint64_t> Weight = getBlockWeight(&BB); |

345 | if (Weight) { |

346 | BlockWeights[&BB] = Weight.get(); |

347 | VisitedBlocks.insert(&BB); |

348 | Changed = true; |

349 | } |

350 | LLVM_DEBUG(printBlockWeight(dbgs(), &BB)); |

351 | } |

352 | |

353 | return Changed; |

354 | } |

355 | |

356 | /// Get the FunctionSamples for an instruction. |

357 | /// |

358 | /// The FunctionSamples of an instruction \p Inst is the inlined instance |

359 | /// in which that instruction is coming from. We traverse the inline stack |

360 | /// of that instruction, and match it with the tree nodes in the profile. |

361 | /// |

362 | /// \param Inst Instruction to query. |

363 | /// |

364 | /// \returns the FunctionSamples pointer to the inlined instance. |

365 | template <typename BT> |

366 | const FunctionSamples *SampleProfileLoaderBaseImpl<BT>::findFunctionSamples( |

367 | const InstructionT &Inst) const { |

368 | const DILocation *DIL = Inst.getDebugLoc(); |

369 | if (!DIL) |

370 | return Samples; |

371 | |

372 | auto it = DILocation2SampleMap.try_emplace(DIL, nullptr); |

373 | if (it.second) { |

374 | it.first->second = Samples->findFunctionSamples(DIL, Reader->getRemapper()); |

375 | } |

376 | return it.first->second; |

377 | } |

378 | |

379 | /// Find equivalence classes for the given block. |

380 | /// |

381 | /// This finds all the blocks that are guaranteed to execute the same |

382 | /// number of times as \p BB1. To do this, it traverses all the |

383 | /// descendants of \p BB1 in the dominator or post-dominator tree. |

384 | /// |

385 | /// A block BB2 will be in the same equivalence class as \p BB1 if |

386 | /// the following holds: |

387 | /// |

388 | /// 1- \p BB1 is a descendant of BB2 in the opposite tree. So, if BB2 |

389 | /// is a descendant of \p BB1 in the dominator tree, then BB2 should |

390 | /// dominate BB1 in the post-dominator tree. |

391 | /// |

392 | /// 2- Both BB2 and \p BB1 must be in the same loop. |

393 | /// |

394 | /// For every block BB2 that meets those two requirements, we set BB2's |

395 | /// equivalence class to \p BB1. |

396 | /// |

397 | /// \param BB1 Block to check. |

398 | /// \param Descendants Descendants of \p BB1 in either the dom or pdom tree. |

399 | /// \param DomTree Opposite dominator tree. If \p Descendants is filled |

400 | /// with blocks from \p BB1's dominator tree, then |

401 | /// this is the post-dominator tree, and vice versa. |

402 | template <typename BT> |

403 | void SampleProfileLoaderBaseImpl<BT>::findEquivalencesFor( |

404 | BasicBlockT *BB1, ArrayRef<BasicBlockT *> Descendants, |

405 | PostDominatorTreeT *DomTree) { |

406 | const BasicBlockT *EC = EquivalenceClass[BB1]; |

407 | uint64_t Weight = BlockWeights[EC]; |

408 | for (const auto *BB2 : Descendants) { |

409 | bool IsDomParent = DomTree->dominates(BB2, BB1); |

410 | bool IsInSameLoop = LI->getLoopFor(BB1) == LI->getLoopFor(BB2); |

411 | if (BB1 != BB2 && IsDomParent && IsInSameLoop) { |

412 | EquivalenceClass[BB2] = EC; |

413 | // If BB2 is visited, then the entire EC should be marked as visited. |

414 | if (VisitedBlocks.count(BB2)) { |

415 | VisitedBlocks.insert(EC); |

416 | } |

417 | |

418 | // If BB2 is heavier than BB1, make BB2 have the same weight |

419 | // as BB1. |

420 | // |

421 | // Note that we don't worry about the opposite situation here |

422 | // (when BB2 is lighter than BB1). We will deal with this |

423 | // during the propagation phase. Right now, we just want to |

424 | // make sure that BB1 has the largest weight of all the |

425 | // members of its equivalence set. |

426 | Weight = std::max(Weight, BlockWeights[BB2]); |

427 | } |

428 | } |

429 | const BasicBlockT *EntryBB = getEntryBB(EC->getParent()); |

430 | if (EC == EntryBB) { |

431 | BlockWeights[EC] = Samples->getHeadSamples() + 1; |

432 | } else { |

433 | BlockWeights[EC] = Weight; |

434 | } |

435 | } |

436 | |

437 | /// Find equivalence classes. |

438 | /// |

439 | /// Since samples may be missing from blocks, we can fill in the gaps by setting |

440 | /// the weights of all the blocks in the same equivalence class to the same |

441 | /// weight. To compute the concept of equivalence, we use dominance and loop |

442 | /// information. Two blocks B1 and B2 are in the same equivalence class if B1 |

443 | /// dominates B2, B2 post-dominates B1 and both are in the same loop. |

444 | /// |

445 | /// \param F The function to query. |

446 | template <typename BT> |

447 | void SampleProfileLoaderBaseImpl<BT>::findEquivalenceClasses(FunctionT &F) { |

448 | SmallVector<BasicBlockT *, 8> DominatedBBs; |

449 | LLVM_DEBUG(dbgs() << "\nBlock equivalence classes\n"); |

450 | // Find equivalence sets based on dominance and post-dominance information. |

451 | for (auto &BB : F) { |

452 | BasicBlockT *BB1 = &BB; |

453 | |

454 | // Compute BB1's equivalence class once. |

455 | if (EquivalenceClass.count(BB1)) { |

456 | LLVM_DEBUG(printBlockEquivalence(dbgs(), BB1)); |

457 | continue; |

458 | } |

459 | |

460 | // By default, blocks are in their own equivalence class. |

461 | EquivalenceClass[BB1] = BB1; |

462 | |

463 | // Traverse all the blocks dominated by BB1. We are looking for |

464 | // every basic block BB2 such that: |

465 | // |

466 | // 1- BB1 dominates BB2. |

467 | // 2- BB2 post-dominates BB1. |

468 | // 3- BB1 and BB2 are in the same loop nest. |

469 | // |

470 | // If all those conditions hold, it means that BB2 is executed |

471 | // as many times as BB1, so they are placed in the same equivalence |

472 | // class by making BB2's equivalence class be BB1. |

473 | DominatedBBs.clear(); |

474 | DT->getDescendants(BB1, DominatedBBs); |

475 | findEquivalencesFor(BB1, DominatedBBs, PDT.get()); |

476 | |

477 | LLVM_DEBUG(printBlockEquivalence(dbgs(), BB1)); |

478 | } |

479 | |

480 | // Assign weights to equivalence classes. |

481 | // |

482 | // All the basic blocks in the same equivalence class will execute |

483 | // the same number of times. Since we know that the head block in |

484 | // each equivalence class has the largest weight, assign that weight |

485 | // to all the blocks in that equivalence class. |

486 | LLVM_DEBUG( |

487 | dbgs() << "\nAssign the same weight to all blocks in the same class\n"); |

488 | for (auto &BI : F) { |

489 | const BasicBlockT *BB = &BI; |

490 | const BasicBlockT *EquivBB = EquivalenceClass[BB]; |

491 | if (BB != EquivBB) |

492 | BlockWeights[BB] = BlockWeights[EquivBB]; |

493 | LLVM_DEBUG(printBlockWeight(dbgs(), BB)); |

494 | } |

495 | } |

496 | |

497 | /// Visit the given edge to decide if it has a valid weight. |

498 | /// |

499 | /// If \p E has not been visited before, we copy to \p UnknownEdge |

500 | /// and increment the count of unknown edges. |

501 | /// |

502 | /// \param E Edge to visit. |

503 | /// \param NumUnknownEdges Current number of unknown edges. |

504 | /// \param UnknownEdge Set if E has not been visited before. |

505 | /// |

506 | /// \returns E's weight, if known. Otherwise, return 0. |

507 | template <typename BT> |

508 | uint64_t SampleProfileLoaderBaseImpl<BT>::visitEdge(Edge E, |

509 | unsigned *NumUnknownEdges, |

510 | Edge *UnknownEdge) { |

511 | if (!VisitedEdges.count(E)) { |

512 | (*NumUnknownEdges)++; |

513 | *UnknownEdge = E; |

514 | return 0; |

515 | } |

516 | |

517 | return EdgeWeights[E]; |

518 | } |

519 | |

520 | /// Propagate weights through incoming/outgoing edges. |

521 | /// |

522 | /// If the weight of a basic block is known, and there is only one edge |

523 | /// with an unknown weight, we can calculate the weight of that edge. |

524 | /// |

525 | /// Similarly, if all the edges have a known count, we can calculate the |

526 | /// count of the basic block, if needed. |

527 | /// |

528 | /// \param F Function to process. |

529 | /// \param UpdateBlockCount Whether we should update basic block counts that |

530 | /// has already been annotated. |

531 | /// |

532 | /// \returns True if new weights were assigned to edges or blocks. |

533 | template <typename BT> |

534 | bool SampleProfileLoaderBaseImpl<BT>::propagateThroughEdges( |

535 | FunctionT &F, bool UpdateBlockCount) { |

536 | bool Changed = false; |

537 | LLVM_DEBUG(dbgs() << "\nPropagation through edges\n"); |

538 | for (const auto &BI : F) { |

539 | const BasicBlockT *BB = &BI; |

540 | const BasicBlockT *EC = EquivalenceClass[BB]; |

541 | |

542 | // Visit all the predecessor and successor edges to determine |

543 | // which ones have a weight assigned already. Note that it doesn't |

544 | // matter that we only keep track of a single unknown edge. The |

545 | // only case we are interested in handling is when only a single |

546 | // edge is unknown (see setEdgeOrBlockWeight). |

547 | for (unsigned i = 0; i < 2; i++) { |

548 | uint64_t TotalWeight = 0; |

549 | unsigned NumUnknownEdges = 0, NumTotalEdges = 0; |

550 | Edge UnknownEdge, SelfReferentialEdge, SingleEdge; |

551 | |

552 | if (i == 0) { |

553 | // First, visit all predecessor edges. |

554 | NumTotalEdges = Predecessors[BB].size(); |

555 | for (auto *Pred : Predecessors[BB]) { |

556 | Edge E = std::make_pair(Pred, BB); |

557 | TotalWeight += visitEdge(E, &NumUnknownEdges, &UnknownEdge); |

558 | if (E.first == E.second) |

559 | SelfReferentialEdge = E; |

560 | } |

561 | if (NumTotalEdges == 1) { |

562 | SingleEdge = std::make_pair(Predecessors[BB][0], BB); |

563 | } |

564 | } else { |

565 | // On the second round, visit all successor edges. |

566 | NumTotalEdges = Successors[BB].size(); |

567 | for (auto *Succ : Successors[BB]) { |

568 | Edge E = std::make_pair(BB, Succ); |

569 | TotalWeight += visitEdge(E, &NumUnknownEdges, &UnknownEdge); |

570 | } |

571 | if (NumTotalEdges == 1) { |

572 | SingleEdge = std::make_pair(BB, Successors[BB][0]); |

573 | } |

574 | } |

575 | |

576 | // After visiting all the edges, there are three cases that we |

577 | // can handle immediately: |

578 | // |

579 | // - All the edge weights are known (i.e., NumUnknownEdges == 0). |

580 | // In this case, we simply check that the sum of all the edges |

581 | // is the same as BB's weight. If not, we change BB's weight |

582 | // to match. Additionally, if BB had not been visited before, |

583 | // we mark it visited. |

584 | // |

585 | // - Only one edge is unknown and BB has already been visited. |

586 | // In this case, we can compute the weight of the edge by |

587 | // subtracting the total block weight from all the known |

588 | // edge weights. If the edges weight more than BB, then the |

589 | // edge of the last remaining edge is set to zero. |

590 | // |

591 | // - There exists a self-referential edge and the weight of BB is |

592 | // known. In this case, this edge can be based on BB's weight. |

593 | // We add up all the other known edges and set the weight on |

594 | // the self-referential edge as we did in the previous case. |

595 | // |

596 | // In any other case, we must continue iterating. Eventually, |

597 | // all edges will get a weight, or iteration will stop when |

598 | // it reaches SampleProfileMaxPropagateIterations. |

599 | if (NumUnknownEdges <= 1) { |

600 | uint64_t &BBWeight = BlockWeights[EC]; |

601 | if (NumUnknownEdges == 0) { |

602 | if (!VisitedBlocks.count(EC)) { |

603 | // If we already know the weight of all edges, the weight of the |

604 | // basic block can be computed. It should be no larger than the sum |

605 | // of all edge weights. |

606 | if (TotalWeight > BBWeight) { |

607 | BBWeight = TotalWeight; |

608 | Changed = true; |

609 | LLVM_DEBUG(dbgs() << "All edge weights for "<< BB->getName() |

610 | << " known. Set weight for block: "; |

611 | printBlockWeight(dbgs(), BB);); |

612 | } |

613 | } else if (NumTotalEdges == 1 && |

614 | EdgeWeights[SingleEdge] < BlockWeights[EC]) { |

615 | // If there is only one edge for the visited basic block, use the |

616 | // block weight to adjust edge weight if edge weight is smaller. |

617 | EdgeWeights[SingleEdge] = BlockWeights[EC]; |

618 | Changed = true; |

619 | } |

620 | } else if (NumUnknownEdges == 1 && VisitedBlocks.count(EC)) { |

621 | // If there is a single unknown edge and the block has been |

622 | // visited, then we can compute E's weight. |

623 | if (BBWeight >= TotalWeight) |

624 | EdgeWeights[UnknownEdge] = BBWeight - TotalWeight; |

625 | else |

626 | EdgeWeights[UnknownEdge] = 0; |

627 | const BasicBlockT *OtherEC; |

628 | if (i == 0) |

629 | OtherEC = EquivalenceClass[UnknownEdge.first]; |

630 | else |

631 | OtherEC = EquivalenceClass[UnknownEdge.second]; |

632 | // Edge weights should never exceed the BB weights it connects. |

633 | if (VisitedBlocks.count(OtherEC) && |

634 | EdgeWeights[UnknownEdge] > BlockWeights[OtherEC]) |

635 | EdgeWeights[UnknownEdge] = BlockWeights[OtherEC]; |

636 | VisitedEdges.insert(UnknownEdge); |

637 | Changed = true; |

638 | LLVM_DEBUG(dbgs() << "Set weight for edge: "; |

639 | printEdgeWeight(dbgs(), UnknownEdge)); |

640 | } |

641 | } else if (VisitedBlocks.count(EC) && BlockWeights[EC] == 0) { |

642 | // If a block Weights 0, all its in/out edges should weight 0. |

643 | if (i == 0) { |

644 | for (auto *Pred : Predecessors[BB]) { |

645 | Edge E = std::make_pair(Pred, BB); |

646 | EdgeWeights[E] = 0; |

647 | VisitedEdges.insert(E); |

648 | } |

649 | } else { |

650 | for (auto *Succ : Successors[BB]) { |

651 | Edge E = std::make_pair(BB, Succ); |

652 | EdgeWeights[E] = 0; |

653 | VisitedEdges.insert(E); |

654 | } |

655 | } |

656 | } else if (SelfReferentialEdge.first && VisitedBlocks.count(EC)) { |

657 | uint64_t &BBWeight = BlockWeights[BB]; |

658 | // We have a self-referential edge and the weight of BB is known. |

659 | if (BBWeight >= TotalWeight) |

660 | EdgeWeights[SelfReferentialEdge] = BBWeight - TotalWeight; |

661 | else |

662 | EdgeWeights[SelfReferentialEdge] = 0; |

663 | VisitedEdges.insert(SelfReferentialEdge); |

664 | Changed = true; |

665 | LLVM_DEBUG(dbgs() << "Set self-referential edge weight to: "; |

666 | printEdgeWeight(dbgs(), SelfReferentialEdge)); |

667 | } |

668 | if (UpdateBlockCount && !VisitedBlocks.count(EC) && TotalWeight > 0) { |

669 | BlockWeights[EC] = TotalWeight; |

670 | VisitedBlocks.insert(EC); |

671 | Changed = true; |

672 | } |

673 | } |

674 | } |

675 | |

676 | return Changed; |

677 | } |

678 | |

679 | /// Build in/out edge lists for each basic block in the CFG. |

680 | /// |

681 | /// We are interested in unique edges. If a block B1 has multiple |

682 | /// edges to another block B2, we only add a single B1->B2 edge. |

683 | template <typename BT> |

684 | void SampleProfileLoaderBaseImpl<BT>::buildEdges(FunctionT &F) { |

685 | for (auto &BI : F) { |

686 | BasicBlockT *B1 = &BI; |

687 | |

688 | // Add predecessors for B1. |

689 | SmallPtrSet<BasicBlockT *, 16> Visited; |

690 | if (!Predecessors[B1].empty()) |

691 | llvm_unreachable("Found a stale predecessors list in a basic block."); |

692 | for (BasicBlockT *B2 : predecessors(B1)) |

693 | if (Visited.insert(B2).second) |

694 | Predecessors[B1].push_back(B2); |

695 | |

696 | // Add successors for B1. |

697 | Visited.clear(); |

698 | if (!Successors[B1].empty()) |

699 | llvm_unreachable("Found a stale successors list in a basic block."); |

700 | for (BasicBlockT *B2 : successors(B1)) |

701 | if (Visited.insert(B2).second) |

702 | Successors[B1].push_back(B2); |

703 | } |

704 | } |

705 | |

706 | /// Propagate weights into edges |

707 | /// |

708 | /// The following rules are applied to every block BB in the CFG: |

709 | /// |

710 | /// - If BB has a single predecessor/successor, then the weight |

711 | /// of that edge is the weight of the block. |

712 | /// |

713 | /// - If all incoming or outgoing edges are known except one, and the |

714 | /// weight of the block is already known, the weight of the unknown |

715 | /// edge will be the weight of the block minus the sum of all the known |

716 | /// edges. If the sum of all the known edges is larger than BB's weight, |

717 | /// we set the unknown edge weight to zero. |

718 | /// |

719 | /// - If there is a self-referential edge, and the weight of the block is |

720 | /// known, the weight for that edge is set to the weight of the block |

721 | /// minus the weight of the other incoming edges to that block (if |

722 | /// known). |

723 | template <typename BT> |

724 | void SampleProfileLoaderBaseImpl<BT>::propagateWeights(FunctionT &F) { |

725 | bool Changed = true; |

726 | unsigned I = 0; |

727 | |

728 | // If BB weight is larger than its corresponding loop's header BB weight, |

729 | // use the BB weight to replace the loop header BB weight. |

730 | for (auto &BI : F) { |

731 | BasicBlockT *BB = &BI; |

732 | LoopT *L = LI->getLoopFor(BB); |

733 | if (!L) { |

734 | continue; |

735 | } |

736 | BasicBlockT *Header = L->getHeader(); |

737 | if (Header && BlockWeights[BB] > BlockWeights[Header]) { |

738 | BlockWeights[Header] = BlockWeights[BB]; |

739 | } |

740 | } |

741 | |

742 | // Before propagation starts, build, for each block, a list of |

743 | // unique predecessors and successors. This is necessary to handle |

744 | // identical edges in multiway branches. Since we visit all blocks and all |

745 | // edges of the CFG, it is cleaner to build these lists once at the start |

746 | // of the pass. |

747 | buildEdges(F); |

748 | |

749 | // Propagate until we converge or we go past the iteration limit. |

750 | while (Changed && I++ < SampleProfileMaxPropagateIterations) { |

751 | Changed = propagateThroughEdges(F, false); |

752 | } |

753 | |

754 | // The first propagation propagates BB counts from annotated BBs to unknown |

755 | // BBs. The 2nd propagation pass resets edges weights, and use all BB weights |

756 | // to propagate edge weights. |

757 | VisitedEdges.clear(); |

758 | Changed = true; |

759 | while (Changed && I++ < SampleProfileMaxPropagateIterations) { |

760 | Changed = propagateThroughEdges(F, false); |

761 | } |

762 | |

763 | // The 3rd propagation pass allows adjust annotated BB weights that are |

764 | // obviously wrong. |

765 | Changed = true; |

766 | while (Changed && I++ < SampleProfileMaxPropagateIterations) { |

767 | Changed = propagateThroughEdges(F, true); |

768 | } |

769 | } |

770 | |

771 | /// Generate branch weight metadata for all branches in \p F. |

772 | /// |

773 | /// Branch weights are computed out of instruction samples using a |

774 | /// propagation heuristic. Propagation proceeds in 3 phases: |

775 | /// |

776 | /// 1- Assignment of block weights. All the basic blocks in the function |

777 | /// are initial assigned the same weight as their most frequently |

778 | /// executed instruction. |

779 | /// |

780 | /// 2- Creation of equivalence classes. Since samples may be missing from |

781 | /// blocks, we can fill in the gaps by setting the weights of all the |

782 | /// blocks in the same equivalence class to the same weight. To compute |

783 | /// the concept of equivalence, we use dominance and loop information. |

784 | /// Two blocks B1 and B2 are in the same equivalence class if B1 |

785 | /// dominates B2, B2 post-dominates B1 and both are in the same loop. |

786 | /// |

787 | /// 3- Propagation of block weights into edges. This uses a simple |

788 | /// propagation heuristic. The following rules are applied to every |

789 | /// block BB in the CFG: |

790 | /// |

791 | /// - If BB has a single predecessor/successor, then the weight |

792 | /// of that edge is the weight of the block. |

793 | /// |

794 | /// - If all the edges are known except one, and the weight of the |

795 | /// block is already known, the weight of the unknown edge will |

796 | /// be the weight of the block minus the sum of all the known |

797 | /// edges. If the sum of all the known edges is larger than BB's weight, |

798 | /// we set the unknown edge weight to zero. |

799 | /// |

800 | /// - If there is a self-referential edge, and the weight of the block is |

801 | /// known, the weight for that edge is set to the weight of the block |

802 | /// minus the weight of the other incoming edges to that block (if |

803 | /// known). |

804 | /// |

805 | /// Since this propagation is not guaranteed to finalize for every CFG, we |

806 | /// only allow it to proceed for a limited number of iterations (controlled |

807 | /// by -sample-profile-max-propagate-iterations). |

808 | /// |

809 | /// FIXME: Try to replace this propagation heuristic with a scheme |

810 | /// that is guaranteed to finalize. A work-list approach similar to |

811 | /// the standard value propagation algorithm used by SSA-CCP might |

812 | /// work here. |

813 | /// |

814 | /// \param F The function to query. |

815 | /// |

816 | /// \returns true if \p F was modified. Returns false, otherwise. |

817 | template <typename BT> |

818 | bool SampleProfileLoaderBaseImpl<BT>::computeAndPropagateWeights( |

819 | FunctionT &F, const DenseSet<GlobalValue::GUID> &InlinedGUIDs) { |

820 | bool Changed = (InlinedGUIDs.size() != 0); |

821 | |

822 | // Compute basic block weights. |

823 | Changed |= computeBlockWeights(F); |

824 | |

825 | if (Changed) { |

826 | // Add an entry count to the function using the samples gathered at the |

827 | // function entry. |

828 | // Sets the GUIDs that are inlined in the profiled binary. This is used |

829 | // for ThinLink to make correct liveness analysis, and also make the IR |

830 | // match the profiled binary before annotation. |

831 | getFunction(F).setEntryCount( |

832 | ProfileCount(Samples->getHeadSamples() + 1, Function::PCT_Real), |

833 | &InlinedGUIDs); |

834 | |

835 | // Compute dominance and loop info needed for propagation. |

836 | computeDominanceAndLoopInfo(F); |

837 | |

838 | // Find equivalence classes. |

839 | findEquivalenceClasses(F); |

840 | |

841 | // Propagate weights to all edges. |

842 | propagateWeights(F); |

843 | } |

844 | |

845 | return Changed; |

846 | } |

847 | |

848 | template <typename BT> |

849 | void SampleProfileLoaderBaseImpl<BT>::emitCoverageRemarks(FunctionT &F) { |

850 | // If coverage checking was requested, compute it now. |

851 | const Function &Func = getFunction(F); |

852 | if (SampleProfileRecordCoverage) { |

853 | unsigned Used = CoverageTracker.countUsedRecords(Samples, PSI); |

854 | unsigned Total = CoverageTracker.countBodyRecords(Samples, PSI); |

855 | unsigned Coverage = CoverageTracker.computeCoverage(Used, Total); |

856 | if (Coverage < SampleProfileRecordCoverage) { |

857 | Func.getContext().diagnose(DiagnosticInfoSampleProfile( |

858 | Func.getSubprogram()->getFilename(), getFunctionLoc(F), |

859 | Twine(Used) + " of "+ Twine(Total) + " available profile records ("+ |

860 | Twine(Coverage) + "%) were applied", |

861 | DS_Warning)); |

862 | } |

863 | } |

864 | |

865 | if (SampleProfileSampleCoverage) { |

866 | uint64_t Used = CoverageTracker.getTotalUsedSamples(); |

867 | uint64_t Total = CoverageTracker.countBodySamples(Samples, PSI); |

868 | unsigned Coverage = CoverageTracker.computeCoverage(Used, Total); |

869 | if (Coverage < SampleProfileSampleCoverage) { |

870 | Func.getContext().diagnose(DiagnosticInfoSampleProfile( |

871 | Func.getSubprogram()->getFilename(), getFunctionLoc(F), |

872 | Twine(Used) + " of "+ Twine(Total) + " available profile samples ("+ |

873 | Twine(Coverage) + "%) were applied", |

874 | DS_Warning)); |

875 | } |

876 | } |

877 | } |

878 | |

879 | /// Get the line number for the function header. |

880 | /// |

881 | /// This looks up function \p F in the current compilation unit and |

882 | /// retrieves the line number where the function is defined. This is |

883 | /// line 0 for all the samples read from the profile file. Every line |

884 | /// number is relative to this line. |

885 | /// |

886 | /// \param F Function object to query. |

887 | /// |

888 | /// \returns the line number where \p F is defined. If it returns 0, |

889 | /// it means that there is no debug information available for \p F. |

890 | template <typename BT> |

891 | unsigned SampleProfileLoaderBaseImpl<BT>::getFunctionLoc(FunctionT &F) { |

892 | const Function &Func = getFunction(F); |

893 | if (DISubprogram *S = Func.getSubprogram()) |

894 | return S->getLine(); |

895 | |

896 | if (NoWarnSampleUnused) |

897 | return 0; |

898 | |

899 | // If the start of \p F is missing, emit a diagnostic to inform the user |

900 | // about the missed opportunity. |

901 | Func.getContext().diagnose(DiagnosticInfoSampleProfile( |

902 | "No debug information found in function "+ Func.getName() + |

903 | ": Function profile not used", |

904 | DS_Warning)); |

905 | return 0; |

906 | } |

907 | |

908 | template <typename BT> |

909 | void SampleProfileLoaderBaseImpl<BT>::computeDominanceAndLoopInfo( |

910 | FunctionT &F) { |

911 | DT.reset(new DominatorTreeT); |

912 | DT->recalculate(F); |

913 | |

914 | PDT.reset(new PostDominatorTree(F)); |

915 | |

916 | LI.reset(new LoopInfoT); |

917 | LI->analyze(*DT); |

918 | } |

919 | |

920 | #undef DEBUG_TYPE |

921 | |

922 | } // namespace llvm |

923 | #endif // LLVM_TRANSFORMS_UTILS_SAMPLEPROFILELOADERBASEIMPL_H |

924 |