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/InitializePasses.h"
22 #include "llvm/Support/CommandLine.h"
23 #include "llvm/Support/Debug.h"
24 #include "llvm/Support/raw_ostream.h"
25 #include "llvm/Transforms/Utils/SampleProfileLoaderBaseUtil.h"
26
27 using namespace llvm;
28 using namespace sampleprof;
29 using namespace sampleprofutil;
30
31 #define DEBUG_TYPE "mirfs-discriminators"
32
33 char MIRAddFSDiscriminators::ID = 0;
34
35 INITIALIZE_PASS(MIRAddFSDiscriminators, DEBUG_TYPE,
36 "Add MIR Flow Sensitive Discriminators",
37 /* cfg = */ false, /* is_analysis = */ false)
38
39 char &llvm::MIRAddFSDiscriminatorsID = MIRAddFSDiscriminators::ID;
40
createMIRAddFSDiscriminatorsPass(FSDiscriminatorPass P)41 FunctionPass *llvm::createMIRAddFSDiscriminatorsPass(FSDiscriminatorPass P) {
42 return new MIRAddFSDiscriminators(P);
43 }
44
45 // Compute a hash value using debug line number, and the line numbers from the
46 // inline stack.
getCallStackHash(const MachineBasicBlock & BB,const MachineInstr & MI,const DILocation * DIL)47 static uint64_t getCallStackHash(const MachineBasicBlock &BB,
48 const MachineInstr &MI,
49 const DILocation *DIL) {
50 auto updateHash = [](const StringRef &Str) -> uint64_t {
51 if (Str.empty())
52 return 0;
53 return MD5Hash(Str);
54 };
55 uint64_t Ret = updateHash(std::to_string(DIL->getLine()));
56 Ret ^= updateHash(BB.getName());
57 Ret ^= updateHash(DIL->getScope()->getSubprogram()->getLinkageName());
58 for (DIL = DIL->getInlinedAt(); DIL; DIL = DIL->getInlinedAt()) {
59 Ret ^= updateHash(std::to_string(DIL->getLine()));
60 Ret ^= updateHash(DIL->getScope()->getSubprogram()->getLinkageName());
61 }
62 return Ret;
63 }
64
65 // Traverse the CFG and assign FD discriminators. If two instructions
66 // have the same lineno and discriminator, but residing in different BBs,
67 // the latter instruction will get a new discriminator value. The new
68 // discriminator keeps the existing discriminator value but sets new bits
69 // b/w LowBit and HighBit.
runOnMachineFunction(MachineFunction & MF)70 bool MIRAddFSDiscriminators::runOnMachineFunction(MachineFunction &MF) {
71 if (!EnableFSDiscriminator)
72 return false;
73 if (!MF.getFunction().shouldEmitDebugInfoForProfiling())
74 return false;
75
76 bool Changed = false;
77 using LocationDiscriminator = std::tuple<StringRef, unsigned, unsigned>;
78 using BBSet = DenseSet<const MachineBasicBlock *>;
79 using LocationDiscriminatorBBMap = DenseMap<LocationDiscriminator, BBSet>;
80 using LocationDiscriminatorCurrPassMap =
81 DenseMap<LocationDiscriminator, unsigned>;
82
83 LocationDiscriminatorBBMap LDBM;
84 LocationDiscriminatorCurrPassMap LDCM;
85
86 // Mask of discriminators before this pass.
87 unsigned BitMaskBefore = getN1Bits(LowBit);
88 // Mask of discriminators including this pass.
89 unsigned BitMaskNow = getN1Bits(HighBit);
90 // Mask of discriminators for bits specific to this pass.
91 unsigned BitMaskThisPass = BitMaskNow ^ BitMaskBefore;
92 unsigned NumNewD = 0;
93
94 LLVM_DEBUG(dbgs() << "MIRAddFSDiscriminators working on Func: "
95 << MF.getFunction().getName() << "\n");
96 for (MachineBasicBlock &BB : MF) {
97 for (MachineInstr &I : BB) {
98 const DILocation *DIL = I.getDebugLoc().get();
99 if (!DIL)
100 continue;
101 unsigned LineNo = DIL->getLine();
102 if (LineNo == 0)
103 continue;
104 unsigned Discriminator = DIL->getDiscriminator();
105 LocationDiscriminator LD{DIL->getFilename(), LineNo, Discriminator};
106 auto &BBMap = LDBM[LD];
107 auto R = BBMap.insert(&BB);
108 if (BBMap.size() == 1)
109 continue;
110
111 unsigned DiscriminatorCurrPass;
112 DiscriminatorCurrPass = R.second ? ++LDCM[LD] : LDCM[LD];
113 DiscriminatorCurrPass = DiscriminatorCurrPass << LowBit;
114 DiscriminatorCurrPass += getCallStackHash(BB, I, DIL);
115 DiscriminatorCurrPass &= BitMaskThisPass;
116 unsigned NewD = Discriminator | DiscriminatorCurrPass;
117 const auto *const NewDIL = DIL->cloneWithDiscriminator(NewD);
118 if (!NewDIL) {
119 LLVM_DEBUG(dbgs() << "Could not encode discriminator: "
120 << DIL->getFilename() << ":" << DIL->getLine() << ":"
121 << DIL->getColumn() << ":" << Discriminator << " "
122 << I << "\n");
123 continue;
124 }
125
126 I.setDebugLoc(NewDIL);
127 NumNewD++;
128 LLVM_DEBUG(dbgs() << DIL->getFilename() << ":" << DIL->getLine() << ":"
129 << DIL->getColumn() << ": add FS discriminator, from "
130 << Discriminator << " -> " << NewD << "\n");
131 Changed = true;
132 }
133 }
134
135 if (Changed) {
136 createFSDiscriminatorVariable(MF.getFunction().getParent());
137 LLVM_DEBUG(dbgs() << "Num of FS Discriminators: " << NumNewD << "\n");
138 (void) NumNewD;
139 }
140
141 return Changed;
142 }
143