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 
createMIRAddFSDiscriminatorsPass(FSDiscriminatorPass P)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.
getCallStackHashV0(const MachineBasicBlock & BB,const MachineInstr & MI,const DILocation * DIL)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 
getCallStackHash(const DILocation * DIL)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.
runOnMachineFunction(MachineFunction & MF)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 }
205