328 lines · cpp
1//===- bolt/Core/DynoStats.cpp - Dynamic execution stats ------------------===//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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the DynoStats class.10//11//===----------------------------------------------------------------------===//12 13#include "bolt/Core/DynoStats.h"14#include "bolt/Core/BinaryBasicBlock.h"15#include "bolt/Core/BinaryFunction.h"16#include "llvm/ADT/StringRef.h"17#include "llvm/Support/CommandLine.h"18#include "llvm/Support/Debug.h"19#include "llvm/Support/raw_ostream.h"20#include <algorithm>21#include <string>22 23#undef DEBUG_TYPE24#define DEBUG_TYPE "bolt"25 26using namespace llvm;27using namespace bolt;28 29namespace opts {30 31extern cl::OptionCategory BoltCategory;32 33static cl::opt<uint32_t>34DynoStatsScale("dyno-stats-scale",35 cl::desc("scale to be applied while reporting dyno stats"),36 cl::Optional,37 cl::init(1),38 cl::Hidden,39 cl::cat(BoltCategory));40 41static cl::opt<uint32_t>42PrintDynoOpcodeStat("print-dyno-opcode-stats",43 cl::desc("print per instruction opcode dyno stats and the function"44 "names:BB offsets of the nth highest execution counts"),45 cl::init(0),46 cl::Hidden,47 cl::cat(BoltCategory));48 49} // namespace opts50 51namespace llvm {52namespace bolt {53 54bool DynoStats::operator<(const DynoStats &Other) const {55 return std::lexicographical_compare(56 &Stats[FIRST_DYNO_STAT], &Stats[LAST_DYNO_STAT],57 &Other.Stats[FIRST_DYNO_STAT], &Other.Stats[LAST_DYNO_STAT]);58}59 60bool DynoStats::operator==(const DynoStats &Other) const {61 return std::equal(&Stats[FIRST_DYNO_STAT], &Stats[LAST_DYNO_STAT],62 &Other.Stats[FIRST_DYNO_STAT]);63}64 65bool DynoStats::lessThan(const DynoStats &Other,66 ArrayRef<Category> Keys) const {67 return std::lexicographical_compare(68 Keys.begin(), Keys.end(), Keys.begin(), Keys.end(),69 [this, &Other](const Category A, const Category) {70 return Stats[A] < Other.Stats[A];71 });72}73 74void DynoStats::print(raw_ostream &OS, const DynoStats *Other,75 MCInstPrinter *Printer) const {76 auto printStatWithDelta = [&](const std::string &Name, uint64_t Stat,77 uint64_t OtherStat) {78 OS << format("%'20lld : ", Stat * opts::DynoStatsScale) << Name;79 if (Other) {80 if (Stat != OtherStat) {81 OtherStat = std::max(OtherStat, uint64_t(1)); // to prevent divide by 082 OS << format(" (%+.1f%%)", ((float)Stat - (float)OtherStat) * 100.0 /83 (float)(OtherStat));84 } else {85 OS << " (=)";86 }87 }88 OS << '\n';89 };90 91 for (auto Stat = DynoStats::FIRST_DYNO_STAT + 1;92 Stat < DynoStats::LAST_DYNO_STAT; ++Stat) {93 94 if (!PrintAArch64Stats && Stat == DynoStats::VENEER_CALLS_AARCH64)95 continue;96 97 printStatWithDelta(Desc[Stat], Stats[Stat], Other ? (*Other)[Stat] : 0);98 }99 if (opts::PrintDynoOpcodeStat && Printer) {100 OS << "\nProgram-wide opcode histogram:\n";101 OS << " Opcode, Execution Count, Max Exec Count, "102 "Function Name:Offset ...\n";103 std::vector<std::pair<uint64_t, unsigned>> SortedHistogram;104 for (const OpcodeStatTy &Stat : OpcodeHistogram)105 SortedHistogram.emplace_back(Stat.second.first, Stat.first);106 107 // Sort using lexicographic ordering108 llvm::sort(SortedHistogram);109 110 // Dump in ascending order: Start with Opcode with Highest execution111 // count.112 for (auto &Stat : llvm::reverse(SortedHistogram)) {113 OS << format("%20s,%'18lld", Printer->getOpcodeName(Stat.second).data(),114 Stat.first * opts::DynoStatsScale);115 auto It = OpcodeHistogram.find(Stat.second);116 assert(It != OpcodeHistogram.end());117 MaxOpcodeHistogramTy MaxMultiMap = It->second.second;118 // Start with function name:BB offset with highest execution count.119 for (auto &Max : llvm::reverse(MaxMultiMap)) {120 OS << format(", %'18lld, ", Max.first * opts::DynoStatsScale)121 << Max.second.first.str() << ':' << Max.second.second;122 }123 OS << '\n';124 }125 }126}127 128void DynoStats::operator+=(const DynoStats &Other) {129 for (auto Stat = DynoStats::FIRST_DYNO_STAT + 1;130 Stat < DynoStats::LAST_DYNO_STAT; ++Stat) {131 Stats[Stat] += Other[Stat];132 }133 for (const OpcodeStatTy &Stat : Other.OpcodeHistogram) {134 auto I = OpcodeHistogram.find(Stat.first);135 if (I == OpcodeHistogram.end()) {136 OpcodeHistogram.emplace(Stat);137 } else {138 // Merge other histograms, log only the opts::PrintDynoOpcodeStat'th139 // maximum counts.140 I->second.first += Stat.second.first;141 auto &MMap = I->second.second;142 auto &OtherMMap = Stat.second.second;143 auto Size = MMap.size();144 assert(Size <= opts::PrintDynoOpcodeStat);145 for (auto OtherMMapPair : llvm::reverse(OtherMMap)) {146 if (Size++ >= opts::PrintDynoOpcodeStat) {147 auto First = MMap.begin();148 if (OtherMMapPair.first <= First->first)149 break;150 MMap.erase(First);151 }152 MMap.emplace(OtherMMapPair);153 }154 }155 }156}157 158DynoStats getDynoStats(BinaryFunction &BF) {159 auto &BC = BF.getBinaryContext();160 161 DynoStats Stats(/*PrintAArch64Stats*/ BC.isAArch64());162 163 // Return empty-stats about the function we don't completely understand.164 if (!BF.isSimple() || !BF.hasValidProfile() || !BF.hasCanonicalCFG())165 return Stats;166 167 // Update enumeration of basic blocks for correct detection of branch'168 // direction.169 BF.getLayout().updateLayoutIndices();170 171 for (BinaryBasicBlock *const BB : BF.getLayout().blocks()) {172 // The basic block execution count equals to the sum of incoming branch173 // frequencies. This may deviate from the sum of outgoing branches of the174 // basic block especially since the block may contain a function that175 // does not return or a function that throws an exception.176 const uint64_t BBExecutionCount = BB->getKnownExecutionCount();177 178 // Ignore empty blocks and blocks that were not executed.179 if (BB->getNumNonPseudos() == 0 || BBExecutionCount == 0)180 continue;181 182 // Count AArch64 linker-inserted veneers183 if (BF.isAArch64Veneer())184 Stats[DynoStats::VENEER_CALLS_AARCH64] += BF.getKnownExecutionCount();185 186 // Count various instruction types by iterating through all instructions.187 // When -print-dyno-opcode-stats is on, count per each opcode and record188 // maximum execution counts.189 for (const MCInst &Instr : *BB) {190 if (opts::PrintDynoOpcodeStat) {191 unsigned Opcode = Instr.getOpcode();192 auto I = Stats.OpcodeHistogram.find(Opcode);193 if (I == Stats.OpcodeHistogram.end()) {194 DynoStats::MaxOpcodeHistogramTy MMap;195 MMap.emplace(BBExecutionCount,196 std::make_pair(BF.getOneName(), BB->getOffset()));197 Stats.OpcodeHistogram.emplace(Opcode,198 std::make_pair(BBExecutionCount, MMap));199 } else {200 I->second.first += BBExecutionCount;201 bool Insert = true;202 if (I->second.second.size() == opts::PrintDynoOpcodeStat) {203 auto First = I->second.second.begin();204 if (First->first < BBExecutionCount)205 I->second.second.erase(First);206 else207 Insert = false;208 }209 if (Insert) {210 I->second.second.emplace(211 BBExecutionCount,212 std::make_pair(BF.getOneName(), BB->getOffset()));213 }214 }215 }216 217 if (BC.MIB->mayStore(Instr)) {218 Stats[DynoStats::STORES] += BBExecutionCount;219 }220 if (BC.MIB->mayLoad(Instr)) {221 Stats[DynoStats::LOADS] += BBExecutionCount;222 }223 if (!BC.MIB->isCall(Instr))224 continue;225 226 uint64_t CallFreq = BBExecutionCount;227 if (BC.MIB->getConditionalTailCall(Instr)) {228 CallFreq =229 BC.MIB->getAnnotationWithDefault<uint64_t>(Instr, "CTCTakenCount");230 }231 Stats[DynoStats::FUNCTION_CALLS] += CallFreq;232 if (BC.MIB->isIndirectCall(Instr)) {233 Stats[DynoStats::INDIRECT_CALLS] += CallFreq;234 } else if (const MCSymbol *CallSymbol = BC.MIB->getTargetSymbol(Instr)) {235 const BinaryFunction *BF = BC.getFunctionForSymbol(CallSymbol);236 if (BF && BF->isPLTFunction()) {237 Stats[DynoStats::PLT_CALLS] += CallFreq;238 239 // We don't process PLT functions and hence have to adjust relevant240 // dynostats here for:241 //242 // jmp *GOT_ENTRY(%rip)243 //244 // NOTE: this is arch-specific.245 Stats[DynoStats::FUNCTION_CALLS] += CallFreq;246 Stats[DynoStats::INDIRECT_CALLS] += CallFreq;247 Stats[DynoStats::LOADS] += CallFreq;248 Stats[DynoStats::INSTRUCTIONS] += CallFreq;249 }250 }251 }252 253 Stats[DynoStats::INSTRUCTIONS] += BB->getNumNonPseudos() * BBExecutionCount;254 255 // Jump tables.256 const MCInst *LastInstr = BB->getLastNonPseudoInstr();257 if (BC.MIB->getJumpTable(*LastInstr)) {258 Stats[DynoStats::JUMP_TABLE_BRANCHES] += BBExecutionCount;259 LLVM_DEBUG(260 static uint64_t MostFrequentJT;261 if (BBExecutionCount > MostFrequentJT) {262 MostFrequentJT = BBExecutionCount;263 dbgs() << "BOLT-INFO: most frequently executed jump table is in "264 << "function " << BF << " in basic block " << BB->getName()265 << " executed totally " << BBExecutionCount << " times.\n";266 }267 );268 continue;269 }270 271 if (BC.MIB->isIndirectBranch(*LastInstr) && !BC.MIB->isCall(*LastInstr)) {272 Stats[DynoStats::UNKNOWN_INDIRECT_BRANCHES] += BBExecutionCount;273 continue;274 }275 276 // Update stats for branches.277 const MCSymbol *TBB = nullptr;278 const MCSymbol *FBB = nullptr;279 MCInst *CondBranch = nullptr;280 MCInst *UncondBranch = nullptr;281 if (!BB->analyzeBranch(TBB, FBB, CondBranch, UncondBranch))282 continue;283 284 if (!CondBranch && !UncondBranch)285 continue;286 287 // Simple unconditional branch.288 if (!CondBranch) {289 Stats[DynoStats::UNCOND_BRANCHES] += BBExecutionCount;290 continue;291 }292 293 // CTCs: instruction annotations could be stripped, hence check the number294 // of successors to identify conditional tail calls.295 if (BB->succ_size() == 1) {296 if (BB->branch_info_begin() != BB->branch_info_end())297 Stats[DynoStats::UNCOND_BRANCHES] += BB->branch_info_begin()->Count;298 continue;299 }300 301 // Conditional branch that could be followed by an unconditional branch.302 uint64_t TakenCount = BB->getTakenBranchInfo().Count;303 if (TakenCount == BinaryBasicBlock::COUNT_NO_PROFILE)304 TakenCount = 0;305 306 uint64_t NonTakenCount = BB->getFallthroughBranchInfo().Count;307 if (NonTakenCount == BinaryBasicBlock::COUNT_NO_PROFILE)308 NonTakenCount = 0;309 310 if (BF.isForwardBranch(BB, BB->getConditionalSuccessor(true))) {311 Stats[DynoStats::FORWARD_COND_BRANCHES] += BBExecutionCount;312 Stats[DynoStats::FORWARD_COND_BRANCHES_TAKEN] += TakenCount;313 } else {314 Stats[DynoStats::BACKWARD_COND_BRANCHES] += BBExecutionCount;315 Stats[DynoStats::BACKWARD_COND_BRANCHES_TAKEN] += TakenCount;316 }317 318 if (UncondBranch) {319 Stats[DynoStats::UNCOND_BRANCHES] += NonTakenCount;320 }321 }322 323 return Stats;324}325 326} // namespace bolt327} // namespace llvm328