llvm/lib/CodeGen/MIRFSDiscriminator.cpp

   1 //===-------- MIRFSDiscriminator.cpp: Flow Sensitive Discriminator --------===//
   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 provides the implementation of a machine pass that adds the flow
  10 // sensitive discriminator to the instruction debug information.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/CodeGen/MIRFSDiscriminator.h"
  15 #include "llvm/ADT/DenseMap.h"
  16 #include "llvm/ADT/DenseSet.h"
  17 #include "llvm/Analysis/BlockFrequencyInfoImpl.h"
  18 #include "llvm/CodeGen/Passes.h"
  19 #include "llvm/IR/DebugInfoMetadata.h"
  20 #include "llvm/IR/Function.h"
  21 #include "llvm/IR/Module.h"
  22 #include "llvm/IR/PseudoProbe.h"
  23 #include "llvm/InitializePasses.h"
  24 #include "llvm/Support/CommandLine.h"
  25 #include "llvm/Support/Debug.h"
  26 #include "llvm/Support/raw_ostream.h"
  27 #include "llvm/Support/xxhash.h"
  28 #include "llvm/Transforms/Utils/SampleProfileLoaderBaseUtil.h"
  29
  30 using namespace llvm;
  31 using namespace sampleprof;
  32 using namespace sampleprofutil;
  33
  34 #define DEBUG_TYPE "mirfs-discriminators"
  35
  36 // TODO(xur): Remove this option and related code once we make true as the
  37 // default.
  38 namespace llvm {
  39 cl::opt<bool> ImprovedFSDiscriminator(
  40     "improved-fs-discriminator", cl::Hidden, cl::init(false),
  41     cl::desc("New FS discriminators encoding (incompatible with the original "
  42              "encoding)"));
  43 }
  44
  45 char MIRAddFSDiscriminators::ID = 0;
  46
  47 INITIALIZE_PASS(MIRAddFSDiscriminators, DEBUG_TYPE,
  48                 "Add MIR Flow Sensitive Discriminators",
  49                 /* cfg = */ false, /* is_analysis = */ false)
  50
  51 char &llvm::MIRAddFSDiscriminatorsID = MIRAddFSDiscriminators::ID;
  52
  53 FunctionPass *llvm::createMIRAddFSDiscriminatorsPass(FSDiscriminatorPass P) {
  54   return new MIRAddFSDiscriminators(P);
  55 }
  56
  57 // TODO(xur): Remove this once we switch to ImprovedFSDiscriminator.
  58 // Compute a hash value using debug line number, and the line numbers from the
  59 // inline stack.
  60 static uint64_t getCallStackHashV0(const MachineBasicBlock &BB,
  61                                    const MachineInstr &MI,
  62                                    const DILocation *DIL) {
  63   auto updateHash = [](const StringRef &Str) -> uint64_t {
  64     if (Str.empty())
  65       return 0;
  66     return MD5Hash(Str);
  67   };
  68   uint64_t Ret = updateHash(std::to_string(DIL->getLine()));
  69   Ret ^= updateHash(BB.getName());
  70   Ret ^= updateHash(DIL->getScope()->getSubprogram()->getLinkageName());
  71   for (DIL = DIL->getInlinedAt(); DIL; DIL = DIL->getInlinedAt()) {
  72     Ret ^= updateHash(std::to_string(DIL->getLine()));
  73     Ret ^= updateHash(DIL->getScope()->getSubprogram()->getLinkageName());
  74   }
  75   return Ret;
  76 }
  77
  78 static uint64_t getCallStackHash(const DILocation *DIL) {
  79   auto hashCombine = [](const uint64_t Seed, const uint64_t Val) {
  80     std::hash<uint64_t> Hasher;
  81     return Seed ^ (Hasher(Val) + 0x9e3779b9 + (Seed << 6) + (Seed >> 2));
  82   };
  83   uint64_t Ret = 0;
  84   for (DIL = DIL->getInlinedAt(); DIL; DIL = DIL->getInlinedAt()) {
  85     Ret = hashCombine(Ret, xxh3_64bits(ArrayRef<uint8_t>(DIL->getLine())));
  86     Ret = hashCombine(Ret, xxh3_64bits(DIL->getSubprogramLinkageName()));
  87   }
  88   return Ret;
  89 }
  90
  91 // Traverse the CFG and assign FD discriminators. If two instructions
  92 // have the same lineno and discriminator, but residing in different BBs,
  93 // the latter instruction will get a new discriminator value. The new
  94 // discriminator keeps the existing discriminator value but sets new bits
  95 // b/w LowBit and HighBit.
  96 bool MIRAddFSDiscriminators::runOnMachineFunction(MachineFunction &MF) {
  97   if (!EnableFSDiscriminator)
  98     return false;
  99
 100   bool HasPseudoProbe = MF.getFunction().getParent()->getNamedMetadata(
 101       PseudoProbeDescMetadataName);
 102
 103   if (!HasPseudoProbe && !MF.getFunction().shouldEmitDebugInfoForProfiling())
 104     return false;
 105
 106   bool Changed = false;
 107   using LocationDiscriminator =
 108       std::tuple<StringRef, unsigned, unsigned, uint64_t>;
 109   using BBSet = DenseSet<const MachineBasicBlock *>;
 110   using LocationDiscriminatorBBMap = DenseMap<LocationDiscriminator, BBSet>;
 111   using LocationDiscriminatorCurrPassMap =
 112       DenseMap<LocationDiscriminator, unsigned>;
 113
 114   LocationDiscriminatorBBMap LDBM;
 115   LocationDiscriminatorCurrPassMap LDCM;
 116
 117   // Mask of discriminators before this pass.
 118   // TODO(xur): simplify this once we switch to ImprovedFSDiscriminator.
 119   unsigned LowBitTemp = LowBit;
 120   assert(LowBit > 0 && "LowBit in FSDiscriminator cannot be 0");
 121   if (ImprovedFSDiscriminator)
 122     LowBitTemp -= 1;
 123   unsigned BitMaskBefore = getN1Bits(LowBitTemp);
 124   // Mask of discriminators including this pass.
 125   unsigned BitMaskNow = getN1Bits(HighBit);
 126   // Mask of discriminators for bits specific to this pass.
 127   unsigned BitMaskThisPass = BitMaskNow ^ BitMaskBefore;
 128   unsigned NumNewD = 0;
 129
 130   LLVM_DEBUG(dbgs() << "MIRAddFSDiscriminators working on Func: "
 131                     << MF.getFunction().getName() << " Highbit=" << HighBit
 132                     << "\n");
 133
 134   for (MachineBasicBlock &BB : MF) {
 135     for (MachineInstr &I : BB) {
 136       if (HasPseudoProbe) {
 137         // Only assign discriminators to pseudo probe instructions. Call
 138         // instructions are excluded since their dwarf discriminators are used
 139         // for other purposes, i.e, storing probe ids.
 140         if (!I.isPseudoProbe())
 141           continue;
 142       } else if (ImprovedFSDiscriminator && I.isMetaInstruction()) {
 143         continue;
 144       }
 145       const DILocation *DIL = I.getDebugLoc().get();
 146       if (!DIL)
 147         continue;
 148
 149       // Use the id of pseudo probe to compute the discriminator.
 150       unsigned LineNo =
 151           I.isPseudoProbe() ? I.getOperand(1).getImm() : DIL->getLine();
 152       if (LineNo == 0)
 153         continue;
 154       unsigned Discriminator = DIL->getDiscriminator();
 155       // Clean up discriminators for pseudo probes at the first FS discriminator
 156       // pass as their discriminators should not ever be used.
 157       if ((Pass == FSDiscriminatorPass::Pass1) && I.isPseudoProbe()) {
 158         Discriminator = 0;
 159         I.setDebugLoc(DIL->cloneWithDiscriminator(0));
 160       }
 161       uint64_t CallStackHashVal = 0;
 162       if (ImprovedFSDiscriminator)
 163         CallStackHashVal = getCallStackHash(DIL);
 164
 165       LocationDiscriminator LD{DIL->getFilename(), LineNo, Discriminator,
 166                                CallStackHashVal};
 167       auto &BBMap = LDBM[LD];
 168       auto R = BBMap.insert(&BB);
 169       if (BBMap.size() == 1)
 170         continue;
 171
 172       unsigned DiscriminatorCurrPass;
 173       DiscriminatorCurrPass = R.second ? ++LDCM[LD] : LDCM[LD];
 174       DiscriminatorCurrPass = DiscriminatorCurrPass << LowBit;
 175       if (!ImprovedFSDiscriminator)
 176         DiscriminatorCurrPass += getCallStackHashV0(BB, I, DIL);
 177       DiscriminatorCurrPass &= BitMaskThisPass;
 178       unsigned NewD = Discriminator | DiscriminatorCurrPass;
 179       const auto *const NewDIL = DIL->cloneWithDiscriminator(NewD);
 180       if (!NewDIL) {
 181         LLVM_DEBUG(dbgs() << "Could not encode discriminator: "
 182                           << DIL->getFilename() << ":" << DIL->getLine() << ":"
 183                           << DIL->getColumn() << ":" << Discriminator << " "
 184                           << I << "\n");
 185         continue;
 186       }
 187
 188       I.setDebugLoc(NewDIL);
 189       NumNewD++;
 190       LLVM_DEBUG(dbgs() << DIL->getFilename() << ":" << DIL->getLine() << ":"
 191                         << DIL->getColumn() << ": add FS discriminator, from "
 192                         << Discriminator << " -> " << NewD << "\n");
 193       Changed = true;
 194     }
 195   }
 196
 197   if (Changed) {
 198     createFSDiscriminatorVariable(MF.getFunction().getParent());
 199     LLVM_DEBUG(dbgs() << "Num of FS Discriminators: " << NumNewD << "\n");
 200     (void) NumNewD;
 201   }
 202
 203   return Changed;
 204 }