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