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/IR/Function.h"
  19 #include "llvm/Support/CommandLine.h"
  20 #include "llvm/Support/Debug.h"
  21 #include "llvm/Support/raw_ostream.h"
  22 #include "llvm/Transforms/Utils/SampleProfileLoaderBaseUtil.h"
  23 #include <unordered_map>
  24
  25 using namespace llvm;
  26 using namespace sampleprof;
  27 using namespace sampleprofutil;
  28
  29 #define DEBUG_TYPE "mirfs-discriminators"
  30
  31 char MIRAddFSDiscriminators::ID = 0;
  32
  33 INITIALIZE_PASS(MIRAddFSDiscriminators, DEBUG_TYPE,
  34                 "Add MIR Flow Sensitive Discriminators",
  35                 /* cfg = */ false, /* is_analysis = */ false)
  36
  37 char &llvm::MIRAddFSDiscriminatorsID = MIRAddFSDiscriminators::ID;
  38
  39 FunctionPass *llvm::createMIRAddFSDiscriminatorsPass(FSDiscriminatorPass P) {
  40   return new MIRAddFSDiscriminators(P);
  41 }
  42
  43 // Compute a hash value using debug line number, and the line numbers from the
  44 // inline stack.
  45 static uint64_t getCallStackHash(const MachineBasicBlock &BB,
  46                                  const MachineInstr &MI,
  47                                  const DILocation *DIL) {
  48   auto updateHash = [](const StringRef &Str) -> uint64_t {
  49     if (Str.empty())
  50       return 0;
  51     return MD5Hash(Str);
  52   };
  53   uint64_t Ret = updateHash(std::to_string(DIL->getLine()));
  54   Ret ^= updateHash(BB.getName());
  55   Ret ^= updateHash(DIL->getScope()->getSubprogram()->getLinkageName());
  56   for (DIL = DIL->getInlinedAt(); DIL; DIL = DIL->getInlinedAt()) {
  57     Ret ^= updateHash(std::to_string(DIL->getLine()));
  58     Ret ^= updateHash(DIL->getScope()->getSubprogram()->getLinkageName());
  59   }
  60   return Ret;
  61 }
  62
  63 // Traverse the CFG and assign FD discriminators. If two instructions
  64 // have the same lineno and discriminator, but residing in different BBs,
  65 // the latter instruction will get a new discriminator value. The new
  66 // discriminator keeps the existing discriminator value but sets new bits
  67 // b/w LowBit and HighBit.
  68 bool MIRAddFSDiscriminators::runOnMachineFunction(MachineFunction &MF) {
  69   if (!EnableFSDiscriminator)
  70     return false;
  71
  72   bool Changed = false;
  73   using LocationDiscriminator = std::tuple<StringRef, unsigned, unsigned>;
  74   using BBSet = DenseSet<const MachineBasicBlock *>;
  75   using LocationDiscriminatorBBMap = DenseMap<LocationDiscriminator, BBSet>;
  76   using LocationDiscriminatorCurrPassMap =
  77       DenseMap<LocationDiscriminator, unsigned>;
  78
  79   LocationDiscriminatorBBMap LDBM;
  80   LocationDiscriminatorCurrPassMap LDCM;
  81
  82   // Mask of discriminators before this pass.
  83   unsigned BitMaskBefore = getN1Bits(LowBit);
  84   // Mask of discriminators including this pass.
  85   unsigned BitMaskNow = getN1Bits(HighBit);
  86   // Mask of discriminators for bits specific to this pass.
  87   unsigned BitMaskThisPass = BitMaskNow ^ BitMaskBefore;
  88   unsigned NumNewD = 0;
  89
  90   LLVM_DEBUG(dbgs() << "MIRAddFSDiscriminators working on Func: "
  91                     << MF.getFunction().getName() << "\n");
  92   for (MachineBasicBlock &BB : MF) {
  93     for (MachineInstr &I : BB) {
  94       const DILocation *DIL = I.getDebugLoc().get();
  95       if (!DIL)
  96         continue;
  97       unsigned LineNo = DIL->getLine();
  98       if (LineNo == 0)
  99         continue;
 100       unsigned Discriminator = DIL->getDiscriminator();
 101       LocationDiscriminator LD{DIL->getFilename(), LineNo, Discriminator};
 102       auto &BBMap = LDBM[LD];
 103       auto R = BBMap.insert(&BB);
 104       if (BBMap.size() == 1)
 105         continue;
 106
 107       unsigned DiscriminatorCurrPass;
 108       DiscriminatorCurrPass = R.second ? ++LDCM[LD] : LDCM[LD];
 109       DiscriminatorCurrPass = DiscriminatorCurrPass << LowBit;
 110       DiscriminatorCurrPass += getCallStackHash(BB, I, DIL);
 111       DiscriminatorCurrPass &= BitMaskThisPass;
 112       unsigned NewD = Discriminator | DiscriminatorCurrPass;
 113       const auto *const NewDIL = DIL->cloneWithDiscriminator(NewD);
 114       if (!NewDIL) {
 115         LLVM_DEBUG(dbgs() << "Could not encode discriminator: "
 116                           << DIL->getFilename() << ":" << DIL->getLine() << ":"
 117                           << DIL->getColumn() << ":" << Discriminator << " "
 118                           << I << "\n");
 119         continue;
 120       }
 121
 122       I.setDebugLoc(NewDIL);
 123       NumNewD++;
 124       LLVM_DEBUG(dbgs() << DIL->getFilename() << ":" << DIL->getLine() << ":"
 125                         << DIL->getColumn() << ": add FS discriminator, from "
 126                         << Discriminator << " -> " << NewD << "\n");
 127       Changed = true;
 128     }
 129   }
 130
 131   if (Changed) {
 132     createFSDiscriminatorVariable(MF.getFunction().getParent());
 133     LLVM_DEBUG(dbgs() << "Num of FS Discriminators: " << NumNewD << "\n");
 134   }
 135
 136   return Changed;
 137 }