1fe6060f1SDimitry Andric //===-------- MIRFSDiscriminator.cpp: Flow Sensitive Discriminator --------===//
2fe6060f1SDimitry Andric //
3fe6060f1SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4fe6060f1SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
5fe6060f1SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6fe6060f1SDimitry Andric //
7fe6060f1SDimitry Andric //===----------------------------------------------------------------------===//
8fe6060f1SDimitry Andric //
9fe6060f1SDimitry Andric // This file provides the implementation of a machine pass that adds the flow
10fe6060f1SDimitry Andric // sensitive discriminator to the instruction debug information.
11fe6060f1SDimitry Andric //
12fe6060f1SDimitry Andric //===----------------------------------------------------------------------===//
13fe6060f1SDimitry Andric
14fe6060f1SDimitry Andric #include "llvm/CodeGen/MIRFSDiscriminator.h"
15fe6060f1SDimitry Andric #include "llvm/ADT/DenseMap.h"
16fe6060f1SDimitry Andric #include "llvm/ADT/DenseSet.h"
17fe6060f1SDimitry Andric #include "llvm/Analysis/BlockFrequencyInfoImpl.h"
1881ad6265SDimitry Andric #include "llvm/CodeGen/Passes.h"
1981ad6265SDimitry Andric #include "llvm/IR/DebugInfoMetadata.h"
20fe6060f1SDimitry Andric #include "llvm/IR/Function.h"
2106c3fb27SDimitry Andric #include "llvm/IR/Module.h"
2206c3fb27SDimitry Andric #include "llvm/IR/PseudoProbe.h"
2381ad6265SDimitry Andric #include "llvm/InitializePasses.h"
24fe6060f1SDimitry Andric #include "llvm/Support/CommandLine.h"
25fe6060f1SDimitry Andric #include "llvm/Support/Debug.h"
26fe6060f1SDimitry Andric #include "llvm/Support/raw_ostream.h"
2706c3fb27SDimitry Andric #include "llvm/Support/xxhash.h"
28fe6060f1SDimitry Andric #include "llvm/Transforms/Utils/SampleProfileLoaderBaseUtil.h"
29fe6060f1SDimitry Andric
30fe6060f1SDimitry Andric using namespace llvm;
31fe6060f1SDimitry Andric using namespace sampleprof;
32fe6060f1SDimitry Andric using namespace sampleprofutil;
33fe6060f1SDimitry Andric
34fe6060f1SDimitry Andric #define DEBUG_TYPE "mirfs-discriminators"
35fe6060f1SDimitry Andric
3606c3fb27SDimitry Andric // TODO(xur): Remove this option and related code once we make true as the
3706c3fb27SDimitry Andric // default.
38*5f757f3fSDimitry Andric namespace llvm {
3906c3fb27SDimitry Andric cl::opt<bool> ImprovedFSDiscriminator(
4006c3fb27SDimitry Andric "improved-fs-discriminator", cl::Hidden, cl::init(false),
4106c3fb27SDimitry Andric cl::desc("New FS discriminators encoding (incompatible with the original "
4206c3fb27SDimitry Andric "encoding)"));
43*5f757f3fSDimitry Andric }
4406c3fb27SDimitry Andric
45fe6060f1SDimitry Andric char MIRAddFSDiscriminators::ID = 0;
46fe6060f1SDimitry Andric
47fe6060f1SDimitry Andric INITIALIZE_PASS(MIRAddFSDiscriminators, DEBUG_TYPE,
48fe6060f1SDimitry Andric "Add MIR Flow Sensitive Discriminators",
49fe6060f1SDimitry Andric /* cfg = */ false, /* is_analysis = */ false)
50fe6060f1SDimitry Andric
51fe6060f1SDimitry Andric char &llvm::MIRAddFSDiscriminatorsID = MIRAddFSDiscriminators::ID;
52fe6060f1SDimitry Andric
createMIRAddFSDiscriminatorsPass(FSDiscriminatorPass P)53fe6060f1SDimitry Andric FunctionPass *llvm::createMIRAddFSDiscriminatorsPass(FSDiscriminatorPass P) {
54fe6060f1SDimitry Andric return new MIRAddFSDiscriminators(P);
55fe6060f1SDimitry Andric }
56fe6060f1SDimitry Andric
5706c3fb27SDimitry Andric // TODO(xur): Remove this once we switch to ImprovedFSDiscriminator.
58fe6060f1SDimitry Andric // Compute a hash value using debug line number, and the line numbers from the
59fe6060f1SDimitry Andric // inline stack.
getCallStackHashV0(const MachineBasicBlock & BB,const MachineInstr & MI,const DILocation * DIL)6006c3fb27SDimitry Andric static uint64_t getCallStackHashV0(const MachineBasicBlock &BB,
61fe6060f1SDimitry Andric const MachineInstr &MI,
62fe6060f1SDimitry Andric const DILocation *DIL) {
63fe6060f1SDimitry Andric auto updateHash = [](const StringRef &Str) -> uint64_t {
64fe6060f1SDimitry Andric if (Str.empty())
65fe6060f1SDimitry Andric return 0;
66fe6060f1SDimitry Andric return MD5Hash(Str);
67fe6060f1SDimitry Andric };
68fe6060f1SDimitry Andric uint64_t Ret = updateHash(std::to_string(DIL->getLine()));
69fe6060f1SDimitry Andric Ret ^= updateHash(BB.getName());
70fe6060f1SDimitry Andric Ret ^= updateHash(DIL->getScope()->getSubprogram()->getLinkageName());
71fe6060f1SDimitry Andric for (DIL = DIL->getInlinedAt(); DIL; DIL = DIL->getInlinedAt()) {
72fe6060f1SDimitry Andric Ret ^= updateHash(std::to_string(DIL->getLine()));
73fe6060f1SDimitry Andric Ret ^= updateHash(DIL->getScope()->getSubprogram()->getLinkageName());
74fe6060f1SDimitry Andric }
75fe6060f1SDimitry Andric return Ret;
76fe6060f1SDimitry Andric }
77fe6060f1SDimitry Andric
getCallStackHash(const DILocation * DIL)7806c3fb27SDimitry Andric static uint64_t getCallStackHash(const DILocation *DIL) {
7906c3fb27SDimitry Andric auto hashCombine = [](const uint64_t Seed, const uint64_t Val) {
8006c3fb27SDimitry Andric std::hash<uint64_t> Hasher;
8106c3fb27SDimitry Andric return Seed ^ (Hasher(Val) + 0x9e3779b9 + (Seed << 6) + (Seed >> 2));
8206c3fb27SDimitry Andric };
8306c3fb27SDimitry Andric uint64_t Ret = 0;
8406c3fb27SDimitry Andric for (DIL = DIL->getInlinedAt(); DIL; DIL = DIL->getInlinedAt()) {
8506c3fb27SDimitry Andric Ret = hashCombine(Ret, xxh3_64bits(ArrayRef<uint8_t>(DIL->getLine())));
8606c3fb27SDimitry Andric Ret = hashCombine(Ret, xxh3_64bits(DIL->getSubprogramLinkageName()));
8706c3fb27SDimitry Andric }
8806c3fb27SDimitry Andric return Ret;
8906c3fb27SDimitry Andric }
9006c3fb27SDimitry Andric
91fe6060f1SDimitry Andric // Traverse the CFG and assign FD discriminators. If two instructions
92fe6060f1SDimitry Andric // have the same lineno and discriminator, but residing in different BBs,
93fe6060f1SDimitry Andric // the latter instruction will get a new discriminator value. The new
94fe6060f1SDimitry Andric // discriminator keeps the existing discriminator value but sets new bits
95fe6060f1SDimitry Andric // b/w LowBit and HighBit.
runOnMachineFunction(MachineFunction & MF)96fe6060f1SDimitry Andric bool MIRAddFSDiscriminators::runOnMachineFunction(MachineFunction &MF) {
97fe6060f1SDimitry Andric if (!EnableFSDiscriminator)
98fe6060f1SDimitry Andric return false;
9906c3fb27SDimitry Andric
10006c3fb27SDimitry Andric bool HasPseudoProbe = MF.getFunction().getParent()->getNamedMetadata(
10106c3fb27SDimitry Andric PseudoProbeDescMetadataName);
10206c3fb27SDimitry Andric
10306c3fb27SDimitry Andric if (!HasPseudoProbe && !MF.getFunction().shouldEmitDebugInfoForProfiling())
10481ad6265SDimitry Andric return false;
105fe6060f1SDimitry Andric
106fe6060f1SDimitry Andric bool Changed = false;
10706c3fb27SDimitry Andric using LocationDiscriminator =
10806c3fb27SDimitry Andric std::tuple<StringRef, unsigned, unsigned, uint64_t>;
109fe6060f1SDimitry Andric using BBSet = DenseSet<const MachineBasicBlock *>;
110fe6060f1SDimitry Andric using LocationDiscriminatorBBMap = DenseMap<LocationDiscriminator, BBSet>;
111fe6060f1SDimitry Andric using LocationDiscriminatorCurrPassMap =
112fe6060f1SDimitry Andric DenseMap<LocationDiscriminator, unsigned>;
113fe6060f1SDimitry Andric
114fe6060f1SDimitry Andric LocationDiscriminatorBBMap LDBM;
115fe6060f1SDimitry Andric LocationDiscriminatorCurrPassMap LDCM;
116fe6060f1SDimitry Andric
117fe6060f1SDimitry Andric // Mask of discriminators before this pass.
11806c3fb27SDimitry Andric // TODO(xur): simplify this once we switch to ImprovedFSDiscriminator.
11906c3fb27SDimitry Andric unsigned LowBitTemp = LowBit;
12006c3fb27SDimitry Andric assert(LowBit > 0 && "LowBit in FSDiscriminator cannot be 0");
12106c3fb27SDimitry Andric if (ImprovedFSDiscriminator)
12206c3fb27SDimitry Andric LowBitTemp -= 1;
12306c3fb27SDimitry Andric unsigned BitMaskBefore = getN1Bits(LowBitTemp);
124fe6060f1SDimitry Andric // Mask of discriminators including this pass.
125fe6060f1SDimitry Andric unsigned BitMaskNow = getN1Bits(HighBit);
126fe6060f1SDimitry Andric // Mask of discriminators for bits specific to this pass.
127fe6060f1SDimitry Andric unsigned BitMaskThisPass = BitMaskNow ^ BitMaskBefore;
128fe6060f1SDimitry Andric unsigned NumNewD = 0;
129fe6060f1SDimitry Andric
130fe6060f1SDimitry Andric LLVM_DEBUG(dbgs() << "MIRAddFSDiscriminators working on Func: "
13106c3fb27SDimitry Andric << MF.getFunction().getName() << " Highbit=" << HighBit
13206c3fb27SDimitry Andric << "\n");
13306c3fb27SDimitry Andric
134fe6060f1SDimitry Andric for (MachineBasicBlock &BB : MF) {
135fe6060f1SDimitry Andric for (MachineInstr &I : BB) {
13606c3fb27SDimitry Andric if (HasPseudoProbe) {
13706c3fb27SDimitry Andric // Only assign discriminators to pseudo probe instructions. Call
13806c3fb27SDimitry Andric // instructions are excluded since their dwarf discriminators are used
13906c3fb27SDimitry Andric // for other purposes, i.e, storing probe ids.
14006c3fb27SDimitry Andric if (!I.isPseudoProbe())
14106c3fb27SDimitry Andric continue;
14206c3fb27SDimitry Andric } else if (ImprovedFSDiscriminator && I.isMetaInstruction()) {
14306c3fb27SDimitry Andric continue;
14406c3fb27SDimitry Andric }
145fe6060f1SDimitry Andric const DILocation *DIL = I.getDebugLoc().get();
146fe6060f1SDimitry Andric if (!DIL)
147fe6060f1SDimitry Andric continue;
14806c3fb27SDimitry Andric
14906c3fb27SDimitry Andric // Use the id of pseudo probe to compute the discriminator.
15006c3fb27SDimitry Andric unsigned LineNo =
15106c3fb27SDimitry Andric I.isPseudoProbe() ? I.getOperand(1).getImm() : DIL->getLine();
152fe6060f1SDimitry Andric if (LineNo == 0)
153fe6060f1SDimitry Andric continue;
154fe6060f1SDimitry Andric unsigned Discriminator = DIL->getDiscriminator();
15506c3fb27SDimitry Andric // Clean up discriminators for pseudo probes at the first FS discriminator
15606c3fb27SDimitry Andric // pass as their discriminators should not ever be used.
15706c3fb27SDimitry Andric if ((Pass == FSDiscriminatorPass::Pass1) && I.isPseudoProbe()) {
15806c3fb27SDimitry Andric Discriminator = 0;
15906c3fb27SDimitry Andric I.setDebugLoc(DIL->cloneWithDiscriminator(0));
16006c3fb27SDimitry Andric }
16106c3fb27SDimitry Andric uint64_t CallStackHashVal = 0;
16206c3fb27SDimitry Andric if (ImprovedFSDiscriminator)
16306c3fb27SDimitry Andric CallStackHashVal = getCallStackHash(DIL);
16406c3fb27SDimitry Andric
16506c3fb27SDimitry Andric LocationDiscriminator LD{DIL->getFilename(), LineNo, Discriminator,
16606c3fb27SDimitry Andric CallStackHashVal};
167fe6060f1SDimitry Andric auto &BBMap = LDBM[LD];
168fe6060f1SDimitry Andric auto R = BBMap.insert(&BB);
169fe6060f1SDimitry Andric if (BBMap.size() == 1)
170fe6060f1SDimitry Andric continue;
171fe6060f1SDimitry Andric
172fe6060f1SDimitry Andric unsigned DiscriminatorCurrPass;
173fe6060f1SDimitry Andric DiscriminatorCurrPass = R.second ? ++LDCM[LD] : LDCM[LD];
174fe6060f1SDimitry Andric DiscriminatorCurrPass = DiscriminatorCurrPass << LowBit;
17506c3fb27SDimitry Andric if (!ImprovedFSDiscriminator)
17606c3fb27SDimitry Andric DiscriminatorCurrPass += getCallStackHashV0(BB, I, DIL);
177fe6060f1SDimitry Andric DiscriminatorCurrPass &= BitMaskThisPass;
178fe6060f1SDimitry Andric unsigned NewD = Discriminator | DiscriminatorCurrPass;
179fe6060f1SDimitry Andric const auto *const NewDIL = DIL->cloneWithDiscriminator(NewD);
180fe6060f1SDimitry Andric if (!NewDIL) {
181fe6060f1SDimitry Andric LLVM_DEBUG(dbgs() << "Could not encode discriminator: "
182fe6060f1SDimitry Andric << DIL->getFilename() << ":" << DIL->getLine() << ":"
183fe6060f1SDimitry Andric << DIL->getColumn() << ":" << Discriminator << " "
184fe6060f1SDimitry Andric << I << "\n");
185fe6060f1SDimitry Andric continue;
186fe6060f1SDimitry Andric }
187fe6060f1SDimitry Andric
188fe6060f1SDimitry Andric I.setDebugLoc(NewDIL);
189fe6060f1SDimitry Andric NumNewD++;
190fe6060f1SDimitry Andric LLVM_DEBUG(dbgs() << DIL->getFilename() << ":" << DIL->getLine() << ":"
191fe6060f1SDimitry Andric << DIL->getColumn() << ": add FS discriminator, from "
192fe6060f1SDimitry Andric << Discriminator << " -> " << NewD << "\n");
193fe6060f1SDimitry Andric Changed = true;
194fe6060f1SDimitry Andric }
195fe6060f1SDimitry Andric }
196fe6060f1SDimitry Andric
197fe6060f1SDimitry Andric if (Changed) {
198fe6060f1SDimitry Andric createFSDiscriminatorVariable(MF.getFunction().getParent());
199fe6060f1SDimitry Andric LLVM_DEBUG(dbgs() << "Num of FS Discriminators: " << NumNewD << "\n");
20081ad6265SDimitry Andric (void) NumNewD;
201fe6060f1SDimitry Andric }
202fe6060f1SDimitry Andric
203fe6060f1SDimitry Andric return Changed;
204fe6060f1SDimitry Andric }
205