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