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