bolt/lib/Passes/Instrumentation.cpp

   1 //===- bolt/Passes/Instrumentation.cpp ------------------------------------===//
   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 Instrumentation class.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "bolt/Passes/Instrumentation.h"
  14 #include "bolt/Core/ParallelUtilities.h"
  15 #include "bolt/RuntimeLibs/InstrumentationRuntimeLibrary.h"
  16 #include "bolt/Utils/CommandLineOpts.h"
  17 #include "bolt/Utils/Utils.h"
  18 #include "llvm/Support/CommandLine.h"
  19 #include "llvm/Support/RWMutex.h"
  20 #include <stack>
  21
  22 #define DEBUG_TYPE "bolt-instrumentation"
  23
  24 using namespace llvm;
  25
  26 namespace opts {
  27 extern cl::OptionCategory BoltInstrCategory;
  28
  29 cl::opt<std::string> InstrumentationFilename(
  30     "instrumentation-file",
  31     cl::desc("file name where instrumented profile will be saved (default: "
  32              "/tmp/prof.fdata)"),
  33     cl::init("/tmp/prof.fdata"), cl::Optional, cl::cat(BoltInstrCategory));
  34
  35 cl::opt<std::string> InstrumentationBinpath(
  36     "instrumentation-binpath",
  37     cl::desc("path to instumented binary in case if /proc/self/map_files "
  38              "is not accessible due to access restriction issues"),
  39     cl::Optional, cl::cat(BoltInstrCategory));
  40
  41 cl::opt<bool> InstrumentationFileAppendPID(
  42     "instrumentation-file-append-pid",
  43     cl::desc("append PID to saved profile file name (default: false)"),
  44     cl::init(false), cl::Optional, cl::cat(BoltInstrCategory));
  45
  46 cl::opt<bool> ConservativeInstrumentation(
  47     "conservative-instrumentation",
  48     cl::desc("disable instrumentation optimizations that sacrifice profile "
  49              "accuracy (for debugging, default: false)"),
  50     cl::init(false), cl::Optional, cl::cat(BoltInstrCategory));
  51
  52 cl::opt<uint32_t> InstrumentationSleepTime(
  53     "instrumentation-sleep-time",
  54     cl::desc("interval between profile writes (default: 0 = write only at "
  55              "program end).  This is useful for service workloads when you "
  56              "want to dump profile every X minutes or if you are killing the "
  57              "program and the profile is not being dumped at the end."),
  58     cl::init(0), cl::Optional, cl::cat(BoltInstrCategory));
  59
  60 cl::opt<bool> InstrumentationNoCountersClear(
  61     "instrumentation-no-counters-clear",
  62     cl::desc("Don't clear counters across dumps "
  63              "(use with instrumentation-sleep-time option)"),
  64     cl::init(false), cl::Optional, cl::cat(BoltInstrCategory));
  65
  66 cl::opt<bool> InstrumentationWaitForks(
  67     "instrumentation-wait-forks",
  68     cl::desc("Wait until all forks of instrumented process will finish "
  69              "(use with instrumentation-sleep-time option)"),
  70     cl::init(false), cl::Optional, cl::cat(BoltInstrCategory));
  71
  72 cl::opt<bool>
  73     InstrumentHotOnly("instrument-hot-only",
  74                       cl::desc("only insert instrumentation on hot functions "
  75                                "(needs profile, default: false)"),
  76                       cl::init(false), cl::Optional,
  77                       cl::cat(BoltInstrCategory));
  78
  79 cl::opt<bool> InstrumentCalls("instrument-calls",
  80                               cl::desc("record profile for inter-function "
  81                                        "control flow activity (default: true)"),
  82                               cl::init(true), cl::Optional,
  83                               cl::cat(BoltInstrCategory));
  84 } // namespace opts
  85
  86 namespace llvm {
  87 namespace bolt {
  88
  89 static bool hasAArch64ExclusiveMemop(BinaryFunction &Function) {
  90   // FIXME ARMv8-a architecture reference manual says that software must avoid
  91   // having any explicit memory accesses between exclusive load and associated
  92   // store instruction. So for now skip instrumentation for functions that have
  93   // these instructions, since it might lead to runtime deadlock.
  94   BinaryContext &BC = Function.getBinaryContext();
  95   for (const BinaryBasicBlock &BB : Function)
  96     for (const MCInst &Inst : BB)
  97       if (BC.MIB->isAArch64Exclusive(Inst)) {
  98         if (opts::Verbosity >= 1)
  99           outs() << "BOLT-INSTRUMENTER: Function " << Function
 100                  << " has exclusive instructions, skip instrumentation\n";
 101         return true;
 102       }
 103
 104   return false;
 105 }
 106
 107 uint32_t Instrumentation::getFunctionNameIndex(const BinaryFunction &Function) {
 108   auto Iter = FuncToStringIdx.find(&Function);
 109   if (Iter != FuncToStringIdx.end())
 110     return Iter->second;
 111   size_t Idx = Summary->StringTable.size();
 112   FuncToStringIdx.emplace(std::make_pair(&Function, Idx));
 113   Summary->StringTable.append(getEscapedName(Function.getOneName()));
 114   Summary->StringTable.append(1, '\0');
 115   return Idx;
 116 }
 117
 118 bool Instrumentation::createCallDescription(FunctionDescription &FuncDesc,
 119                                             const BinaryFunction &FromFunction,
 120                                             uint32_t From, uint32_t FromNodeID,
 121                                             const BinaryFunction &ToFunction,
 122                                             uint32_t To, bool IsInvoke) {
 123   CallDescription CD;
 124   // Ordinarily, we don't augment direct calls with an explicit counter, except
 125   // when forced to do so or when we know this callee could be throwing
 126   // exceptions, in which case there is no other way to accurately record its
 127   // frequency.
 128   bool ForceInstrumentation = opts::ConservativeInstrumentation || IsInvoke;
 129   CD.FromLoc.FuncString = getFunctionNameIndex(FromFunction);
 130   CD.FromLoc.Offset = From;
 131   CD.FromNode = FromNodeID;
 132   CD.Target = &ToFunction;
 133   CD.ToLoc.FuncString = getFunctionNameIndex(ToFunction);
 134   CD.ToLoc.Offset = To;
 135   CD.Counter = ForceInstrumentation ? Summary->Counters.size() : 0xffffffff;
 136   if (ForceInstrumentation)
 137     ++DirectCallCounters;
 138   FuncDesc.Calls.emplace_back(CD);
 139   return ForceInstrumentation;
 140 }
 141
 142 void Instrumentation::createIndCallDescription(
 143     const BinaryFunction &FromFunction, uint32_t From) {
 144   IndCallDescription ICD;
 145   ICD.FromLoc.FuncString = getFunctionNameIndex(FromFunction);
 146   ICD.FromLoc.Offset = From;
 147   Summary->IndCallDescriptions.emplace_back(ICD);
 148 }
 149
 150 void Instrumentation::createIndCallTargetDescription(
 151     const BinaryFunction &ToFunction, uint32_t To) {
 152   IndCallTargetDescription ICD;
 153   ICD.ToLoc.FuncString = getFunctionNameIndex(ToFunction);
 154   ICD.ToLoc.Offset = To;
 155   ICD.Target = &ToFunction;
 156   Summary->IndCallTargetDescriptions.emplace_back(ICD);
 157 }
 158
 159 bool Instrumentation::createEdgeDescription(FunctionDescription &FuncDesc,
 160                                             const BinaryFunction &FromFunction,
 161                                             uint32_t From, uint32_t FromNodeID,
 162                                             const BinaryFunction &ToFunction,
 163                                             uint32_t To, uint32_t ToNodeID,
 164                                             bool Instrumented) {
 165   EdgeDescription ED;
 166   auto Result = FuncDesc.EdgesSet.insert(std::make_pair(FromNodeID, ToNodeID));
 167   // Avoid creating duplicated edge descriptions. This happens in CFGs where a
 168   // block jumps to its fall-through.
 169   if (Result.second == false)
 170     return false;
 171   ED.FromLoc.FuncString = getFunctionNameIndex(FromFunction);
 172   ED.FromLoc.Offset = From;
 173   ED.FromNode = FromNodeID;
 174   ED.ToLoc.FuncString = getFunctionNameIndex(ToFunction);
 175   ED.ToLoc.Offset = To;
 176   ED.ToNode = ToNodeID;
 177   ED.Counter = Instrumented ? Summary->Counters.size() : 0xffffffff;
 178   if (Instrumented)
 179     ++BranchCounters;
 180   FuncDesc.Edges.emplace_back(ED);
 181   return Instrumented;
 182 }
 183
 184 void Instrumentation::createLeafNodeDescription(FunctionDescription &FuncDesc,
 185                                                 uint32_t Node) {
 186   InstrumentedNode IN;
 187   IN.Node = Node;
 188   IN.Counter = Summary->Counters.size();
 189   ++LeafNodeCounters;
 190   FuncDesc.LeafNodes.emplace_back(IN);
 191 }
 192
 193 InstructionListType
 194 Instrumentation::createInstrumentationSnippet(BinaryContext &BC, bool IsLeaf) {
 195   auto L = BC.scopeLock();
 196   MCSymbol *Label = BC.Ctx->createNamedTempSymbol("InstrEntry");
 197   Summary->Counters.emplace_back(Label);
 198   return BC.MIB->createInstrIncMemory(Label, BC.Ctx.get(), IsLeaf,
 199                                       BC.AsmInfo->getCodePointerSize());
 200 }
 201
 202 // Helper instruction sequence insertion function
 203 static BinaryBasicBlock::iterator
 204 insertInstructions(InstructionListType &Instrs, BinaryBasicBlock &BB,
 205                    BinaryBasicBlock::iterator Iter) {
 206   for (MCInst &NewInst : Instrs) {
 207     Iter = BB.insertInstruction(Iter, NewInst);
 208     ++Iter;
 209   }
 210   return Iter;
 211 }
 212
 213 void Instrumentation::instrumentLeafNode(BinaryBasicBlock &BB,
 214                                          BinaryBasicBlock::iterator Iter,
 215                                          bool IsLeaf,
 216                                          FunctionDescription &FuncDesc,
 217                                          uint32_t Node) {
 218   createLeafNodeDescription(FuncDesc, Node);
 219   InstructionListType CounterInstrs = createInstrumentationSnippet(
 220       BB.getFunction()->getBinaryContext(), IsLeaf);
 221   insertInstructions(CounterInstrs, BB, Iter);
 222 }
 223
 224 void Instrumentation::instrumentIndirectTarget(BinaryBasicBlock &BB,
 225                                                BinaryBasicBlock::iterator &Iter,
 226                                                BinaryFunction &FromFunction,
 227                                                uint32_t From) {
 228   auto L = FromFunction.getBinaryContext().scopeLock();
 229   const size_t IndCallSiteID = Summary->IndCallDescriptions.size();
 230   createIndCallDescription(FromFunction, From);
 231
 232   BinaryContext &BC = FromFunction.getBinaryContext();
 233   bool IsTailCall = BC.MIB->isTailCall(*Iter);
 234   InstructionListType CounterInstrs = BC.MIB->createInstrumentedIndirectCall(
 235       std::move(*Iter),
 236       IsTailCall ? IndTailCallHandlerExitBBFunction->getSymbol()
 237                  : IndCallHandlerExitBBFunction->getSymbol(),
 238       IndCallSiteID, &*BC.Ctx);
 239
 240   Iter = BB.eraseInstruction(Iter);
 241   Iter = insertInstructions(CounterInstrs, BB, Iter);
 242   --Iter;
 243 }
 244
 245 bool Instrumentation::instrumentOneTarget(
 246     SplitWorklistTy &SplitWorklist, SplitInstrsTy &SplitInstrs,
 247     BinaryBasicBlock::iterator &Iter, BinaryFunction &FromFunction,
 248     BinaryBasicBlock &FromBB, uint32_t From, BinaryFunction &ToFunc,
 249     BinaryBasicBlock *TargetBB, uint32_t ToOffset, bool IsLeaf, bool IsInvoke,
 250     FunctionDescription *FuncDesc, uint32_t FromNodeID, uint32_t ToNodeID) {
 251   BinaryContext &BC = FromFunction.getBinaryContext();
 252   {
 253     auto L = BC.scopeLock();
 254     bool Created = true;
 255     if (!TargetBB)
 256       Created = createCallDescription(*FuncDesc, FromFunction, From, FromNodeID,
 257                                       ToFunc, ToOffset, IsInvoke);
 258     else
 259       Created = createEdgeDescription(*FuncDesc, FromFunction, From, FromNodeID,
 260                                       ToFunc, ToOffset, ToNodeID,
 261                                       /*Instrumented=*/true);
 262     if (!Created)
 263       return false;
 264   }
 265
 266   InstructionListType CounterInstrs = createInstrumentationSnippet(BC, IsLeaf);
 267
 268   const MCInst &Inst = *Iter;
 269   if (BC.MIB->isCall(Inst)) {
 270     // This code handles both
 271     // - (regular) inter-function calls (cross-function control transfer),
 272     // - (rare) intra-function calls (function-local control transfer)
 273     Iter = insertInstructions(CounterInstrs, FromBB, Iter);
 274     return true;
 275   }
 276
 277   if (!TargetBB || !FuncDesc)
 278     return false;
 279
 280   // Indirect branch, conditional branches or fall-throughs
 281   // Regular cond branch, put counter at start of target block
 282   //
 283   // N.B.: (FromBB != TargetBBs) checks below handle conditional jumps where
 284   // we can't put the instrumentation counter in this block because not all
 285   // paths that reach it at this point will be taken and going to the target.
 286   if (TargetBB->pred_size() == 1 && &FromBB != TargetBB &&
 287       !TargetBB->isEntryPoint()) {
 288     insertInstructions(CounterInstrs, *TargetBB, TargetBB->begin());
 289     return true;
 290   }
 291   if (FromBB.succ_size() == 1 && &FromBB != TargetBB) {
 292     Iter = insertInstructions(CounterInstrs, FromBB, Iter);
 293     return true;
 294   }
 295   // Critical edge, create BB and put counter there
 296   SplitWorklist.emplace_back(&FromBB, TargetBB);
 297   SplitInstrs.emplace_back(std::move(CounterInstrs));
 298   return true;
 299 }
 300
 301 void Instrumentation::instrumentFunction(BinaryFunction &Function,
 302                                          MCPlusBuilder::AllocatorIdTy AllocId) {
 303   if (Function.hasUnknownControlFlow())
 304     return;
 305
 306   BinaryContext &BC = Function.getBinaryContext();
 307   if (BC.isMachO() && Function.hasName("___GLOBAL_init_65535/1"))
 308     return;
 309
 310   if (BC.isAArch64() && hasAArch64ExclusiveMemop(Function))
 311     return;
 312
 313   SplitWorklistTy SplitWorklist;
 314   SplitInstrsTy SplitInstrs;
 315
 316   FunctionDescription *FuncDesc = nullptr;
 317   {
 318     std::unique_lock<llvm::sys::RWMutex> L(FDMutex);
 319     Summary->FunctionDescriptions.emplace_back();
 320     FuncDesc = &Summary->FunctionDescriptions.back();
 321   }
 322
 323   FuncDesc->Function = &Function;
 324   Function.disambiguateJumpTables(AllocId);
 325   Function.deleteConservativeEdges();
 326
 327   std::unordered_map<const BinaryBasicBlock *, uint32_t> BBToID;
 328   uint32_t Id = 0;
 329   for (auto BBI = Function.begin(); BBI != Function.end(); ++BBI) {
 330     BBToID[&*BBI] = Id++;
 331   }
 332   std::unordered_set<const BinaryBasicBlock *> VisitedSet;
 333   // DFS to establish edges we will use for a spanning tree. Edges in the
 334   // spanning tree can be instrumentation-free since their count can be
 335   // inferred by solving flow equations on a bottom-up traversal of the tree.
 336   // Exit basic blocks are always instrumented so we start the traversal with
 337   // a minimum number of defined variables to make the equation solvable.
 338   std::stack<std::pair<const BinaryBasicBlock *, BinaryBasicBlock *>> Stack;
 339   std::unordered_map<const BinaryBasicBlock *,
 340                      std::set<const BinaryBasicBlock *>>
 341       STOutSet;
 342   for (auto BBI = Function.getLayout().block_rbegin();
 343        BBI != Function.getLayout().block_rend(); ++BBI) {
 344     if ((*BBI)->isEntryPoint() || (*BBI)->isLandingPad()) {
 345       Stack.push(std::make_pair(nullptr, *BBI));
 346       if (opts::InstrumentCalls && (*BBI)->isEntryPoint()) {
 347         EntryNode E;
 348         E.Node = BBToID[&**BBI];
 349         E.Address = (*BBI)->getInputOffset();
 350         FuncDesc->EntryNodes.emplace_back(E);
 351         createIndCallTargetDescription(Function, (*BBI)->getInputOffset());
 352       }
 353     }
 354   }
 355
 356   // Modified version of BinaryFunction::dfs() to build a spanning tree
 357   if (!opts::ConservativeInstrumentation) {
 358     while (!Stack.empty()) {
 359       BinaryBasicBlock *BB;
 360       const BinaryBasicBlock *Pred;
 361       std::tie(Pred, BB) = Stack.top();
 362       Stack.pop();
 363       if (llvm::is_contained(VisitedSet, BB))
 364         continue;
 365
 366       VisitedSet.insert(BB);
 367       if (Pred)
 368         STOutSet[Pred].insert(BB);
 369
 370       for (BinaryBasicBlock *SuccBB : BB->successors())
 371         Stack.push(std::make_pair(BB, SuccBB));
 372     }
 373   }
 374
 375   // Determine whether this is a leaf function, which needs special
 376   // instructions to protect the red zone
 377   bool IsLeafFunction = true;
 378   DenseSet<const BinaryBasicBlock *> InvokeBlocks;
 379   for (const BinaryBasicBlock &BB : Function) {
 380     for (const MCInst &Inst : BB) {
 381       if (BC.MIB->isCall(Inst)) {
 382         if (BC.MIB->isInvoke(Inst))
 383           InvokeBlocks.insert(&BB);
 384         if (!BC.MIB->isTailCall(Inst))
 385           IsLeafFunction = false;
 386       }
 387     }
 388   }
 389
 390   for (auto BBI = Function.begin(), BBE = Function.end(); BBI != BBE; ++BBI) {
 391     BinaryBasicBlock &BB = *BBI;
 392     bool HasUnconditionalBranch = false;
 393     bool HasJumpTable = false;
 394     bool IsInvokeBlock = InvokeBlocks.count(&BB) > 0;
 395
 396     for (auto I = BB.begin(); I != BB.end(); ++I) {
 397       const MCInst &Inst = *I;
 398       if (!BC.MIB->getOffset(Inst))
 399         continue;
 400
 401       const bool IsJumpTable = Function.getJumpTable(Inst);
 402       if (IsJumpTable)
 403         HasJumpTable = true;
 404       else if (BC.MIB->isUnconditionalBranch(Inst))
 405         HasUnconditionalBranch = true;
 406       else if ((!BC.MIB->isCall(Inst) && !BC.MIB->isConditionalBranch(Inst)) ||
 407                BC.MIB->isUnsupportedBranch(Inst))
 408         continue;
 409
 410       const uint32_t FromOffset = *BC.MIB->getOffset(Inst);
 411       const MCSymbol *Target = BC.MIB->getTargetSymbol(Inst);
 412       BinaryBasicBlock *TargetBB = Function.getBasicBlockForLabel(Target);
 413       uint32_t ToOffset = TargetBB ? TargetBB->getInputOffset() : 0;
 414       BinaryFunction *TargetFunc =
 415           TargetBB ? &Function : BC.getFunctionForSymbol(Target);
 416       if (TargetFunc && BC.MIB->isCall(Inst)) {
 417         if (opts::InstrumentCalls) {
 418           const BinaryBasicBlock *ForeignBB =
 419               TargetFunc->getBasicBlockForLabel(Target);
 420           if (ForeignBB)
 421             ToOffset = ForeignBB->getInputOffset();
 422           instrumentOneTarget(SplitWorklist, SplitInstrs, I, Function, BB,
 423                               FromOffset, *TargetFunc, TargetBB, ToOffset,
 424                               IsLeafFunction, IsInvokeBlock, FuncDesc,
 425                               BBToID[&BB]);
 426         }
 427         continue;
 428       }
 429       if (TargetFunc) {
 430         // Do not instrument edges in the spanning tree
 431         if (llvm::is_contained(STOutSet[&BB], TargetBB)) {
 432           auto L = BC.scopeLock();
 433           createEdgeDescription(*FuncDesc, Function, FromOffset, BBToID[&BB],
 434                                 Function, ToOffset, BBToID[TargetBB],
 435                                 /*Instrumented=*/false);
 436           continue;
 437         }
 438         instrumentOneTarget(SplitWorklist, SplitInstrs, I, Function, BB,
 439                             FromOffset, *TargetFunc, TargetBB, ToOffset,
 440                             IsLeafFunction, IsInvokeBlock, FuncDesc,
 441                             BBToID[&BB], BBToID[TargetBB]);
 442         continue;
 443       }
 444
 445       if (IsJumpTable) {
 446         for (BinaryBasicBlock *&Succ : BB.successors()) {
 447           // Do not instrument edges in the spanning tree
 448           if (llvm::is_contained(STOutSet[&BB], &*Succ)) {
 449             auto L = BC.scopeLock();
 450             createEdgeDescription(*FuncDesc, Function, FromOffset, BBToID[&BB],
 451                                   Function, Succ->getInputOffset(),
 452                                   BBToID[&*Succ], /*Instrumented=*/false);
 453             continue;
 454           }
 455           instrumentOneTarget(
 456               SplitWorklist, SplitInstrs, I, Function, BB, FromOffset, Function,
 457               &*Succ, Succ->getInputOffset(), IsLeafFunction, IsInvokeBlock,
 458               FuncDesc, BBToID[&BB], BBToID[&*Succ]);
 459         }
 460         continue;
 461       }
 462
 463       // Handle indirect calls -- could be direct calls with unknown targets
 464       // or secondary entry points of known functions, so check it is indirect
 465       // to be sure.
 466       if (opts::InstrumentCalls && BC.MIB->isIndirectCall(*I))
 467         instrumentIndirectTarget(BB, I, Function, FromOffset);
 468
 469     } // End of instructions loop
 470
 471     // Instrument fallthroughs (when the direct jump instruction is missing)
 472     if (!HasUnconditionalBranch && !HasJumpTable && BB.succ_size() > 0 &&
 473         BB.size() > 0) {
 474       BinaryBasicBlock *FTBB = BB.getFallthrough();
 475       assert(FTBB && "expected valid fall-through basic block");
 476       auto I = BB.begin();
 477       auto LastInstr = BB.end();
 478       --LastInstr;
 479       while (LastInstr != I && BC.MIB->isPseudo(*LastInstr))
 480         --LastInstr;
 481       uint32_t FromOffset = 0;
 482       // The last instruction in the BB should have an annotation, except
 483       // if it was branching to the end of the function as a result of
 484       // __builtin_unreachable(), in which case it was deleted by fixBranches.
 485       // Ignore this case. FIXME: force fixBranches() to preserve the offset.
 486       if (!BC.MIB->getOffset(*LastInstr))
 487         continue;
 488       FromOffset = *BC.MIB->getOffset(*LastInstr);
 489
 490       // Do not instrument edges in the spanning tree
 491       if (llvm::is_contained(STOutSet[&BB], FTBB)) {
 492         auto L = BC.scopeLock();
 493         createEdgeDescription(*FuncDesc, Function, FromOffset, BBToID[&BB],
 494                               Function, FTBB->getInputOffset(), BBToID[FTBB],
 495                               /*Instrumented=*/false);
 496         continue;
 497       }
 498       instrumentOneTarget(SplitWorklist, SplitInstrs, I, Function, BB,
 499                           FromOffset, Function, FTBB, FTBB->getInputOffset(),
 500                           IsLeafFunction, IsInvokeBlock, FuncDesc, BBToID[&BB],
 501                           BBToID[FTBB]);
 502     }
 503   } // End of BBs loop
 504
 505   // Instrument spanning tree leaves
 506   if (!opts::ConservativeInstrumentation) {
 507     for (auto BBI = Function.begin(), BBE = Function.end(); BBI != BBE; ++BBI) {
 508       BinaryBasicBlock &BB = *BBI;
 509       if (STOutSet[&BB].size() == 0)
 510         instrumentLeafNode(BB, BB.begin(), IsLeafFunction, *FuncDesc,
 511                            BBToID[&BB]);
 512     }
 513   }
 514
 515   // Consume list of critical edges: split them and add instrumentation to the
 516   // newly created BBs
 517   auto Iter = SplitInstrs.begin();
 518   for (std::pair<BinaryBasicBlock *, BinaryBasicBlock *> &BBPair :
 519        SplitWorklist) {
 520     BinaryBasicBlock *NewBB = Function.splitEdge(BBPair.first, BBPair.second);
 521     NewBB->addInstructions(Iter->begin(), Iter->end());
 522     ++Iter;
 523   }
 524
 525   // Unused now
 526   FuncDesc->EdgesSet.clear();
 527 }
 528
 529 void Instrumentation::runOnFunctions(BinaryContext &BC) {
 530   const unsigned Flags = BinarySection::getFlags(/*IsReadOnly=*/false,
 531                                                  /*IsText=*/false,
 532                                                  /*IsAllocatable=*/true);
 533   BC.registerOrUpdateSection(".bolt.instr.counters", ELF::SHT_PROGBITS, Flags,
 534                              nullptr, 0, 1);
 535
 536   BC.registerOrUpdateNoteSection(".bolt.instr.tables", nullptr, 0,
 537                                  /*Alignment=*/1,
 538                                  /*IsReadOnly=*/true, ELF::SHT_NOTE);
 539
 540   Summary->IndCallCounterFuncPtr =
 541       BC.Ctx->getOrCreateSymbol("__bolt_ind_call_counter_func_pointer");
 542   Summary->IndTailCallCounterFuncPtr =
 543       BC.Ctx->getOrCreateSymbol("__bolt_ind_tailcall_counter_func_pointer");
 544
 545   createAuxiliaryFunctions(BC);
 546
 547   ParallelUtilities::PredicateTy SkipPredicate = [&](const BinaryFunction &BF) {
 548     return (!BF.isSimple() || BF.isIgnored() ||
 549             (opts::InstrumentHotOnly && !BF.getKnownExecutionCount()));
 550   };
 551
 552   ParallelUtilities::WorkFuncWithAllocTy WorkFun =
 553       [&](BinaryFunction &BF, MCPlusBuilder::AllocatorIdTy AllocatorId) {
 554         instrumentFunction(BF, AllocatorId);
 555       };
 556
 557   ParallelUtilities::runOnEachFunctionWithUniqueAllocId(
 558       BC, ParallelUtilities::SchedulingPolicy::SP_INST_QUADRATIC, WorkFun,
 559       SkipPredicate, "instrumentation", /* ForceSequential=*/true);
 560
 561   if (BC.isMachO()) {
 562     if (BC.StartFunctionAddress) {
 563       BinaryFunction *Main =
 564           BC.getBinaryFunctionAtAddress(*BC.StartFunctionAddress);
 565       assert(Main && "Entry point function not found");
 566       BinaryBasicBlock &BB = Main->front();
 567
 568       ErrorOr<BinarySection &> SetupSection =
 569           BC.getUniqueSectionByName("I__setup");
 570       if (!SetupSection) {
 571         llvm::errs() << "Cannot find I__setup section\n";
 572         exit(1);
 573       }
 574       MCSymbol *Target = BC.registerNameAtAddress(
 575           "__bolt_instr_setup", SetupSection->getAddress(), 0, 0);
 576       MCInst NewInst;
 577       BC.MIB->createCall(NewInst, Target, BC.Ctx.get());
 578       BB.insertInstruction(BB.begin(), std::move(NewInst));
 579     } else {
 580       llvm::errs() << "BOLT-WARNING: Entry point not found\n";
 581     }
 582
 583     if (BinaryData *BD = BC.getBinaryDataByName("___GLOBAL_init_65535/1")) {
 584       BinaryFunction *Ctor = BC.getBinaryFunctionAtAddress(BD->getAddress());
 585       assert(Ctor && "___GLOBAL_init_65535 function not found");
 586       BinaryBasicBlock &BB = Ctor->front();
 587       ErrorOr<BinarySection &> FiniSection =
 588           BC.getUniqueSectionByName("I__fini");
 589       if (!FiniSection) {
 590         llvm::errs() << "Cannot find I__fini section\n";
 591         exit(1);
 592       }
 593       MCSymbol *Target = BC.registerNameAtAddress(
 594           "__bolt_instr_fini", FiniSection->getAddress(), 0, 0);
 595       auto IsLEA = [&BC](const MCInst &Inst) { return BC.MIB->isLEA64r(Inst); };
 596       const auto LEA = std::find_if(
 597           std::next(llvm::find_if(reverse(BB), IsLEA)), BB.rend(), IsLEA);
 598       LEA->getOperand(4).setExpr(
 599           MCSymbolRefExpr::create(Target, MCSymbolRefExpr::VK_None, *BC.Ctx));
 600     } else {
 601       llvm::errs() << "BOLT-WARNING: ___GLOBAL_init_65535 not found\n";
 602     }
 603   }
 604
 605   setupRuntimeLibrary(BC);
 606 }
 607
 608 void Instrumentation::createAuxiliaryFunctions(BinaryContext &BC) {
 609   auto createSimpleFunction =
 610       [&](StringRef Title, InstructionListType Instrs) -> BinaryFunction * {
 611     BinaryFunction *Func = BC.createInjectedBinaryFunction(std::string(Title));
 612
 613     std::vector<std::unique_ptr<BinaryBasicBlock>> BBs;
 614     BBs.emplace_back(Func->createBasicBlock());
 615     BBs.back()->addInstructions(Instrs.begin(), Instrs.end());
 616     BBs.back()->setCFIState(0);
 617     Func->insertBasicBlocks(nullptr, std::move(BBs),
 618                             /*UpdateLayout=*/true,
 619                             /*UpdateCFIState=*/false);
 620     Func->updateState(BinaryFunction::State::CFG_Finalized);
 621     return Func;
 622   };
 623
 624   // Here we are creating a set of functions to handle BB entry/exit.
 625   // IndCallHandlerExitBB contains instructions to finish handling traffic to an
 626   // indirect call. We pass it to createInstrumentedIndCallHandlerEntryBB(),
 627   // which will check if a pointer to runtime library traffic accounting
 628   // function was initialized (it is done during initialization of runtime
 629   // library). If it is so - calls it. Then this routine returns to normal
 630   // execution by jumping to exit BB.
 631   BinaryFunction *IndCallHandlerExitBB =
 632       createSimpleFunction("__bolt_instr_ind_call_handler",
 633                            BC.MIB->createInstrumentedIndCallHandlerExitBB());
 634
 635   IndCallHandlerExitBBFunction =
 636       createSimpleFunction("__bolt_instr_ind_call_handler_func",
 637                            BC.MIB->createInstrumentedIndCallHandlerEntryBB(
 638                                Summary->IndCallCounterFuncPtr,
 639                                IndCallHandlerExitBB->getSymbol(), &*BC.Ctx));
 640
 641   BinaryFunction *IndTailCallHandlerExitBB = createSimpleFunction(
 642       "__bolt_instr_ind_tail_call_handler",
 643       BC.MIB->createInstrumentedIndTailCallHandlerExitBB());
 644
 645   IndTailCallHandlerExitBBFunction = createSimpleFunction(
 646       "__bolt_instr_ind_tailcall_handler_func",
 647       BC.MIB->createInstrumentedIndCallHandlerEntryBB(
 648           Summary->IndTailCallCounterFuncPtr,
 649           IndTailCallHandlerExitBB->getSymbol(), &*BC.Ctx));
 650
 651   createSimpleFunction("__bolt_num_counters_getter",
 652                        BC.MIB->createNumCountersGetter(BC.Ctx.get()));
 653   createSimpleFunction("__bolt_instr_locations_getter",
 654                        BC.MIB->createInstrLocationsGetter(BC.Ctx.get()));
 655   createSimpleFunction("__bolt_instr_tables_getter",
 656                        BC.MIB->createInstrTablesGetter(BC.Ctx.get()));
 657   createSimpleFunction("__bolt_instr_num_funcs_getter",
 658                        BC.MIB->createInstrNumFuncsGetter(BC.Ctx.get()));
 659
 660   if (BC.isELF()) {
 661     if (BC.StartFunctionAddress) {
 662       BinaryFunction *Start =
 663           BC.getBinaryFunctionAtAddress(*BC.StartFunctionAddress);
 664       assert(Start && "Entry point function not found");
 665       const MCSymbol *StartSym = Start->getSymbol();
 666       createSimpleFunction(
 667           "__bolt_start_trampoline",
 668           BC.MIB->createSymbolTrampoline(StartSym, BC.Ctx.get()));
 669     }
 670     if (BC.FiniFunctionAddress) {
 671       BinaryFunction *Fini =
 672           BC.getBinaryFunctionAtAddress(*BC.FiniFunctionAddress);
 673       assert(Fini && "Finalization function not found");
 674       const MCSymbol *FiniSym = Fini->getSymbol();
 675       createSimpleFunction(
 676           "__bolt_fini_trampoline",
 677           BC.MIB->createSymbolTrampoline(FiniSym, BC.Ctx.get()));
 678     } else {
 679       // Create dummy return function for trampoline to avoid issues
 680       // with unknown symbol in runtime library. E.g. for static PIE
 681       // executable
 682       createSimpleFunction("__bolt_fini_trampoline",
 683                            BC.MIB->createDummyReturnFunction(BC.Ctx.get()));
 684     }
 685   }
 686 }
 687
 688 void Instrumentation::setupRuntimeLibrary(BinaryContext &BC) {
 689   uint32_t FuncDescSize = Summary->getFDSize();
 690
 691   outs() << "BOLT-INSTRUMENTER: Number of indirect call site descriptors: "
 692          << Summary->IndCallDescriptions.size() << "\n";
 693   outs() << "BOLT-INSTRUMENTER: Number of indirect call target descriptors: "
 694          << Summary->IndCallTargetDescriptions.size() << "\n";
 695   outs() << "BOLT-INSTRUMENTER: Number of function descriptors: "
 696          << Summary->FunctionDescriptions.size() << "\n";
 697   outs() << "BOLT-INSTRUMENTER: Number of branch counters: " << BranchCounters
 698          << "\n";
 699   outs() << "BOLT-INSTRUMENTER: Number of ST leaf node counters: "
 700          << LeafNodeCounters << "\n";
 701   outs() << "BOLT-INSTRUMENTER: Number of direct call counters: "
 702          << DirectCallCounters << "\n";
 703   outs() << "BOLT-INSTRUMENTER: Total number of counters: "
 704          << Summary->Counters.size() << "\n";
 705   outs() << "BOLT-INSTRUMENTER: Total size of counters: "
 706          << (Summary->Counters.size() * 8) << " bytes (static alloc memory)\n";
 707   outs() << "BOLT-INSTRUMENTER: Total size of string table emitted: "
 708          << Summary->StringTable.size() << " bytes in file\n";
 709   outs() << "BOLT-INSTRUMENTER: Total size of descriptors: "
 710          << (FuncDescSize +
 711              Summary->IndCallDescriptions.size() * sizeof(IndCallDescription) +
 712              Summary->IndCallTargetDescriptions.size() *
 713                  sizeof(IndCallTargetDescription))
 714          << " bytes in file\n";
 715   outs() << "BOLT-INSTRUMENTER: Profile will be saved to file "
 716          << opts::InstrumentationFilename << "\n";
 717
 718   InstrumentationRuntimeLibrary *RtLibrary =
 719       static_cast<InstrumentationRuntimeLibrary *>(BC.getRuntimeLibrary());
 720   assert(RtLibrary && "instrumentation runtime library object must be set");
 721   RtLibrary->setSummary(std::move(Summary));
 722 }
 723 } // namespace bolt
 724 } // namespace llvm