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/MIRFSDiscriminatorOptions.h"
19#include "llvm/CodeGen/Passes.h"
20#include "llvm/IR/DebugInfoMetadata.h"
21#include "llvm/IR/Function.h"
22#include "llvm/IR/Module.h"
23#include "llvm/IR/PseudoProbe.h"
24#include "llvm/InitializePasses.h"
25#include "llvm/Support/CommandLine.h"
26#include "llvm/Support/Debug.h"
27#include "llvm/Support/raw_ostream.h"
28#include "llvm/Support/xxhash.h"
29#include "llvm/Transforms/Utils/SampleProfileLoaderBaseUtil.h"
30
31using namespace llvm;
32using namespace sampleprof;
33using namespace sampleprofutil;
34
35#define DEBUG_TYPE "mirfs-discriminators"
36
37// TODO(xur): Remove this option and related code once we make true as the
38// default.
39cl::opt<bool> llvm::ImprovedFSDiscriminator(
40 "improved-fs-discriminator", cl::Hidden, cl::init(Val: false),
41 cl::desc("New FS discriminators encoding (incompatible with the original "
42 "encoding)"));
43char MIRAddFSDiscriminators::ID = 0;
44
45INITIALIZE_PASS(MIRAddFSDiscriminators, DEBUG_TYPE,
46 "Add MIR Flow Sensitive Discriminators",
47 /* cfg = */ false, /* is_analysis = */ false)
48
49char &llvm::MIRAddFSDiscriminatorsID = MIRAddFSDiscriminators::ID;
50
51FunctionPass *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.
58static 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(val: 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(val: DIL->getLine()));
71 Ret ^= updateHash(DIL->getScope()->getSubprogram()->getLinkageName());
72 }
73 return Ret;
74}
75
76static 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(data: ArrayRef<uint8_t>(DIL->getLine())));
84 Ret = hashCombine(Ret, xxh3_64bits(data: 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.
94bool MIRAddFSDiscriminators::runOnMachineFunction(MachineFunction &MF) {
95 if (!EnableFSDiscriminator)
96 return false;
97
98 bool HasPseudoProbe = MF.getFunction().getParent()->getNamedMetadata(
99 Name: 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(N: LowBitTemp);
122 // Mask of discriminators including this pass.
123 unsigned BitMaskNow = getN1Bits(N: 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(i: 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(Discriminator: 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(V: &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, MI: I, DIL);
175 DiscriminatorCurrPass &= BitMaskThisPass;
176 unsigned NewD = Discriminator | DiscriminatorCurrPass;
177 const auto *const NewDIL = DIL->cloneWithDiscriminator(Discriminator: 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(M: MF.getFunction().getParent());
197 LLVM_DEBUG(dbgs() << "Num of FS Discriminators: " << NumNewD << "\n");
198 (void) NumNewD;
199 }
200
201 return Changed;
202}
203