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/IR/Module.h" 22 #include "llvm/IR/PseudoProbe.h" 23 #include "llvm/InitializePasses.h" 24 #include "llvm/Support/CommandLine.h" 25 #include "llvm/Support/Debug.h" 26 #include "llvm/Support/raw_ostream.h" 27 #include "llvm/Support/xxhash.h" 28 #include "llvm/Transforms/Utils/SampleProfileLoaderBaseUtil.h" 29 30 using namespace llvm; 31 using namespace sampleprof; 32 using namespace sampleprofutil; 33 34 #define DEBUG_TYPE "mirfs-discriminators" 35 36 // TODO(xur): Remove this option and related code once we make true as the 37 // default. 38 cl::opt<bool> ImprovedFSDiscriminator( 39 "improved-fs-discriminator", cl::Hidden, cl::init(false), 40 cl::desc("New FS discriminators encoding (incompatible with the original " 41 "encoding)")); 42 43 char MIRAddFSDiscriminators::ID = 0; 44 45 INITIALIZE_PASS(MIRAddFSDiscriminators, DEBUG_TYPE, 46 "Add MIR Flow Sensitive Discriminators", 47 /* cfg = */ false, /* is_analysis = */ false) 48 49 char &llvm::MIRAddFSDiscriminatorsID = MIRAddFSDiscriminators::ID; 50 51 FunctionPass *llvm::createMIRAddFSDiscriminatorsPass(FSDiscriminatorPass P) { 52 return new MIRAddFSDiscriminators(P); 53 } 54 55 // TODO(xur): Remove this once we switch to ImprovedFSDiscriminator. 56 // Compute a hash value using debug line number, and the line numbers from the 57 // inline stack. 58 static uint64_t getCallStackHashV0(const MachineBasicBlock &BB, 59 const MachineInstr &MI, 60 const DILocation *DIL) { 61 auto updateHash = [](const StringRef &Str) -> uint64_t { 62 if (Str.empty()) 63 return 0; 64 return MD5Hash(Str); 65 }; 66 uint64_t Ret = updateHash(std::to_string(DIL->getLine())); 67 Ret ^= updateHash(BB.getName()); 68 Ret ^= updateHash(DIL->getScope()->getSubprogram()->getLinkageName()); 69 for (DIL = DIL->getInlinedAt(); DIL; DIL = DIL->getInlinedAt()) { 70 Ret ^= updateHash(std::to_string(DIL->getLine())); 71 Ret ^= updateHash(DIL->getScope()->getSubprogram()->getLinkageName()); 72 } 73 return Ret; 74 } 75 76 static uint64_t getCallStackHash(const DILocation *DIL) { 77 auto hashCombine = [](const uint64_t Seed, const uint64_t Val) { 78 std::hash<uint64_t> Hasher; 79 return Seed ^ (Hasher(Val) + 0x9e3779b9 + (Seed << 6) + (Seed >> 2)); 80 }; 81 uint64_t Ret = 0; 82 for (DIL = DIL->getInlinedAt(); DIL; DIL = DIL->getInlinedAt()) { 83 Ret = hashCombine(Ret, xxh3_64bits(ArrayRef<uint8_t>(DIL->getLine()))); 84 Ret = hashCombine(Ret, xxh3_64bits(DIL->getSubprogramLinkageName())); 85 } 86 return Ret; 87 } 88 89 // Traverse the CFG and assign FD discriminators. If two instructions 90 // have the same lineno and discriminator, but residing in different BBs, 91 // the latter instruction will get a new discriminator value. The new 92 // discriminator keeps the existing discriminator value but sets new bits 93 // b/w LowBit and HighBit. 94 bool MIRAddFSDiscriminators::runOnMachineFunction(MachineFunction &MF) { 95 if (!EnableFSDiscriminator) 96 return false; 97 98 bool HasPseudoProbe = MF.getFunction().getParent()->getNamedMetadata( 99 PseudoProbeDescMetadataName); 100 101 if (!HasPseudoProbe && !MF.getFunction().shouldEmitDebugInfoForProfiling()) 102 return false; 103 104 bool Changed = false; 105 using LocationDiscriminator = 106 std::tuple<StringRef, unsigned, unsigned, uint64_t>; 107 using BBSet = DenseSet<const MachineBasicBlock *>; 108 using LocationDiscriminatorBBMap = DenseMap<LocationDiscriminator, BBSet>; 109 using LocationDiscriminatorCurrPassMap = 110 DenseMap<LocationDiscriminator, unsigned>; 111 112 LocationDiscriminatorBBMap LDBM; 113 LocationDiscriminatorCurrPassMap LDCM; 114 115 // Mask of discriminators before this pass. 116 // TODO(xur): simplify this once we switch to ImprovedFSDiscriminator. 117 unsigned LowBitTemp = LowBit; 118 assert(LowBit > 0 && "LowBit in FSDiscriminator cannot be 0"); 119 if (ImprovedFSDiscriminator) 120 LowBitTemp -= 1; 121 unsigned BitMaskBefore = getN1Bits(LowBitTemp); 122 // Mask of discriminators including this pass. 123 unsigned BitMaskNow = getN1Bits(HighBit); 124 // Mask of discriminators for bits specific to this pass. 125 unsigned BitMaskThisPass = BitMaskNow ^ BitMaskBefore; 126 unsigned NumNewD = 0; 127 128 LLVM_DEBUG(dbgs() << "MIRAddFSDiscriminators working on Func: " 129 << MF.getFunction().getName() << " Highbit=" << HighBit 130 << "\n"); 131 132 for (MachineBasicBlock &BB : MF) { 133 for (MachineInstr &I : BB) { 134 if (HasPseudoProbe) { 135 // Only assign discriminators to pseudo probe instructions. Call 136 // instructions are excluded since their dwarf discriminators are used 137 // for other purposes, i.e, storing probe ids. 138 if (!I.isPseudoProbe()) 139 continue; 140 } else if (ImprovedFSDiscriminator && I.isMetaInstruction()) { 141 continue; 142 } 143 const DILocation *DIL = I.getDebugLoc().get(); 144 if (!DIL) 145 continue; 146 147 // Use the id of pseudo probe to compute the discriminator. 148 unsigned LineNo = 149 I.isPseudoProbe() ? I.getOperand(1).getImm() : DIL->getLine(); 150 if (LineNo == 0) 151 continue; 152 unsigned Discriminator = DIL->getDiscriminator(); 153 // Clean up discriminators for pseudo probes at the first FS discriminator 154 // pass as their discriminators should not ever be used. 155 if ((Pass == FSDiscriminatorPass::Pass1) && I.isPseudoProbe()) { 156 Discriminator = 0; 157 I.setDebugLoc(DIL->cloneWithDiscriminator(0)); 158 } 159 uint64_t CallStackHashVal = 0; 160 if (ImprovedFSDiscriminator) 161 CallStackHashVal = getCallStackHash(DIL); 162 163 LocationDiscriminator LD{DIL->getFilename(), LineNo, Discriminator, 164 CallStackHashVal}; 165 auto &BBMap = LDBM[LD]; 166 auto R = BBMap.insert(&BB); 167 if (BBMap.size() == 1) 168 continue; 169 170 unsigned DiscriminatorCurrPass; 171 DiscriminatorCurrPass = R.second ? ++LDCM[LD] : LDCM[LD]; 172 DiscriminatorCurrPass = DiscriminatorCurrPass << LowBit; 173 if (!ImprovedFSDiscriminator) 174 DiscriminatorCurrPass += getCallStackHashV0(BB, I, DIL); 175 DiscriminatorCurrPass &= BitMaskThisPass; 176 unsigned NewD = Discriminator | DiscriminatorCurrPass; 177 const auto *const NewDIL = DIL->cloneWithDiscriminator(NewD); 178 if (!NewDIL) { 179 LLVM_DEBUG(dbgs() << "Could not encode discriminator: " 180 << DIL->getFilename() << ":" << DIL->getLine() << ":" 181 << DIL->getColumn() << ":" << Discriminator << " " 182 << I << "\n"); 183 continue; 184 } 185 186 I.setDebugLoc(NewDIL); 187 NumNewD++; 188 LLVM_DEBUG(dbgs() << DIL->getFilename() << ":" << DIL->getLine() << ":" 189 << DIL->getColumn() << ": add FS discriminator, from " 190 << Discriminator << " -> " << NewD << "\n"); 191 Changed = true; 192 } 193 } 194 195 if (Changed) { 196 createFSDiscriminatorVariable(MF.getFunction().getParent()); 197 LLVM_DEBUG(dbgs() << "Num of FS Discriminators: " << NumNewD << "\n"); 198 (void) NumNewD; 199 } 200 201 return Changed; 202 } 203