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