bolt/lib/Passes/ReorderFunctions.cpp

   1 //===- bolt/Passes/ReorderFunctions.cpp - Function reordering pass --------===//
   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 ReorderFunctions class.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "bolt/Passes/ReorderFunctions.h"
  14 #include "bolt/Passes/HFSort.h"
  15 #include "bolt/Utils/Utils.h"
  16 #include "llvm/ADT/STLExtras.h"
  17 #include "llvm/Support/CommandLine.h"
  18 #include "llvm/Transforms/Utils/CodeLayout.h"
  19 #include <fstream>
  20
  21 #define DEBUG_TYPE "hfsort"
  22
  23 using namespace llvm;
  24
  25 namespace opts {
  26
  27 extern cl::OptionCategory BoltOptCategory;
  28 extern cl::opt<unsigned> Verbosity;
  29 extern cl::opt<uint32_t> RandomSeed;
  30
  31 extern size_t padFunction(const bolt::BinaryFunction &Function);
  32
  33 extern cl::opt<bolt::ReorderFunctions::ReorderType> ReorderFunctions;
  34 cl::opt<bolt::ReorderFunctions::ReorderType> ReorderFunctions(
  35     "reorder-functions",
  36     cl::desc("reorder and cluster functions (works only with relocations)"),
  37     cl::init(bolt::ReorderFunctions::RT_NONE),
  38     cl::values(clEnumValN(bolt::ReorderFunctions::RT_NONE, "none",
  39                           "do not reorder functions"),
  40                clEnumValN(bolt::ReorderFunctions::RT_EXEC_COUNT, "exec-count",
  41                           "order by execution count"),
  42                clEnumValN(bolt::ReorderFunctions::RT_HFSORT, "hfsort",
  43                           "use hfsort algorithm"),
  44                clEnumValN(bolt::ReorderFunctions::RT_HFSORT_PLUS, "hfsort+",
  45                           "use cache-directed sort"),
  46                clEnumValN(bolt::ReorderFunctions::RT_CDSORT, "cdsort",
  47                           "use cache-directed sort"),
  48                clEnumValN(bolt::ReorderFunctions::RT_PETTIS_HANSEN,
  49                           "pettis-hansen", "use Pettis-Hansen algorithm"),
  50                clEnumValN(bolt::ReorderFunctions::RT_RANDOM, "random",
  51                           "reorder functions randomly"),
  52                clEnumValN(bolt::ReorderFunctions::RT_USER, "user",
  53                           "use function order specified by -function-order")),
  54     cl::ZeroOrMore, cl::cat(BoltOptCategory),
  55     cl::callback([](const bolt::ReorderFunctions::ReorderType &option) {
  56       if (option == bolt::ReorderFunctions::RT_HFSORT_PLUS) {
  57         errs() << "BOLT-WARNING: '-reorder-functions=hfsort+' is deprecated,"
  58                << " please use '-reorder-functions=cdsort' instead\n";
  59         ReorderFunctions = bolt::ReorderFunctions::RT_CDSORT;
  60       }
  61     }));
  62
  63 static cl::opt<bool> ReorderFunctionsUseHotSize(
  64     "reorder-functions-use-hot-size",
  65     cl::desc("use a function's hot size when doing clustering"), cl::init(true),
  66     cl::cat(BoltOptCategory));
  67
  68 static cl::opt<std::string> FunctionOrderFile(
  69     "function-order",
  70     cl::desc("file containing an ordered list of functions to use for function "
  71              "reordering"),
  72     cl::cat(BoltOptCategory));
  73
  74 static cl::opt<std::string> GenerateFunctionOrderFile(
  75     "generate-function-order",
  76     cl::desc("file to dump the ordered list of functions to use for function "
  77              "reordering"),
  78     cl::cat(BoltOptCategory));
  79
  80 static cl::opt<std::string> LinkSectionsFile(
  81     "generate-link-sections",
  82     cl::desc("generate a list of function sections in a format suitable for "
  83              "inclusion in a linker script"),
  84     cl::cat(BoltOptCategory));
  85
  86 static cl::opt<bool>
  87     UseEdgeCounts("use-edge-counts",
  88                   cl::desc("use edge count data when doing clustering"),
  89                   cl::init(true), cl::cat(BoltOptCategory));
  90
  91 static cl::opt<bool> CgFromPerfData(
  92     "cg-from-perf-data",
  93     cl::desc("use perf data directly when constructing the call graph"
  94              " for stale functions"),
  95     cl::init(true), cl::ZeroOrMore, cl::cat(BoltOptCategory));
  96
  97 static cl::opt<bool> CgIgnoreRecursiveCalls(
  98     "cg-ignore-recursive-calls",
  99     cl::desc("ignore recursive calls when constructing the call graph"),
 100     cl::init(true), cl::cat(BoltOptCategory));
 101
 102 static cl::opt<bool> CgUseSplitHotSize(
 103     "cg-use-split-hot-size",
 104     cl::desc("use hot/cold data on basic blocks to determine hot sizes for "
 105              "call graph functions"),
 106     cl::init(false), cl::ZeroOrMore, cl::cat(BoltOptCategory));
 107
 108 } // namespace opts
 109
 110 namespace llvm {
 111 namespace bolt {
 112
 113 using NodeId = CallGraph::NodeId;
 114 using Arc = CallGraph::Arc;
 115 using Node = CallGraph::Node;
 116
 117 void ReorderFunctions::reorder(BinaryContext &BC,
 118                                std::vector<Cluster> &&Clusters,
 119                                std::map<uint64_t, BinaryFunction> &BFs) {
 120   std::vector<uint64_t> FuncAddr(Cg.numNodes()); // Just for computing stats
 121   uint64_t TotalSize = 0;
 122   uint32_t Index = 0;
 123
 124   // Set order of hot functions based on clusters.
 125   for (const Cluster &Cluster : Clusters) {
 126     for (const NodeId FuncId : Cluster.targets()) {
 127       Cg.nodeIdToFunc(FuncId)->setIndex(Index++);
 128       FuncAddr[FuncId] = TotalSize;
 129       TotalSize += Cg.size(FuncId);
 130     }
 131   }
 132
 133   // Assign valid index for functions with valid profile.
 134   for (auto &It : BFs) {
 135     BinaryFunction &BF = It.second;
 136     if (!BF.hasValidIndex() && BF.hasValidProfile())
 137       BF.setIndex(Index++);
 138   }
 139
 140   if (opts::ReorderFunctions == RT_NONE)
 141     return;
 142
 143   printStats(BC, Clusters, FuncAddr);
 144 }
 145
 146 void ReorderFunctions::printStats(BinaryContext &BC,
 147                                   const std::vector<Cluster> &Clusters,
 148                                   const std::vector<uint64_t> &FuncAddr) {
 149   if (opts::Verbosity == 0) {
 150 #ifndef NDEBUG
 151     if (!DebugFlag || !isCurrentDebugType("hfsort"))
 152       return;
 153 #else
 154     return;
 155 #endif
 156   }
 157
 158   bool PrintDetailed = opts::Verbosity > 1;
 159 #ifndef NDEBUG
 160   PrintDetailed |=
 161       (DebugFlag && isCurrentDebugType("hfsort") && opts::Verbosity > 0);
 162 #endif
 163   uint64_t TotalSize = 0;
 164   uint64_t CurPage = 0;
 165   uint64_t Hotfuncs = 0;
 166   double TotalDistance = 0;
 167   double TotalCalls = 0;
 168   double TotalCalls64B = 0;
 169   double TotalCalls4KB = 0;
 170   double TotalCalls2MB = 0;
 171   if (PrintDetailed)
 172     BC.outs() << "BOLT-INFO: Function reordering page layout\n"
 173               << "BOLT-INFO: ============== page 0 ==============\n";
 174   for (const Cluster &Cluster : Clusters) {
 175     if (PrintDetailed)
 176       BC.outs() << format(
 177           "BOLT-INFO: -------- density = %.3lf (%u / %u) --------\n",
 178           Cluster.density(), Cluster.samples(), Cluster.size());
 179
 180     for (NodeId FuncId : Cluster.targets()) {
 181       if (Cg.samples(FuncId) > 0) {
 182         Hotfuncs++;
 183
 184         if (PrintDetailed)
 185           BC.outs() << "BOLT-INFO: hot func " << *Cg.nodeIdToFunc(FuncId)
 186                     << " (" << Cg.size(FuncId) << ")\n";
 187
 188         uint64_t Dist = 0;
 189         uint64_t Calls = 0;
 190         for (NodeId Dst : Cg.successors(FuncId)) {
 191           if (FuncId == Dst) // ignore recursive calls in stats
 192             continue;
 193           const Arc &Arc = *Cg.findArc(FuncId, Dst);
 194           const auto D = std::abs(FuncAddr[Arc.dst()] -
 195                                   (FuncAddr[FuncId] + Arc.avgCallOffset()));
 196           const double W = Arc.weight();
 197           if (D < 64 && PrintDetailed && opts::Verbosity > 2)
 198             BC.outs() << "BOLT-INFO: short (" << D << "B) call:\n"
 199                       << "BOLT-INFO:   Src: " << *Cg.nodeIdToFunc(FuncId)
 200                       << "\n"
 201                       << "BOLT-INFO:   Dst: " << *Cg.nodeIdToFunc(Dst) << "\n"
 202                       << "BOLT-INFO:   Weight = " << W << "\n"
 203                       << "BOLT-INFO:   AvgOffset = " << Arc.avgCallOffset()
 204                       << "\n";
 205           Calls += W;
 206           if (D < 64)
 207             TotalCalls64B += W;
 208           if (D < 4096)
 209             TotalCalls4KB += W;
 210           if (D < (2 << 20))
 211             TotalCalls2MB += W;
 212           Dist += Arc.weight() * D;
 213           if (PrintDetailed)
 214             BC.outs() << format("BOLT-INFO: arc: %u [@%lu+%.1lf] -> %u [@%lu]: "
 215                                 "weight = %.0lf, callDist = %f\n",
 216                                 Arc.src(), FuncAddr[Arc.src()],
 217                                 Arc.avgCallOffset(), Arc.dst(),
 218                                 FuncAddr[Arc.dst()], Arc.weight(), D);
 219         }
 220         TotalCalls += Calls;
 221         TotalDistance += Dist;
 222         TotalSize += Cg.size(FuncId);
 223
 224         if (PrintDetailed) {
 225           BC.outs() << format("BOLT-INFO: start = %6u : avgCallDist = %lu : ",
 226                               TotalSize, Calls ? Dist / Calls : 0)
 227                     << Cg.nodeIdToFunc(FuncId)->getPrintName() << '\n';
 228           const uint64_t NewPage = TotalSize / HugePageSize;
 229           if (NewPage != CurPage) {
 230             CurPage = NewPage;
 231             BC.outs() << format(
 232                 "BOLT-INFO: ============== page %u ==============\n", CurPage);
 233           }
 234         }
 235       }
 236     }
 237   }
 238   BC.outs() << "BOLT-INFO: Function reordering stats\n"
 239             << format("BOLT-INFO:  Number of hot functions: %u\n"
 240                       "BOLT-INFO:  Number of clusters: %lu\n",
 241                       Hotfuncs, Clusters.size())
 242             << format("BOLT-INFO:  Final average call distance = %.1lf "
 243                       "(%.0lf / %.0lf)\n",
 244                       TotalCalls ? TotalDistance / TotalCalls : 0,
 245                       TotalDistance, TotalCalls)
 246             << format("BOLT-INFO:  Total Calls = %.0lf\n", TotalCalls);
 247   if (TotalCalls)
 248     BC.outs()
 249         << format("BOLT-INFO:  Total Calls within 64B = %.0lf (%.2lf%%)\n",
 250                   TotalCalls64B, 100 * TotalCalls64B / TotalCalls)
 251         << format("BOLT-INFO:  Total Calls within 4KB = %.0lf (%.2lf%%)\n",
 252                   TotalCalls4KB, 100 * TotalCalls4KB / TotalCalls)
 253         << format("BOLT-INFO:  Total Calls within 2MB = %.0lf (%.2lf%%)\n",
 254                   TotalCalls2MB, 100 * TotalCalls2MB / TotalCalls);
 255 }
 256
 257 Error ReorderFunctions::readFunctionOrderFile(
 258     std::vector<std::string> &FunctionNames) {
 259   std::ifstream FuncsFile(opts::FunctionOrderFile, std::ios::in);
 260   if (!FuncsFile)
 261     return createFatalBOLTError(Twine("Ordered functions file \"") +
 262                                 Twine(opts::FunctionOrderFile) +
 263                                 Twine("\" can't be opened."));
 264
 265   std::string FuncName;
 266   while (std::getline(FuncsFile, FuncName))
 267     FunctionNames.push_back(FuncName);
 268   return Error::success();
 269 }
 270
 271 Error ReorderFunctions::runOnFunctions(BinaryContext &BC) {
 272   auto &BFs = BC.getBinaryFunctions();
 273   if (opts::ReorderFunctions != RT_NONE &&
 274       opts::ReorderFunctions != RT_EXEC_COUNT &&
 275       opts::ReorderFunctions != RT_USER) {
 276     Cg = buildCallGraph(
 277         BC,
 278         [](const BinaryFunction &BF) {
 279           if (!BF.hasProfile())
 280             return true;
 281           if (BF.getState() != BinaryFunction::State::CFG)
 282             return true;
 283           return false;
 284         },
 285         opts::CgFromPerfData,
 286         /*IncludeSplitCalls=*/false, opts::ReorderFunctionsUseHotSize,
 287         opts::CgUseSplitHotSize, opts::UseEdgeCounts,
 288         opts::CgIgnoreRecursiveCalls);
 289     Cg.normalizeArcWeights();
 290   }
 291
 292   std::vector<Cluster> Clusters;
 293
 294   switch (opts::ReorderFunctions) {
 295   case RT_NONE:
 296     break;
 297   case RT_EXEC_COUNT: {
 298     std::vector<BinaryFunction *> SortedFunctions(BFs.size());
 299     llvm::transform(llvm::make_second_range(BFs), SortedFunctions.begin(),
 300                     [](BinaryFunction &BF) { return &BF; });
 301     llvm::stable_sort(SortedFunctions,
 302                       [&](const BinaryFunction *A, const BinaryFunction *B) {
 303                         if (A->isIgnored())
 304                           return false;
 305                         if (B->isIgnored())
 306                           return true;
 307                         const size_t PadA = opts::padFunction(*A);
 308                         const size_t PadB = opts::padFunction(*B);
 309                         if (!PadA || !PadB) {
 310                           if (PadA)
 311                             return true;
 312                           if (PadB)
 313                             return false;
 314                         }
 315                         if (!A->hasProfile())
 316                           return false;
 317                         if (!B->hasProfile())
 318                           return true;
 319                         return A->getExecutionCount() > B->getExecutionCount();
 320                       });
 321     uint32_t Index = 0;
 322     for (BinaryFunction *BF : SortedFunctions)
 323       if (BF->hasProfile()) {
 324         BF->setIndex(Index++);
 325         LLVM_DEBUG(if (opts::Verbosity > 1) {
 326           dbgs() << "BOLT-INFO: hot func " << BF->getPrintName() << " ("
 327                  << BF->getExecutionCount() << ")\n";
 328         });
 329       }
 330   } break;
 331   case RT_HFSORT:
 332     Clusters = clusterize(Cg);
 333     break;
 334   case RT_CDSORT: {
 335     // It is required that the sum of incoming arc weights is not greater
 336     // than the number of samples for every function. Ensuring the call graph
 337     // obeys the property before running the algorithm.
 338     Cg.adjustArcWeights();
 339
 340     // Initialize CFG nodes and their data
 341     std::vector<uint64_t> FuncSizes;
 342     std::vector<uint64_t> FuncCounts;
 343     std::vector<codelayout::EdgeCount> CallCounts;
 344     std::vector<uint64_t> CallOffsets;
 345     for (NodeId F = 0; F < Cg.numNodes(); ++F) {
 346       FuncSizes.push_back(Cg.size(F));
 347       FuncCounts.push_back(Cg.samples(F));
 348       for (NodeId Succ : Cg.successors(F)) {
 349         const Arc &Arc = *Cg.findArc(F, Succ);
 350         CallCounts.push_back({F, Succ, uint64_t(Arc.weight())});
 351         CallOffsets.push_back(uint64_t(Arc.avgCallOffset()));
 352       }
 353     }
 354
 355     // Run the layout algorithm.
 356     std::vector<uint64_t> Result = codelayout::computeCacheDirectedLayout(
 357         FuncSizes, FuncCounts, CallCounts, CallOffsets);
 358
 359     // Create a single cluster from the computed order of hot functions.
 360     std::vector<CallGraph::NodeId> NodeOrder(Result.begin(), Result.end());
 361     Clusters.emplace_back(Cluster(NodeOrder, Cg));
 362   } break;
 363   case RT_PETTIS_HANSEN:
 364     Clusters = pettisAndHansen(Cg);
 365     break;
 366   case RT_RANDOM:
 367     std::srand(opts::RandomSeed);
 368     Clusters = randomClusters(Cg);
 369     break;
 370   case RT_USER: {
 371     // Build LTOCommonNameMap
 372     StringMap<std::vector<uint64_t>> LTOCommonNameMap;
 373     for (const BinaryFunction &BF : llvm::make_second_range(BFs))
 374       for (StringRef Name : BF.getNames())
 375         if (std::optional<StringRef> LTOCommonName = getLTOCommonName(Name))
 376           LTOCommonNameMap[*LTOCommonName].push_back(BF.getAddress());
 377
 378     uint32_t Index = 0;
 379     uint32_t InvalidEntries = 0;
 380     std::vector<std::string> FunctionNames;
 381     if (Error E = readFunctionOrderFile(FunctionNames))
 382       return Error(std::move(E));
 383
 384     for (const std::string &Function : FunctionNames) {
 385       std::vector<uint64_t> FuncAddrs;
 386
 387       BinaryData *BD = BC.getBinaryDataByName(Function);
 388       if (!BD) {
 389         // If we can't find the main symbol name, look for alternates.
 390         uint32_t LocalID = 1;
 391         while (true) {
 392           const std::string FuncName = Function + "/" + std::to_string(LocalID);
 393           BD = BC.getBinaryDataByName(FuncName);
 394           if (BD)
 395             FuncAddrs.push_back(BD->getAddress());
 396           else
 397             break;
 398           LocalID++;
 399         }
 400         // Strip LTO suffixes
 401         if (std::optional<StringRef> CommonName = getLTOCommonName(Function))
 402           if (LTOCommonNameMap.contains(*CommonName))
 403             llvm::append_range(FuncAddrs, LTOCommonNameMap[*CommonName]);
 404       } else {
 405         FuncAddrs.push_back(BD->getAddress());
 406       }
 407
 408       if (FuncAddrs.empty()) {
 409         if (opts::Verbosity >= 1)
 410           BC.errs() << "BOLT-WARNING: Reorder functions: can't find function "
 411                     << "for " << Function << "\n";
 412         ++InvalidEntries;
 413         continue;
 414       }
 415
 416       for (const uint64_t FuncAddr : FuncAddrs) {
 417         const BinaryData *FuncBD = BC.getBinaryDataAtAddress(FuncAddr);
 418         assert(FuncBD);
 419
 420         BinaryFunction *BF = BC.getFunctionForSymbol(FuncBD->getSymbol());
 421         if (!BF) {
 422           if (opts::Verbosity >= 1)
 423             BC.errs() << "BOLT-WARNING: Reorder functions: can't find function "
 424                       << "for " << Function << "\n";
 425           ++InvalidEntries;
 426           break;
 427         }
 428         if (!BF->hasValidIndex())
 429           BF->setIndex(Index++);
 430         else if (opts::Verbosity > 0)
 431           BC.errs() << "BOLT-WARNING: Duplicate reorder entry for " << Function
 432                     << "\n";
 433       }
 434     }
 435     if (InvalidEntries)
 436       BC.errs() << "BOLT-WARNING: Reorder functions: can't find functions for "
 437                 << InvalidEntries << " entries in -function-order list\n";
 438   } break;
 439
 440   default:
 441     llvm_unreachable("unexpected layout type");
 442   }
 443
 444   reorder(BC, std::move(Clusters), BFs);
 445
 446   BC.HasFinalizedFunctionOrder = true;
 447
 448   std::unique_ptr<std::ofstream> FuncsFile;
 449   if (!opts::GenerateFunctionOrderFile.empty()) {
 450     FuncsFile = std::make_unique<std::ofstream>(opts::GenerateFunctionOrderFile,
 451                                                 std::ios::out);
 452     if (!FuncsFile) {
 453       BC.errs() << "BOLT-ERROR: ordered functions file "
 454                 << opts::GenerateFunctionOrderFile << " cannot be opened\n";
 455       return createFatalBOLTError("");
 456     }
 457   }
 458
 459   std::unique_ptr<std::ofstream> LinkSectionsFile;
 460   if (!opts::LinkSectionsFile.empty()) {
 461     LinkSectionsFile =
 462         std::make_unique<std::ofstream>(opts::LinkSectionsFile, std::ios::out);
 463     if (!LinkSectionsFile) {
 464       BC.errs() << "BOLT-ERROR: link sections file " << opts::LinkSectionsFile
 465                 << " cannot be opened\n";
 466       return createFatalBOLTError("");
 467     }
 468   }
 469
 470   if (FuncsFile || LinkSectionsFile) {
 471     std::vector<BinaryFunction *> SortedFunctions(BFs.size());
 472     llvm::transform(llvm::make_second_range(BFs), SortedFunctions.begin(),
 473                     [](BinaryFunction &BF) { return &BF; });
 474
 475     // Sort functions by index.
 476     llvm::stable_sort(SortedFunctions,
 477                       [](const BinaryFunction *A, const BinaryFunction *B) {
 478                         if (A->hasValidIndex() && B->hasValidIndex())
 479                           return A->getIndex() < B->getIndex();
 480                         if (A->hasValidIndex() && !B->hasValidIndex())
 481                           return true;
 482                         if (!A->hasValidIndex() && B->hasValidIndex())
 483                           return false;
 484                         return A->getAddress() < B->getAddress();
 485                       });
 486
 487     for (const BinaryFunction *Func : SortedFunctions) {
 488       if (!Func->hasValidIndex())
 489         break;
 490       if (Func->isPLTFunction())
 491         continue;
 492
 493       if (FuncsFile)
 494         *FuncsFile << Func->getOneName().str() << '\n';
 495
 496       if (LinkSectionsFile) {
 497         const char *Indent = "";
 498         std::vector<StringRef> AllNames = Func->getNames();
 499         llvm::sort(AllNames);
 500         for (StringRef Name : AllNames) {
 501           const size_t SlashPos = Name.find('/');
 502           if (SlashPos != std::string::npos) {
 503             // Avoid duplicates for local functions.
 504             if (Name.find('/', SlashPos + 1) != std::string::npos)
 505               continue;
 506             Name = Name.substr(0, SlashPos);
 507           }
 508           *LinkSectionsFile << Indent << ".text." << Name.str() << '\n';
 509           Indent = " ";
 510         }
 511       }
 512     }
 513
 514     if (FuncsFile) {
 515       FuncsFile->close();
 516       BC.outs() << "BOLT-INFO: dumped function order to "
 517                 << opts::GenerateFunctionOrderFile << '\n';
 518     }
 519
 520     if (LinkSectionsFile) {
 521       LinkSectionsFile->close();
 522       BC.outs() << "BOLT-INFO: dumped linker section order to "
 523                 << opts::LinkSectionsFile << '\n';
 524     }
 525   }
 526   return Error::success();
 527 }
 528
 529 } // namespace bolt
 530 } // namespace llvm