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   if (!MF.getFunction().isDebugInfoForProfiling())
72     return false;
73 
74   bool Changed = false;
75   using LocationDiscriminator = std::tuple<StringRef, unsigned, unsigned>;
76   using BBSet = DenseSet<const MachineBasicBlock *>;
77   using LocationDiscriminatorBBMap = DenseMap<LocationDiscriminator, BBSet>;
78   using LocationDiscriminatorCurrPassMap =
79       DenseMap<LocationDiscriminator, unsigned>;
80 
81   LocationDiscriminatorBBMap LDBM;
82   LocationDiscriminatorCurrPassMap LDCM;
83 
84   // Mask of discriminators before this pass.
85   unsigned BitMaskBefore = getN1Bits(LowBit);
86   // Mask of discriminators including this pass.
87   unsigned BitMaskNow = getN1Bits(HighBit);
88   // Mask of discriminators for bits specific to this pass.
89   unsigned BitMaskThisPass = BitMaskNow ^ BitMaskBefore;
90   unsigned NumNewD = 0;
91 
92   LLVM_DEBUG(dbgs() << "MIRAddFSDiscriminators working on Func: "
93                     << MF.getFunction().getName() << "\n");
94   for (MachineBasicBlock &BB : MF) {
95     for (MachineInstr &I : BB) {
96       const DILocation *DIL = I.getDebugLoc().get();
97       if (!DIL)
98         continue;
99       unsigned LineNo = DIL->getLine();
100       if (LineNo == 0)
101         continue;
102       unsigned Discriminator = DIL->getDiscriminator();
103       LocationDiscriminator LD{DIL->getFilename(), LineNo, Discriminator};
104       auto &BBMap = LDBM[LD];
105       auto R = BBMap.insert(&BB);
106       if (BBMap.size() == 1)
107         continue;
108 
109       unsigned DiscriminatorCurrPass;
110       DiscriminatorCurrPass = R.second ? ++LDCM[LD] : LDCM[LD];
111       DiscriminatorCurrPass = DiscriminatorCurrPass << LowBit;
112       DiscriminatorCurrPass += getCallStackHash(BB, I, DIL);
113       DiscriminatorCurrPass &= BitMaskThisPass;
114       unsigned NewD = Discriminator | DiscriminatorCurrPass;
115       const auto *const NewDIL = DIL->cloneWithDiscriminator(NewD);
116       if (!NewDIL) {
117         LLVM_DEBUG(dbgs() << "Could not encode discriminator: "
118                           << DIL->getFilename() << ":" << DIL->getLine() << ":"
119                           << DIL->getColumn() << ":" << Discriminator << " "
120                           << I << "\n");
121         continue;
122       }
123 
124       I.setDebugLoc(NewDIL);
125       NumNewD++;
126       LLVM_DEBUG(dbgs() << DIL->getFilename() << ":" << DIL->getLine() << ":"
127                         << DIL->getColumn() << ": add FS discriminator, from "
128                         << Discriminator << " -> " << NewD << "\n");
129       Changed = true;
130     }
131   }
132 
133   if (Changed) {
134     createFSDiscriminatorVariable(MF.getFunction().getParent());
135     LLVM_DEBUG(dbgs() << "Num of FS Discriminators: " << NumNewD << "\n");
136   }
137 
138   return Changed;
139 }
140