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