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
30using namespace llvm;
31using namespace sampleprof;
32using 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.
38namespace llvm {
39cl::opt<bool> ImprovedFSDiscriminator(
40 "improved-fs-discriminator", cl::Hidden, cl::init(Val: false),
41 cl::desc("New FS discriminators encoding (incompatible with the original "
42 "encoding)"));
43}
44
45char MIRAddFSDiscriminators::ID = 0;
46
47INITIALIZE_PASS(MIRAddFSDiscriminators, DEBUG_TYPE,
48 "Add MIR Flow Sensitive Discriminators",
49 /* cfg = */ false, /* is_analysis = */ false)
50
51char &llvm::MIRAddFSDiscriminatorsID = MIRAddFSDiscriminators::ID;
52
53FunctionPass *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.
60static 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(val: 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(val: DIL->getLine()));
73 Ret ^= updateHash(DIL->getScope()->getSubprogram()->getLinkageName());
74 }
75 return Ret;
76}
77
78static 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(data: ArrayRef<uint8_t>(DIL->getLine())));
86 Ret = hashCombine(Ret, xxh3_64bits(data: 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.
96bool MIRAddFSDiscriminators::runOnMachineFunction(MachineFunction &MF) {
97 if (!EnableFSDiscriminator)
98 return false;
99
100 bool HasPseudoProbe = MF.getFunction().getParent()->getNamedMetadata(
101 Name: 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(N: LowBitTemp);
124 // Mask of discriminators including this pass.
125 unsigned BitMaskNow = getN1Bits(N: 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(i: 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(Discriminator: 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(V: &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, MI: I, DIL);
177 DiscriminatorCurrPass &= BitMaskThisPass;
178 unsigned NewD = Discriminator | DiscriminatorCurrPass;
179 const auto *const NewDIL = DIL->cloneWithDiscriminator(Discriminator: 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(M: MF.getFunction().getParent());
199 LLVM_DEBUG(dbgs() << "Num of FS Discriminators: " << NumNewD << "\n");
200 (void) NumNewD;
201 }
202
203 return Changed;
204}
205