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