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 
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.
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.
70 bool MIRAddFSDiscriminators::runOnMachineFunction(MachineFunction &MF) {
71   if (!EnableFSDiscriminator)
72     return false;
73   if (!MF.getFunction().isDebugInfoForProfiling())
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