bolt/lib/Passes/ContinuityStats.cpp

   1 //===- bolt/Passes/ContinuityStats.cpp --------------------------*- 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 // This file implements the continuity stats calculation pass.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "bolt/Passes/ContinuityStats.h"
  14 #include "bolt/Core/BinaryBasicBlock.h"
  15 #include "bolt/Core/BinaryFunction.h"
  16 #include "bolt/Utils/CommandLineOpts.h"
  17 #include "llvm/Support/CommandLine.h"
  18 #include <queue>
  19 #include <unordered_map>
  20 #include <unordered_set>
  21
  22 #define DEBUG_TYPE "bolt-opts"
  23
  24 using namespace llvm;
  25 using namespace bolt;
  26
  27 namespace opts {
  28 extern cl::opt<unsigned> Verbosity;
  29 cl::opt<unsigned> NumFunctionsForContinuityCheck(
  30     "num-functions-for-continuity-check",
  31     cl::desc("number of hottest functions to print aggregated "
  32              "CFG discontinuity stats of."),
  33     cl::init(1000), cl::ZeroOrMore, cl::Hidden, cl::cat(BoltOptCategory));
  34 } // namespace opts
  35
  36 namespace {
  37 using FunctionListType = std::vector<const BinaryFunction *>;
  38 using function_iterator = FunctionListType::iterator;
  39
  40 template <typename T>
  41 void printDistribution(raw_ostream &OS, std::vector<T> &values,
  42                        bool Fraction = false) {
  43   if (values.empty())
  44     return;
  45   // Sort values from largest to smallest and print the MAX, TOP 1%, 5%, 10%,
  46   // 20%, 50%, 80%, MIN. If Fraction is true, then values are printed as
  47   // fractions instead of integers.
  48   std::sort(values.begin(), values.end());
  49
  50   auto printLine = [&](std::string Text, double Percent) {
  51     int Rank = int(values.size() * (1.0 - Percent / 100));
  52     if (Percent == 0)
  53       Rank = values.size() - 1;
  54     if (Fraction)
  55       OS << "  " << Text << std::string(9 - Text.length(), ' ') << ": "
  56          << format("%.2lf%%", values[Rank] * 100) << "\n";
  57     else
  58       OS << "  " << Text << std::string(9 - Text.length(), ' ') << ": "
  59          << values[Rank] << "\n";
  60   };
  61
  62   printLine("MAX", 0);
  63   const int percentages[] = {1, 5, 10, 20, 50, 80};
  64   for (size_t i = 0; i < sizeof(percentages) / sizeof(percentages[0]); ++i) {
  65     printLine("TOP " + std::to_string(percentages[i]) + "%", percentages[i]);
  66   }
  67   printLine("MIN", 100);
  68 }
  69
  70 void printCFGContinuityStats(raw_ostream &OS,
  71                              iterator_range<function_iterator> &Functions) {
  72   // Given a perfect profile, every positive-execution-count BB should be
  73   // connected to an entry of the function through a positive-execution-count
  74   // directed path in the control flow graph.
  75   std::vector<size_t> NumUnreachables;
  76   std::vector<size_t> SumECUnreachables;
  77   std::vector<double> FractionECUnreachables;
  78
  79   for (auto it = Functions.begin(); it != Functions.end(); ++it) {
  80     const BinaryFunction *Function = *it;
  81     if (Function->size() <= 1)
  82       continue;
  83
  84     // Compute the sum of all BB execution counts (ECs).
  85     size_t NumPosECBBs = 0;
  86     size_t SumAllBBEC = 0;
  87     for (const BinaryBasicBlock &BB : *Function) {
  88       const size_t BBEC = BB.getKnownExecutionCount();
  89       NumPosECBBs += BBEC > 0 ? 1 : 0;
  90       SumAllBBEC += BBEC;
  91     }
  92
  93     // Perform BFS on subgraph of CFG induced by positive weight edges.
  94     // Compute the number of BBs reachable from the entry(s) of the function and
  95     // the sum of their execution counts (ECs).
  96     std::unordered_map<unsigned, const BinaryBasicBlock *> IndexToBB;
  97     std::unordered_set<unsigned> Visited;
  98     std::queue<unsigned> Queue;
  99     for (const BinaryBasicBlock &BB : *Function) {
 100       // Make sure BB.getIndex() is not already in IndexToBB.
 101       assert(IndexToBB.find(BB.getIndex()) == IndexToBB.end());
 102       IndexToBB[BB.getIndex()] = &BB;
 103       if (BB.isEntryPoint() && BB.getKnownExecutionCount() > 0) {
 104         Queue.push(BB.getIndex());
 105         Visited.insert(BB.getIndex());
 106       }
 107     }
 108     while (!Queue.empty()) {
 109       const unsigned BBIndex = Queue.front();
 110       const BinaryBasicBlock *BB = IndexToBB[BBIndex];
 111       Queue.pop();
 112       auto SuccBIIter = BB->branch_info_begin();
 113       for (const BinaryBasicBlock *Succ : BB->successors()) {
 114         const uint64_t Count = SuccBIIter->Count;
 115         if (Count == BinaryBasicBlock::COUNT_NO_PROFILE || Count == 0) {
 116           ++SuccBIIter;
 117           continue;
 118         }
 119         if (!Visited.insert(Succ->getIndex()).second) {
 120           ++SuccBIIter;
 121           continue;
 122         }
 123         Queue.push(Succ->getIndex());
 124         ++SuccBIIter;
 125       }
 126     }
 127
 128     const size_t NumReachableBBs = Visited.size();
 129
 130     // Loop through Visited, and sum the corresponding BBs' execution counts
 131     // (ECs).
 132     size_t SumReachableBBEC = 0;
 133     for (const unsigned BBIndex : Visited) {
 134       const BinaryBasicBlock *BB = IndexToBB[BBIndex];
 135       SumReachableBBEC += BB->getKnownExecutionCount();
 136     }
 137
 138     const size_t NumPosECBBsUnreachableFromEntry =
 139         NumPosECBBs - NumReachableBBs;
 140     const size_t SumUnreachableBBEC = SumAllBBEC - SumReachableBBEC;
 141     const double FractionECUnreachable =
 142         (double)SumUnreachableBBEC / SumAllBBEC;
 143
 144     if (opts::Verbosity >= 2 && FractionECUnreachable >= 0.05) {
 145       OS << "Non-trivial CFG discontinuity observed in function "
 146          << Function->getPrintName() << "\n";
 147       LLVM_DEBUG(Function->dump());
 148     }
 149
 150     NumUnreachables.push_back(NumPosECBBsUnreachableFromEntry);
 151     SumECUnreachables.push_back(SumUnreachableBBEC);
 152     FractionECUnreachables.push_back(FractionECUnreachable);
 153   }
 154
 155   if (FractionECUnreachables.empty())
 156     return;
 157
 158   std::sort(FractionECUnreachables.begin(), FractionECUnreachables.end());
 159   const int Rank = int(FractionECUnreachables.size() * 0.95);
 160   OS << format("top 5%% function CFG discontinuity is %.2lf%%\n",
 161                FractionECUnreachables[Rank] * 100);
 162
 163   if (opts::Verbosity >= 1) {
 164     OS << "abbreviations: EC = execution count, POS BBs = positive EC BBs\n"
 165        << "distribution of NUM(unreachable POS BBs) among all focal "
 166           "functions\n";
 167     printDistribution(OS, NumUnreachables);
 168
 169     OS << "distribution of SUM_EC(unreachable POS BBs) among all focal "
 170           "functions\n";
 171     printDistribution(OS, SumECUnreachables);
 172
 173     OS << "distribution of [(SUM_EC(unreachable POS BBs) / SUM_EC(all "
 174           "POS BBs))] among all focal functions\n";
 175     printDistribution(OS, FractionECUnreachables, /*Fraction=*/true);
 176   }
 177 }
 178
 179 void printAll(BinaryContext &BC, FunctionListType &ValidFunctions,
 180               size_t NumTopFunctions) {
 181   // Sort the list of functions by execution counts (reverse).
 182   llvm::sort(ValidFunctions,
 183              [&](const BinaryFunction *A, const BinaryFunction *B) {
 184                return A->getKnownExecutionCount() > B->getKnownExecutionCount();
 185              });
 186
 187   const size_t RealNumTopFunctions =
 188       std::min(NumTopFunctions, ValidFunctions.size());
 189
 190   iterator_range<function_iterator> Functions(
 191       ValidFunctions.begin(), ValidFunctions.begin() + RealNumTopFunctions);
 192
 193   BC.outs() << format("BOLT-INFO: among the hottest %zu functions ",
 194                       RealNumTopFunctions);
 195   printCFGContinuityStats(BC.outs(), Functions);
 196
 197   // Print more detailed bucketed stats if requested.
 198   if (opts::Verbosity >= 1 && RealNumTopFunctions >= 5) {
 199     const size_t PerBucketSize = RealNumTopFunctions / 5;
 200     BC.outs() << format(
 201         "Detailed stats for 5 buckets, each with  %zu functions:\n",
 202         PerBucketSize);
 203
 204     // For each bucket, print the CFG continuity stats of the functions in the
 205     // bucket.
 206     for (size_t BucketIndex = 0; BucketIndex < 5; ++BucketIndex) {
 207       const size_t StartIndex = BucketIndex * PerBucketSize;
 208       const size_t EndIndex = StartIndex + PerBucketSize;
 209       iterator_range<function_iterator> Functions(
 210           ValidFunctions.begin() + StartIndex,
 211           ValidFunctions.begin() + EndIndex);
 212       const size_t MaxFunctionExecutionCount =
 213           ValidFunctions[StartIndex]->getKnownExecutionCount();
 214       const size_t MinFunctionExecutionCount =
 215           ValidFunctions[EndIndex - 1]->getKnownExecutionCount();
 216       BC.outs() << format("----------------\n|   Bucket %zu:  "
 217                           "|\n----------------\n",
 218                           BucketIndex + 1)
 219                 << format(
 220                        "execution counts of the %zu functions in the bucket: "
 221                        "%zu-%zu\n",
 222                        EndIndex - StartIndex, MinFunctionExecutionCount,
 223                        MaxFunctionExecutionCount);
 224       printCFGContinuityStats(BC.outs(), Functions);
 225     }
 226   }
 227 }
 228 } // namespace
 229
 230 bool PrintContinuityStats::shouldOptimize(const BinaryFunction &BF) const {
 231   if (BF.empty() || !BF.hasValidProfile())
 232     return false;
 233
 234   return BinaryFunctionPass::shouldOptimize(BF);
 235 }
 236
 237 Error PrintContinuityStats::runOnFunctions(BinaryContext &BC) {
 238   // Create a list of functions with valid profiles.
 239   FunctionListType ValidFunctions;
 240   for (const auto &BFI : BC.getBinaryFunctions()) {
 241     const BinaryFunction *Function = &BFI.second;
 242     if (PrintContinuityStats::shouldOptimize(*Function))
 243       ValidFunctions.push_back(Function);
 244   }
 245   if (ValidFunctions.empty() || opts::NumFunctionsForContinuityCheck == 0)
 246     return Error::success();
 247
 248   printAll(BC, ValidFunctions, opts::NumFunctionsForContinuityCheck);
 249   return Error::success();
 250 }