LLVM 19.0.0git
MIRFSDiscriminator.cpp
Go to the documentation of this file.
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
15#include "llvm/ADT/DenseMap.h"
16#include "llvm/ADT/DenseSet.h"
18#include "llvm/CodeGen/Passes.h"
20#include "llvm/IR/Function.h"
21#include "llvm/IR/Module.h"
22#include "llvm/IR/PseudoProbe.h"
25#include "llvm/Support/Debug.h"
27#include "llvm/Support/xxhash.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 {
40 "improved-fs-discriminator", cl::Hidden, cl::init(false),
41 cl::desc("New FS discriminators encoding (incompatible with the original "
42 "encoding)"));
43}
44
46
48 "Add MIR Flow Sensitive Discriminators",
49 /* cfg = */ false, /* is_analysis = */ false)
50
52
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.
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
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.
96bool MIRAddFSDiscriminators::runOnMachineFunction(MachineFunction &MF) {
98 return false;
99
100 bool HasPseudoProbe = MF.getFunction().getParent()->getNamedMetadata(
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>;
110 using LocationDiscriminatorBBMap = DenseMap<LocationDiscriminator, BBSet>;
111 using LocationDiscriminatorCurrPassMap =
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");
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;
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;
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}
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition: MD5.cpp:58
static uint64_t getCallStackHashV0(const MachineBasicBlock &BB, const MachineInstr &MI, const DILocation *DIL)
static uint64_t getCallStackHash(const DILocation *DIL)
#define DEBUG_TYPE
Module.h This file contains the declarations for the Module class.
#define P(N)
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
static ManagedStatic< cl::opt< uint64_t >, CreateSeed > Seed
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file provides the utility functions for the sampled PGO loader base implementation.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
Debug location.
const DILocation * cloneWithDiscriminator(unsigned Discriminator) const
Returns a new DILocation with updated Discriminator.
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
bool shouldEmitDebugInfoForProfiling() const
Returns true if we should emit debug info for profiling.
Definition: Metadata.cpp:1834
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:655
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
Function & getFunction()
Return the LLVM function that this machine code represents.
Representation of each machine instruction.
Definition: MachineInstr.h:69
NamedMDNode * getNamedMetadata(const Twine &Name) const
Return the first NamedMDNode in the module with the specified name.
Definition: Module.cpp:262
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:94
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
uint64_t MD5Hash(const FunctionId &Obj)
Definition: FunctionId.h:167
void createFSDiscriminatorVariable(Module *M)
Create a global variable to flag FSDiscriminators are used.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
uint64_t xxh3_64bits(ArrayRef< uint8_t > data)
Definition: xxhash.cpp:397
cl::opt< bool > EnableFSDiscriminator
FunctionPass * createMIRAddFSDiscriminatorsPass(sampleprof::FSDiscriminatorPass P)
Add Flow Sensitive Discriminators.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
cl::opt< bool > ImprovedFSDiscriminator("improved-fs-discriminator", cl::Hidden, cl::init(false), cl::desc("New FS discriminators encoding (incompatible with the original " "encoding)"))
static unsigned getN1Bits(int N)
constexpr const char * PseudoProbeDescMetadataName
Definition: PseudoProbe.h:25
char & MIRAddFSDiscriminatorsID
This pass adds flow sensitive discriminators.