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